1.4. Минимизация логических функций

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

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

Метод Квайна

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

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

Пусть задана функция (таблица 1.12).

Таблица 1.12

X1 X2 X3	0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1
Y	0 1 0 0 0 1 1 1

Запишем ее СДНФ:

.

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

1 и 2: + = ;

2 и 4: + = ;

3 и 4: + = .

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

+ + + .

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

Y = + + .

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

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

Таблица 1.13

Простые импликанты	Члены СДНФ
	*	*
		*		*
			*	*

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

Окончательная минимальная форма (МДНФ) имеет вид:

Y = + .

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