При помощи эквивалентных преобразований составить СДНФ и СКНФ для формулы (¬y ∨ (x ∧ ¬z)) ≡ (y → x)

1. Преобразование формулы:

Начнём с левой части формулы: ¬y ∨ (x ∧ ¬z)

Далее преобразуем правую часть формулы, используя определение импликации (A → B ≡ ¬A ∨ B):

y → x ≡ ¬y ∨ x

Теперь исходная формула выглядит так: ¬y ∨ (x ∧ ¬z) ≡ ¬y ∨ x

Чтобы сравнить левую и правую части, нужно привести их к одинаковому виду. Видно, что левая часть сложнее. Раскроем скобки в левой части, используя дистрибутивный закон (A ∨ (B ∧ C) ≡ (A ∨ B) ∧ (A ∨ C)):

(¬y ∨ x) ∧ (¬y ∨ ¬z) ≡ ¬y ∨ x

Это эквивалентно:

(¬y ∨ x) ∧ (¬y ∨ ¬z) ≡ ¬y ∨ x

Эта формула не может быть упрощена до правой части с помощью эквивалентных преобразований. Очевидно, что исходное равенство не является тождеством. Следовательно, невозможно составить СДНФ и СКНФ, которые были бы тождественно истинными.

2. Таблица истинности:

Проверим это с помощью таблицы истинности:

x y z y z x ∧ z ¬y ∨ (x ∧ ¬z) ¬y ∨ x (¬y ∨ (x ∧ ¬z)) ≡ (¬y ∨ x)
0 0 0 1 1 0 1 0 0
0 0 1 1 0 0 1 0 0
0 1 0 0 1 0 0 0 1
0 1 1 0 0 0 0 0 1
1 0 0 1 1 1 1 1 1
1 0 1 1 0 0 1 1 1
1 1 0 0 1 1 1 1 1
1 1 1 0 0 0 0 1 0
Как видно из таблицы истинности, формула (¬y ∨ (x ∧ ¬z)) ≡ (y → x) не является тождеством. Поэтому для нее нельзя построить СДНФ и СКНФ так, чтобы они были тождественно истинными. В лучшем случае можно будет построить СДНФ и СКНФ для обеих частей по отдельности, но они не будут эквивалентны.