Принципы минимизации

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

Аналогично для КНФ:

Возможность поглощения следует из очевидных равенств

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

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

Если требуется получить карту Карно для какой – либо функции, сначала надо записать эту функцию в СДНФ, – в совершенной дизъюнктивно нормальной форме, или в виде таблицы истинности.

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

Taблица истинности для четырех переменных включает 16 строк, следовательно карта Карно должна состоять из 16 клеток, как показано на рис.1.

Рис.1. Форма карты Карно для 4 – х переменных.

У карты Карно для четырех переменных клетки крайнего левого столбца должны рассматриваться как соседние для клеток крайнего правого столбца, а клетки верхней строки, – как соседние для клеток нижней строки. Другими словами можно сказать, что эта карта расположена на поверхности цилиндра (склеили правый край карты с левым), изогнутого и растянутого так, что его верхний срез соединяется с нижним срезом; при этом цилиндр превращается в тор (бублик).

Для построения минимальной ДНФ производится процедура склеивания "1". Склеивающимся значениям "1" соответствуют соседние клетки, т.е. клетки отличающиеся лишь значением одной переменной (на графическом изображении разделенных вертикальной или горизонтальной линией с учетом соседства противоположных крайних клеток).
Процесс склеивания "1" сводится к объединению в группы единичных клеток карты Карно, при этом необходимо выполнять следующие правила;
1. Количество клеток, входящих в одну группу, должно выражаться числом кратным 2, т.е. 2^m где m=0,1,2,...
2. Каждая клетка, входящая в группу из 2^m клеток, должна иметь m соседних в группе.
3. Каждая клетка должна входить хотя бы в одну группу.
4. В каждую группу должно входить максимальное число клеток, т.е. ни одна группа не должна содержаться в другой группе.
5. Число групп должно быть минимальным.
Считывание функции f по группе склеивания производится следующим образом: переменные, которые сохраняют одинаковые значения в клетках группы склеивания, входят в конъюнкцию, причем значениям 1 соответствуют сами переменные, а значениям 0 их отрицания.

Примеры упрощения булевых выражений с помощью карты Карно:

Рис.2. Пример минимизации булевой функции F1 с помощью карты Карно для 4 – х переменных.

В первом примере минимизации булевой функции F1 нижний контур из двух единиц 1₅ и 1₆ , соответствующие пятому и шестому слагаемым в исходном булевом выражении, дает возможность опустить B и`B. После этого в нем остается произведение `A C`D. В верхнем контуре из четырех единиц 1<sub>1</sub>, 1<sub>2</sub>, 1<sub>3</sub> и 1<sub>4</sub>, соответствующие первым четырем слагаемым в исходном булевом выражении попарно опускаются A и`A, D и`D, так что в результате этого верхний контур дает произведение B C.

Рис.3. Пример минимизации булевой функции F2 с помощью карты Карно для 4 – ах переменных.

Во втором примере минимизации булевой функции F2 контур из двух единиц 1₂ и 1₃ , соответствующие второму и третьему слагаемым в исходном булевом выражении, дает возможность опустить А и`А. После этого в нем остается произведение B`C`D. В контуре из четырех единиц 1<sub>1</sub>, 1<sub>2</sub>, 1<sub>4</sub> и 1<sub>5</sub>, соответствующие другим четырем слагаемым из исходного булева выражения, попарно опускаются В и`В, С и`С, так что в результате этого верхний контур дает произведение `A`D.

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

Дата добавления: 2015-07-08