Минимизация с использованием карт Карно

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

х₂

x₁

	1

х₃

Рис. 5.10. Области карты Карно

На рис. 5.10 заштрихованная область со штрихом с наклоном влево соответствует истинным значениям х₁, где отсутствует данная штриховка значения х₁-ложные; заштрихованная область со штрихом с наклоном вправо соответствует истинным значениям х₂, в остальных ячейках карты значения х₂- ложные. Изображенная на рисунке единица соответствует вершине гиперкуба .

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

1. Число ячеек карты соответствует всем возможным комбинациям входных аргументов булевой функции, т.е. равно 2^k, где - число аргументов.

2. Каждая переменная делит карту на две равные непрерывные области: область истинных значений и область ложных значений. Для разных переменных области не должны совпадать. При этом считается, что края карты склеены, т.е., например, первая и последняя ячейки строки являются соседними.

При минимизации функции с помощью карт Карно поступают следующим образом.

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

2. Отыскивают группы смежных единиц с числом единиц в группе 2, 4, 8, …, 2m, где m=1, 2, 3,… . Две смежные единицы образуют 1-куб, четыре смежные единицы – 2-куб, восемь смежных единиц 3-куб и т.д. Одна, одиночная единица соответствует 0-кубу.

3. Отдавая предпочтение группам с небольшим количеством единиц, пытаются покрыть все единицы минимальным количеством групп. Группы могут пересекаться. Следует учитывать, что края карты считаются склеенными. По найденному покрытию записывается минимальная форма как дизъюнкция -кубов, соответствующих выделенным группам смежных единиц.

Пример 5.20.

Функция трех переменных задана в СДНФ и представлена на карте Карно (рис. 5.11).

х₂

x₁

х₃

	1	1 -1
1 3	2 1		3 1

Рис. 5.11. Определение групп смежных единиц

В данном случае можно выделить три группы по две смежные единицы, которые покрывают все вершины гиперкуба. 1-я группа соответствует истинным значениям переменных х₁ и х₃ (переменная х₂ в одной единице группы истинна, в другой – ложна), следовательно, соответствует терму минимальной формы х₁ х₃, аналогично 2-я группа соответствует х₂ х₃ и 3-я группа (3-я группа построена с учетом склеивания краев карты Карно).

.

Пример. 5.21. (рис. 5.12).

х₂

х₁

1	1	1
			1

х₃

Рис. 5.12. «Одиночная» единица

В данном случае одна единица не имеет смежных, поэтому минимальная форма содержит 0-куб.

.

Пример 5.22.