Методы минимизации булевых функций

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

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

Замечание. Как правило, при нахождении МДНФ на карте Карно фиксируются только единичные значения функции, в то время как нулевые значения соответствуют пустым клеткам. В свою очередь, при нахождении МКНФ фиксируются нулевые значения функции, а единичным соответствуют пустые клетки.

Решение задачи минимизации сводится к нахождению минимального покрытия булевой функции, которое строится из максимальных кубов, представленных на карте Карно прямоугольниками с числом клеток, равным 2^k, где k – размерность куба. При минимизации функций от трех и четырех переменных карта Карно состоит из 8 или 16 клеток соответственно, причем все кубы покрытия (в том числе и минимального) размещаются внутри карты.

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

При минимизации функций от большего числа аргументов (пять или шесть) карта Карно представляется двумя или четырьмя квадратами по 16 клеток в каждом. При этом кубы, образующие покрытие, могут размещаться либо в одном квадрате, либо в двух (n = 5, 6), либо в четырех (n = 6). Однако, при этом в разных квадратах они представляются одинаково расположенными конфигурациями (прямоугольниками).

Для получения минимального покрытия на карте Карно используется следующий принцип: покрытие булевой функции будет являться действительно минимальным, если оно по сравнению с другими покрытиями состоит из минимально возможного числа кубов, каждый из которых обладает максимально возможной размерностью. Более детально графический метод минимизации булевых функций с использованием карт Карно описан в разделе 2.12.

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

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

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

Рассмотрим наиболее известные аналитические методы минимизации.

Метод Квайна:

В методе Квайна простые импликанты находятся по канонической дизъюнктивной нормальной форме в результате последовательного применения к ней операций неполного склеивания и элементарного поглощения.

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

Алгоритм Квайна:

1. Минимизируемая булева функция f от n переменных записывается в КДНФ f_0.

2. Строим последовательность ДНФ f₀, f₁, … , f_i, … до тех пор, пока две какие-либо ДНФ f_k и f_k+1 не совпадут между собой. Переход от формы f_i к форме f_i+1 производится по следующему правилу: в форме f_i выполняются все операции неполного склеивания, применимые к элементарным произведениям длины n - i, после чего исключаются все те элементарные произведения длины n – i, которые могут быть исключены на основании закона поглощения.

3. Результатом применения алгоритма Квайна к функции f является сокращенная ДНФ (СДНФ) f_k.

Доказана следующая теорема Квайна:

Теорема. Для любой булевой функции f результатом применения алгоритма Квайна к КДНФ этой функции будет СДНФ функции f.

Иными словами, с помощью последовательного применения операций неполного склеивания и элементарного поглощения в конечное число шагов КДНФ любой булевой функции преобразуется СДНФ этой функции.

Более подробно метод Кавйна изложен в [1, стр. 278-282] и [3, стр.196-199].

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

Метод представляет собой формализованный на этапе нахождения простых импликант метод Квайна. Формализация производится следующим образом:

1. Все конституанты единицы из СДНФ булевой функции f записываются их двоичными номерами.

2. Все номера разбиваются на непересекающиеся группы. Признак образования i-й группы: i единиц в каждом двоичном номере конституенты единицы.

3. Склеивание производят только между номерами соседних групп. Склеиваемые номера отмечаются каким-либо знаком (зачеркиванием).

4. Склеивания производят всевозможные, как и в методе Квайна. Неотмеченные после склеивания номера являются простыми импликантами.

Метод Квайна-Мак-Класки подробно рассмотрен в подразделе 2.14 настоящего пособия.

Недостатком метода Квайна-Мак-Класки является то, что для его применения необходимо представить функцию в КДНФ. Процесс такого представления для функции с большим числом аргументов зачастую является весьма громоздкой задачей, т.е. было бы желательно найти возможность построения сокращенной ДНФ не по КДНФ, а по произвольной ДНФ данной функции. Идея построения сокращенной ДНФ по произвольной ДНФ была предложена в работах А. Блейка и П.С. Порецкого.

Метод Блейка-Порецкого:

Суть метода состоит в том, что в произвольной ДНФ осуществляют все операции обобщенного склеивания. Суть этой операции состоит в применении следующего тождественного соотношения булевой алгебры: