3. Минимизация функции пяти переменных на картах Карно

Матричная (двумерная) форма наиболее удобна при работе на листе бумаги. Для сопоставления 2ⁿ наборов элементам матрицы множество переменных разбивается на два подмножества младших и старших переменных:

,

где – наименьшее целое, большее или равное .

Наборы значений множества младших переменных сопоставляются строкам матрицы, наборы старших – столбцам (или наоборот).

Данное сопоставление можно провести упорядочиванием множества наборов.

Широко распространены два варианта упорядочивания: использования последовательного двоичного кода и использование кода Грея.

Принцип построения кода Грея:

1. Последовательность начинается с нулевого набора (0…0)

2. При переходе от очередного набора к следующему изменяется значение только одной переменной – той младшей переменной, которая приводит к получению нового кода по отношению ко всем ранее построенным.

Построенная в результате таблица – карта Карно.

Этапы заполнения карты Карно в классе ДНФ.

1. Все наборы, присутствующие в функции заносятся в карту с помощью единиц в соответствующие клетки.

2. Выделяют интервалы на карте по следующим правилам:

1. в один интервал объединяют только соседние единицы по вертикали или горизонтали;

2. в один интервал можно объединить 2^k единиц, где k=0,1,2,3,4,….;

3. карта циклически замкнута по вертикали и горизонтали;

4. в выделенный интервал должно быть объединено максимально возможное количество единиц.

Таким образом, процесс минимизации сводится к нахождению наиболее крупных групп из 2^k (k=0,1,2,3,4,….) соседних единичных клеток. Причем каждая из единичных клеток должна входить в некоторую группу (блок, контур), а общее количество таких максимальных групп должно быть минимально. Простой импликант соответствующий максимальному блоку будет содержать в себе символы тех переменных, значения истинности которых совпадают у всех объединенных клеток.

Пример: Минимизировать функцию трех переменных методом карты Карно в классе ДНФ.

x1	x2	x3
0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	1

Строим карту Карно для трех переменных и отмечаем единицей наборы, заданные функцией.

Затем выделяем максимальные интервалы

		00	01	11	10
	0	1	1	0	1
	1	1	0	1	1

.

При правильном объединении функцию больше минимизировать невозможно.

Карта Карно для n=5:

		000	001	011		010	110		111	101	100
	00
	01
	11
	10

Особенности заполнения карты Карно в классе КНФ.

1. Все наборы, отсутствующие в функции (=0) заносятся в карту с помощью нулей в соответствующие клетки.

2. Выделяют интервалы на карте по таким же правилам, как и в классе ДНФ (только 0).

3. Результат записывается в следующем виде:

   • выписываются дизъюнкции, соответствующие выделенным интервалам: если входит как 0, он вписывается без изменений в дизъюнкцию, если входит как 1, то в дизъюнкцию вписывается его отрицание;

   • все полученные дизъюнкции соединяются между собой знаками конъюнкции