Этап. Нахождение существенных импликант. 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₃

x2

x2

x1

x1

x ₇

x₆ x₆

x₅ x₅

x₄ x₄

x2

x2

x3

x3

x₁ x₁

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

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

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

									0							1x3
						x3										0x4
					0	x4										0x5
					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₅