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

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

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

Затем проверяется включение N_Кi Í N_{Кi 1} È N_{Кi 2} È …È 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.

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

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

Пример:

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

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

Таблица 25

					xyz
yz
xy

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

Дата добавления: 2014-01-07