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

Минимизация булевых функций на основе построения тупиковых ДНФ

Сокращенная, тупиковая и минимальная ДНФ находятся в следующем соотношении.

Тупиковая ДНФ получается из сокращенной путем удаления некоторых членов.

Минимальная ДНФ является тупиковой.

Среди тупиковых ДНФ найдется минимальная.

Отсюда процесс построения минимальных ДНФ, если исходить из совершенной ДНФ можно представить следующей схемой (рис. 1).

Рис. 1. Процесс построения минимальных ДНФ

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

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

При использовании этого метода производится покрытие функций алгебры логики (ФАЛ) с помощью правильных конфигураций, содержащих нули или единицы. Правильными конфигурациями на карте Карно для ФАЛ от переменных являются все прямоугольники (горизонтальные, вертикальные, квадраты), имеющие площадь . При этом стремятся, чтобы число покрытий ФАЛ на карте было минимально, а площадь, покрываемая каждой конфигурацией – максимальна. Конфигурации могут перекрываться. Принцип минимизации заключается в объединении соседних полей карты в пределах правильной конфигурации.

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

Например, функция от четырех переменных компактно записывается в форме матрицы размера [ ], как это показано на рис. 2.

Каждой функции сопоставляется подмножество клеток, в которых эта функция равна единице. При этом элементарным конъюнкциям соответствуют некоторые правильно расположенные конфигурации клеток. Для функции переменных конъюнкции ранга соответствует клеток.

Рис. 2. Карта Карно

Для функции от четырех переменных имеем.

1) Конъюнкции ранга 4 соответствует одна клетка:

2) Конъюнкции ранга 3 соответствует пара соседних клеток:

3) Конъюнкции ранга 2 соответствуют 4 клетки, образующие горизонтальный или вертикальный ряд, либо подматрицу размера [ ]:

4) Конъюнкции ранга 1 соответствуют 8 клеток из двух соседних горизонтальных или вертикальных рядов:

Пример 1. Для функции (см. рис. 1) разобьем множество единичных клеток на следующие подмножества:

Объединение этих подмножеств дает все единичные клетки функции . Поэтому

.