Второй этап (получение минимальной формы).

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

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

рис 3.27

Таблица 3.6

Совершенная ДНФ.данной функции

(3.14)

Для получения сокращенной формы проводим операции склеивания и поглощения

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

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

Таблица 3.7
Простые импликанты	Члены СДНФ
	X	X
X		X
		X	X
			X	X
				X	X

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

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

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

(3.16)

Структурная схема, соответствующая этому выражению, приведена на рис. 3.28.

рис 3.28

Переход от сокращенной формы (3.15) к МДНФ (3.16) был осуществлен путем исключения лишних имплнкант и . Покажем допустимость подобного исключения членов из логического выражения.

Импликанты и обращаются в единицу соответственно при следующих наборах значений аргументов:

x₁ = 0; х₂ = 0; х₃ = 0 и х₂ = 1; х₃ = 1; х₄ = 0 (3.17)

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

при x₁ = 0, x₂ = 0, x₃ = 0

при х₂ = 1; х₃ = 1; х₄ = 0

Таким образом, доказана справедливость операции исключения из выражения (3.15) членов и .

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

исходной для минимизации формой логического выражения заданной функции является СКНФ;

пары склеиваемых членов имеют вид и ;

операция поглощения проводится в соответствии с выражением

Рассмотрим применение метода Квайна на примере минимизации функции, заданной таблицей истинности (табл. 3.8).

Совершенная КНФ рассматриваемой функции

Склеивающиеся пары членов:

первый и третий члены (результат склеивания );

первый и четвертый члены (результат склеивания ):

второй и третий члены (результат склеивания ).

Таблица 3.9
Простые импликанты	Члены СДНФ
	X		X
X			X
	X	X

Проводя операции склеивания и поглощения, получаем

Члены операции склеивания

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

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