Сервер Методического Обеспечения вгуэс

Вид материала

Реферат

Содержание F к ДНФ: , то есть и в последнем, третьем случае F

Подобный материал:

• Дипломная работа студента 545 группы, 334.18kb.
• Т. Н. Коржавина Принципы организации службы научного и методического обеспечения колледжа, 47.35kb.
• «sql*net», 239.02kb.
• Генезис развития теории и методики программно-методического обеспечения обучения, 145.89kb.
• Прозрачный прокси сервер на базе squid, ipfw и Freebsd, 8.5kb.
• Доклад «Три кита школьного образования: стандарты, учебники, егэ», 116.02kb.
• Справка по результатам самоаттестации методического объединения учителей русского языка, 447.26kb.
• Большой Сервер Недвижимости 31. 05. 2008: программа, 1328.13kb.
• Т. Г. Римская научный редактор, к и. н., доцент, директор филиала вгуэс в г. Находке, 2476.8kb.
• Владивосток: Изд-во вгуэс, 2005., 1071.2kb.

,

то есть F является дизъюнкцией элементарных конъюнкций, то есть ДНФ.

Во втором случае

.

Так как произведение элементарных конъюнкций есть элементарная конъюнкция, значит, и во втором случае приводимо к ДНФ.

Осталось доказать приводимость к ДНФ в третьем случае, то есть когда .

Для упрощения выкладок будем считать, что l=2 и каждая элементарная конъюнкция есть произведение двух логических переменных или их отрицаний, то есть .

При доказательстве того, что F приводимо к ДНФ, нам придется воспользоваться следующим простым равенством, которое мы рекомендуем доказать самостоятельно:

.

Итак, начинаем приводить F к ДНФ:

,

то есть и в последнем, третьем случае F приводимо к ДНФ.

Таким образом, теорема доказана.

1. Пример

Привести к ДНФ высказывание

.

• Решение

 – ДНФ.

Отметим, что доказательство теоремы носит конструктивный характер. В нем указана последовательность действий (алгоритм), которые необходимо производить с высказыванием, чтобы привести его к ДНФ:

1) используя формулы , , избавляемся в от импликаций и эквивалентностей;

2) используя законы Моргана и закон двойного отрицания, добиваемся того, чтобы отрицания находились лишь над логическими переменными;

3) используя дистрибутивные законы, "раскрываем" скобки и приводим высказывание к ДНФ;

4) используя законы противоречия и исключенного третьего, а также логические тождества, содержащие константы, на каждом этапе и в конце максимально упрощаем получающиеся выражения.

1. Пример

Привести к ДНФ высказывание

.

• Решение

1. Замечание

Вводя понятие элементарной дизъюнкции, конъюнктивной нормальной формы, можно построить аналогичную теорию для КНФ. Читателю, склонному к самостоятельным изысканиям, предлагаем развить эту теорию самостоятельно.

1. §5. Построение высказываний по таблице истинности. Совершенные дизъюнктивные нормальные формы (СДНФ)

Самая первая задача, которую мы научились решать, изучая алгебру высказываний, – это построение по высказыванию его таблицы истинности. Можно ли решить обратную задачу – построить высказывание по таблице истинности?

1. Определение 1

Пусть  – некоторое множество логических переменных. Элементарная конъюнкция, в которую входят все логические переменные, называется полной элементарной конъюнкцией относительно множества .

1. Пример

Пусть . Рассмотрим элементарные конъюнкции: . Лишь третья, пятая, шестая элементарные конъюнкции являются полными относительно .

1. Утверждение 2

Пусть  – полная элементарная конъюнкция относительно множества . Тогда содержит в таблице истинности лишь одну единицу, причем на наборе . И наоборот, если в таблице истинности высказывания имеется лишь одна единица на наборе , то является полной элементарной конъюнкцией, причем .

• Доказательство

Вспомним соотношение: в том и только в том случае, когда . Итак, пусть , отсюда следует, что для любого , а это значит, что . Итак, мы доказали, что полная элементарная конъюнкция равна 1 лишь на одном наборе .

Докажем в другую сторону. Пусть лишь при одном наборе значений , но по доказанному выше этим же свойством обладает полная элементарная конъюнкция , значит

Утверждение доказано.

1. Определение 3

Пусть  – высказывание. Обозначим через множество всех наборов , на которых . называется множеством истинности высказывания . Можно записать: