Минимизация булевых выражений

Логическое устройство, построенное на базе исходного булевого выражения, не является оптимальным с точки зрения количества используемых элементарных элементов. Минимизация булева выражения может быть достигнута при анализе таблицы истинности с помощью теорем булевой алгебры или на основе использования карт Карно.

Рассмотрим минимизацию булевых выражений с помощью теорем булевой алгебры. Эти теоремы отражают связи, существующие между операциями, выполненными над логическими переменными. Основные теоремы представляются следующими выражениями:

1.  , ;

2.   , ;

3.  , ;

4.  ,                                                               (3)

5. , ;

6.  ; ;

7. .

Выражения №6 приведенных формул называют законами де Моргана.

Для минимизации выражения (1)  последовательно используем выражения 5, 7, 4, 1

.

В результате получим следующую булеву функцию

.

Проводим повторную группировку

.

Таким образом, после минимизации булева функция (1) принимает следующий вид

Теперь рассмотрим минимизацию выражения (1) с помощью карт Карно. Карты Карно представляют собой систему графического представления и упрощения булевых выражений.

В карте Карно переменные по горизонтали и вертикали располагаются согласно коду Грея. В коде Грея соседние элементы отличаются только в одном бите. Код Грея для одной переменной A имеет вид 0 1. Для двух переменных AB код Грея – AB = 00 10 11 10, что соответствует булевому выражению

 

 В общем случае число квадрантов карт равно числу возможных комбинаций переменных. Выражение (1) имеет четыре элемента . Таблица истинности для четырех элементов включает 16 возможных комбинаций, которые на рисунке 4 представлены 16 квадрантами карты. Нанесем на карту шесть единиц, которые соответствуют шести слагаемым в заданном булевом выражении. Соседние единицы объединим в группы по две и четыре единицы (рис.6.)

 

Рис.6. Карта Карно

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

.

При минимизации булевых выражений по карте Карно необходимо объединять в контуры не только соседние, но и крайние члены карты. Например, для булевого выражения

карта Карно и минимизированное булево выражение имеют следующий вид

Рис.7. Карта Карно

Для упрощения булевых выражений с двумя, тремя и четырьмя переменными применяют одинаковые процедуры. Необходимо отметить, чем больше единиц объединяется в контуре, тем больше переменных можно опустить.