Карты Карно

Другой способ получения простых импликант формул с малым числом переменных (и, значит, нахождения минимальной ДНФ) основан на использовании так называемых карт Карно.

Карта Карно — это специального вида таблица, которая позволяет упростить процесс поиска минимальных форм и успешно применяется, когда число переменных не превосходит шести. Карты Карно для функций, зависящих от n переменных, представляет собой прямоугольник, разделенный на 2n клеток. Каждой клетке диаграммы ставится в соответствие двоичный n-мерный набор. Значения заданной функции f из таблицы истинности вносятся в нужные квадраты, однако если клетке соответствует 0, то обычно она остается пустой.

В первой таблице показан пример разметки карты Карно для функции, зависящей от трех переменных. Нижние четыре клетки карты соответствуют двоичным наборам, в которых переменная x принимает значение 1, четыре верхние клетки соответствуют наборам, в которых переменная x принимает значение 0. Четырем клеткам составляющим правую половину карты, соответствуют наборы, в которых переменная y; принимает значение 1 и т.д. Во второй таблице приведена разметка карты Карно для n=4 переменных.

y
z

x
0
0
0
1
1
1
1
0
0000001011010
1100101111110
z
w

xy
0
0
0
1
1
1
1
0
000000000100110010
010100010100110010
111100110111111110
101000100110111010

Для построения минимальной ДНФ производится процедура склеивания «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
  11
  11
f=¬z
1111
    
F=¬y
1  1
1  1
F=¬z&¬y
1   
1   
f=¬x&y
 11 
    
F=¬y&x
    
1  1

B) n=4

F=w
  11
  11
  11
  11
f=¬y
1111
    
    
1111
F=¬z
1  1
1  1
1  1
1  1
F=¬x&z
  11
  11
    
    
f=y&w
    
 11 
 11 
    
F=¬x&¬y
1111
    
    
    
F=¬y&¬w
1  1
    
    
1  1
f=¬y&¬z
11  
    
    
11  
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
0011 1
01111 
11 11 
10   1

Сначала смотрим, есть ли покрытия_1 из 16 клеток покрывающих хотя бы одну непокрытую 1. Таких покрытий нет. Переходим к покрытиям из 8 клеток. Смотрим, есть ли покрытия 1 из 8 клеток покрывающих хотя бы одну непокрытую 1. Таких покрытий нет. Переходим к покрытиям из 4 клеток. Смотрим, есть ли покрытия 1 из 4 клеток покрывающих хотя бы одну непокрытую 1. Таких покрытий два. Переходим к покрытиям из 2 клеток. Такое покрытие одно. Таким образом, все 1 стали покрытыми. Далее, смотрим можно ли убрать некоторые покрытия, так чтобы все единицы остались покрытыми. В конце выписываем МДНФ: f=¬X¬ZvYWv¬YZ¬W.

Замечание. Для построения минимальной КНФ функции f, достаточно построить минимальную ДНФ для функции ¬f , а затем использовать f=¬¬f и законы де Моргана.