Докажите равносильность формул сравнением их совершенных нормальных форм (коньюнктивных или дизьюнктивных).

Добавлена: 30.04.2026
Обновлена: 30.04.2026
Предмет: Логика
Автор: Кэмп

#Основы формальной логики
#Теория доказательств

Докажите равносильность формул сравнением их совершенных нормальных форм (коньюнктивных или дизьюнктивных).

Условие:

Докажите равносильность формул $\overline{x \bar{y}}\rightarrow(\vec{y}\rightarrow x)_{}\mathbf{x}\rightarrow\mathbf{y}\vee\mathbf{x}\vee\mathbf{y}$ сравнением их совершенных нормальных форм (коньюнктивных или дизьюнктивных).

Решение:

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

Начнём с Ф1:
(1) ¬(x ∧ ¬y) → (y → x)

Заметим, что импликация A → B эквивалентна формуле ¬A ∨ B. Применяя это, получаем:
(2) ¬[¬(x ∧ ¬y)] ∨ (y → x)

При этом двойное отрицание даёт:
(3) = (x ∧ ¬y) ∨ (y → x)

Теперь заметим, что и в правой части импликация y → x равносильна формуле ¬y ∨ x:
(4) = (x ∧ ¬y) ∨ (¬y ∨ x)

Покажем, что дизъюнкция (x ∧ ¬y) ∨ (¬y ∨ x) всегда равна (x ∨ ¬y). Действительно, поскольку формула (¬y ∨ x) уже содержит все случаи, когда (x ∧ ¬y) истинн...