МЛОИ

5.?(?(??X&?Y)&?(??Y&?X)) ??(?(X&?Y)&?(Y&?X)) (снятие двойного отрицания).
Итак, окончательно: X?Y ? ?(?(X&?Y)&?( Y&?X)).

Пример 2. Упростить выражение: X&Y ? (X&Y?Z).
1.X&Y ? (X&Y?Z) ?X&Y ? (?(X&Y) ? Z) (выражение импликации через дизъюнкцию и отрицание).
2.X&Y ? (?(X&Y) ? Z)?(X&Y ? ?(X&Y)) ? Z (ассоциативность дизъюнкции).
3.(X&Y ? ?(X&Y)) ? Z ? И ? Z (закон исключенного третьего)
4.И ? Z ? И (свойство логических констант).
Итак, X&Y ? (X&Y?Z) ? И, то есть исходная формула является тождественно истинной.

Пример 3. Упростить выражение: X&Z ? Y&Z ? X&?Z ? Y&?Z.
1.X&Z?Y&Z ?X&?Z?Y&?Z ? X&Z?X&?Z?Y&Z?Y&?Z (коммутативность дизъюнкции).
2.X&Z?X&?Z?Y&Z?Y&?Z ? (X&Z ? X&?Z) ?(Y&Z?Y&?Z) (ассоциативность дизъюнкции).
3.(X&Z?X&?Z) ? (Y&Z?Y&?Z) ? X&(Z??Z)?Y&(Z??Z)
(дистрибутивность конъюнкции относительно дизъюнкции).
4.X&(Z??Z)?Y&(Z??Z) ? X&И?Y&И
(закон исключенного третьего).
5.X&И ? Y&И ? X ? Y (свойства логических констант).
Итак, X&Z ? Y&Z ? X&?Z ? Y&?Z ? X ? Y.
Полагаем, что приведенных примеров достаточно, чтобы уяснить суть эквивалентных (тождественных) преобразований в логике высказываний.

4. Вывод следствий в логике высказываний

Пусть дана совокупность формул логики высказываний F={F1,F2,F3,…,Fm}. Формулы множества F называют посылками (или гипотезами). Определим понятие логического вывода формулы Ф из множества посылок (гипотез) F.
Вначале определим содержательно понятие логического следствия.
Будем говорить, что формула Ф является логическим следствием множества формул F1,F2,F3,…,Fn, если формула F1&F2&F3&…&Fn?Ф является тождественно-истинной (или тавтологией).
Например, формула X является логическим следствием формул (?X?Y) и (?X??Y), поскольку формула (?X?Y)&(?X??Y)?X тождественно истинна, в чем легко убедиться с помощью таблицы истинности:

(
?
X
?
Y
)
&
(
?
X
?
?
Y
)
?
X

И
Л
Л
Л

Л

И
Л
И
И
Л

И
Л

И
Л
И
И

Л

И
Л
Л
Л
И

И
Л

Л
И
И
Л

И

Л
И
И
И
Л

И
И

Л
И
И
И

И

Л
И
И
Л
И

И
И

Ясно, что если две формулы равносильны, то каждая из них является логическим следствием другой.
Построение логического вывода некоторой формулы основывается на применении в процессе вывода специальных правил, называемых правилами вывода
Наиболее часто используются следующие правила вывода:
1.Правило замены формулы равносильной. В процессе вывода в любой момент любую формулу (или подформулу) можно заменить равносильной ей формулой.
Например, формулу ?(A?B) в любой момент можно заменить равносильной ей формулой ?A&?B (второй закон Де Моргана), а формулу A??A — пропозициональной константой И (закон исключенного третьего).
2.Правило подстановки. Если в формулу F вместо всех вхождений пропозициональной переменной Xi подставить одну и ту же формулу ?, то полученная в результате формула будет логическим следствием формулы F.