Совершенные нормальные формы.

↑

▷ Содержание

⇐ ПредыдущаяСтр 5 из 15Следующая ⇒

Формулы х и  будем называть литералами, т.е. литерал – это или х, или .

Если в ДНФ каждое элементарное произведение содержит все элементарные высказывания, но только в виде единственного литерала, то ДНФ называется совершенной дизъюнктивной нормальной формой (СДНФ).

Например: =pqr r является ДНФ, но не является СДНФ, т.к. во второе элементарно произведение не входит ни р, ни .

Формула = pqr r  – СДНФ.

Формула = pqr rq – не СДНФ, т.к. во втором элементарном произведении содержится два литерала.

Теорема. Любаяформула, отличная от 0, представима в виде СДНФ.

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

Пусть Ф – формула, содержащая n литералов. Пусть ДНФ содержит элементарное произведение без литерала . = ,  - литералы. Введем дизъюнкцию , которая равна 1. Получим = ( )=(по первому закону дистрибутивности)= .

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

Что и требовалось доказать.

Пример 1.

Пусть = pqr q – ДНФ.

Приведем к СДНФ. Добавим 1 в виде дизъюнкции r . Получим =pqr q (r ) pqr qr q  - СДНФ.

Если каждая элементарная сумма КНФ формулы содержит все литералы по одному разу, то такая форма называется совершенной конъюнктивной нормальной формой (СКНФ).

Теорема. Любая формула может быть приведена к СКНФ.

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

Если элементарная сумма не содержит литерал , то можно в нее ввести конъюнкцию  и воспользоваться вторым законом дистрибутивности.

Пример 2. Пусть =(p q r) ( q) – КНФ.

Приведем к СКНФ. Добавим 0 в виде r . Получим

=(p q r) ( q r ) (p q r) ( q r) ( q )

это – СКНФ.

Восстановление формул.

Каждой формуле соответствует таблица истинности, следовательно, каждой таблице истинности соответствует некоторая формула. Возникает задача - для заданной таблицы истинности восстановить формулу, которой она соответствует. Этого можно достичь двумя способами:

С помощью СКНФ или с помощью ДНФ.

1. СКНФ.

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

Пример: дана таблица

Так как во 2-ой строке функция ложна, то должна быть ложна элементарная сумма. А элементарная сумма ложна тогда, когда каждый ее член равен 0.

Т. к. р=1, =0; и в дизъюнкцию должно входить .

Т. к. q=1, =0; и в дизъюнкцию должно входить .

r=0- без отрицания.

Получим: r.

Аналогично

Для 4-ой строки: р

Для 7-ой строки: . Тогда

Ф=( r)(р )( ).

2. СДНФ.

В таблице истинности выделяются строки, в которых формула истинна. Каждой такой строке поставим в соответствие элементарное произведение, которое должно быть истинно. В это произведение истинные высказывания входят без отрицания, а ложные - с отрицанием. Затем составляется дизъюнкция элементарных произведений.

Для нашего примера:

Ф = рqr р r р q

Построение минимальной ДНФ.

Формула (булева функция) имеет минимальную ДНФ, если она содержит наименьшее количество литералов среди всех ДНФ, эквивалентных ей.

Пример:

ДНФ -  содержит 4 литерала, но она не является минимальной. Преобразуем ее ( ) =1* = . Получили один литерал.

Рассмотрим алгоритм Квайна Мак-Клоски:

Пусть функция задана СДНФ и ,  - два элементарных произведения, входящих в СДНФ. Пусть х - литерал, такой, что =xk и = k. Тогда = хk k = (x )k = k. Мы получили элементарное произведение, содержащее на один литерал меньше.

Такая операция называется склейкой.

Пример:

Ф=pqr р r q r. Произведем склейку 1й и 2й, а так же 3й и 4й элементарных произведений.

Ф= pr(q ) (q ) r pr r.

Решение логических задач.

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

Задача:

В конкурсе участвовало 4 девушки: Оля, Нина, Марина и Тамара.

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

Оля 1 -  Нина-2,         

Оля-2 - Тамара-3,   

Марина-2 - Тамара-4.

Известно, что хотя бы одна высказывание в каждом ответе истинно. Как распределились места?

Решение:

Введем обозначения:

О Н ; О Т ; М Т .

Тогда КНФ: (О Н ) (О Т ) (М Т ) 1, т.к. Каждое из элементарных сумм истинно.

 Преобразуем в  ДНФ, раскрывая скобки:

(О  Н ) (О  М  О  Т Т  М  Т  Т )

(т.к. О₂ М ₂ =0 и Т₃Т₄=0) (О  Н ) (О  Т  Т  М )  (раскрываем скобки)

О  О  Т  О  Т  М  Н  О  Т  Н  Т  М

О  Т  М  .

Получили О  Т  М 1.

Следовательно: Оля-1,Марина-2, Тамара-3, Нина-4.

Анализ рассуждений.

     Рассуждение - это вывод, позволяющий из данных высказываний (называемых посылками) получить новое высказывание (заключение).

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

Познавательные статьи:



Как правильно слушать собеседника

Типичные ошибки при выполнении бросков в баскетболе

Принятие христианства на Руси и его значение

Средства массовой информации США