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

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

	x1

Рис. 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).

	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.

Дана функция четырех переменных (рис. 5.13):

4 х1 1 1		3 1	1 4
1	1 2		х4
1
4 1			4 1

Рис 5.13. Минимизация функции четырех переменных

Минимизируя, получим: .

Метод карт Карно обычно применяется для минимизации функций до пяти переменных. Карты Карно пяти переменных приводятся на рис. 5.14.Для данной карты помеченные области и прилегающие к ним считаются смежными (помеченная область соответствует x₂ x₃).

							х3
			х4

Рис. 5.14. Карты Карно для функции пяти переменных

Пример 5.23. Функция пяти переменных представлена на карте (рис. 5.15).

х1		1
	1						х3
1

Рис. 5.15. Минимизация функции пяти переменных

.

Замечание: В ряде случаев эффективно производить минимизацию «по нулям», т.е. отделять группы смежных нулей и записать выражение для инверсии минимизируемой функции.

Пример 5.24.Функция трех переменных представлена на карте (рис 5.16).

	х1

0	0	0
			1

Рис. 5.16. Минимизация «по нулям»

Не нашли, что искали? Воспользуйтесь поиском по сайту: