Стандартные формулы преобразования булевых функций

1) – правило поглащения;

2) – правило поглащения;

3) – правило склеивания;

4) – правило вычеркивания.

Теорема:

МДНФ функции, отличной от 0 или 1, является дизъюнкция некоторых простых импликантов.

Доказательство:

Рассмотрим МДНФ функции (*). Предположим, что некоторая конъюнкция из этого представления, например, не является простым импликантом. Это означает, что из нее путем вычеркивания какой-то переменной можно образовать импликант. Рассмотрим функциюи покажем, что она совпадает с функциейf. Для этого достаточно показать, чтоиобращаются в 1 на одних и тех же наборах. Рассмотрим произвольный набор. При укорачивании конъюнкции область ее единичных значений не уменьшается, поэтому можно записатьна всех наборах. Следовательно, если, то и. Пусть теперь, это означает, что либо, либообращается в 1 на этом наборе, тогда равенствов первом случае следует из того, чтоимпликант, а во 2-м случае из представления (*). Т.о. мы имеем, что. Но, посколькуимеет на одно вхождение переменных меньше, то это противоречит посылке теоремы о том, что (*) есть МДНФ. Ч.т.д.

Геометрическая интерпретация

Любой двоичный набор можно рассматривать как вершину единичногоn-мерного гиперкуба. Тогда любую функциюможно задать множеством вершин куба, на которых она принимает значение 1. Функцияявляется импликантом для функцииf, если соответствующее ей множество вершин содержится во множестве вершин дляf. Всякая конъюнкциязадает вершины (n-p)-мерного гиперкуба, для которого,,…,, а значение остальных (n-p) компонент могут быть выбраны произвольно. Простой импликант определяет подкуб, все вершины которого принадлежат множеству единичных вершин функций. При этом он не содержится ни в каком большем подкубе, обладающим этим свойством. Такие подкубы называютсямаксимальными.

Всякая ДНФ задает некоторое покрытие множества единичных вершин множества подкубами в соответствии с ее формулами.

ПРИМЕР:

Рассмотрим 3-х мерный случай: ,максимальные подкубы:

, .

Построение простых импликантов

Рассмотрим некий импликант g функции , который является конъюнкцией. Будем считать, что в него входят первые p переменных, т.е. будем считать, что. На всех наборах видапри различныхимпликант=1. Поэтому функция f на этих наборах также обращается в 1. Это означает, что в ее СДНФ имеются всевозможные конъюнкции вида(1) и в частности (1)и (1). Взяв их дизъюнкцию, мы получим. Затем можно аналогично применить склеивание по переменнойи т.д. до, до тех пор, пока не получим конъюнкцию, исходно определяющую g. Т.о. всякий импликант, имеющий вид конъюнкции, можно получить из конъюнкции СДНФ(совершенная дизъюнктивная нормальная форма) последовательным применением операции склеивания. Верно и обратное: всякая конъюнкция, полученная таким образом, является импликантом функции f, поэтому можно сделать вывод, что все импликанты, имеющие вид конъюнкции и только они могут быть образованы в результате последовательного склеивания конъюнкций из СДНФ.

ПРИМЕР:

Пусть в СДНФ функции входят следующие конъюнкции:=– импликант функции f.

Конъюнкции можно задавать наборами длины n и символими 1, 0,–. Если в конъюнкции имеется , то на i-м месте ставится значение, если жеотсутствует, то на этом месте поставим «_». Рассмотренный ранее пример можно записать следующим образом:

1 – 0 –

На основе сказанного строится алгоритм построения всех импликантов, имеющих вид конъюнкции. Изложение алгоритма будет показано на примере функции, заданной таблицей:

0	0	0	0	1
0	0	0	1	1
0	0	1	0	0
0	0	1	1	1
0	1	0	0	1
0	1	0	1	0
0	1	1	0	1
0	1	1	1	0
1	0	0	0	1
1	0	0	1	1
1	0	1	0	0
1	0	1	1	1
1	1	0	0	1
1	1	0	1	1
1	1	1	0	0
1	1	1	1	0

Выпишем все наборы, на которых функция f обращается в 1. Для осуществления алгоритма их удобно выписывать разбитыми на группы в соответствии с количеством 1 в наборах.

0	0000	+		000-	+	-00-	+
1	0001	+		0-00	+	--00	+
2	0100	+		-000	+	-0-1	+
3	1000	+		00-1	+	1-0-	+
4	0011	+		-001	+
5	0110	+		01-0	+
6	1001	+		-100	+
7	1100	+		100-	+
8	1011	+		1-00	+
9	1101	+		-011 10-1 1-01 110-	+
					+
					+
					+

Поскольку склеиваются лишь наборы, отличающиеся в одной компоненте, то, для того, чтобы произвести все склеивания по одной переменной, достаточно рассмотреть все возможные пары наборов, входящих в соседние компоненты. Каждый набор, для которого имеется пара для склеивания, помечается +, а результат склеивания выписывается в новую таблицу. Для новой таблицы повторяем те же действия. Поскольку возможных выборов пар для склейки может быть много, то в новую таблицу выписываем все возможные результаты склеивания. Работа алгоритма прекращается тогда, когда в очередной таблице не будет найдено ни одной пары строк для склеивания. Во всех сформированных таблицах содержатся импликанты исходных функций f, имеющие вид конъюнкции. Простыми импликантами будут те из них, которые не отмечены знаком +. В рассмотренном нами примере простыми импликантами будут конъюнкции: ,,,,.