1.2. Минимизация логических функций
Полученную по таблице истинности запись логической функции в виде СДНФ или СКНФ почти всегда можно упростить с помощью теорем и правил алгебры логики, причем часто довольно существенно. Однако наиболее полного упрощения удается достичь с помощью алгоритма минимизации с использованием так называемых карт Карно. Этот алгоритм основан на представлении функции в виде СДНФ, дистрибутивном законе (4) и правиле отрицания (7).
Карта Карно представляет собой двумерную таблицу истинности логической функции, ячейки которой заполнены значениями функции в соответствии с циклическим кодом Грея, который замечателен тем, что при переходе в соседнюю ячейку всегда меняется значение только одной логической переменной. Приведем последовательность трехразрядных чисел, выстроенных по коду Грея: 000, 001, 011, 010, 110, 111, 101, 100. Построение кода Грея для чисел с большей разрядностью очевидно. При формировании карты Карно все N переменных логической функции делятся на две группы, причем число переменных в одной группе не более чем на единицу отличается от числа переменных в другой. Таким образом, если N четно, карта получается квадратной, если нечетно – прямоугольной. Далее карта Карно заполняется в соответствии с заданной таблицей истинности.
Для минимизации логической функции следует объединить контурами соседние ячейки карты Карно, содержащие либо логическую единицу, либо неопределенное значение (которое маркируется крестом). Соседними считаются две ячейки, отличающиеся друг от друга значением лишь одной логической переменной. Контуры должны содержать 2M ячеек (то есть 2, 4, 8 и так далее), их форма должна быть квадратной или прямоугольной. Кроме того, контуры могут пересекаться. Для полной минимизации необходимо размеры контуров сделать максимальными, а их количество должно быть минимальным.
После выделения всех контуров для каждого из них выписывается произведение тех логических переменных, которые в пределах данного контура не меняют своего значения; причем если в пределах контура переменная xi принимает значение 1, она выписывается в прямой форме, а если 0 – в инверсной. Сумма таких произведений дает минимальную запись логической функции, то есть в результате минимизации мы получаем запись логической функции в виде ДНФ. Почти очевидно, что в основе данного метода минимизации лежит дистрибутивный закон (4).
Рассмотрим пример, задав произвольную таблицу истинности логической функции:
x3 |
x2 |
x1 |
x0 |
f |
|
x3 |
x2 |
x1 |
x0 |
f |
0 |
0 |
0 |
0 |
0 |
|
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
|
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
|
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
|
1 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
|
1 |
1 |
0 |
0 |
x |
0 |
1 |
0 |
1 |
0 |
|
1 |
1 |
0 |
1 |
x |
0 |
1 |
1 |
0 |
0 |
|
1 |
1 |
1 |
0 |
x |
0 |
1 |
1 |
1 |
1 |
|
1 |
1 |
1 |
1 |
x |
Соответствующая этой логической функции карта Карно будет иметь вид:
Теперь выпишем логические произведения для каждого из контуров (слева направо), сумма которых даст нам ДНФ логической функции:
.
Необходимо заметить, что производить минимизацию таким образом имеет смысл для тех логических функций, у которых количество единиц в таблице истинности превышает количество нулей. В противном случае удобнее производить минимизацию не самой логической функции, а ее инверсного образа, а затем проинвертировать получившуюся ДНФ.
Часто необходимо преобразовывать полученную при минимизации ДНФ логической функции к виду, использующему только операции И-НЕ или ИЛИ-НЕ (говорят, что функция приводится к базису И-НЕ или ИЛИ-НЕ). Приведение к базису производится с помощью теоремы де Моргана (9). Полученная в нашем примере функция, записанная в базисе И-НЕ, будет иметь вид:
.