МЛОИ

Если множества пропозициональных переменных, входящих в формулы F и Ф не совпадают, то можно добиться этого совпадения, введя в ту или другую формулу недостающую переменную в качестве «фиктивной». Пусть, например, формула F не содержит пропозициональной переменной Xi. Тогда эту переменную можно ввести в формулу F «фиктивно», заменив формулу F на формулу F?( Xi?? Xi) или на формулу F&( Xi?? Xi), которые на основании закона противоречия, закона исключенного третьего и свойств логических констант Л и И, равносильны F. Аналогично можно «фиктивно» ввести в формулы F и Ф все другие недостающие переменные. Это соображение легко распространить на любое число формул.
Как мы условились выше, тот факт, что формулы F и Ф логически равносильны будем обозначать F?Ф.
Отношение равносильности формул, очевидно, обладает свойством транзитивности: если F?Ф и Ф??, то F??.
Приведенные выше свойства операций и законы логики высказываний, как легко проверить с помощью таблиц истинности, выражают логическую равносильность (эквивалентность) тех или иных формул.
Кроме приведенных выше равносильностей в логике высказываний большое значение имеют и другие, среди которых отметим следующие:
Коммутативность строгой дизъюнкции: X?Y ? Y?X.
Ассоциативность строгой дизъюнкции:
X?(Y?Z) ?(X?Y)?Z.
Закон контрапозтиции: X?Y ? ?Y ? ?X.
Транзитивность импликации: (X?Y)&(Y?Z)?(X?Z).
Выражение импликации через дизъюнкцию и отрицание:
X?Y ? ?X?Y.
Выражение эквиваленции через импликацию и конъюнкцию:
(X?Y) ?(X?Y)&(Y?X).
Выражение дизъюнкции через конъюнкцию и отрицание:
X?Y ? ?(?X??Y).
Выражение конъюнкции через дизъюнкцию и отрицание:
X&Y ? ?(?X??Y).
Логические равносильности играет важную роль в логике высказываний. Они фактически являются правилами и законами логических рассуждений, законами правильного мышления.1) Ниже мы покажем их применение, например, к анализу структуры математических доказательств. На основании перечисленных выше равносильностей, к которым относятся свойства логических операций, логические законы и т.д., осуществляются равносильные (тождественные) преобразования формул логики высказываний с целью упрощения выражений или приведения к определенному виду (подобно тому, как это делается в школьной алгебре на основании свойств арифметических операций, алгебраических законов и иных тождественных соотношений).
3. Равносильные преобразования формул
Рассмотрим на примерах равносильные (тождественные) преобразования формул логики высказываний.

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