Построение днф по карте Карно

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

Пример:

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

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

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

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

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

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

Пример:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

МДНФ₂ =.

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

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