Читайте также:
|
|
Для проверки того, что формула является тавтологией, существует более экономный метод, чем построение таблицы истинности. Поясним его суть на примерах. Пусть требуется проверить, является ли тавтологией формула
.
Предположим (І шаг), что она не является тавтологией и, следовательно, хотя бы один раз принимает значение Л. Выведем из этого утверждения следствия с помощью определения связок. Если в результате мы придем к противоречию, то формула является тавтологией, если противоречия не получится, то найдем значения переменных, при которых формула ложна, и, следовательно, в самом деле, она не является тавтологией.
и? и и л и л л л 4 2 5 1 6 3 7 8 | (1) |
л л и л и л 4 5 6 8 9 7 | (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 | Как видно из таблицы, мы получаем, что ложь при А – истинно, В – истинно, т.е. формула не является тавтологией. |
л и л 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.(Принцип двойственности). а) Пусть формула Ф содержит только связки , а формула Ф' получена из Ф заменой всюду на и на . Доказать, что тогда и только тогда, когда ;
б) Пусть формула Ф содержит только связки , а формула Ф* получается из Ф заменой на , на и каждая буква – ее отрицанием (формула Ф* называется двойственной для Ф). Доказать, что .
Дата добавления: 2015-11-14; просмотров: 102 | Нарушение авторских прав
<== предыдущая страница | | | следующая страница ==> |
Формулы. Булевы функции | | | Равносильные формулы |