Метод мак-класки

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

Пример 2-4. Найти минимальную нормальную форму функции,

принимающей значение нуль на наборах с номерами 0, 2, 4, 6, 8, 10, 12, 13, 14.

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

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

По неотмеченным наборам строится сокращенная нормальная форма, учитывая что нулю в наборе соответствует x_i, а единице – .

Как и в предыдущем примере, единственная переменная вырожденного минитерма инвертируется: .

группа	Ранг
	0000*	00-0*	0- -0*	---0
	0010*	0-00*	-0-0*
	0100*	-000*	--00*
	1000*	0-10*	--10*
	0110*	-010*	-1-0*
	1010*	01-0*	1- -0*
	1100*	-100*
	1101*	10-0*
1110*	1-00*
		-110*
		1-10*
		110-
		11-0*

В данном случае сокращенная нормальная форма совпадает с минимальной: .

Если бы этого не было, то пришлось бы строить таблицу инверсант и производить расстановку меток обычным способом.

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

Поясним сказанное на примере 2-5.

Пример 2-5. Найти минимальную нормальную форму в моно-функциональном базисе для функции из примера 2-4 по второму из подходов к минимизации ФАЛ:

1-й шаг – сначала найти МДНФ исходной ФАЛ в базисе {-, &, };

2-й шаг – перевести полученную МДНФ в заданный моно-функциональный базис.