«Минимизация с помощью минимизирующих карт»

Графический метод минимизации – Карты Карно

Карты Карно – это графическое представление операций попарного неполного склеивания и элементарного поглощения.

Карты Карно рассматриваются как перестроенная соответствующим образом таблица истинности функции.
Карты Карно – определенная плоская развертка n-мерного булева куба.
Строится таблица истинности функции определенным образом. Каждая клетка таблицы соответствует вполне определенной вершине булева куба. Нулевые значения не записываются.
Карта Карно для функции 4-х переменных:

Карта Карно рассматривается как поверхность фигуры под названием тор ("бублик").

p-клетки – клетки карты Карно, соответствующие единичному значению функции.
Соседние наборы – наборы, которые различаются только одним аргументом (одной орбитой).
Любой паре соседних наборов в Карте Карно соответствуют соседние клетки.
Две соседние p-клетки на карте Карно дают импликанту первого ранга. Например, клетки 1100 и 1101 отличаются только значением переменной x₃, следовательно, они дают импликанту 1 2 4.
Две соседние импликанты первого ранга образуют импликанту второго ранга.

На этой карте соседние клетки образуют импликанты a, b, c, d, e. При этом импликанты a и b являются соседними, поэтому они образуют импликанту второго ранга.
Если функция имеет 5 переменных, то рисуются 2 Карты Карно: для x₅=0 и для x₅=1. Если 6 переменных – 4 Карты, так чтобы в соседних картах соседние клетки имели одинаковые координаты:

Соседние p-клетки, соответствующие импликанте образуют компактную группу.

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

	00	01	11	10
00
01
11
10

Компактных групп размера 4 – 2

Компактных групп размера 2 – 2