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