Домашняя работа. Доказательство равносильности логических функций.
Задание а. Доказать равносильность \( F_1 = X \to Y \) и \( F_2 = \neg Y \to \neg X \).
Для доказательства построим таблицу истинности. Равносильность функций означает, что при одинаковых наборах входных переменных значения функций совпадают.
Порядок действий:
1. Записать все возможные комбинации переменных \( X \) и \( Y \).
2. Вычислить значение импликации \( F_1 = X \to Y \). Напомним, что импликация ложна только тогда, когда из истины следует ложь (\( 1 \to 0 = 0 \)).
3. Найти отрицания \( \neg X \) и \( \neg Y \).
4. Вычислить значение импликации \( F_2 = \neg Y \to \neg X \).
Таблица истинности для пункта а:
| \( X \) |
\( Y \) |
\( F_1 = X \to Y \) |
\( \neg Y \) |
\( \neg X \) |
\( F_2 = \neg Y \to \neg X \) |
| 0 |
0 |
1 |
1 |
1 |
1 |
| 0 |
1 |
1 |
0 |
1 |
1 |
| 1 |
0 |
0 |
1 |
0 |
0 |
| 1 |
1 |
1 |
0 |
0 |
1 |
Вывод по пункту а: Столбцы для \( F_1 \) и \( F_2 \) полностью совпадают. Следовательно, функции равносильны. Данный закон в логике называется законом контрапозиции.
Задание б. Доказать равносильность \( F_1 = A \leftrightarrow B \) и \( F_2 = (\neg A \lor B) \land (A \lor \neg B) \).
Порядок действий:
1. Записать комбинации для \( A \) и \( B \).
2. Вычислить эквивалентность \( F_1 = A \leftrightarrow B \). Она истинна (1), когда значения переменных одинаковы.
3. Найти отрицания \( \neg A \) и \( \neg B \).
4. Вычислить значения в скобках: \( (\neg A \lor B) \) и \( (A \lor \neg B) \). Дизъюнкция (\( \lor \)) ложна только если оба операнда ложны.
5. Вычислить итоговую конъюнкцию (\( \land \)) для \( F_2 \). Конъюнкция истинна только если обе скобки равны 1.
Таблица истинности для пункта б:
| \( A \) |
\( B \) |
\( F_1 = A \leftrightarrow B \) |
\( \neg A \) |
\( \neg B \) |
\( \neg A \lor B \) |
\( A \lor \neg B \) |
\( F_2 = (\dots) \land (\dots) \) |
| 0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
| 0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
| 1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
| 1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
Вывод по пункту б: Значения в столбцах \( F_1 \) и \( F_2 \) идентичны на всех наборах входных данных. Это доказывает, что \( F_1 \equiv F_2 \). Данное выражение представляет собой определение эквивалентности через импликации, так как \( A \to B \) это \( \neg A \lor B \).
