Равносильность формул логики высказываний

Определение. Пусть А и В – две формулы, зависящие от одного и того же списка переменных. Будем называть их равносильными, если для любого набора значений переменных они принимают одинаковые значения.

Другой способ доказательства равносильности формул или проверки их тождественной истинности или ложности состоит в использовании так называемых основных логических законов (основных равносильностей), обоснование которых можно провести путем построения соответствующих таблиц истинности. К основным логическим законам обычно относят следующие соотношения:

Рассмотрим основные равносильности логики высказываний.

Пусть А, В, С – произвольные формулы.

Таблица 3 – Основные логические законы

1. Идемпотентность
А Ù А = А	А Ú А = А
2. Коммутативность
А Ù В = В Ù А	А Ú В = В Ú А
3. Ассоциативность
А Ù (В Ù С) = (А Ù В) Ù С	А Ú (В Ú С) = (А Ú В) Ú С
4. Правила поглощения
А Ù (А Ú В) = А	А Ú (А Ù В) = А
5. Дистрибутивность
А Ù (В Ú С) = (А Ù В) Ú (А Ù С)	А Ú (В Ù С) = (А Ú В) Ù (А Ú С)
6. Правила де Моргана
7. Свойства констант
А Ù 1 = А А Ù 0 = 0	А Ú 0 = А А Ú 1 = 1
8. Закон исключения третьего и закон противоречия
9. Снятие двойного отрицания
10. Формулы расщепления (склеивания)
11. Связь дизъюнкции, конъюнкции, отрицания и импликации
12. Выражение эквивалентности

Определение. Такие преобразования, использующие равносильности формул (запас которых можно расширять с помощью правила подстановки) и правило замены, называются тождественными преобразованиями.

Тождественные преобразования являются мощным средством доказательства равносильности формул и тождественной истинности или тождественной ложности формул, как правило, более эффективным, чем их вычисление на наборах значений переменных (т.е. чем составление таблиц истинности).

Отметим, что «тактика» доказательства равносильности может быть разная: либо преобразуем одну из формул, приводя ее к виду другой, либо преобразуем обе формулы, приводя их к одной и той же формуле.

Примеры.

1. Упростить формулу: .

2. Определить, является ли формула тавтологией, противоречием или ни тем, ни другим:

a) ;

b) .

Решение.

1.

2. a)

Поскольку формула при любых значениях переменных равна нулю, то данная формула является противоречием.

b)