7. Алгоритм Куайна

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

1) На каждом шаге 1-го этапа для очередного максимального интервала (простой импликанты) строится окрестность 1-го порядка: S₁(N_Кi)={N_Кi, N_Кi1, N_Кi2,…,N_Кim}, где N_Кi1, N_Кi2,…,N_Кim – это максимальные интервалы функции f, имеющие непустое пересечение с интервалом N_Кi.

Затем проверяется включение N_Кi  N_Кi1  N_Кi2  … N_Кim.

Если это включение не имеет места, то конъюнкция K_i отмечается некоторым способом, как входящая во все МДНФ или как ядровая конъюнкция, а интервал N_Кi – как ядровой интервал. Объединение всех ядровых интервалов называется ядром сокращенного покрытия.

2) Пусть на первом этапе множество максимальных интервалов функции f разбилось на два подмножества: Я={Я₁,Я₂,…,Я_р} – все ядровые интервалы и В={В₁,В₂,…,В_q} – все остальные интервалы (или что то же самое – конъюнкции).

Для каждого интервала из множества В проверяется включение в ядро, т.е. В_iЯ₁  Я₂  …  Я_р. Об интервалах, для которых это включение выполняется, говорят, что они покрываются ядром. Соответствующие им простые импликанты не входят ни в одну МДНФ, они удаляются из СокрДНФ.

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

Пример.

Пусть функция задана в виде СокрДНФ:  = К₁ К₂ К₃

Или, что то же самое, в виде сокращенного покрытия:

N_f = {(0,0,0),(0,0,1)}  {(0,0,0),(1,0,0)}  {(1,0,0),(1,1,0)}= N₁  N₂  N₃, где N₁, N₂, N₃ – максимальные интервалы для f.

На первом этапе строим окрестности 1-го порядка для каждого максимального интервала

S₁(N₁)={N₁, N₂} и т.к. N₁N₂ N₁ – ядровой интервал;

S₁(N₂)={N₂, N₁, N₃} и т.к. N₂  N₁  N₃ N₂ – не ядровой интервал;

S₁(N₃)={N₃, N₂} и т.к. N₃N₂ N₃ – ядровой интервал;

На втором этапе имеем множество ядровых интервалов: Я={N₁, N₃} и один не ядровой интервал N₂ и, т.к. N₂  N₁  N₃, – покрывается ядром, то конъюнкцию, соответствующую интервалу N₂, можно удалить. В результате ДНФ Куайна имеет вид: f(x, y, z) =

В данном случае ДНФ Куайна совпадает с МДНФ функции f.

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

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

Пример:

Пусть функция задана в виде СДНФ: .

Построим её СокрДНФ:

						xyz
	1			1
yz			1			1
				1	1
xy					1	1
		Таблица 25

Таблица Куайна этой функции представлена в табл. 25. Ввиду наличия единственной единицы в столбцах 1 и 2, конъюнкции и yz являются ядровыми. Таким образом единицы ядра находятся в столбцах: 1, 2, 3 и 5 (в таблице 25 эти ячейки слегка затемнены). Ни одна из единиц 4–го столбца не покрывается ядром. Тем самым, обе остальные конъюнкции входят в ДНФ Куайна, которая в данном случае совпадает с Сокращенной ДНФ. Для построения МДНФ достаточно иметь одну единицу в 4–ом столбце, это равносильно удалению из СокрДНФ любой из конъюнкций: или xy. При этом получаются две минимальные ДНФ: и .