Таблично-аналитический метод минимизации логических функций

Существует несколько методов нахождения импликант и построения минимальной ДНФ. Одним из них является метод попарного сравнения всех конституент, входящих в функцию, так называемый метод Квайна – Мак-Класки.

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

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

Рассмотрим пример. Необходимо минимизировать функцию, заданную в СДНФ:

Расположим все конституенты в столбик по группам и произведем операцию склеивания. Для наглядности каждое склеивание отметим направляющими линиями:

После первого шага склеивания получим все простые импликанты. СкДНФ исходной функции имеет вид:

Чтобы найти минимальную ДНФ функции, необходимо определить все ее тупиковые ДНФ, т.е. получить все приведенные системы простых импликант. Для этого строят таблицу покрытий (импликантную таблицу) с числом столбцов, равным числу конституент, входящих в функцию, и числом строк, равным числу простых импликант. Если импликанта покрывает данную конституенту, т.е. является ее частью, то в соответствующей клетке таблицы ставится метка «+». Для нахождения всех возможных покрытий каждой импликанте приписывается буквенное обозначение A, B, C, … и для каждой конституенты записывается дизъюнкция (ИЛИ) символов тех импликант, которые ее покрывают.

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

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

	Таблица 3.2
	Простые импликанты	Конституенты	Обозначение импликант
		+	+					A
		+			+			B
			+	+				C
					+	+		D
				+			+	E
						+	+	F

Построим таблицу покрытий для нашего примера (Таблица 3.2).

Составляем конъюнктивное представление таблицы:

Получим пять приведенных систем простых импликант, т.е. пять тупиковых ДНФ, среди которых есть и минимальные:

и

Совершенно очевидно, что из всех тупиковых форм минимальными ДНФ исходной функции являются

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

Пример 3.6 Найти минимальную ДНФ функции

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

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

	0001*
			0 – 01*
	0101*		00 – 1*		0 – – 1
	0011*		– 001*		– 0 – 1
	1001*
			– 011*
	1011*		10 – 1*
	0111*		01 – 1*
			0 – 11*
	1111*				– – 11
			1 – 11*
			– 111*

При склеивании двоичных чисел вместо склеиваемого разряда ставится прочерк (–).

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

В результате получили обозначения трех простых импликант: 0 – – 1, – 0 – 1, – – 11.

	Таблица 3.3
	0 – – 1	+	+	+			+		A
	– 0 – 1	+		+	+	+			B
	– – 11			+		+	+	+	C

Строим таблицу покрытий (импликантную таблицу) – таблица 3.3. Из таблицы получаем:

Видим, что МДНФ данной функции включает в себя все три простые импликанты A, B, C.

Перейдем опять к буквенным обозначениям при выбранной базе:

Таким образом, искомая МДНФ имеет вид:

Заметим, что рассмотренный метод дает точное решение задачи минимизации логической функции – нахождение общей минимальной дизъюнктивной нормальной формы. Он применяется для функций, заданных в СДНФ, причем для полностью определенных функций. Все наборы переменных, входящие в СДНФ, являются рабочими, остальные (до полного перебора 2 ⁿ) считаются запрещенными.

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

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

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

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

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