Примеры. 1. Докажем 1-й из законов поглощения XÚ(XY) º X, используя правило замены

1. Докажем 1-й из законов поглощения X Ú(X Y) º X, используя правило замены.

– по свойству констант (№ 6).

Вынесем Х за скобки по закону дистрибутивности:

– два раза воспользовались свойствами констант.

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

Воспользуемся 1-м законом поглощения: (XY)ÚХ º X. Сделаем в нём подстановку , получим º X. Теперь в исходной формуле сделаем замену () / Х. Получим º.

Приведем еще несколько эквивалентностей, имеющих широкое применение.

11. .

12. .

13. Законы склеивания

, .

Эквивалентность формул является отношением эквивалентности, поэтому, согласно известной теореме о разбиении, множество M можно разбить на классы эквивалентности, включив в один класс эквивалентные между собой формулы. Каждой формуле U соответствует класс эквивалентности, который обозначается [ U ].

Определение. Формула называется приведенной, если она содержит операции конъюнкции, дизъюнкции и операцию отрицания, относящуюся к высказывательным переменным.

Теорема 2.5. Каждый класс эквивалентности [ U ] может быть представлен приведенной формулой, т.е. для любой формулы U M существует приведенная формула V.

Доказательство теоремы проведём конструктивно, т.е. определим порядок построения приведенной формулы.

1. Удаляются операции «импликация» и «эквиваленция» по формулам 11, 12.

2. Операции отрицания спускаются до высказывательных переменных с помощью законов де Моргана и двойного отрицания.

3. Если это возможно, то полученная приведенная формула упрощается с помощью свойств 3, 4, 5, 6, 9, 10.

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

Замечание. Приведенная формула для данного класса эквивалентности не является единственной.

Пример. Упростить формулу .

Решение. º – заменили импликацию по № 11.

Далее º ºº A.

Дата добавления: 2014-01-11