Минимизация ДНФ методом Квайна

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

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

1) последовательным применением эквивалентных преобразо­ваний логическая функция приводится к ДНФ, то есть к форме, не содержащей знаков отрицания над функциями, более сложными, чем один из аргументов;

2) каждый член ДНФ, представляющий собой конъюнкцию ме­нее n членов (n – количество аргументов функции), развер­тывается в дизъюнкцию нескольких элементарных конъюнкций умножением на выражение вида (х₁ Ú`х<sub>1</sub>) • (х<sub>2</sub> Ú`х₂)•…, тождественно равное едини­це;

3) приводятся, если возможно, подобные члены.

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

В результате выявляются группы конъюнкций, содержа­щие по (n - 1) члену. С этой группой конъюнкций проводится та же процедура, после которой получим группы конъюнкций, содержа­щие по (n - 2) членов и так далее, пока не останется ни одного члена, допускающего склеивания с каким либо другим членом.

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

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

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

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

Эту задачу можно выполнить в следующей последовательно­сти:

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

2) если после этого в таблице окажутся такие пары столбцов, что всем отмеченным клеткам второго столбца соответствуют в тех же строках отмеченные клетки первого столбца, а возможно, и неко­торые другие отмеченные клетки, то первый столбец вычеркивается. Это возможно потому, что какую бы совокупность простых импликантов, покрывающую элементарную конъюнкцию, которая соот­ветствует второму столбцу мы ни подобрали, этой совокупностью автоматически будет покрываться и конъюнкция, соответствующая первому столбцу;

3) строки, не содержащие после выполнения п.п. 1 и 2 ни од­ной отмеченной клетки, также вычеркиваются. Это возможно потому, что все конъюнкции, которые могут быть покрыты данным про­стым импликантом, уже покрыты другими простыми импликантами, которые должны войти в окончательное выражение для ДНФ;

4) в сокращенной таблице выявляется пара строк, содержащая хотя бы по одной отмеченной клетке в каждом столбце. Простые импликанты, соответствующие этим строкам, добавляются к ДНФ;

5) если оказывается несколько вариантов выполнения п. 4, то все они сравниваются, и выбирается простейший вариант.

Пример. Минимизировать функцию:

f(х₁, х₂, х₃, х₄) = х₁ х₂ х₄ Ú х₂ х₃ х₄ Ú`х<sub>1</sub>`х₂ х₃ Ú`х<sub>1</sub>`х₂`х₄.

В результате развертывания элементар­ных конъюнкций получим:

Таблица 2.7. Импликантная таблица

	х1х2 х3 х4	х1х2`х3 х4	`х1 х2 х3 х4	`х1`х2 х3 х4	`х1`х2 х3`х4	`х1`х2`х3`х4
х1 х2 х4	Х	Х
х2 х3 х4	Х		Х
`х1 х3 х4			Х	Х
`х1`х2 х3				Х	Х
`х1`х2`х4					Х	Х

 

Вычеркивая строки и столбцы, соответствующие обязательным импликантам х₁ х₂ х₄ и `х<sub>1</sub>`х₂`х₄, получим упрощенную импликантную таблицу (табл. 2.8).

Таблица 2.8. Упрощенная импликантная таблица

	`х1 х2 х3 х4	`х1`х2 х3 х4
х2 х3 х4	X
`х1 х3 х4	X	X
`х1`х2 х3		X

Из упрощенной таблицы видно, что простой импликант `х₁х₃ х₄ покрывает обе оставшиеся конъюнкции. Теперь можно окончатель­но записать минимальную ДНФ для функции f(х₁, х₂, х₃, х₄):

f(х₁, х₂, х₃, х₄) = х₁ х₂ х₄ Ú`х<sub>1</sub>`х₂`х<sub>4</sub> Ú `х₁ х₃ х₄.

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