Другой способ получения простых импликант формул с малым числом переменных (и, значит, нахождения минимальной ДНФ) основан на использовании так называемых карт Карно.
Карта Карно — это специального вида таблица, которая позволяет упростить процесс поиска минимальных форм и успешно применяется, когда число переменных не превосходит шести. Карты Карно для функций, зависящих от n переменных, представляет собой прямоугольник, разделенный на 2n клеток. Каждой клетке диаграммы ставится в соответствие двоичный n-мерный набор. Значения заданной функции f из таблицы истинности вносятся в нужные квадраты, однако если клетке соответствует 0, то обычно она остается пустой.
В первой таблице показан пример разметки карты Карно для функции, зависящей от трех переменных. Нижние четыре клетки карты соответствуют двоичным наборам, в которых переменная x принимает значение 1, четыре верхние клетки соответствуют наборам, в которых переменная x принимает значение 0. Четырем клеткам составляющим правую половину карты, соответствуют наборы, в которых переменная y; принимает значение 1 и т.д. Во второй таблице приведена разметка карты Карно для n=4 переменных.
| y z — x | 0 0 | 0 1 | 1 1 | 1 0 |
| 0 | 000 | 001 | 011 | 010 |
| 1 | 100 | 101 | 111 | 110 |
| z w — xy | 0 0 | 0 1 | 1 1 | 1 0 |
| 00 | 0000 | 0001 | 0011 | 0010 |
| 01 | 0100 | 0101 | 0011 | 0010 |
| 11 | 1100 | 1101 | 1111 | 1110 |
| 10 | 1000 | 1001 | 1011 | 1010 |
Для построения минимальной ДНФ производится процедура склеивания «1». Склеивающимся значениям «1» соответствуют соседние клетки, т.е. клетки отличающиеся лишь значением одной переменной (на графическом изображении разделенных вертикальной или горизонтальной линией с учетом соседства противоположных крайних клеток).
Процесс склеивания «1» сводится к объединению в группы единичных клеток карты Карно, при этом необходимо выполнять следующие правила:
1. Количество клеток, входящих в одну группу, должно выражаться числом кратным 2, т.е. 2m где m=0,1,2,…
2. Каждая клетка, входящая в группу из 2m клеток, должна иметь m соседних в группе.
3. Каждая клетка должна входить хотя бы в одну группу.
4. В каждую группу должно входить максимальное число клеток, т.е. ни одна группа не должна содержаться в другой группе.
5. Число групп должно быть минимальным.
Считывание функции f по группе склеивания производится следующим образом: переменные, которые сохраняют одинаковые значения в клетках группы склеивания, входят в конъюнкцию, причем значениям 1 соответствуют сами переменные, а значениям 0 их отрицания.
Приведем шаблоны, которые помогают строить покрытия 1 (переменные считаем теми же, но их писать не будем). Для упрощения записи мы не будем отмечать переменные, хотя сохраним их обозначения как и в вышеприведенных таблицах.
A) n=3
| F=z | |||
| 1 | 1 | ||
| 1 | 1 | ||
| f=¬z | |||
| 1 | 1 | 1 | 1 |
| F=¬y | |||
| 1 | 1 | ||
| 1 | 1 | ||
| F=¬z&¬y | |||
| 1 | |||
| 1 | |||
| f=¬x&y | |||
| 1 | 1 | ||
| F=¬y&x | |||
| 1 | 1 | ||
B) n=4
| F=w | |||
| 1 | 1 | ||
| 1 | 1 | ||
| 1 | 1 | ||
| 1 | 1 | ||
| f=¬y | |||
| 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 |
| F=¬z | |||
| 1 | 1 | ||
| 1 | 1 | ||
| 1 | 1 | ||
| 1 | 1 | ||
| F=¬x&z | |||
| 1 | 1 | ||
| 1 | 1 | ||
| f=y&w | |||
| 1 | 1 | ||
| 1 | 1 | ||
| F=¬x&¬y | |||
| 1 | 1 | 1 | 1 |
| F=¬y&¬w | |||
| 1 | 1 | ||
| 1 | 1 | ||
| f=¬y&¬z | |||
| 1 | 1 | ||
| 1 | 1 | ||
| F=¬z&¬x | |||
| 1 | 1 | ||
| 1 | 1 | ||
| F=y&z&w | |||
| 1 | |||
| 1 | |||
| f=¬y&¬z&¬w | |||
| 1 | |||
| 1 | |||
| F=x&y&¬z | |||
| 1 | 1 | ||
Пример: Построить МДНФ
| z w — xy | 0 0 | 0 1 | 1 1 | 1 0 |
| 00 | 1 | 1 | 1 | |
| 01 | 1 | 1 | 1 | |
| 11 | 1 | 1 | ||
| 10 | 1 |
Сначала смотрим, есть ли покрытия_1 из 16 клеток покрывающих хотя бы одну непокрытую 1. Таких покрытий нет. Переходим к покрытиям из 8 клеток. Смотрим, есть ли покрытия 1 из 8 клеток покрывающих хотя бы одну непокрытую 1. Таких покрытий нет. Переходим к покрытиям из 4 клеток. Смотрим, есть ли покрытия 1 из 4 клеток покрывающих хотя бы одну непокрытую 1. Таких покрытий два. Переходим к покрытиям из 2 клеток. Такое покрытие одно. Таким образом, все 1 стали покрытыми. Далее, смотрим можно ли убрать некоторые покрытия, так чтобы все единицы остались покрытыми. В конце выписываем МДНФ: f=¬X¬ZvYWv¬YZ¬W.
Замечание. Для построения минимальной КНФ функции f, достаточно построить минимальную ДНФ для функции ¬f , а затем использовать f=¬¬f и законы де Моргана.