Проверить равносильность формул логики высказываний с помощью тождественных преобразований и таблицы истинности

Предмет: Математика

Раздел предмета: Математическая логика

Задание: Проверить равносильность формул логики высказываний с помощью тождественных преобразований и таблицы истинности. Формулы: \[ \neg (Y \lor (X \to (\neg Z \land X))) \equiv (X \lor Y) \land (Z \lor \neg X) \]

Шаг 1: Тождественные преобразования

Легкая дизъюнкция

Для начала преобразуем выражение \(X \to (\neg Z \land X)\) в эквивалентное: \[ X \to (\neg Z \land X) \equiv \neg X \lor (\neg Z \land X) \]

Нейтральная форма

Теперь используем дистрибутивное свойство: \[ \neg X \lor (\neg Z \land X) \equiv (\neg X \lor \neg Z) \land (\neg X \lor X) \] Поскольку (\(\neg X \lor X\)) всегда истинно, результат сводится к: \[ (\neg X \lor \neg Z) \]

Подстановка результатов обратно в оригинальную формулу

Теперь у нас формула: \[ \neg (Y \lor (\neg X \lor \neg Z)) \] Используя законы де Моргана, это эквивалентно: \[ \neg Y \land \neg (\neg X \lor \neg Z) \] И снова по законам де Моргана: \[ \neg Y \land (X \land Z) \]

Шаг 2: Проверка таблицей истинности

Составим таблицу истинности для обоих выражений и удостоверимся в их равносильности.

X	Y	Z	\(X \lor Y\)	\(\neg X\)	\(Z \lor \neg X\)	\((X \lor Y) \land (Z \lor \neg X)\)	\(X \to (\neg Z \land X)\)	\(Y \lor (X \to (\neg Z \land X))\)	\(\neg (Y \lor (X \to (\neg Z \land X)))\)	\((\neg Y \land (X \land Z))\)
0	0	0	0	1	0	0	1	1	0	0
0	0	1	0	1	1	0	0	0	1	1
0	1	0	1	1	0	0	1	1	0	0
0	1	1	1	1	1	1	0	1	0	0
1	0	0	1	0	0	0	0	0	1	0
1	0	1	1	0	1	1	0	0	1	0
1	1	0	1	0	0	0	0	1	0	0
1	1	1	1	0	1	1	0	1	0	0

Из таблицы видно, что выражения \(\neg (\neg X \lor \neg Z) \equiv (X \land Y \land Z)\) - \((\neg Y \land (X \land Z))\), и \(\neg (Y \lor (\neg X \lor \neg Z))\) дают одинаковые результаты, следовательно выражения равносильны. Таким образом, оба выражения эквивалентны, что подтверждено как тождественными преобразованиями, так и таблицей истинности.