2.4.3. Карты Карно
Карты Карно булевой функции F(X1, X2, ..., XN) называется прямоугольной таблицей (см. рис.) в которой K строчек, соответствуют первым K переменным и 
столбцов, соответствующие остальным переменным (обычно 
или 
, в случае нечётного). Каждому бинарному
|
Набору (σ1, σ2, ..., σN) соответствует строка, а набору (σk+1, σk+2, ..., σn) – столбец. В клетке на пересечении данной строчки и столбца записывается значение функции F(σ1,σ2,...,σk,σk+1,...,σn). Обычно в клетки записывают только значения 1, а клетки, которым соответствует значение 0, оставляют пустыми. Таким образом, отмечаются клетки, составляющие область истинности F. |
: Xk+1 X1 ... Xk |
0 : 0 |
: : : |
σN : σK+1 |
: : : |
0 : 1 | |
|
0 ... 0 |
* |
... |
* |
... |
* | ||
|
…… |
... |
... |
... |
... |
... | ||
|
σ1 ... σK |
* |
... |
* |
... |
* | ||
|
……. |
... |
... |
... |
... |
... | ||
|
1 … 0 |
* |
... |
* |
... |
* |
Xn Для решения задачи минимизации на множестве клеток введём отношение соседства следующим образом. Две клетки будем называть соседними, если соответствующие им (полные) бинарные наборы (σ1,σ2,...,σk,σk+1,...,σn) отличаются только в одном разряде. Для того, чтобы такое отношение было наглядным бинарные наборы (σ1,σ2,...,σk) по строкам и наборы (σk+1,σk+2,...,σn) по столбцам перечисляют в таком порядке, чтобы каждый последующий отличался от предыдущего также только в одном разряде. Тогда соседними будут клетки, имеющие общую сторону, а также (возможно) некоторые клетки, расположенные на противоположных краях таблицы
Карты Карно для функций небольшого числа переменных покажем на следующих примерах:
Пример 1. Минимизировать функцию 
. В клетках таблицы, составляющих область истинности, стоят «1».
|
Заметим, что здесь соседними являются также клетки первого и последнего столбца. Поэтому карту Карно в данном примере следует представлять себе в форме цилиндра, который получится, если склеить |
X2 X1 |
0 0 |
1 0 |
1 1 |
0 1 | |
|
0 |
1 |
1 | ||||
|
1 |
1 |
1 |
X3Левую сторону прямоугольника с правой.
На цилиндре соседними будут в точности клетки, имеющие общую сторону. Минитермы, соответствующие двум соседним клеткам, склеиваются по той переменной, по которой они отличаются. В данном примере имеется две пары: 1). (000) и (100) -- при склеивании получи (-00); 2) (000) и (001) -- при склеивании получим (00-). Клетка (11,1) не имеет соседних. Таким образом, получаем ответ: 
Пример 2. На следующем рисунке заполнена карта Карно для функции 
. Здесь помимо клеток с общей стороной соседними являются также клетки первого и последнего столбца, а также верхней и нижней строчек.
|
|
X3 X1 X2 |
0 0 |
1 0 |
1 1 |
0 1 | |
|
0 0 |
1 |
1 | ||||
|
0 1 |
1 |
1 | ||||
|
1 1 |
1 |
1 | ||||
|
1 0 |
1 |
1 |
1 |
Если склеить левую границу квадрата с правой, а затем верхнюю границу с нижней, то получим тор, на котором соединениями будут в точности клетки, имеющие общую сторону. Склеивать можно не только пары, а также
X4Четвёрки, состоящие из двух соседних пар (квадраты 2´2 или полосы 1´4, 4´1). В результате такого склеивания исчезают две переменные (по которым различаются данные клетки) и получается минитерм 2 ранга. Две соседние четвёрки (две полоски или два квадрата), имеющие общую сторону, также можно склеить вместе, получая минитерм 1 ранга.
В данном примере имеется 3 четвёрки и одна пара:
1) (01,01) Ú (01,11) Ú (11,01) Ú (11,11) = (-1-1);
2) (00,00) Ú (00,01) Ú (10,00) Ú (10,01) = (-00-)
3) (10,00) Ú (10,10) = (10-0)
(Все минитермы четверки 00,01) Ú (01,01) Ú (11,01) Ú (10,01) уже содержатся в 1) и 2). )
Таким образом, получаем ответ: 
.
Как видно из примера, прежде всего, необходимо склеивать клетки, составляющие максимальные наборы (прямоугольники максимальной площади); каждая клетка может быть использована при склеивании столько раз, сколько это нужно для составления максимальных наборов.
Пример 3. На следующем рисунке приведена карта Карно для функций пяти переменных. Её следует рассматривать, как два квадрата 4´4, лежащих друг на друге,
|
|
X5 X4 X3 X1 X2 |
0 0 0 |
1 0 0 |
1 1 0 |
0 1 0 |
0 0 1 |
1 0 1 |
1 1 1 |
0 1 1 | |
|
0 0 |
1 |
1 |
1 |
1 | ||||||
|
0 1 |
1 |
1 | ||||||||
|
1 1 |
1 |
1 |
1 |
1 |
1 |
1 | ||||
|
1 0 |
1 |
1 |
1 |
1 |
Каждый из которых склеен в тор. Помимо клеток имеющих общую сторону в одном из квадратов (точнее – на торе), соседними так же являются клетки из разных квадратов, расположенные одна над другой.Для карты на рисунке получим следующий результат:
.
Карты Карно для функций с большим числом переменных для минимизации практически не используется, поскольку в этом случае более сложно проследить за отношением соседства. Однако, разбив всю карту на фрагменты 4´4, можно произвести частичные склеивания, а затем продолжить минимизацию, например, упрощая формулу путем тождественных преобразований.
| < Предыдущая | Следующая > |
|---|
