Основные равносильности булевых формул

1. aÚbºbÚa 1¢. aÙbºbÙa

2. aÚ(bÚc)º(aÚb)Úc 2¢. aÙ(bÙc)º(aÙb)Ùc

3. aÚ(bÙc)º(aÚb)Ù(aÚc) 3¢. aÙ(bÚc)º(aÙb)Ú(aÙc)

4.aÚ(aÙb)ºa 4¢. aÙ(aÚb)ºa

5. º`aÙ`b 5¢. º`aÚ`b

6. aÚaºa 6¢. aÙaºa

7. aÚ`aº1 7¢. aÙ`aº0

8. aÚ1º1 8¢. aÙ0º0

9. aÚ0ºa 9¢. aÙ1ºa

10. =a

Все эти равносильности могут быть доказаны с помощью таблицы истинности.

Замечания:

1. Нетрудно убедиться в том, что данные равносильности аналогичны таблице равенства множеств, в которой пересечение заменено конъюнкцией, а объединение - дизъюнкцией, пустое множество - тождественно ложным, а универсальное множество - тождественно истинным высказыванием. Сами эти равносильности называются так же, как и соответствующие равенства. Так 5 и 5¢ называются законами де Моргана, а 10 - закон снятия двойного отрицания.

2. Можно заметить, что правый столбец получается из левого заменой конъюнкции на дизъюнкцию, дизъюнкции на конъюнкцию, 1 заменяется на 0, а 0 на 1.

Вернёмся к теореме. Не проводя доказательства, покажем на примере, как найти равносильную булевую формулу.

Пример. F=(a®(bÚс))®aº(`aÚ(bÚс))®aº Úaº Úaº(aÙ(`bÙ`c)Úaºa`b`cÚa

Приведённой булевой формулой называется булева формула, в которой символ отрицания относится только к символам простых компонент. Так, формула Úa является булевой, но не приведённой, а равносильная ей a`b`cÚa - приведённая.

Следствие. Всякая формула логики высказываний равносильна приведённой булевой формуле.

Это следует из правил подстановки, законов до Моргана и снятия двойного отрицания.