Построение ДНФ по карте Карно

Для построения ДНФ функции, представленной в виде карты Карно, рассматривают ячейки с единицами. Соседние ячейки с единицами, образующие прямоугольник размером 2 ^a ´2 ^b, объединяют, формируя группы так, чтобы каждая единица вошла хотя бы в одну группу. Затем для каждой выбранной таким образом группы записывают элементарную конъюнкцию и строят ДНФ из выписанных конъюнкций. Важнейшим условием в этой процедуре является то, чтобы группами были охвачены (покрыты) все единицы.

Пример:

Таблица 31

			z w
y
x

Рассмотрим функцию четырех переменных, заданную картой Карно (см. табл. 31). Объединим ячейки с единицами, выделив 4 группы, как показано в таблице 31. Запишем для каждой выделенной группы соответствующую элементарную конъюнкцию: группа из 4‑х угловых ячеек – , группа из 4‑х ячеек во втором столбце таблицы – , группа из 2‑х ячеек в четвертом столбце таблицы – и ячейка на пересечении третьей строки и третьего столбца таблицы – xyzw. Теперь ДНФ по выбранным группам: . Заметим, что сложность полученной ДНФ равна 11.

Очевидно, что процесс выделения групп с единицами не является однозначным. И можно выделить группы так, чтобы соответствующая ДНФ содержала меньше букв. Выполним для той же функции разбиение единиц на группы другим способом, как показано в таблице 32. Тогда соответствующая этому разбиению ДНФ равна . Сложность этой ДНФ – 9.

Таблица 32

			z w
y
x

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

Алгоритм построения МДНФ по картам Карно.

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

Далее выбирается другая ячейка с теми же свойствами и ещё не вошедшая в ранее сформированные группы, для этой ячейки формируется её наибольшая группа.

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

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

Пример:

Пусть задана функция f (x, y, z, w)=(1,1,1,0,0,0,0,0,1,1,1,0,0,0,1,0). Значения функции перечислены в порядке естественного увеличения наборов значений переменных, рассматриваемых как четырехразрядные двоичные числа.

Таблица 33

			z w
y
x

В таблице 33 представлена карта Карно для данной функции. Пустые ячейки соответствуют значениям, равным нулю.

Выберем верхнюю правую ячейку, её группа состоит из четырех угловых ячеек, и соответствующая конъюнкция является простой импликантой.

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

Таким образом, минимальная ДНФ здесь совпадает с сокращенной и равна .

Таблица 34

			z w
		00
y
x

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

Вторая ячейка в верхней строке таблицы может быть скомпонована двумя способами: 1) с ячейкой ниже неё во второй строке и 2) с ячейкой в четвертой строке того же столбца. Обе группы имеют одинаковый размер и являются максимальными для рассматриваемой ячейки. Соответствующие им простые импликанты равны .

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

Вторая ячейка второй строки может входить в две максимальные группы, одна из которых уже была рассмотрена – это группа с ячейкой, находящейся выше неё, и вторая – это группа с ячейкой слева в той же строке. Её простая импликанта равна .

Крайняя правая ячейка второй строки, а также ячейка под ней и крайняя левая ячейка третьей строки могут войти только в одну максимальную группу, которой соответствует простая импликанта .

Для ячейки, находящейся на пересечении третьей строки и третьего столбца таблицы, можно сформировать две максимальные группы: 1) с ячейкой справа в той же строке и импликантой xyz и 2) с ячейкой ниже неё и импликантой xzw.

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

Теперь сокращенная ДНФ есть дизъюнкция всех выделенных простых импликант: .

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

Один из возможных вариантов приведен в таблице 34. Соответствующая ему МНДФ₁ =. Другие варианты приведены ниже.

Таблица 35 Таблица 36

			z w
		00
y
x

			z w
		00
y
x

			z w
		00
y
x

Таблица 37

Для покрытия, указанного в таблице 35,

МДНФ₂ =.

Выбранному покрытию в таблице 36 соответствует МДНФ₃ =.

И, наконец, выбранное в таблице 37 покрытие записывается в виде МДНФ₄ =.

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