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

I Важным примером эквивалентности является разложение булевой функции по переменной- представление функции

в виде

| Справедливостьэтого тождества следует из того, что оба слагаемых, связанных знаком дизъюнкции, не могут одновременно равняться 1,|

•< i - :> ч - - -так как один из сомножителей X или X равняется 0. При подстановке

i,-- ' i -О в левую часть равенства константы 0 на место Х второе слагаемое в

правой части обращается в 0, а при подстановке константы 1 - первое.

(Функции (/1 — 1) переменныхимеют в качестве столбцов значений соответственно верхнюю и нижнюю половины столбца значений I Например, функция

, имеющая столбец значений, при разложении

по первой переменной может быть представлена.

, и поскольку- таблица для конъюнкции, а- для дизъюнкции, то

В каждом из слагаемых функции от переменныхмогут

_; быть таким же образом разложены по переменномуи т д.

Примеры.1) Для функции одной переменной разложение

имеет видОбозначим

Тогда - константы, равные значениям

функции j В этих обозначениях таблица функции

есть

I 2) Для функции 3 переменных разложение по

переменной X даег

Далее, обозначая - через

, разложим их по переменной Y :

Тем самым, получаем разложение исходной функции на 4 логических слагаемых: /

[раскрывая скобки]

Далее, вводя новые обозначения,

, разложим эти 4 функции по их единственной переменной Z:

i

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

переменным в виде дизъюнкции 8 логических слагаемых:

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

' функциина определенном наборе своих переменных, причем -переменная входит в конъюнкцию с отрицанием только, если ее значение в этом наборе равно 0. В связи с этим введем понятие: [ Элементарная конъюнкция- конъюнкция нескольких I переменных и их отрицаний, в которую каждая переменная входит не

! более одного раза.(Примеры элементарных конъюнкций:[. Формулы не являются элементарными

[конъюнкциями: первая содержит одновременно переменную X и ее [отрицание, во вторую переменная X входит дважды. | I Для дальнейшего введем удобное обозначение: - форма

^записи функции , где X - переменная, а- двоичный

параметр.! Рассмотрим подробнее:/если подставить константу вместо

обеих переменных, получим равенства;

подстановка констант вместо X дает:; наконец, при

подстановке констант вместополучаем. |

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

и т.п. элементарная конъюнкция, соответствующая набору

=- конъюнкция . Для п -мерного

набора конъюнкция содержит ровно п множителей с отрицаниями или

i без них. Как функция п переменных она принимает значение 1 только на наборе

Используя введенные обозначения, можно записать предыдущее

i разложение функциипо-другому:

I

Теперь можно удалить из этой логической суммы те слагаемые, для

которых (пользуясь свойствами 16 и 15). Логическую

сумму оставшихся членов можно записать так:

иликороче:

Имеется в виду, что в логической сумме участвуют только те элементарные конъюнкции, которые соответствуют наборам констант

, для которых

Подобное представление возможно для любой булевой функции, и мы приходим к важному понятию, j

Совершенная дизъюнктивная нормальная форма (СДНФ) -

представление функциив виде дизъюнкции всех

элементарных конъюнкций, соответствующих наборам значений , на которых Z = 1 :

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

. На каждом из наборов либо все логические слагаемые СДНФ обращаются в 0 (если функцияна этом наборе

равна 0), либо ровно одна конъюнкция обращается в 1 (еслиравна 1) Не имеет СДНФ единственная функция - тождественно равная нулю

(константа 0).

Отсюда - простой способ выражения любой функции (кроме константы 0), заданной таблично, в виде СДНФ. По таблице значений составляются соответствующие элементарные конъюнкции и связываются знаком дизъюнкции.

Примеры.1) Выражения

суть СДНФ этих

функций, ане СДНФ..

2) СДНФ для функции большинства содержит 4

элементарные конъюнкции:

3) СДНФ для функции 4 переменных со столбцом

значенийсодержит 6 элементарных конъюнкций:

Совершенная дизъюнктивная нормальная форма является частным случаем более общего вида формул.

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

дизъюнкции и отрицания например,- не ДНФ, однако ее

можно привести к ДНФ, раскрывая скобки:

Используя некоторые из эквивалентностей, прежде всего, 1-6, можно выносить за скобки общие множители, а применяя равенства 7-10, 13-18, а также приемы склеивания, упрощать формулы, поскольку, как уже отмечалось, в этих равенствах правые части короче левых.

Примеры.1) Докажем тождество:

= [раскрываем скобки] == [устраняем

кратность] =

2) Докажем тождество:> Преобразуем обе части равенства, выражая импликацию через

'дизъюнкцию: ; получаем:= [снимаем

двойное отрицание] =. Равенство доказано, поскольку

дизъюнкция - коммутативная операция.

I 3) Упростить формулу . Выносим за скобки

[общий множитель

i