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

Рассмотрим некий импликант 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, имеющие вид конъюнкции. Простыми импликантами будут те из них, которые не отмечены знаком +. В рассмотренном нами примере простыми импликантами будут конъюнкции: ,,,,.