Карты Карно – это графическое изображение таблиц истинности.
Пусть задана функция 
. Подмножество элементов 
, в которых 
, называется носителем функции f и обозначается через supp(f). Конечные пересечения подмножеств вида: 
называются кубиками. Кубики будут равны: 
, для некоторых 
и 
, таких, что 
. Если кубики являются максимальными, содержащимися в носителе, и попарно не пересекаются, то формула
будет давать разложение в дизъюнктивную нормальную форму, минимальное по количеству слагаемых. Карты Карно позволяют «увидеть» эти кубики. Для функций двух, трех и четырех переменных они имеют следующие структуры:
|
x1 |
x2 |
0 |
1 |
|
0 |
f(0,0) |
f(0,1) |
|
|
1 |
f(1,0) |
f(1,1) |
|
|
x2 x3 |
00 |
01 |
11 |
10 |
|
|
x1 |
|||||
|
0 |
f(0,0,0) |
f(0,0,1) |
f(0,1,1) |
f(0,1,0) |
|
|
1 |
f(1,0,0) |
f(1,0,1) |
f(1,1,1) |
f(1,1,0) |
|
|
х3 x4 |
00 |
01 |
11 |
10 |
|
|
x1 x2 |
|||||
|
00 |
f(0,0,0,0) |
f(0,0,0,1) |
f(0,0,1,1) |
f(0,0,1,0) |
|
|
01 |
f(0,1,0,0) |
f(0,1,0,1) |
f(0,1,1,1) |
f(0,1,1,0) |
|
|
11 |
f(1,1,0,0) |
f(1,1,0,1) |
f(1,1,1,1) |
f(1,1,1,0) |
|
|
10 |
f(1,0,0,0) |
f(1,0,0,1) |
f(1,0,1,1) |
f(1,0,1,0) |
|
Кубикам будут соответствовать отрезки и квадраты. Рассмотрим примеры кубиков и соответствующих им логических произведений:
|
00 |
01 |
11 |
10 |
|
|
00 |
0 |
0 |
0 |
0 |
|
01 |
0 |
1 |
1 |
0 |
|
11 |
0 |
0 |
0 |
0 |
|
10 |
0 |
0 |
0 |
0 |
|
00 |
01 |
11 |
10 |
|
|
00 |
0 |
0 |
0 |
0 |
|
01 |
1 |
1 |
0 |
0 |
|
11 |
1 |
1 |
0 |
0 |
|
10 |
0 |
0 |
0 |
0 |
Возможно превращение кубиков в квадраты и отрезки после отождествления противоположных сторон карты Карно, например:
|
00 |
01 |
11 |
10 |
|
|
00 |
0 |
0 |
0 |
0 |
|
01 |
0 |
0 |
0 |
0 |
|
11 |
1 |
0 |
0 |
1 |
|
10 |
0 |
0 |
0 |
0 |
|
00 |
01 |
11 |
10 |
|
|
00 |
0 |
0 |
0 |
0 |
|
01 |
1 |
0 |
0 |
1 |
|
11 |
1 |
0 |
0 |
1 |
|
10 |
0 |
0 |
0 |
0 |
Логические произведения состоят из сомножителей, значения которых не изменяются внутри кубика.
Если это значение равно 1, то для переменной 
берется сомножитель , а если это значение равно 0 – то сомножитель 
.
Пример
Для булевой функции:
найти дизъюнктивную нормальную форму с наименьшим числом логических слагаемых.
Решение. Составим карту Карно:
|
|
х3 x4 |
00 |
01 |
11 |
10 |
|
x1 x2 |
|||||
|
00 |
1 |
0 |
0 |
1 |
|
|
01 |
0 |
0 |
1 |
0 |
|
|
11 |
0 |
0 |
1 |
0 |
|
|
10 |
1 |
0 |
0 |
1 |
|
Получаем 2 кубика: 
и 
. Внутри первого кубика не изменяются переменные 
и 
, и равны 0. Значит, первое слагаемое равно: 
. Внутри второго кубика не изменяются 
и 
, откуда второе слагаемое равно: 
. Следовательно, искомая дизъюнктивная нормальная форма равна: 
.
