Эквивалентность формул. Основные тавтологии алгебры логики

Ранее было показано, что каждой формуле над соответствует функция алгебры логики, причем различным формулам могут соответствовать равные функции.

Определение. Формулы и называются эквивалентными, если соответствующие им функции и равны, т. е. . Запись означает, что формулы и эквивалентны.

Приведем список основных эквивалентностей (тождеств, тавтологий) алгебры логики, которые соответствуют теоретико-множественным тождествам, если заменить дизъюнкцию на объединение, конъюнкцию – на пересечение, отрицание – на дополнение.

1. (коммутативность дизъюнкции).

2. (ассоциативность дизъюнкции).

3. (коммутативность конъюнкции).

4. (ассоциативность конъюнкции).

5. (правило повторения для дизъюнкции).

6. (правило повторения для конъюнкции).

(операции с 0 и 1 для дизъюнкции и конъюнкции).

11. (закон двойного отрицания).

(правила инверсии).

14. (дистрибутивность конъюнкции).

15. (дистрибутивность дизъюнкции).

(законы де Моргана).

18. .

19. .

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

С целью упрощения записи формул принимают следующие соглашения.

1. Приоритет логических связок. Пусть – множество логических связок:

.

а) считают, что связка сильнее любой двухместной связки из ;

б) связка считается сильнее, чем любая из оставшихся связок.

2. Обозначим через любую из связок , . В силу закона ассоциативности можно вместо формул , использовать выражение , которое не является формулой, но может быть превращено в нее путем расстановки скобок.

3. Внешние скобки у формул опускаются. Опускаются также скобки у выражения, над которым стоит знак отрицания.

Эти соглашения позволяют, например, формулу записать в виде .

Рассмотрим некоторые следствия из тождеств 1 – 19.

Тождества 2 и 3 позволяют рассматривать логические суммы и произведения с любым числом слагаемых и результат не зависит от расстановки скобок. Поэтому далее будем использовать следующие обозначения:

, .

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

1) Если в логическом произведении один из сомножителей равен 0, то и произведение равно 0.

2) Если в логическом произведении, содержащем не менее двух сомножителей, имеется сомножитель, равный 1, то этот сомножитель можно зачеркнуть.

3) Если в логической сумме, содержащей не менее двух слагаемых, имеется слагаемое, равное 0, то это слагаемое можно зачеркнуть.

4) Если в логической сумме одно из слагаемых равно 1, то сумма равна 1.

Пример 7. Правило поглощения:

.