3.5. Минимизация булевых функций.

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

Для упрощения можно использовать как непосредственно аксиомы алгебры логики, так и специальные приемы. Произведем упрощение выражения для F на основе аксиом:

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

Метод карт Карно. Карта Карно является специальной формой таблицы истинности функции, позволяющей не только её задать, но и выполнить минимизацию. Карта содержит 2n клеток для всех возможных сочетаний переменных и их инверсий, причём каждой клетке соответствует строго определённый минтерм. Так, для трёх переменных А, В и С карта содержит 23 = 8 клеток, а для четырех переменных – 24 = 16, и имеет вид, показанный на рис. 3.3.

Рис. 3.3 Карта Карно для четырёх переменных

Обычно в клетки карты заносят не сами минтермы, а метят единицами клетки, соответствующие этим минтермам. Правила минимизации с использованием карт Карно заключаются в следующем:

1) В карту Карно заносится исходная функция. Для этого метятся единицами клетки, соответствующие присутствующим в этой функции минтермам. Если на одну и ту же клетку приходится несколько единиц, то она метится лишь один раз.

2) Соседние, помеченные единицами клетки обводятся контурами («склеива-ются»). Контур склейки должен иметь форму квадрата или прямоугольника и содержать число клеток 2i (i = 0, 1, 2,…n).

3) Одни и те же клетки можно обводить сколько угодно раз.

4) При проведении контуров крайние строки карты (верхние и нижние, левые и правые), а также угловые клетки считаются соседними (для карт до четырех переменных).

5) Каждый контур должен включать максимально возможное количество клеток, а число контуров должно быть минимальным.

6) Функция выписывается из контуров карты. Переменная, входящая в контур как в прямом, так и в переменном виде, поглощается (см. закон поглощения).

7) Все единицы в карте (даже одиночные) должны быть охвачены контурами.

Принцип минимизации заключается в объединении соседних полей карты в пределах правильных конфигураций. При нахождении минимальной формы ФАЛ, выписываются переменные, не изменяющие своего значения в пределах склейки

Рис. 3.4 Диаграмма минимизации функции F

Пример минимизации приведённой выше функции F методом Карт Карно представлен на рис. 3.4. Значения 0 либо 1 над клетками карты указывают, в каких полях карты ложны либо истинны значения Х1  либо Х2.

Запись функции F заключается в занесении единиц в клетки карты, соответствующие минтермам этой функции. Для данного случая можно построить три контура, содержащих по две клетки. Искомое минимизированное выражение есть логическая сумма укороченных произведений переменных, имеющих одно значение в пределах контура, без переменных, имеющих оба возможных значения (0 и 1) в пределах контура. Таким образом, согласно рис. 3.4, будем иметь

где первый член дает вертикальный контур, второй член – правый горизонтальный контур, и третий член определяется левым горизонтальным контуром.

После этого можно уже составлять функциональную схему, выполняющую операцию F (рис. 3.5).

Рис. 3.5 Схема реализации упрощённой функции F

Использование избыточных комбинаций. При проектировании