Поставим задачу: построить для произвольной булевой функции минимальные ДНФ. 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), запишем:

а) ;

б) ;

в) ;

г) .

д) решите самостоятельно. ►

§ 2.3. Минимизация булевых функций в классе ДНФ

Пусть задан алфавит переменных .

Определение. Формулу вида ( при , ) называют элементарной конъюнкцией ранга r над множеством X. Константа 1 рассматривается как элементарная конъюнкция ранга 0.

Например, формула - элементарная конъюнкция ранга 3 над множеством ; в то время как формула элементарной конъюнкцией не является.

Упражнение 2.22. а)Перечислите все элементарные конъюнкции ранга 3 над множеством , обращающиеся в единицу на наборе .

б)Перечислите все элементарные конъюнкции над множеством , обращающиеся в единицу на наборе .

◄ а) , , , ; б) , , , , , , ,1.►

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

Например, - ДНФ сложности 6; - ДНФ сложности 4; - ДНФ сложности 3 над множеством .

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

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

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

Поставим задачу: построить для произвольной булевой функции минимальные ДНФ.

Заметим, что у этой задачи существует тривиальное решение. Дадим его пошаговое описание.

1. Строим все ДНФ над множеством . Их . Действительно, число различных элементарных конъюнкций равно , так как для каждой переменной имеется три возможности: присутствовать в конъюнкции, присутствовать с отрицанием и отсутствовать («пустой» конъюнкции сопоставлена константа 1). Каждая из конъюнкций, в свою очередь, может либо входить, либо не входить в ДНФ.

2. Отбираем из построенных ДНФ те, которые реализуют функцию .

3. Для отобранных ДНФ определяем сложности; ДНФ наименьшей сложности и есть искомые минимальные ДНФ функции .