Question

Приведите формулу ¬((y⇒¬x)⇔y) к к.н.ф. или д.н.ф методом равносильных преобразований.

Answer 1

$\neg ((y \to \neg x) \leftrightarrow y) = \neg ((\neg y \vee \neg x) \leftrightarrow y) = \neg ((\neg y \vee \neg x) \wedge y \vee \neg (\neg y \vee \neg x) \wedge \neg y) = \\\\= \neg ((\neg y \vee \neg x) \wedge y \vee y \wedge x \wedge \neg y) = \neg ((\neg y \vee \neg x) \wedge y \vee 0) = \neg (( y \wedge \neg y) \vee (y \wedge \neg x)) =\\\\= \neg (0 \vee y \wedge \neg x) = \neg (y \wedge \neg x) = \neg y \vee x$

Получили КНФ: $\neg y \vee x$

Answer 2

Для преобразования данной логической формулы в конъюктивную нормальную форму (КНФ) или дизъюнктивную нормальную форму (ДНФ) сначала разберемся с имеющейся формулой:

Исходная формула: ¬((y⇒¬x)⇔y)

1. Применим законы эквивалентности и импликации: ¬((¬y ∨ ¬x) ∧ (y ∨ x))

2. Применим закон де Моргана для отрицания конъюнкции: (y ∧ ¬x) ∨ (¬y ∧ ¬x)

3. Применим распределение конъюнкции относительно дизъюнкции: (y ∨ ¬y) ∧ (y ∨ ¬x) ∧ (¬y ∨ ¬y) ∧ (¬y ∨ ¬x)

4. Упростим выражения с тавтологиями (y ∨ ¬y) и (¬y ∨ ¬y): Итоговая формула: y ∧ (y ∨ ¬x) ∧ ¬y ∧ (¬y ∨ ¬x)

Теперь мы можем преобразовать итоговую формулу в КНФ или ДНФ:

Конъюктивная нормальная форма (КНФ): (y ∨ ¬x) ∧ ¬y ∧ (¬y ∨ ¬x)

Дизъюнктивная нормальная форма (ДНФ): (y ∧ ¬y ∧ ¬y ∨ ¬x)