4.7.2. Развертка гиперкуба на плоскости. Карта Карно

Еще более удобной формой представления булева пространства является двумерная таблица, которую принято называть картой Карно. Карта Карно имеет ту же структуру, что и развертка гиперкуба на плоскости. Каждая ее клетка соответствует элементу булева пространства. Булеву функцию можно задать расположением нулей и единиц в клетках в соответствии с теми значениями, которые принимает функция на соответствующих элементах булева пространства. Другим способом задания булевой функции на карте Карно является разметка клеток, соответствующих элементам множества М_f¹. При этом клетки, соответствующие элементам множества М_f⁰, остаются пустыми. Оба способа представлены на рис. 4.3, где показан пример задания функции f (х₁, х₂, х₃) = х₁ х₂ х₁х₂ х₃. Коды строк и столбцов, из которых составляются коды клеток, представлены отрезками прямых. Отрезок вертикальной прямой возле нижней строки показывает, что переменная х₁ в коде этой строки имеет значение 1, а его отсутствие у верхней строки говорит, что в ее коде х₁ = 0. Аналогично горизонтальные отрезки показывают значения переменных х₂ и х₃ в кодах столбцов.

х₂х₃ х₂х₃

0	0	0	1							
0	1	1	0						

х₁х₁

Рис. 4.3. Задание булевой функции с помощью карты Карно

Удобство работы с картами Карно обеспечивается применением кода Грея для кодирования ее строк и столбцов.

Пусть надо закодировать в коде Грея последовательность некоторых объектов, число которых N. Коды этих объектов, так же как и коды в виде двоичных чисел, являются булевыми векторами. Длина кода п должна быть такой, чтобы выполнялось N  2^п, или п = log₂N, где а – ближайшее к а сверху целое число. Первому объекту присваивается код, состоящий только из нулей – 0 0 … 0. Далее коды определяются по следующему правилу.

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

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

Другой способ построения кода Грея заключается в следующем. Сначала берется последовательность из двух однокомпонентных кодов: (0), (1). Приписав к этой последовательности те же коды в обратном порядке, получим (0), (1), (1), (0). Добавляем слева 0 к элементам исходной последовательности и 1 – к приписанной. Получим (0 0), (0 1), (1 1), (1 0).

Благодаря коду Грея, два соседних элемента булева пространства или два соседних интервала расположены на карте Карно симметрично некоторой оси, т. е. отношение соседства элементов булева пространства представляется отношением симметрии в карте Карно. На рис. 4.4 показана шестимерная карта Карно с осями симметрии. Оси симметрии проходят в местах изменения значений переменных в кодах строк и столбцов. Каждая ось имеет свою зону симметрии, ширина которой определяется рангом оси.

Оси, связанной с переменной, наиболее часто меняющей свое значение а последовательности кодов строк (или столбцов), придается ранг 1. Если ось связана с переменной, которая меняет свое значение в два раза меньше, ей приписывается ранг 2, если в четыре раза меньше, – ранг 3 и т. д. Ширина оси симметрии ранга k равна 2^k (рис. 4.4).

Рис. 4.4. Зоны симметрии карты Карно

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

Рекомендуется в первую очередь выделять те максимальные интервалы, где имеется элемент, для которого данный максимальный интервал является единственным, его содержащим. Такие интервалы называются обязательными, а соответствующие элементы – определяющими.

Если пользоваться «жадным» способом, т. е. стараться покрыть одним интервалом как можно большее число элементов, то в полученной ДНФ может оказаться избыточная элементарная конъюнкция, как, например, для функции f(x₁ x₂ x₃ x₄) = x₁x₂ x₃  x₁ x₂ x₄ x₁ x₂ x₃ x₁x₂ x₄, представленной картой Карно на рис. 4.5. Самый большой интервал, представленный конъюнкцией х₃ х₄, покрывается остальными интервалами, поэтому является избыточным.

Примером получения упрощенной ДНФ является получение ее для функции, представленной картой Карно на рис. 4.6, где определяющие элементы отмечены кружками. ДНФ этой функции имеет вид

х₂х₃ х₄х₆ х₁ х₃х₄ х₅  х₂ х₃х₄ х₅  х₂ х₃ х₅ х₆ х₁ х₃х₄ х₆ х₁ х₂х₃ х₅х₆

Эта ДНФ является минимальной, поскольку из шести интервалов, покрывающих множество М_f¹, пять являются обязательными.

х₃х₄

			
		
			
		

х₁х₂

Рис. 4.5. Область М_f¹с избыточным максимальным интервалом

х₄х₅х₆

						

х₁х₂х₃

Рис. 4.6. Задание булевой функции с помощью карты Карно.

Кружками отмечены определяющие элементы