Этап. Нахождение существенных импликант. 1 страница

Если в каком-либо столбце составленной таблицы меток имеется только одна метка, то первичная импликанта, стоящая в соответствующей строке, является существенной. Она не может быть исключена из минимальной формы функции, т.к. без нее не может быть получено покрытие всего множества импликант данной функции. Из таблицы меток исключаются строки и столбцы, на пересечении которых стоит эта единственная метка.

В таблице меток (см. пример 6) столбцами с единственной меткой являются столбцы (2), (7). Соответствующая импликанта является существенной. Метку обводят кружочком, существенные импликанты – рамочкой, а столбцы с единственной меткой вычеркивают из таблицы. По закону поглощения меньшее количество меток в столбце может исключить большее. Так (2) и (7) столбцы входят соответственно в (3) и в (8), поэтому исключаем (3) и (8) столбцы из таблицы меток. 3-й этап закончен.

4 этап. Вычеркивание лишних столбцов.

Если в таблице после 3-го этапа два одинаковых столбца (в которых метки стоят в одинаковых строках), то один из них вычеркивается, т.к. покрытие оставшегося столбца будет осуществлять покрытие выброшенной исходной импликанты. В рассматриваемом примере таких столбцов нет.

5 этап. Вычеркивание лишних строк.

Если в таблице после 4-го этапа появились строки, в которых нет ни одной метки, то их вычеркивают, т.е. первичные импликанты, соответствующие им, исключаются из минимальной формы функции, т.к. они не покрывают оставшихся исходных импликант. В рассмотренном примере таких строк нет.

6 этап. Выбор минимального покрытия.

	(1)	(4)	(5)	(6)
	v	v
	v			v
		v
			v	v
			v

Исследуем таблицу, полученную после всех предыдущих этапов (см. 3-й этап). Выбирается такая совокупность первичных импликант, которая бы имела метки во всех столбцах. Предпочтение отдается варианту покрытия с минимальным числом букв в первичных импликантах, образующих покрытие. В данном примере все оставшиеся первичные импликанты содержат одинаковое число букв. Выберем покрытие из импликант и , т.к. они покрывают все 4 оставшиеся исходные импликанты. Они и будут существенными импликантами.

Итак, из оставшихся существенных импликант записываем тупиковую форму данной функции.

Она должна быть неизбыточной. В данном примере – это и есть минимальная форма функции.

Замечание 1. В методе Квайна есть одно существенное неудобство – необходимость полного попарного сравнения на этапе нахождения первичных импликант. С ростом числа аргументов функции и определяющих ее членов СДНФ растет число этих сравнений. Этот рост характеризуется факториальной функцией. Поэтому применение метода Квайна становится затруднительным.

Замечание 2. По методу Квайна получаются тупиковые формы. Их может быть несколько. Среди них и надо искать минимальные формы. Все возможные тупиковые формы можно найти по методу Петрика.

Метод Петрика нахождения всех возможных тупиковых форм.

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

где - простые импликанты, соответствующие меткам -го столбца, - количество меток в -м столбце, - количество столбцов в таблице меток. Формула дает полную совершенную дизъюнктивную нормальную форму функции, т.е. .

Если в формуле встретятся члены и , то член можно не писать, ибо (вот почему на 3 этапе метода Квайна выброшены большие столбцы).

Выражение необходимо упростить (раскрыть скобки с учетом закона поглощения и применить законы алгебры логики). Получим дизъюнкцию членов, каждый из которых дает множество простых импликант, входящих в тупиковую форму.

Тупиковые формы с наименьшим числом букв и есть минимальные формы, тупиковые формы с наименьшим числом членов есть кратчайшие формы. Чаще всего минимальная форма не совпадает с кратчайшей.

Рассмотрим на примере 5 этот метод (см. таблицу этапа 2 в методе Квайна). Начертим ее здесь, обозначив первичные импликанты латинскими буквами a, b, c, d, e, f, а столбцы цифрами (1), (2), … , (8).

	x1 x2 x3 x4	x1 x2 x3 x4	x1 x2 x3 x4	x1x2 x3 x4	x1 x2 x3 x4	x1 x2 x3 x4	x1 x2 x3 x4	x1 x2 x3 x4
	(1)	(2)	(3)	(4)	(5)	(6)	(7)	(8)
x1 x3 x4	a	v			v
x2 x3 x4	b	v					v
x1 x2 x4	c			v	v
x1 x2 x4	d					v	v
x1 x3 x4	e					v			v
x1 x3	f		v	v				v	v

Составим функцию :

Дизъюнкция включается для реализации меток 1-го столбца и т.д. По закону поглощения , поэтому члены 3 и 8 столбцов можно не записывать. Упростим .

Раскроем скобки

Каждый из членов дает тупиковую форму данной функции. Составим таблицу всех тупиковых форм.

№	Тупиковые формы	Общее число букв в тупиковой форме	Число членов в тупиковой форме
1.		3+3+2=8
2.		3+3+3+2=11
3.		3+3+3+2=11
4.		3+3+3+2=11

Из таблицы следует, что 1-е решение есть минимальная форма (сравните результат), оно же дает кратчайшую форму. Отметим еще раз, что кратчайшая и минимальные формы могут не совпадать.

Итак, есть минимальная форма данной функции.

Замечание 3. Таблица покрытий может не содержать существенных импликаций. Поясним, как в этом случае поступить. Пусть таблица меток имеет вид: (см. ниже).

Исключим 2 и 7 столбцы, т.к. 3 и 5 являются их частями, а из оставшихся столбцов выбираем столбец с наименьшим числом меток. Здесь во всех столбцах их по 2, поэтому возьмем 1-й столбец. Примем за псевдосущественную импликанту , а затем .

a	v	v	v				v
b		v	v	v		v
c		v		v	v		v
d	v				v	v	v

Рассмотрим 2 частных случая:

1)

3

2)

4

a

v

v

a

v

v

a

v

v

b

v

v

v

b

v

v

v

b

v

v

v

c

v

v

c

v

v

c

v

v

d

v

v

v

d

v

v

v

d

v

v

v

Исключим большие столбцы, содержащие в себе выбранные псевдостолбцы. Запишем множество тупиковых форм для каждой таблицы. Это можно сделать по методу Петрика, но здесь можно перебрать все возможные варианты по таблице

1)		(1)	2)		(4)
		(2)			(5)
		(3)

Рассмотрим совместно множества решений. Решение (2) входит в (5), (3) совпадает с (4), а (1) нет соответствующего во 2-й таблице, наиболее простая тупиковая форма (5). Таким образом, разбиение на подтаблицы упрощает отыскание тупиковых форм.

5 Метод Квайна-Мак-Класки

Этот метод является модернизацией метода Квайна (его 1-го этапа). Мак-Класки предложил записывать исходные импликанты данной функции, заданной в СДНФ, в виде их двоичных кодов (каждому члену ставится в соответствие по известному правилу его собственная вершина). Все множество так записанных импликант разбивается по числу единиц в их кодах на группы. При этом в -ю группу войдут коды, имеющие в своей записи единиц. Попарное сравнение импликант достаточно производить только между соседними группами, т.к. только эти группы отличаются одним знаком в кодах входящих в них членов. Сравнивая коды членов соседних групп, образуют члены низшего ранга. На месте исключенного знака пишут в них “тире”. Затем всю совокупность членов низшего ранга снова разбивают на группы по местоположению знака “тире”.Снова сравнивают члены соседних групп, но уже внутри групп, образуя члены низшего ранга по тому же правилу и т.д.

Далее все производится по методу Квайна, но в кодовых значениях импликант. Рассмотрим это на примере 6.

Заменим исходные импликанты их кодами в двоичных переменных: 0011, 0100, 0101, 0111, 1001, 1011, 1100, 1101.

Разобьем коды исходных импликант на группы, поместим их в таблицу. Далее применим закон склеивания к членам соседних групп, перебирая каждый член 1-й группы со всеми членами 2-й группы и т.д.

Можно все это сразу делать в таблице.

Данная функция	Результаты 1-го склеивания	Результаты 2-го склеивания
Коды	группы	Коды	группы	Коды	группы
	0-я	-	0-11	1-я	-011	-10-
	1-я	0100 *	-011		-100 *	-10-
	2-я	0011 *	010-		-101 *
		0101 *		2-я	0-11
		1001 *	01-1		1-01
		1100 *	-101	3-я	01-1
	3-я	0111 *	10-1		10-1
		1011 *	1-01	4-я	010- *
		1101 *	110-		110- *

Далее строится таблица меток, но в нее вписываются исходные и первичные импликанты в виде двоичных кодов. Обратите внимание, что первичные импликанты записаны в другом порядке (согласно их группам), поэтому таблица меток выглядит иначе, чем в примере 6.

-011		v					v
0-11		v				v
1-01				v				v
01-1			v			v
10-1				v			v
-10-	v		v		v			v

Обработка таблицы меток производится по методу Квайна.

Окончательно помещаем минимальную форму данной функции

6 Метод карт карно (вейча).

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

Карта Карно представляет собою специальную таблицу функции.

Рассмотрим карту для функции 2-х переменных.

							x1 x2
		1	x1=0
		1	x1=1

Можно упростить карту, если для аргументов ввести символические обозначения черточкой, поставив ее там, где они равны единице.

В карту вносятся значения функции, соответствующие наборам переменных.

Расположение клеток таблицы легко позволяет определить склеивающиеся члены. Соседние клетки соответствуют членам, отличающимся одним знаком, и их можно склеивать, если значение функции в них равно единице.

Записав члены СДНФ функции в соответствующих клетках, можно легко это увидеть. Например, в приведенной выше карте

Члены столбца склеиваются той переменной, которой соответствует весь столбец, а строки – вся строка.