Минимизация функций

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

Выражение (1.1) можно упростить, если добавить в него дважды abc (закон тавтологии), сгруппировать попарно слагаемые (сочетательный закон) и исключить (закон склеивания) переменные, которые в группе меняют свои значения.

abcabc= (abc ac)(abc bc)(abcab) =

= ac(b)bc(a)ac(c) = acbcac (1.2)

Рис. 1.7. Схема, реализующая (1.2).а-в булевском базисе; б) в базисе И-НЕ.

В инженерной практике для минимизации наиболее часто применяют карты Карнау (Карно).

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

Таблица истинности (а) и структура карты Карно (б) для функции двух переменных.

x1	x2	f(x1,x2)
		f(0,0)
		f(0,1)
		f(1,0)
		f(1,1)

	x2
x1
	f(0,0)	f(0,1)
	f(1,0)	f(1,1)

б)

	а)

Таблица истинности (а) и структура карты Карно (б) для функции трех переменных.

x1	x2	x3	f(x1,x2,x3)
			f(0,0,0)
			f(0,0,1)
			f(0,1,0)
			f(0,1,1)
			f(1,0,0)
			f(1,0,1)
			f(1,1,0)
			f(1,1,1)

а)

	x2,x3
x1
	f(0,0,0)	f(0,0,1)	f(0,1,1)	f(0,1,0)
	f(1,0,0)	f(1,0,1)	f(1,1,1)	f(1,1,0)

	б)

Структура карты Карно для функции четырех переменных.

	x3,х4
x1,х2
	f(0,0,0,0)	f(0,0,0,1)	f(0,0,1,1)	f(0,0,1,0)
	f(0,1,0,0)	f(0,1,0,1)	f(0,1,1,1)	f(0,1,1,0)
	f(1,1,0,0)	f(1,1,0,1)	f(1,1,1,1)	f(1,1,1,0)
	f(1,0,0,0)	f(1,0,0,1)	f(1,0,1,1)	f(1,0,1,0)

Карта размечается системой координат, соответствующих значениям входных переменных. Например, верхняя строка карты для функции от трех переменных соответствует нулевому значению переменной х1, а нижняя – ее единичному значению. Каждый столбец этой карты характеризуется значениями двух переменных: х2 и х3.

Обратим внимание на то, что координаты строк и столбцов следуют не в естественном порядке возрастания двоичных кодов, а в порядке 00, 01, 11, 10. Это код Грея. Изменение порядка следования наборов сделано для того, чтобы соседние наборы (отличающиеся между собой лишь цифрой одного разряда) были соседними в геометрическом смысле.

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

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

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

Рассмотренные примеры позволяют сформулировать последовательность действий, выполненных для минимизации логических функций с использованием карт Карно:

Изображается таблица для n переменных и производится разметка ее сторон.

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

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

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