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

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

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

1. , ;

2.   , ;

3.  , ;

4.  ,                                                               (3)

5. , ;

6.  ; ;

7. .

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

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

.

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

.

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

.

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

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

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

 

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

 

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

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

.

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

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

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

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