Номер 5.9, страница 38 - гдз по алгебре 8 класс учебник Мерзляк, Поляков

Глава 1. Множества и операции над ними. Параграф 5. Элементы математической логики - номер 5.9, страница 38.

Условие.

5.9. Докажите, что логическое выражение является тавтологией:

1) $A \Rightarrow \overline{\overline{A}}$

2) $A \wedge \overline{A}$

3) $A \wedge \overline{A} \Rightarrow B$

4) $A \Rightarrow (B \Rightarrow A)$

5) $(A \Rightarrow B) \vee (B \Rightarrow A)$

6) $A \wedge (A \Rightarrow B) \Rightarrow B$

7) $\overline{B} \wedge (A \Rightarrow B) \Rightarrow \overline{A}$

8) $((A \Rightarrow B) \wedge (B \Rightarrow C)) \Rightarrow (A \Rightarrow C)$

Решение.

Для доказательства того, что логическое выражение является тавтологией, мы будем использовать равносильные преобразования, основанные на законах алгебры логики, или построение таблиц истинности. Тавтология — это выражение, которое истинно при любых значениях входящих в него переменных.

1) $A \Rightarrow A$;

Используем определение операции импликации: $X \Rightarrow Y \equiv \overline{X} \lor Y$.
Применив это определение к нашему выражению, получаем:
$A \Rightarrow A \equiv \overline{A} \lor A$.
Согласно закону исключённого третьего, выражение $\overline{A} \lor A$ всегда истинно (равно 1 или T).
Следовательно, исходное выражение является тавтологией.

Ответ: Выражение $A \Rightarrow A$ является тавтологией.

2) $\overline{\overline{A \land \overline{A}}}$;

В данном виде выражение $\overline{\overline{A \land \overline{A}}}$ не является тавтологией.
Согласно закону двойного отрицания ($\overline{\overline{X}} \equiv X$), выражение упрощается:
$\overline{\overline{A \land \overline{A}}} \equiv A \land \overline{A}$.
Выражение $A \land \overline{A}$ является противоречием (тождественно ложно) согласно закону непротиворечия.
Вероятно, в условии задачи допущена опечатка, и имелось в виду выражение с одинарным отрицанием: $\overline{A \land \overline{A}}$. Докажем, что это выражение является тавтологией.
По закону непротиворечия, $A \land \overline{A}$ всегда ложно (F).
Тогда $\overline{A \land \overline{A}} \equiv \overline{F} \equiv T$.
Таким образом, выражение $\overline{A \land \overline{A}}$ является тавтологией.

Ответ: Выражение, как оно записано в задании, является противоречием. Если предположить опечатку и рассматривать выражение $\overline{A \land \overline{A}}$, то оно является тавтологией.

3) $A \land \overline{A} \Rightarrow B$;

Выражение в левой части импликации, $A \land \overline{A}$, согласно закону непротиворечия, всегда ложно (F).
Таким образом, всё выражение принимает вид $F \Rightarrow B$.
Импликация является ложной только в одном случае: когда из истины следует ложь ($T \Rightarrow F$). Во всех остальных случаях она истинна. Поскольку посылка ($A \land \overline{A}$) всегда ложна, импликация $F \Rightarrow B$ всегда будет истинной, независимо от значения $B$.
Это свойство также известно как принцип "из лжи следует всё что угодно" (ex falso quodlibet).

Ответ: Выражение $A \land \overline{A} \Rightarrow B$ является тавтологией.

4) $A \Rightarrow (B \Rightarrow A)$;

Преобразуем выражение, дважды применив определение импликации $X \Rightarrow Y \equiv \overline{X} \lor Y$.
$A \Rightarrow (B \Rightarrow A) \equiv \overline{A} \lor (B \Rightarrow A)$
$\equiv \overline{A} \lor (\overline{B} \lor A)$
Используя коммутативный и ассоциативный законы для дизъюнкции, перегруппируем члены:
$\equiv (\overline{A} \lor A) \lor \overline{B}$
По закону исключённого третьего, $\overline{A} \lor A \equiv T$.
Выражение становится $T \lor \overline{B}$.
По закону поглощения для истины, $T \lor X \equiv T$.
Следовательно, выражение является тавтологией.

Ответ: Выражение $A \Rightarrow (B \Rightarrow A)$ является тавтологией.

5) $(A \Rightarrow B) \lor (B \Rightarrow A)$;

Раскроем обе импликации по определению $X \Rightarrow Y \equiv \overline{X} \lor Y$:
$(A \Rightarrow B) \lor (B \Rightarrow A) \equiv (\overline{A} \lor B) \lor (\overline{B} \lor A)$.
Используя коммутативный и ассоциативный законы, сгруппируем переменные и их отрицания:
$\equiv (\overline{A} \lor A) \lor (\overline{B} \lor B)$.
По закону исключённого третьего, оба выражения в скобках тождественно истинны: $\overline{A} \lor A \equiv T$ и $\overline{B} \lor B \equiv T$.
Получаем выражение $T \lor T$, которое равно $T$.
Следовательно, выражение является тавтологией.

Ответ: Выражение $(A \Rightarrow B) \lor (B \Rightarrow A)$ является тавтологией.

6) $A \land (A \Rightarrow B) \Rightarrow B$;

Это логическое правило вывода известно как Modus Ponens. Докажем, что оно является тавтологией.
Преобразуем выражение, используя определение импликации:
$A \land (A \Rightarrow B) \Rightarrow B \equiv A \land (\overline{A} \lor B) \Rightarrow B$.
Применим дистрибутивный закон к выражению в скобках: $A \land (\overline{A} \lor B) \equiv (A \land \overline{A}) \lor (A \land B)$.
Так как $A \land \overline{A} \equiv F$, получаем $F \lor (A \land B) \equiv A \land B$.
Исходное выражение упрощается до $(A \land B) \Rightarrow B$.
Снова раскроем импликацию: $(A \land B) \Rightarrow B \equiv \overline{(A \land B)} \lor B$.
Применим закон де Моргана: $\overline{(A \land B)} \equiv \overline{A} \lor \overline{B}$.
Получаем: $(\overline{A} \lor \overline{B}) \lor B \equiv \overline{A} \lor (\overline{B} \lor B)$.
По закону исключённого третьего $\overline{B} \lor B \equiv T$.
Итоговое выражение: $\overline{A} \lor T \equiv T$.
Следовательно, выражение является тавтологией.

Ответ: Выражение $A \land (A \Rightarrow B) \Rightarrow B$ является тавтологией.

7) $\overline{B} \land (A \Rightarrow B) \Rightarrow \overline{A}$;

Это логическое правило вывода известно как Modus Tollens. Докажем, что оно является тавтологией.
Преобразуем выражение, используя определение импликации:
$\overline{B} \land (A \Rightarrow B) \Rightarrow \overline{A} \equiv \overline{B} \land (\overline{A} \lor B) \Rightarrow \overline{A}$.
Применим дистрибутивный закон: $\overline{B} \land (\overline{A} \lor B) \equiv (\overline{B} \land \overline{A}) \lor (\overline{B} \land B)$.
Так как $\overline{B} \land B \equiv F$, получаем $(\overline{B} \land \overline{A}) \lor F \equiv \overline{B} \land \overline{A}$.
Исходное выражение упрощается до $(\overline{B} \land \overline{A}) \Rightarrow \overline{A}$.
Снова раскроем импликацию: $(\overline{B} \land \overline{A}) \Rightarrow \overline{A} \equiv \overline{(\overline{B} \land \overline{A})} \lor \overline{A}$.
Применим закон де Моргана: $\overline{(\overline{B} \land \overline{A})} \equiv \overline{\overline{B}} \lor \overline{\overline{A}} \equiv B \lor A$.
Получаем: $(B \lor A) \lor \overline{A} \equiv B \lor (A \lor \overline{A})$.
По закону исключённого третьего $A \lor \overline{A} \equiv T$.
Итоговое выражение: $B \lor T \equiv T$.
Следовательно, выражение является тавтологией.

Ответ: Выражение $\overline{B} \land (A \Rightarrow B) \Rightarrow \overline{A}$ является тавтологией.

8) $((A \Rightarrow B) \land (B \Rightarrow C)) \Rightarrow (A \Rightarrow C)$;

Это правило вывода называется транзитивностью импликации или гипотетическим силлогизмом.
Преобразуем выражение, раскрывая все импликации: $X \Rightarrow Y \equiv \overline{X} \lor Y$.
$((\overline{A} \lor B) \land (\overline{B} \lor C)) \Rightarrow (\overline{A} \lor C)$.
$\equiv \overline{((\overline{A} \lor B) \land (\overline{B} \lor C))} \lor (\overline{A} \lor C)$.
Применим закон де Моргана к левой части:
$\equiv (\overline{(\overline{A} \lor B)} \lor \overline{(\overline{B} \lor C)}) \lor (\overline{A} \lor C)$.
$\equiv ((A \land \overline{B}) \lor (B \land \overline{C})) \lor \overline{A} \lor C$.
Сгруппируем члены, используя ассоциативность и коммутативность:
$\equiv ( (A \land \overline{B}) \lor \overline{A} ) \lor ( (B \land \overline{C}) \lor C )$.
Рассмотрим каждую группу отдельно, используя дистрибутивный закон $X \lor (Y \land Z) \equiv (X \lor Y) \land (X \lor Z)$:
1) $(A \land \overline{B}) \lor \overline{A} \equiv \overline{A} \lor (A \land \overline{B}) \equiv (\overline{A} \lor A) \land (\overline{A} \lor \overline{B}) \equiv T \land (\overline{A} \lor \overline{B}) \equiv \overline{A} \lor \overline{B}$.
2) $(B \land \overline{C}) \lor C \equiv C \lor (B \land \overline{C}) \equiv (C \lor B) \land (C \lor \overline{C}) \equiv (C \lor B) \land T \equiv C \lor B$.
Подставим упрощенные части обратно в выражение:
$\equiv (\overline{A} \lor \overline{B}) \lor (C \lor B)$.
$\equiv \overline{A} \lor C \lor (\overline{B} \lor B)$.
По закону исключённого третьего, $\overline{B} \lor B \equiv T$.
Получаем $\overline{A} \lor C \lor T$, что тождественно истинно ($T$).
Следовательно, выражение является тавтологией.

Ответ: Выражение $((A \Rightarrow B) \land (B \Rightarrow C)) \Rightarrow (A \Rightarrow C)$ является тавтологией.