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

Нахождение тупиковых форм

Обозначения:

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

Цветом выделены компактные группы наибольшей размерности, вошедшие в ядро.
Ядро: v v
МДНФ: v v , цена=7

Минимизация булевых функций методом Карно

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

Пусть задана функция 3-х переменных

Заданную функцию представим с помощью карты Карно:

Затем производится объединение 2-х, 4-х или 8-ми единиц. В данном случае объединение двух единиц по горизонтали соответствует операции склеивания над конституантами и , в результате которой исключается переменная B и получена импликанта .Объединение двух единиц по вертикали соответствует операции склеивания над конституантами и , в результате которой исключена переменная С и будет получена импликанта . Следовательно, минимальная форма заданной функции примет следующий вид:

Ниже приведены ряд примеров, поясняющие процесс минимизации функции 3-х переменных методом Карно.

В последнем примере показано, что может быть получено несколько минимальных форм. Если объединить единицы так, как показано сплошной линией, то получим форму . При объединении единиц способом, показанным пунктирной линией, получим другую минимальную форму

Рассмотрим минимизацию функции 4-х переменных. Пусть задана функция


.

Представим в виде карты Карно.

В данном случае возможно объединение 4-х единиц, в результате получим минимальную форму

Ниже приведены примеры минимизации функции 4-х переменных.

Методом Карно возможна минимизация функций 5 переменных. Карта в этом случае имеет 32 поля. Рассмотрим минимизацию следующей функции 5 переменных , которая задана в виде карты Карно.

В результате минимизации, получим следующую форму:

Таким образом, при объединении 2-х полей исключается одна переменная, при объединении 4-х полей – две переменные, при объединении 8-ми полей – три переменные.

Метод Карно целесообразно применять для функций, имеющих не более 5 переменных. При большом количестве переменных используют формальные методы Квайна или Квайна-Мак-Класки.