Способ минимизации дизъюнктивных нормальных форм булевых функций
Автор: Песков Роман Николаевич, Щенников Владимир Николаевич
Журнал: Инженерные технологии и системы @vestnik-mrsu
Рубрика: Алгебра и геометрия
Статья в выпуске: 4, 2010 года.
Бесплатный доступ
Рассмотрена задача минимизации булевых функций в классе дизъюнктивных нормальных форм. Приведено описание метода, использующего разложение в виде декомпозиционного дерева, для поиска простых импликант. По импликант-ной матрице строится система ограничений и составляется задача линейного программирования. Предложено использовать разбиение системы ограничений в случае большого количества переменных.
Короткий адрес: https://sciup.org/14719576
IDR: 14719576
Текст научной статьи Способ минимизации дизъюнктивных нормальных форм булевых функций
СПОСОБ МИНИМИЗАЦИИДИЗЪЮНКТИВНЫХ НОРМАЛЬНЫХ ФОРМ БУЛЕВЫХ ФУНКЦИЙ
Р. Н, Песков, В. Н. Щенников
Рассмотрена задача минимизации булевых функций в классе дизъюнктивных нормальных форм- Приведено описание метода, использующего разложение в виде декомпозиционного дерева, для поиска простых импликант. По импликант-ной матрице строится система ограничений и составляется задача линейного программирования. Предложено использовать разбиение системы ограничений в случае большого количества переменных.
Существует большое количество алгоритмов минимизации булевых функций в классе ДНФ. Их обзор и классификация достаточно полно даются в [3]. Переформулировка задачи минимизации в терминах целочисленного линейного программирования приведена в работе [2]. В настоящей статье предлагается модификация этого метода, которая ускоряет поиск минимальной ДНФ.
Прежде, чем воспользоваться аппаратом линейного программирования, необходимо найти все простые импликанты булевой функции. Введем определения из [1]:
Определение 1. Булева функция д = s(ti, ...дЖп) называется импликантой булевой функции / = Дш,..., тД, если па любом наборе значений переменных xi,..., хп, на котором значение функции д равно единице, значение функции / также равно единице.
Определение 2. Простой импликантой функции / называется всякое элементарное произведениед ~ х^х^.-.хц, являющееся им-пликаптой булевой функции /, и такое, что никакая его собственная часть (т. е. произведение, получающееся из произведения д вы брасыванием одного или нескольких сомножителей iij) уже не является импликантой функции /.
Для поиска простых импликант в работе [2] предлагается использовать алгоритм Куайна-Мак-Класки, который является наиболее распространенным. В настоящее время существует способ разложения булевой функции в виде декомпозиционного дерева [4}, который имеет меньшую временную сложность, чем алгоритм Куайна-Мак-Класки.
Декомпозиция есть разбиение функции / на две функции Д и ft, которые определяются положительным и отрицательным значениями входной переменной т,:
/о = /(^-1з ■ ■ - з т,—1, 0, Жг-^1, - - - , Zfc)
D1' ■ W
/1 f^$h • ■ ■ ,Xi-l, I,Xt+l, - . - , Тй).
Декомпозиция DtDj - это комбинация Dt-й и Dj-й декомпозиции:
/оО /(^-11 * * ■ ; Xi — 11 б, Xj-^. 1, . . . , Tj —1,0, X j + 1, - ■ ■ , Zfc )
Zpi / (^11 ■ ■ ■ > -®i — li6,Z^i,...,X,'— 1,1, 21j+i, . . . , Zk)
DiDj : (2)
/10 J (*^11 ■ ■ ■ з Ti —1, 1, Zj-|-1, . . , , Xj— 1,0, Zj-|-1, . , . , Xfc)
/11 J ("^ 1, ■ • ■ f Xi — 1, 1, Zj-f-1, . . . , Tj — 1, 1, Tja 1 r ■ ■ ■ з Xk )-
Полное описание алгоритма приводится в [4]. Здесь используем его только для опреде ления всех простых импликант в описываемом примере.
Пусть функция / четырех переменных задана последовательностью нулей и единиц своих значений: 1101010110001100. Будем также получать функции у,, = /о A f{,i = 1,4. Первый уровень дерева будут составлять декомпозиции Di, D2, Ds, D4.
11010101 |
11011000 |
11011011 |
10001010 |
Di : Л1О0О1100; О2 |
: Л01011100; j |
Оз : Л01010000; |
04 : ЛИ 110010. |
gi = 10000100 |
92 = 01011000 |
дз = 01010000 |
94 = 10000010 |
Второй уровень: |
|||
1000 |
1001 |
1000 |
|
D12 : |
Л0100; /Да : |
Л0000; П14 : |
лоощ |
#12 - |
= 0000 913 |
= 0000 914 |
= 0000 |
оно |
0010 |
0000 |
|
^23 : |
Л0100; Ю24 : |
Л1100; Р34 : |
л иоо. |
#23 : |
= 0100 924 |
= 0000 9з4 |
= 0000 |
При последующем разложении все функции д будут равны 00, поэтому нет необходимости построения третьего уровня.
По лемме 3.1 из [4]: если д^а^, ...^а^ = 1, то р = х^Т^-'-Х^ импликанта функции /, где
* х Xi, at = 0.
Тогда, учитывая, что часть импликант первого уровня будет поглощена импликан-тами второго уровня, для примера, описанного выше, получим 6 простых импликант: Х2Ж3Х4, Х2Х3Х4,11X3X4, Х1Х4,Х1Т2Хз, X1X2X3.
После того как все простые импликанты были определены, необходимо построить им пликантную таблицу. Импликаптная таблица функции / представляет собой прямоугольную таблицу, строки которой обозначаются различными простыми импликантами функции f, а столбцы - наборами значений переменных, па которых функция обращается в едшЕицу (копституентами единицы). Правило заполнения импликантной таблицы следующее: на пересечении р-й строки и А'-т столбца импликантной таблицы тогда и только тогда ставится метка, когда импликанта р составляет некоторую часть копституенты К (возможно совпадающую со всей конституеп-той).
Для примера, описанного выше, импли-кантная матрица имеет вид:
=1=2Т374 |
i1^2i:3z:4 |
х^^з *з®4 |
2,12=3=4 |
Т,Т2тЗ=4 |
Ti=2=3x4 |
ZL^З^З®^ |
T I ЕЕ 2 т 3^4 |
|
= 1=4 |
* |
* |
* |
* |
||||
=1=2=’з |
* |
+ |
||||||
=1=3®4 |
* |
* |
||||||
=2=»=4 |
* |
* |
||||||
T2S3X4 |
* |
* |
||||||
Ti^^a |
* |
Если в каком-либо столбце имеется только одна метка, то импликанта, стоящая в соответствующей строке, является существенной - без нее не может быть получено покрытие всего множества импликант данной функция. Так как существенные импликап-ты в любом случае должны входить в ми нимальную форму функции, то можно сразу включить их в минимальную форму и не рассматривать далее. Поэтому можно сократить количество операций, исключив из таблицы соответствующие им строки и столбцы тех коиституеит, которые покрываются ими. Для рассмотренного выше примера получим:
$ 1 з^2 ^3^4 |
ElE2i:gT4 |
Щ£ Я12Я!5ЯГ4 |
||
я^З^з |
* |
* |
||
^1^3 ^4 |
* |
* |
||
112^3*4 |
* - |
|||
^2 ^3^4 |
* |
* |
||
$1$2$3 |
* |
На втором этапе необходимо из простых импликант выбрать минимальное их количество так, чтобы покрывались все конституен-ты. Из таблицы получим систему ограничений
У^ ари, 5 Д J — 1? 2,..., t, (3) »=1
где коэффициент а^ равен 1 или 0 в зависимости от того, стоит ли метка в j-м столбце г-й строке импликантной таблицы, а и, соответствуют простым импликантам ре Для получения кратчайшей ДНФ минимизируется линейная форма

при условии системы ограничений (3) и что щ равно 1 или 0.
Для рассматриваемого примера система (3) и форма L будут следующие:
' U4 + Us > 1, U2 + U4 > 1, Ul + U2 5 Ij
, щ 4- из > 1.
L = ui + иг + из + ii4 + us-
Таким образом, получается задача целочисленного линейного программирования. В математическом пакете Mathematica с помощью функции LinearProgramming находим решение: ui — 1, иг = 0, из = 0, «4 = 1, us = 0. Отсюда следует, что в кратчайшую ДНФ будут входить первая и четвертая им-пликанты. Добавив их к существенной им-пликаите, определенной ранее, можно получить минимальную ДНФ:
271^2^3 V Я2Т3Т4 V Т1Т4.
В комментариях к [2] указано, что импли-кантная таблица будет иметь размеры поряд-ка т х t - 2" х 2" - ^1^(1-^ 0< е< lf
£ —> 0 при п -> оо [4]. Поэтому для функций большого количества переменных может потребоваться огромное количество вычислений. В таких случаях предлагается воспользоваться расчленением ограничений.
Пусть дана система ограничений (1): Ли > 1. Представим матрицу коэффициентов в виде

Л12
Л 22
Л32
Л1з
Л23
Лзз
Введем в рассмотрение матрицы Ai и Аг, т. е.
/ Ац А12 Y л _ / Л 22 Азз \ У А21 А22 / 2 \ ^32 А33 у
Матрица Ло = А22 ■
Получим две задачи линейного программирования:
Li = У^ u^ -> min i=l
Aiu(1) > 1
0 < ж(1) < 1
L2 = у^ ^F^ ~*m™
Аги^ > 1
0 < xW < 1.
Решив их, найдем L — Li + L^.
Переставляя строки в импликантной таблице таким образом, чтобы в матрицах А13 и Л31 было больше нулевых элементов, можно добиться, чтобы коэффициент оптимальности 5 — 7 был ближе к 1.
Список литературы Способ минимизации дизъюнктивных нормальных форм булевых функций
- Глушков В. М. Синтез цифровых автоматов/В. М. Глушков. -М. Физматгиз, 1962. -С. 264-267.
- Майстрова Т. Л. Линейное программирование и задача минимизации нормальных форм булевых функций/Т. Л. Майстрова//Проблемы передачи информации: Сб. -М.: АН СССР, 1962. -Вып. 12. -С. 5-15.
- Сапоженко А. А. Минимизация булевых функций в классе дизъюнктивных нормальных форм/А. А. Сапоженко, И. П. Чухров//Итоги науки и техники: Сб. -М.: ВИНИТИ, 1987. -Т. 25. -С. 68-116.
- Friedel М. The Decomposition Tree for analyses of Boolean functions/M. Friedel, S. Nikolajewa, T. Wilhelm//Math. Struct, in Comp. Science. -2008. -Vol. 18. -P. 411-426.