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

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

Реферат

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

• Дипломная работа студента 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.

§4. Дизъюнктивные нормальные формы (ДНФ)

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

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

Пусть F – высказывание и .

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

в том и только в том случае, когда .

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

Достаточно построить таблицу истинности для :


001010100111

Непосредственно видно, что на тех и только тех наборах, где .

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

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

Конъюнкция логических переменных или их отрицаний называется элементарной конъюнкцией.

Общий вид элементарной конъюнкции: .

1. Примеры

.

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

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

Высказывание называется дизъюнктивной нормальной формой, если оно представляет собою дизъюнкцию элементарных конъюнкций. Общий вид ДНФ: , где каждая , в свою очередь, является элементарной конъюнкцией.

1. Примеры

1) ;

2) ;

3) ;

4) ;

5) ;

6) ;

7) .

Второе высказывание не является ДНФ, так как в ДНФ перемножаются лишь переменные или их отрицания. Пятое высказывание не является ДНФ, так как в ДНФ отрицание может располагаться лишь над переменными. Остальные высказывания являются дизъюнктивными нормальными формами.

1. Теорема 5

Любое высказывание равносильно дизъюнктивной нормальной форме (говорят еще так: “любое высказывание приводимо к ДНФ”).

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

Будем доказывать методом математической индукции по числу логических операций, входящих в высказывание .

В силу тождеств можно в высказывании избавиться от всех импликаций и эквивалентностей, входящих в . Например, пусть , тогда .

Получили высказывание, равносильное и не содержащее "®" и "«". В дальнейшем будем считать, что высказывание построено из логических переменных и операций . Через n обозначим количество операций, входящих в .

Пусть n=0, тогда высказывание , следуя определению, может быть лишь простейшим высказыванием или логической переменной . Очевидно, что это высказывание есть ДНФ.

Допустим, утверждение о приведении к ДНФ доказано для всех высказываний с числом логических операций . И докажем теперь его для высказывания , которое содержит логических операций. Опять же, следуя определению высказывания и тому обстоятельству, что в нет импликаций и эквивалентностей, представимо в одном из трех видов:

, или , или .

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


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