Поставим задачу: построить для произвольной булевой функции минимальные ДНФ. 3 страница
а) ;
б) .
◄ а)Преобразуемформулу, используя равносильность :
.
Поскольку на любом наборе
и на любом наборе
, то согласно определению
,
- фиктивные переменные. Переменная же
- существенная, т.к.
,
.
б)выполнить самостоятельно.►
Обратите внимание. Если функция реализована формулой, в которую некоторая переменная не входит, то эта переменная фиктивная. Обратное утверждение неверно. Действительно, в упражнении 14 а) мы рассмотрели функцию, реализованную формулой, содержащую переменные ,
, однако эти переменные оказались фиктивными.
Упражнение 2.15. Выяснить, на скольких векторах 4-х мерного булева куба обращается в ноль функция: а) ; б)
.
◄а)Функция обращается в ноль, если
или
. Равенства
выполняются, только если все переменные равны единице. Равенства
выполняются на таких наборах
значений переменных
, у которых
одновременно не равны единице и
одновременно не равны единице. При построении конкретного булевого вектора
, отвечающего этим требованиям, будем сначала выбирать пару
, а затем пару
. Каждую из этих пар можно выбрать тремя способами (взять 0,0, или 0,1, или 1,0). Значит, согласно правилу произведения построить булев вектор, на котором оба слагаемых
и
равны нулю, можно девятью способами.
Таким образом, есть десять векторов, на которых функция обращается в нуль.
б)решить самостоятельно.►
Нормальные формы
2.2.1. Принцип двойственности
Определение. Функция, реализуемая формулой , называется двойственной к функции
.
Функцию, двойственную к , обозначают
, т.е.
.
Упражнение 2.16.Используя определение, найти двойственные функции для дизъюнкции, конъюнкции и функций одной переменной.
◄ Пусть . Тогда
.
Пусть . Тогда
.
Пусть . Тогда
.
Пусть . Тогда
.
Пусть . Тогда
.
Пусть . Тогда
.►
Утверждение. Для любой функции выполняется равенство
.
◄ .►
Обсудим, как найти двойственную функцию, если сама функция задана таблицей или вектором значений. Рассмотрим таблицы истинности для произвольной функции двух переменных , а также двойственной к ней функции
:
![]() | ![]() | ![]() | ![]() |
![]() | ![]() | ||
![]() | ![]() | ||
![]() | ![]() | ||
![]() | ![]() |
Нетрудно заметить, что столбец значений функции можно получить из столбца значений функции
, если действовать по следующему алгоритму:
1. столбец значений функции переписать в обратном порядке (т.е. число, стоящее в первой строке, записать в последнюю строку; число, стоящее во второй строке - в предпоследнюю строку и т.д.);
2. в получившемся в результате выполнения пункта 1 столбце значений каждое число заменить его отрицанием (0 заменить 1 и 1 заменить 0).
Аналогичного алгоритма для получения двойственной функции можно придерживаться и в случае любого числа аргументов.
Упражнение 2.17.Найти функции, двойственные данным:
а) ; б)
;
в) ; г)
.
◄ а) .
б) .
в)и г) решите самостоятельно.►
Упражнение 2.18.Найти функции, двойственные данным:
а) ; б)
.
◄ а) Вначале зададим функцию таблицей:
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() |
Далее: .
б)решите самостоятельно.►
Итак, если функция задана формулой, то, чтобы найти двойственную к
функцию, можно вначале задать функцию
вектором значений, а затем по вектору значений
выписать вектор значений
. Но можно действовать и по другому: строить формулу, реализующую
, непосредственно по формуле, реализующей
. Алгоритм такого построения дает принцип двойственности.
Принцип двойственности. Если формула реализует функцию
, то формула, полученная из нее заменой символов функций
на символы двойственных к ним функций
, реализует функцию
, двойственную к функции
(эту формулу будем называть двойственной к
и обозначать
).
Принцип двойственности удобен при нахождении двойственных функций в случае, если функция задана формулой. Особенно часто используют его следствие:
Поскольку ,
,
,
,
,
, то для получения формулы, двойственной к формуле
, нужно в формуле
заменить 0 на 1, 1 на 0, связку
на связку
, связку
на связку
.
Упражнение 2.19. Реализовать формулами функции, двойственные данным:
а) ; б)
; в)
; г)
.
◄ а) .
Обратите внимание на следующее обстоятельство. В записи формулы, реализующей , конъюнкция, согласно соглашению о краткой записи формул, в скобки не взята. Записывая двойственную формулу, мы меняем конъюнкцию на дизъюнкцию. Но связка «
» имеет меньший приоритет выполнения, чем «
», поэтому, чтобы двойственная формула сохранила структуру исходной формулы, при переходе от конъюнкции к дизъюнкции нужно взять дизъюнкцию в скобки. В то же время при переходе от дизъюнкции к конъюнкции скобки можно опустить.
б) .
в)и г) решите самостоятельно.►
2.2.2. Реализация булевых функций в виде СДНФ и СКНФ.
Мы научились задавать вектором значений функцию, реализованную формулой. Для приложений важно уметь решать и обратную задачу, т.е. уметь реализовывать формулой функцию, заданную вектором значений. У этой задачи не одно решение, поскольку существуют семейства равносильных между собой формул.
Начнем с того, что научимся реализовывать функцию в виде совершенной дизъюнктивной нормальной формы.
Введем обозначение:
Теорема (о реализации функции в виде СДНФ). Если , то она может быть реализована формулой
. (*)
Формулу (*) называют совершенной дизъюнктивной нормальной формой или, сокращенно,СДНФ.
Согласно (*), чтобы записать СДНФ функции, нужно действовать так:
1) выбрать в таблице истинности функции все наборы значений переменных, на которых функция равна 1;
2) для каждого такого набора записать конъюнкцию, в которую войдут все переменные, причем, если значение переменной на данном наборе равно 0, то она войдет в конъюнкцию со знаком отрицания, а если – 1, то без знака отрицания;
3) записать дизъюнкцию всех выписанных в п. 2 конъюнкций.
Упражнение 2.20.Реализоватьфункции в виде СДНФ:
а) ; б)
; в)
; г)
; д)
.
◄ а) – в) Зададим функции таблично и выпишем для них СДНФ.
![]() | ![]() | ![]() | ![]() | ![]() |
;
;
.
г) Таблица истинности функции приведена в упражнении 2.18 б. Запишем СДНФ:
.
д)решите самостоятельно. ►
Рассмотрим еще один способ реализации функции формулой.
Теорема (о реализации функции в виде СКНФ). Если , то она может быть реализована формулой
. (**)
Формулу (**), называют совершенной конъюнктивной нормальной формой или, сокращенно,СКНФ.
Согласно (**), чтобы записать СКНФ функции, нужно действовать так:
1) выбрать в ее таблице истинности все наборы значений переменных, на которых функция равна 0;
2) для каждого такого набора записать дизъюнкцию, в которую войдут все переменные, причем, если значение переменной на данном наборе равно 1, то она войдет в дизъюнкцию со знаком отрицания, а если – 1, то без знака отрицания;
3) записать конъюнкцию всех выписанных в п. 2 дизъюнкций.
Упражнение 2.21.Реализоватьфункции в виде СКНФ:
а) ; б)
; в)
; г)
; д)
.
◄ а) – г) Опираясь на таблицы истинности функций (они приведены в упражнениях 20 и 18), запишем:
а) ;
б) ;
в) ;
г) .
д) решите самостоятельно. 63-221.gif"> , ; б)
,
,
,
,
,
,
,1.►
Определение. Формулу вида (
при
), где через
обозначены элементарные конъюнкции над множеством X, называют дизъюнктивной нормальной формой (ДНФ) над множеством X. Сумма рангов конъюнкций, входящих в ДНФ, называется сложностью ДНФ.
Например, - ДНФ сложности 6;
- ДНФ сложности 4;
- ДНФ сложности 3 над множеством
.
Заметим, что формулы равносильны и, следовательно, реализуют одну и ту же функцию h. Делаем вывод: функция может быть реализована в виде ДНФ не единственным образом, причем ДНФ, реализующие функцию, могут иметь различную сложность.
Определение. ДНФ, имеющая по сравнению с другими ДНФ, реализующими данную функцию, наименьшую сложность, называется минимальной дизъюнктивной нормальной формой данной функции.
Так, для функции h (см. выше), реализуемой дизъюнктивными нормальными формами ,
,
дизъюнктивная нормальная форма
является минимальной, поскольку h зависит от переменных
существенным образом и, значит, не может быть представлена ДНФ, содержащей менее трех букв.
Поставим задачу: построить для произвольной булевой функции минимальные ДНФ.
Заметим, что у этой задачи существует тривиальное решение. Дадим его пошаговое описание.
1. Строим все ДНФ над множеством . Их
. Действительно, число различных элементарных конъюнкций равно
, так как для каждой переменной
имеется три возможности: присутствовать в конъюнкции, присутствовать с отрицанием и отсутствовать («пустой» конъюнкции сопоставлена константа 1). Каждая из конъюнкций, в свою очередь, может либо входить, либо не входить в ДНФ.
2. Отбираем из построенных ДНФ те, которые реализуют функцию .
3. Для отобранных ДНФ определяем сложности; ДНФ наименьшей сложности и есть искомые минимальные ДНФ функции .