Page 53 - ЭВМ

Минимизация булевых функций может быть проведена одним
из известных методов, к числу которых относится метод карт Карно.
Карта Карно для n двоичных переменных представляет собой прямо-
n
угольную таблицу с числом клеток в ней, равным N = 2 . Таким обра-
зом, для трех переменных карта Карно включает восемь клеток, для
четырех – шестнадцать и т. д.
На карту Карно в так называемом циклическом коде Грея зано-
сятся минтермы. Для четырех переменных карта Карно выглядит сле-
дующим образом:

Y1Y2 X1X2
00 01 11 10
00
01
11
10

На карте Карно в коде Грея по горизонтали перечисляются
переменные X1, X2, а по вертикали – переменные Y1, Y2.

Метод карт Карно использует одну из известных аксиом алгеб-
ры Буля:
X + X = 1 .

Можно сформулировать несколько правил, основанных на этой
аксиоме (аксиома склеивания переменных):
1. Если минтермы расположены в соседних или крайних клетках
строки или столбца, то ранг минтерма снижается на один порядок,
а склеиванию подлежит переменная, входящая с разными показате-

лями инверсии. В таблице приведена карта Карно для выражения
F = X 1 2 1 2 + XY Y X 1 2 12 + XY Y X 1 1 12 + X Y Y X 1 2 2 1 + XY Y X 1 2 12 + XY Y
+ XX Y Y
12 1 2:

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

Данное выражение минимизируется и равно

F = XY XY Y
22 +
2 1 2.

53