Минимизация полностью определённых булевых функций.

Существует несколько способов минимизации булевых функций. Прежде всего это метод Квайна-Мак-Класки, метод Блека-Порецкого и метод минимизации с помощью карт Карно или диаграмм Вейча [13, 22, 29]. Здесь будет подробно излагаться метод карт Карно, как самый удобный метод, позволяющий быстро решать задачи минимизации булевых функций от достаточно большого числа аргументов (6-12). При этом получается минимальная форма в базисе И, ИЛИ, НЕ.

Существуют карты Карно на 2 , 3 , 4 , 5 и 6 переменных[13,22]. Причем последние стали использоваться достаточно недавно. На рисунке представлены карты Карно для 2, 3, 4, 5 и 6 аргументов.

Карты и прямоугольники Карно.

Метод Карно основан на законе склеивания. Склеиваются наборы , отличающиеся друг от друга значением одного разряда. Такие наборы называются соседними. Карно закодировал клетки своей карты так ,что в соседних клетках оказались соседние, а значит, склеивающиеся наборы. Соседними могут быть не только отдельные клетки, которые мы назовем элементарными квадратами Карно, но и целые группы соседних клеток(назовем их прямоугольниками Карно). Под прямоугольником Карно[13] будем понимать некоторую, зачастую разрозненную фигуру покрытия, все соседние клетки которой закодированы соседними наборами. Например, на вышеприведённом рисунке в поле карты для 4-х переменных изображён прямоугольник Карно P, состоящий из четырёх элементарных квадратов Карно, описываемых наборами x4'x3'x2'x1' , x4'x3'x2x1' , x4x3'x2'x1' , x4x3'x2x1' . Если над логической суммой этих четырёх наборов произвести последовательно операции склеивания, то мы аналитически получим результат в виде импликанты (под импликантой будем понимать неполный набор)x3'x1'. Карта Карно позволяет получить этот результат графически значительно быстрее и проще. Для решения этой задачи используем алгоритм графической минимизации.Кстати говоря,сам Карно никакого алгоритма не предложил.

Алгоритм "НИИРТА" графической минимизации булевых функций.

1. Заполнить карту Карно нулями и единицами в соответствии с таблицей истинности.

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

3. Каждому прямоугольнику Карно соответствует одна импликанта, причём, если в границах прямоугольника Карно какая-либо переменная принимает значения как 0 , так и 1 , то она склеивается.

Примечание.

Если в карте Карно нулей окажется меньше чем единиц, то удобнее прямоугольниками Карно покрыть все нулевые наборы. В результате мы получим инверсию минимизируемой функции.

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

Применим карту Карно для решения задачи 1. Возможны два варианта решения.

f = x4x1 + x4x2 + x4x3 + x3x2x1f' = x4'x1' + x4'x2' + x4'x3' + x3'x2'x1'

Эти выражения представляют собой пример дизъюнктивной нормальной формы (ДНФ).

В некоторых случаях приведение результата минимизации к скобочной форме позволяет уменьшить количество ИС , необходимые для реализации булевой функции. Скобочная форма для f имеет вид:

f = x4(x1 + x2 + x3) + x3x2x1

Карта Карно для решения задачи 1.