Карты Карно

простоту работы с большими выражениями. Представляет собой операции попарного неполного

склеивания и элементарного поглощения. Карты Карно рассматриваются как перестроенная соответствующим образом таблица истинности функции.

Карты Карно были изобретены в 1952 Эдвардом В. Вейчем и усовершенствованы в 1953 Морисом Карно, физиком из «Bell Labs», и были призваны помочь упростить цифровые электронные схемы.

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

четырех переменных
- для пяти переменных

2-x мерные, т.е. представимы на плоскости.
Карты Карно логических функций 5-ти

и 6-ти переменных 3-х мерные или пространственные.
Метод применим только для логических функций до 7-ми переменных.
Свойства карт Карно:
1. Каждой клетке карты Карно соответствует один аргумент-вектор логической функции.
2. Число соседних клеток к каждой клетке карты Карно равно числу переменных карты.
3. Аргумент-векторы любых двух соседних клеток карты Карно являются ближайшими друг к другу аргумент-векторами (отличаются друг от друга только в одной координате).

для функций
y1,
y2,
y3.

строка для x1=0, x2=1
0
0
0
1
Четвертая строка для x1=1, x2=0 соответственно
1
0
1
1
Третья строка

для x1=1, x2=1 соответственно

0

1

1

1

определенных размеров называют контурами.
Для карт Карно, определенных на плоскости, контурами

являются прямоугольники, с допустимыми размерами сторон 2m x 2n, m, n = 0, 1, 2 …
1 x 1
1 x 2
1 x 4
2 x 1
2 x 2
2 x 4
4 x 1
4 x 2
4 x 4
...

– элементы с единичными элементами.
Выделение контуров:
Возможные контуры
Контуры могут пересекаться, причем

элементы должны входить в максимально большой контур

Также, одно из важных свойств – «склееность» границ карты. Граничные правые элементы являются соседними для граничных левых, верхние – для нижних.

на заполненной карте.

0
0
0
1
0
0
0
1
1
0
1
1
0
1
1
1
Выделим максимально большие контуры (они могут пересекаться)
Теперь

выделим меньшие контуры. Причем, учитывая «склееность» границ карты.

по правилу составления СДНФ или СКНФ по заданной области истинности

или ложности.

0

0

0

1

0

0

0

1

1

0

1

1

0

1

1

1

y1=

Постоянные значения x3 - прямой, x4- прямой

x3x4

Постоянное значение x3 - прямой

Постоянное значение x1 - прямой

+ x1x3

Постоянное значение x4 - прямой

Постоянные значения x1 – прямой, x2 – прямой

+ x1x2x 4

Постоянное значение x4 - инверсный

Постоянные значения x1 – прямой, x2 – инверсный

+ x1x2x 4

x1x2x3x4

истинности и картами Карно.
y1=
x3x4
+ x1x3
+ x1x2x 4
+ x1x2x 4