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

 

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

Графический метод минимизации основан на использовании минимизирующих карт, называемых картами Карно ( диаграммами Вейча ). Карта Карно для функции от 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 настоящего пособия.

 

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

 

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

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

В основу метода положено следующее утверждение ( теорема Блейка ): если в произвольной ДНФ булевой функции f произвести все возможные oбобщенные склеивания, а затем выполнить все поглощения, то в результате получится сокращенная ДНФ функции f.

Метод построения сокращенной ДНФ заключается в том, что если в произвольной форме булевой функции есть конъюнкции с переменными  то не изменяя исходную функцию необходимо пополнить ее новыми членами вида ab. После этого надо провести поглощения и вновь повторить пополнение ДНФ. Этот процесс необходимо производить до тех пор, пока не будут возникать новые конъюнкции вида ab В. По окончании преобразований получаем CДНФ.

Более подробно метод Блейка-Порецкого изложен в [1, стр. 292-297] и [4, стр.66-67].

 

Метод Нельсона:

Этот метод основан на следующей теореме ( теорема Нельсона ):

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

Более подробно метод Нельсона изложен в [1, стр. 297-299].

 

Метод неопределенных коэффициентов:

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

Представим функцию f(x₁, x₂, x₃) в виде следующей ДНФ:

.

Здесь представлены все возможные конъюнктивные термы, которые могут входить в ДНФ представления f(x₁, x₂, x₃). Коэффициенты К с различными индексами являются неопределенными и подбираются так, чтобы получающаяся после этого ДНФ была минимальной. Если теперь задавать всевозможные наборы значений аргументов < x₁, x₂, x₃ > и приравнивать полученное после этого выражение (отбрасывая нулевые конъюнкции) значению функции на выбранных наборах, то получим систему 2³ уравнений для определения коэффициентов К:

Пусть функция f задана таблично, тогда значения функции на конкретных наборах определяет значения правых частей системы (2.1). Если на наборе функция равна нулю, то в правой части соответствующего уравнения будет стоять нуль. Для удовлетворения этого уравнения необходимо приравнять нулю все коэффициенты К, входящие в левую часть рассматриваемого уравнения.

Рассмотрев все наборы, на которых данная функция обращается в нуль, получим все нулевые коэффициенты К. В уравнениях, в которых справа стоят единицы, вычеркнем слева все нулевые коэффициенты. Из оставшихся коэффициентов приравняем единице коэффициент, определяющий конъюнкцию наименьшего возможного ранга, а остальные коэффициенты в левой части данного уравнения примем равными нулю. Единичные коэффициенты К _i определят из (2.1) соответствующую ДНФ.

Более подробно метод неопределенных коэффициентов изложен в [3, стр. 194-195] и [4, стр. 57-60].

 

Метод Рота:

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

Более подробно метод Рота изложен в [6, стр. 95-108] и [2, стр.195-236].

 

Минимизация булевых функций, представленных в других базисах:

Все рассмотренные ранее методы минимизации относились в тому случаю, когда функция описывалась операциями булева базиса (конъюнкция, дизъюнкция и отрицание). Задача минимизации может быть сформулирована и для случая любого другого базиса (см. подраздел 2.7).

Общая идея минимизации булевых функций, представленных в других базисах, описана в  [4, стр. 69-71]. В [3, стр. 207-210] и [4, стр. 77 -84] описаны методы минимизации булевых функций, представленных в монофункциональных базисах (базисы Вебба (Пирса) и Шеффера). Минимизация функций в базисе Жегалкина рассматривается в [4, стр. 71-77], а в базисе (Å, &, ù ) – в [3, стр. 203-207].

 

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

⇐ Предыдущая12345678910Следующая ⇒

Поделиться: