Этап. Нахождение существенных импликант. 2 страница

Рассмотрим карту Карно для функции 3-х переменных. Карту будем строить с симметричным расположением аргументов, один из них расположим с одной стороны, два других – с другой.

 

Разделим карту двумя осями, симметрично которым и будем располагать аргументы (см. карту).

 

 

Каждая клетка карты соответствует членам СДНФ функции, содержащим 3 знака.

Обратите внимание, что каждая пара соседних клеток может быть склеена, могут быть склеены любые четыре соседние клетки и все восемь.

Так можно склеить клетки 1 и 5, 1 и 2 и т.д., а также 2, 3, 6, 7; 1, 5, 4, 8 и т.д.

Если представить карту свернутой по вертикали в цилиндр, то крайние клетки окажутся рядом, их тоже можно склеить.

Рассмотрим несколько примеров

 

1

1

1

 

1

 

1

1

нельзя склеить

Приведем примеры карт Карно для числа аргументов

x ₅

x ₄ x ₄

x ₃ x ₃

x 2

x 2

x 1

x 1

x ₇

x ₆ x ₆

x ₅ x ₅

x ₄ x ₄

x 2

x 2

x 3

x 3

x ₁ x ₁

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

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

Чтобы упростить отыскание нужной клетки в карте Карно, целесообразно дополнительно пронумеровать строки и столбцы.

 

									0							1 x3
						x3										0 x4
					0	x4										0 x5
					x4	x3					x4	x3				x5
0 0							0 0
0 1							0 1
1 1							1 1
1 0	x2						1 0	x2

x₁x₂ x₁ x₁x₂ x₁

Обработка карт.

Из способа построения карты с симметричным расположением аргументов ясно, что каждая клетка функции с аргументами имеет соседних клеток, т.е. тех клеток, с которыми можно производить склеивание.

*				*
					*	*

x₅