2.5. Построение контрпримера

Для проверки того, что формула является тавтологией, существует более экономный метод, чем построение таблицы истинности. Поясним его суть на примерах. Пусть требуется проверить, является ли тавтологией формула

.

Предположим (І шаг), что она не является тавтологией и, следовательно, хотя бы один раз принимает значение Л. Выведем из этого утверждения следствия с помощью определения связок. Если в результате мы придем к противоречию, то формула является тавтологией, если противоречия не получится, то найдем значения переменных, при которых формула ложна, и, следовательно, в самом деле, она не является тавтологией.

и? и и л и л л л 4 2 5 1 6 3 7 8 4	(1)
л л и л и л 4 5 6 8 9 7 5	(2)

Разъяснение. В (1) значение 2 и 3 получаем из 1 по определению операции . Значение 4 – И, поставлено со знаком вопроса. Это значит, что в дальнейшем нужно также рассмотреть и значение Л. 5 – из 4, 2 и определения . 6 – из 4, 5 и определения . 7 – из 6, 3 и определения . 8 – из 7 и определения . Последнее значение противоречит полученному на 4 шаге.

Рассмотрим (2). Необходимость 4 уже объяснялась выше. 5 – из 4, 2 и определения . 6 – из 4, 5 и определения . 7 – из 3, 6 и определения . 8 – из 7 и определения . 9 – из 8 и определения . 9 противоречит 5.

При разборе второго примера не будем приводить подробные объяснения. В этом случае

и и и л и? л и 4 2 5 1 6 7 3 5	Как видно из таблицы, мы получаем, что ложь при А – истинно, В – истинно, т.е. формула не является тавтологией.
л и л 6 7 8

Контрольные вопросы и упражнения

1. Опустить (согласно договоренности о силе операций) возможно большее число скобок:

а) ;

б) ;

в) ;

г) .

2. Сколько столбцов, строк содержит истинностная таблица для формулы ?

3. Сколько существует булевых функций, зависящих от n переменных?

4. Сколькими способами можно расставить скобки в последовательности, чтобы получилась формула:

а) ;

б) .

5. Выписать все подформулы формулы:

а) ;

б) .

6. Построить истинностные таблицы для формул:

а) ;

б) ;

в) ;

г) .

7. Доказать, что формулы 1-10 – тавтологии:

1. ;

2. _;

3. _{; 3'. ;}

4. _{; 4'. ;}

5. _{; 5'. ;}

6. _{; 6'. ;}

7. _{; 7'. ;}

8. _;

9. _;

10. _.

8. Доказать, что если , то и , и если , то .

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

10. Доказать, что если и , то .

11. (Принцип двойственности). а) Пусть формула Ф содержит только связки , а формула Ф' получена из Ф заменой всюду на и на . Доказать, что тогда и только тогда, когда ;

б) Пусть формула Ф содержит только связки , а формула Ф^* получается из Ф заменой на , на и каждая буква – ее отрицанием (формула Ф^* называется двойственной для Ф). Доказать, что .