Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

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

Множества. Равенство множеств | Алгебра множеств | Декартово произведение и отношения | Эквивалентность | Частичный порядок | Высказывания и операции над ними | Анализ сложного высказывания | Некоторые логические законы | Нормальные формы | Логическое следствие |


Читайте также:
  1. Step 3. Построение ИНТЕРВЬЮ!
  2. Анализ и построение линий Ганна.
  3. Анализ факторов, влияющих на построение оргструктуры в организации
  4. НАЧАЛЬНЫЕ НЕПОЛНЫЕ КОМБИНАЦИИ ШАНСЫ НА ПОСТРОЕНИЕ
  5. НОВАЯ ЗАДАЧА ЛИДЕРА: ПОСТРОЕНИЕ ОБУЧАЮЩЕЙСЯ ОРГАНИЗАЦИИ. Питер Сенге
  6. Открытие позиций в середине тренда и построение пирамиды
  7. Построение , назначение и области применения цикловых графиков

 

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

.

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

 

 
и? и и л и л л л 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 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Формулы. Булевы функции| Равносильные формулы

mybiblioteka.su - 2015-2024 год. (0.009 сек.)