Графоаналитический способ упрощения булевых выражений.

Графоаналитический использует Карты Карно (диаграммы Вейтча).

Пример 3. Предположим, что имеется следующая таблица истинности:

X1	X2	X3	X4	F
0	0	0	0	0
0	0	0	1	0
0	0	1	0	1
0	0	1	1	0
0	1	0	0	1
0	1	0	1	0
0	1	1	0	1
0	1	1	1	0
1	0	0	0	0
1	0	0	1	0
1	0	1	0	1
1	0	1	1	0
1	1	0	0	1
1	1	0	1	0
1	1	1	0	1
1	1	1	1	0

При сокращении выражения с помощью карты Карно мы применяли следующие правила.

Число ячеек в карте е равно числу строк в таблице, то есть . Значения функции из столбца таблицы истинности размещены на плоскости карты Карно. Соответствующие значения переменных из таблицы истинности условно обозначены вокруг таблицы. Единице соответствует черта проведенная рядом с таблицей. Вертикальная черта означает, что соответствующая переменная равна "1" во всех ячейках строк, помеченных этой чертой. Аналогично, горизонтальная черта означает, что соответствующая переменная равна "1" во всех ячейках столбцов, помеченных этой чертой.

Отдельная "1" в ячейке карты соответствует одной строке таблицы истинности, следовательно, она описывается тем же термом, что и строка таблицы. Карта Карно для 4-х переменных имеет вид:

			00	01	11	10
		00	0	0	0	1
		01	1	0	0	1
		11	1	0	0	1
		10	0	0	0	1

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

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

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

				x3				x3
		1	1			1	1			x2
	x1	1	1			1	1
X5
		1	1			1	1			x2
	x1	1	1		1	1
					1	1
			x4				x4
						X6

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

При увеличении числа "1", входящих в образуемую группу в 2 раза, число литер в терме уменьшается на одну. Соответственно, в два раза уменьшается и число термов, так как теперь объединенную группу описывает один терм. Следовательно, мы должны стремиться объединить в группу как можно больше стоящих рядом"1". Размер группы может быть любой, отвечающий выражению , где k и j – целые числа = 0,1,2,….Например, ,,,,,,и т.д.

Можно сформулировать следующий алгоритм построения групп. Построение новой группы начинается с выбора "1", не входящей ещё ни в одну уже созданную группу. Вокруг выбранной "1" надо объединить как можно больше "1", в том числе нужно стремиться включать также "1", уже входящие в ранее образованные группы. Далее алгоритм разметки групп повторяется с выбора новой "1" до тех пор пока свободных "1" не останется.

Карты Карно можно применять и для упрощения выражений, содержащих 5 или 6 переменных, но необходимо придерживаться дополнительных правил объединения ячеек в группы. Внутри каждой из четырех карт (квадрантов), отделенных друг от друга жирной линией, действуют те же правила, что и для рассмотренной выше карты для 4-х переменных. При объединении групп, расположенных в разных квадрантах, можно объединять группы, которые занимают одинаковое положение в квадрантах.

Предположим, что имеется карта Карно с набором нулей и единиц как на рис.1.6. Тогда, в одну группу объединены четыре группы по две ячейки, расположенные во всех четырех квадрантах. В этой объединенной группе мы не записываеми,так как они меняют свои значения внутри объединенной группы. Это правило основано на следующем Булевом тождестве

.