Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы.

Элементарной конъюнкциейназывается конъюнкция, состоящая только из переменных или их отрицаний. Например: Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru .

Дизъюнктивно-нормальнойформой (ДНФ) называется дизъюнкция элементарных конъюнкций. Например: Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru .

Если учесть, что нулевые конъюнкции можно опустить, а А*А=А, то приведенная ДНФ сведется к более простому виду: Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru . Дальнейшее упрощение получается с помощью законов поглощения: Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru . Но полученная формула еще не является минимальной. Можно применить правило, основанное на соображениях симметрии: в рассматриваемой формуле каждая из переменных А, В, встречается два раза, но переменная В встречается один раз с отрицанием, а один раз без отрицания. Значит, симметрия нарушена по переменной В. Тогда тот член дизъюнкции, который эту переменную В не содержит, пропадет, т. е. поглотится АС.

Покажем, что это действительно так:

Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru = Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru

(по закону поглощения Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru ) .

Мы доказали следующее правило поглощения:

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

Проиллюстрируем это правило еще на двух примерах.

1. Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru . Этот трехчлен содержит два раза Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru , два раза Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru , но один раз Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru и один раз Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru . Значит,, симметрия нарушена по Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru . Поэтому, согласно нашему правилу, пропадает член, не содержащий букву Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru (т. е. не содержащий ни Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru , ни Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru ). Значит, надо вычеркнуть Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru .

2. Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru . Этот трехчлен содержит два раза Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru , два раза Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru , но один раз Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru и один раз Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru . Симметрия нарушена по Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru . Значит, вычеркиваем член, не содержащий Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru , т. е. вычеркиваем Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru .

Минимальной мы назовемту ДНФ,которая имеет самую ко­роткую запись.

Существует еще одно правило поглощения, которое тоже основано на соображениях симметрии:

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

Например: Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru . Покажем, что это действительно так:

Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru .

Рассмотрим еще несколько примеров, иллюстрирующих это правило.

1. Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru . Этот трехчлен содержит два раза Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru , но содержит по одному разу Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru и Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru , и по одному разу Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru и Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru . Значит, симметрия нарушена дважды: по Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru и по Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru . Симметрия не нарушена только по Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru . Поэтому, применяя наше правило, получим дизъюнкцию, одним членов которой будет Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru , адругим — тот член трехчлена, | который_ не содержит Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru . Значит, получим Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru .

2. Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru . В этом трехчлене симметрия нарушена по Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru и по Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru . Симметрия не нарушена только по Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru . Значит, Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru = Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru .

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

Например: Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru

Среди всех этих ДНФ есть одна, которая отличаете однородностью и «совершенством» своей формы. Mы имеем в виду формулу: Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru Она так и называется: «совершенная дизъюнктивно-нормальная форма»(СДНФ).

Дадим точное определение:

СДНФ — это такая ДНФ, которая удовлетворяет следующим условиям:

1. Все элементарные конъюнкции различны.

2. Нет нулевых конъюнкций.

3. Ни одна из элементарных конъюнкций не содержит одинаковых членов.

4. Каждая элементарная конъюнкция содержит все переменные.

Чтобы получить СДНФ, надо сначала найти минимальную ДНФ. Тогда будут выполнены условия 1, 2, 3. Посли этого надо преобразовать эту минимальную ДНФ таким образом, чтобы было выполнено условие 4. Это делается следующим образом:

Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru Приведение формул алгебры высказываний к КНФ виду

Элементарной дизъюнкциейназывается дизъюнкция, состоящая только из переменных или их отрицаний. Например: Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru .

Конъюнктивной нормальной формой(КНФ) называется конъюнкция элементарных дизъюнкций. Например: Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru . Если воспользоваться равносильностью Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru , то Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru можно заменить через Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru . Кроме того, известно, что, Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru . А если один член дизъюнкции равен 1, то и вся дизъюнкция равна 1. Значит: Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru . Но Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru . Значит, единичный член конъюнкции мож­но просто опустить. Таким образом, первоначальная КНФ| сводится к более простой форме: Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru .

Но эта формула не является еще минимальной. Для КНФ тоже существуют правила поглощения, основанные на соображениях симметрии. Эти правила можно полу­чить по закону двойственности из аналогичных правил, установленных для ДНФ.

Мы знаем, например, что: Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru (симметрия нарушена по переменной Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru . Поглотилось вы­ражение, не содержащее эту переменную). Запишем теперь двойственную равносильность: Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru . В левой части стоит ранее полученная КНФ. Значит, эту КНФ действительно можно свести к более простой форме.

В то же время мы установили новое правило погло­щения:

Если КНФ зависит от трех переменных и представляет собой конъюнкцию трех элементарных дизъюнкций и если симметрия нарушена только по одной из пере­менных, то поглощается та элементарная дизъюнкция, которая эту переменную не содержит.

Аналогичным образом можно получить и второе пра­вило поглощения, основанное на соображениях симмет­рии. Мы уже знаем, что: Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru .

Запишем двойственную равносильность: Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы. - student2.ru

Сформулируем соответствующее правило поглощения:

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

Наши рекомендации