Manipulations on Large Variables Boolean Functions .pdf Булевым пространством размерности n принято называть множество, составленное из 2й булевых n-компонентных векторов, на котором определено отношение соседства - два вектора являются соседними, если они различаются значениями ровно в одной компоненте. Его можно представить графом, вершины которого соответствуют элементам булева пространства, а ребра соединяют вершины, соответствующие соседним элементам. Такой граф принято называть n-мерным кубом, и он широко используется в учебной литературе, при описании методов минимизации булевых функций и решения других задач логического проектирования. Однако уже при n > 5 изображение графа становится слишком громоздким и неудобным для практического использования, в чем можно убедиться, глядя на рис. 1.Более приемлемым с точки зрения программиста является представление булева пространства размерности n в виде булева 2"-вектора, т. е. вектора с 2й компонентами, соответствующими элементам пространства и пронумерованными стандартным образом, начиная с нуля: компоненте с номером k соответствует элемент пространства, представляющий собой n-компонентный булев вектор, задающий двоичный код номера k. Приписывая этим компонентам значения из множества {0, 1}, можно задать любую булеву функцию от n переменных. Например, булев векторf = 10000000 00000000 00001000 00000001 10000000 00000000 00110000 00000001 определяет некоторую булеву функцию f шести переменных x\, x2, x3, x4, x5, x6, принимающую значение 1 на следующих наборах их значений:000000, 010100, 011111, 100000, 110010, 1100011, 111111.Для удобства визуального восприятия вектор f разбит на восемь фрагментов, соответствующих интервалам булева пространства с внутренними переменными x4, x5, x6 и представляющих коэффициенты дизъюнктивного шенноновского разложения функции f по переменным x1, x2, x3.Булевы 2"-векторы служат основными объектами преобразований, проводимых при решении разнообразных логико-комбинаторных задач, которые возникают при проектировании дискретных устройств и разработке систем искусственного интеллекта [1]. С целью повышения эффективности их программирования в данной статье предлагается базисный набор макроопераций над такими векторами, названный POBS (Parallel Operations in Boolean Space).Как показывает опыт, этот набор оказывается весьма эффективным, позволяя быстро оперировать на современной персоналке с длинными булевыми векторами, представляющими произвольные булевы функции многих переменных, до 27 переменных включительно. Заметим, что для однострочной распечатки такого вектора (содержащего 227 = 134 217 728 символов) потребовалась бы бумажная лента длиной свыше 250 километров.1. Покомпонентные операции над булевыми векторамиПростейшими операциями набора POBS служат покомпонентные операции: операция инвертирования над одним вектором и произвольные двухместные булевы операции над парой одноразмерных векторов. Проиллюстрируем их следующими примерами.Обозначим через g и h булевы векторы, представляющие булевы функции g(x) и h(x), где x = (xi, x2, x3, x4, x5). Пустьg = 10001100 00100010 11100001 00101010, h = 00110010 10001111 01100011 01100011.Тогдаg =01110011 11011101 00011110 11010101,g v h =10111110 10101111 11100011 01101011,g л h = 00000000 00000010 01100001 00100010,g 9 h = 10111110 10101101 10000010 01001001 и т. д. Более сложной является операция перестановки аргументов булевой функции, представленной булевым 2"-вектором. Она определяется перестановкой на множестве номеров переменных и приводит к соответствующей перестановке компонент вектора.Например, в результате перестановки номеров (4, 2, 1, 3) переменные множества x = (xb x2, x3, x4) перегруппируются в новую последовательность (x4, x2, xx, x3). Это приводит к соответствующей перестановке компонент вектора f, представляющего булеву функцию f (x). Компонента f помещается на месте с номером i, если двоичный код k номера k представляет собой результат произведения матрицы перестановок P на двоичный код i номера i. Другими словами, вектор k равен покомпонентной дизъюнкции столбцов матрицы P, отмеченных единицами в векторе i. Проиллюстрируем это на примере замещения компоненты f13 компонентой /|4:Pik1000111201001131000х 0= 1400101012341314В результате перестановка (4, 2, 1, 3) на множестве компонент вектора x приводит к следующей перестановке на множестве компонент вектора f:(0, 8, 1, 9, 4, 12, 5, 13, 2, 10, 3, 11, 6, 14, 7, 15).Пусть f = 0111 1010 0100 1001. Тогда рассматриваемая перестановка на множестве компонент этого вектора приводит к его значению f*, соответствующему новому порядку (x4, x2, xx, x3) перечисления аргументов:f* = 0100 1110 1110 0001.2. Операции над соседними элементами в булевом пространствеВ набор POBS входят также операции взаимодействия различных компонент в пределах одного булева 2"-вектораf, задающего функцию f(x) = f(xb x2, xn). Главную роль играют при этом операции над соседними элементами булева пространства. Соседними называются булевы n-векторы, различающиеся значениями ровно в одной компоненте. При представлении булева пространства в виде многомерного булева куба они отображаются вершинами, соединенными ребрами.Использование операций над соседними элементами позволяет параллелить логические вычисления и тем самым ускорять их. Эта идея не нова. Так, в 1961 -1962 гг. в Сибирском физико-техническом институте разрабатывалась специальная приставка к универсальной вычислительной машине, существенно ускоряющая процесс решения задач логического проектирования и названная L-машиной[2, 3]. В ее основу положена идея распределенного в пространстве выполнения логических операций на серии информационных полей, играющих роль своеобразных регистров. Они структурно подобны десятимерному булевому кубу и позволяют непосредственно представлять булевы функции десяти переменных и выполнять покомпонентные операции над ними. Одно из полей называется основным, и в нем могут совершаться преобразования в пределах одной функции. Схемная реализация основного поля обеспечивает одновременное выполнение любой двухместной булевой операции в пределах каждой из 512 пар элементов поля, соседних по некоторой выбранной переменной.Аналогичная идея была положена в основу коммутационной машины, предложенной У.Д. Хиллисом в 1978 г. и разработанной компанией Thinking Machine Corporation в 1985 г. Эта машина обеспечивает информационную связь в многопроцессорном компьютере, компоненты которого непосредственно связаны между собой аналогично вершинам n-мерного булева куба. Передача информации между любыми процессорами в таком компьютере производится не более чем за n тактов. На базе этой разработки была создана серия коммутационных машин, которые используются исследователями, работающими в области искусственного интеллекта, для решения задач логического вывода [4].При значении n, превышающем 5, вектор f удобно задавать булевой матрицей размером 25 х 2й-5, представляя ее 32-элементные строки словами в памяти машины (что естественно для большинства современных компьютеров). В этом случае любые два соседние по переменной xk элемента пространства M находятся в пределах одного слова, если k < 6, и принадлежат различным словам в противном случае, что должно учитываться при программировании. Заметим, что при иллюстрации приводимых ниже примеров используются более компактные матрицы размером 2 х 2 .Введем следующие простейшие операции преобразования булевой функции f (x) = f (xb x2, xn), заданной вектором f, путем взаимодействия соседних элементов:f - k - присвоение значения 0 аргументу xk (получение функции f(xk = 0));f + k - присвоение значения 1 аргументу xk (получение функции f(xk = 1)).Продемонстрируем их выполнение на следующих матрицах, в которых показано разбиение множества элементов на две части, соответствующие различным значениям выбранной переменной xk и называемые ниже условно левой (отмеченной полужирным шрифтом) и правой:ff-4f+40110110101011110 | 0010010000010110 | 1100101001110001|| 01000101 110100110110011001010101 0010001000010001 1100110001110111 0100010011011101 1101110111101110 0100010001100110 1010101000010001 01010101001100110110110101011110 | 0010010000010110| 1100101001110001|| 01000101110100111 2 f0110110101011110 0010010000010110 0110110101011110 0010010000010110f-11100101001110001 0100010111010011 1100101001110001 0100010111010011f+1При выполнении операции f - к оба элемента в каждой паре соседних по переменной xk элементов получают значения из левой части, при выполнении операции f + к - из правой. Если n < 6 (на данном примере n < 5) эта операция реализуется посредством соответствующего сдвига (с вытеснением) столбцов в матрице, в противном случае - путем сдвига строк.В порядке обобщения введем следующие операции, в которых вместо скаляра к используется n-компонентный булев вектор и:f - и - присвоение значения 0 всем аргументам xk, которым соответствуют компоненты uk вектора и со значением 1,f + и - присвоение значения 1 всем аргументам xk, которым соответствуют компоненты uk вектора и со значением 1.Первая из этих операций может интерпретироваться как получение начального коэффициента f дизъюнктивного шенноновского разложения функции / по всем переменным множества и (все такие переменные получают значение нуль), вторая - как конечного коэффициента (переменные получают значение единица).Например, если n = 8 и и = 01100010, то операция f - и эквивалентна композиции (f - 2) - 3) - 7 , а операция f + и эквивалентна композиции ((f + 2) + 3) + 7 . При этом одно и то же значение присваивается переменным x2, x3 и x7 .Введем также операцию симметрирования S f * к, при выполнении которой оба соседних по переменной xk элемента в каждой паре получают одинаковое значение, в результате применения двухместного оператора *, выбираемого из множества (v, л, , Ф, ...}, к исходным значениям этих же элементов. Эта операция также сводится к рассмотренным выше, посколькуS f * к = f - к) * f + к).Например,fSfffilSfv30110110101011110 | 0010010000010110 | 1100101001110001|| 01000101110100111010011100101111 0110000111000101 1010011100101111 0110000111000101 0111111101111111 0011011000110110 1111101111111011 11010111110101111 2В частности, операция S f Ф к представляет хорошо известную операцию дифференцирования булевой функции по переменной xk.Операция симметрирования S f * к также обобщается путем использования вектора и вместо скаляра к. При этом она представляется выражением S f * и и эквивалентна последовательности операций S f * к;, в которой скаляры к представляют номера единичных компонент вектора и. В этом случае оператор * выбирается из множества (v, л, Ф}.Например, если и = 010011, то операция S f л и эквивалентна выражениюS(S(S f л 2) л 5) л 6.Ее можно интерпретировать так: все элементы фрагмента вектора f , соответствующего конъюнкции xj x3 x4 , получают значение 0, если и только если хотя бы один из них был равен 0.3. Операции преобразования размерности булевых векторовТакие операции позволяют реализовать взаимодействие булевых векторов различной размерности.Рассмотрим два булевых вектора:n-вектор и с к единицами, отмечающими некоторые к переменных из множества X = (xj, x2, . ■ ■, xn),2к-вектор h, задающий булеву функцию h отмеченных переменных.Введем в набор POBS операцию h х и переноса функции h в фрагмент пространства n переменных, соответствующий конъюнкции инверсий переменных, не отмеченных в и. Все элементы остальных фрагментов получают при этом значение 0.Пусть, например, n = 5, и = 01101 и h = 10010011.Тогда строится 25-вектор, в котором выделяется фрагмент, соответствующий конъюнкции xj x4:00000000 00000000 00000000 00000000,и в последний вписывается вектор h. В результате получаем:hxu = 10000100 00001100 00000000 00000000.По аналогии вводится операция f : и, осуществляющая обратный перенос информации из упомянутого фрагмента в вектор h, задающий получаемую при этом булеву функцию h от к переменных. Так, если u = 01010 иf = 00110010 11100000 11100110 00011101,то находится фрагмент, соответствующий конъюнкции xj x3 x5:00 110010 11 100000 11100110 00011101,и содержащаяся в нем информации используется для построения искомого вектора:h = f: и = 0111.Если известно, что представленная вектором f функция f зависит лишь от переменных множества и (остальные оказываются фиктивными), то посредством операции f : и они удаляются из функции и результат представляется вектором h.4. Операции над частичными булевыми функциямиПерейдем к рассмотрению частичных булевых функций, широко используемых при решении задач логического проектирования.Произвольную частичную булеву функцию f от n переменных обычно представляют соответствующим 2"-компонентным троичным вектором f -, однако при разработке программ удобнее задавать ее парой булевых векторов f1 и f 0, также 2"-компонентных. При этом единицами в векторе f1 отмечаются компоненты, на которых функция f принимает значение 1, а в векторе f 0 - компоненты, на которых функция равна нулю.Пусть, например,f-= 1-001010 011--01-1.Тогдаf1= 10001010 011000101, f0= 00110101 100001000.В этом случае операция присвоения значения 0 аргументу xk будет представляться парой операций f1- k , f0- k, а значения 1 - парой f1 + k , f0 + k.Подобно вектору f, используемому во введенных выше операциях, вектор u также может оказаться троичным, например, представляя некоторую элементарную конъюнкцию, и тогда его также целесообразно заменить на пару булевых векторов u1 и u0, в данном случае n-компонентных. Например, в операции дизъюнктивного разложения частичной булевой функции f по всем переменным объединенного множества u1 u и0 получение коэффициента при представленной таким образом конъюнкции осуществляется серией операций1 0 0 0 1 1 0 1 f - u , f - u , f + u , f + u .5. Программирование в базисе POBSПродемонстрируем технику программирования в базисе POBS на примерах решения некоторых задач теории булевых функций.1. Проверка частичной булевой функции на монотонностьРассмотрим частичную булеву функцию fx) = (x1, x2, xn), заданную двумя множествами наборов значений аргументов: множеством M1, на котором она принимает значение 1, и множеством где она принимает значение 0. Назовем ее монотонной, а точнее, положительной функцией, если для любой пары наборов p е M1 и q е M выполняется условие p > q (вектор p больше вектора q), т.е. для любой пары (pt, qt) одноименных компонент pt > qt и хотя бы для одной пары pt > qt .Очевиден простой метод проверки функции на монотонность, основанный на переборе всех пар (p, q) и проверке для каждой из них условия p > q . Однако с увеличением числа переменных n и соответственным ростом мощностей множеств M1 и M0 такой метод оказывается слишком трудоемким. Более эффективен предлагаемый ниже метод, использующий операции из набора POBS.Зададим функцию f (x) двумя булевыми 2"-векторами: вектором f 1 и f 0. Элементы множества M1 представлены единицами в векторе f1. Обозначим через M* множество таких элементов булева пространства, каждый из которых больше некоторого элемента из множества M0, и представим это множество вектором f *.Утверждение 1. Функция f (x) монотонна, если и только если f * f 0 = 0.Вектор f можно найти с помощью введенных выше операций набора POBS, последовательностью n шагов. Сначала получим вектор f 2 = f 1 - 1) vf 1, который представит множество M1, дополненное элементами булева пространства, соседними «сверху» к некоторым элементам из M1 по переменной x1. Затем полученное множество расширим аналогичным образом по следующей переменной x2 : f 3 = (f 2 - 1) v f 2. Затем, повторив эту операцию по всем остальным переменным, получим искомый вектор f n1 = f *.Пусть, например, n = 5:f1 = 00010000 00100000 00000001 00001010, f0 = 11000010 00000100 10100000 10000000.В этом случае процесс последовательного расширения множества M1, приводящий к получению вектора f *, представляющего множество M*, отобразится следующей последовательностью векторов, получаемых на очередных шагахf2 = 00010000 00100000 00010001 00101010 , f3 = 00010000 00110000 00010001 00111011 , f4 = 00010001 00110011 00010001 00111011 , f5 = 00010001 00110011 00010001 00111011 , f6 = 00010001 00110011 00010001 00111111 = f * .Покомпонентная конъюнкция полученного вектора с вектором11000010 00000100 10100000 10000000 f0равна нулю f * л f 0 = 0), следовательно, рассматриваемая булева функция монотонна.2. Поиск функциональных закономерностейВ современных информационных технологиях важную роль играют процедуры извлечения знаний из потока данных, т. е. поиска закономерностей, позволяющих находить правильные решения при решении интеллектуальных задач [5]. Ниже рассматривается частный, но важный случай закономерностей, а именно функциональные закономерности, хорошо зарекомендовавшие себя в естествознании.В работе [6] была решена следующая задача. Допустим, что задано множество объектов, представленных различными комбинациями значений n двоичных признаков (признак есть - признака нет). Спрашивается, можно ли всегда однозначно определить значение некоторого выделенного признака, если известны значения остальных? А если можно, то как это сделать?Представим исходную информацию совокупностью R некоторых элементов в n-мерном булевом пространстве M = {0, 1}" над множеством признаков. Эти элементы задают известные объекты, и их можно рассматривать как корни некоторого булева уравнения F = 1 с переменными из множества x = (x1, x2, ..., xn).Говорят, что уравнение F = 1 разрешимо относительно некоторой переменной, если ее можно представить булевой функцией от остальных переменных уравнения, определенной на множестве R [5]. Рассмотрим задачу выявления таких переменных в уравнении F = 1 и построения соответствующих функций.Утверждение 2. Необходимым и достаточным условием разрешимости уравнения F = 1 относительно переменной x, является отсутствие в множестве R пар наборов, соседних по переменной x, .Доказательство от противного (по правилу modus tollens): если найдется такая пара, то переменная x, принимает в ней различные значения на одинаковых наборах значений остальных переменных, что противоречит определению функционального отношения.Обозначим через f (x) характеристическую булеву функцию множества R, положив, что f (qj) = 1, если q,- е R иf (qj) = 0, если q g R. Через f (x; = 0) и f (x; = 1) обозначим результат замены в функции f (x) переменной x, на константу 0 или 1 соответственно.Утверждение 3. Уравнение F = 1 разрешимо относительно переменной x;, если и только если f (x; = 0) л f (x; = 1) = 0.Это утверждение позволяет применить для проверки разрешимости уравнения по переменной x; введенные выше векторные операции f - i и f + i. Переформулируя утверждение в терминах этих операций, можно утверждать, что необходимым и достаточным условием разрешимости уравнения F = 1 относительно переменной x, является выполнение отношенияf - i) л f + i) = 0.При выполнении этого условия возникает задача нахождения соответствующей булевой функции, которая в общем случае оказывается частичной, и ее оптимального доопределения. Оптимизация может заключаться как в минимизации числа аргументов функции, так и в упрощении ее алгебраического представления, например в дизъюнктивной нормальной форме (ДНФ).Рассмотрим первую из этих задач. Она аналогична задаче минимизации безусловного диагностического теста и может решаться тем же методом. Некоторый аргумент xk может быть определен как фиктивный, если после его удаления уравнение остается разрешимым по переменной x;. Операцию удаления аргумента xk можно представить как расширение множества R по этой переменной, т. е. как следующее преобразование его характеристической функции ff :=fx* = 0) v fx* = 1).В терминах введенных выше векторных операций оно определяется как S f v k, откуда следуетУтверждение 4. Аргумент x* можно удалить из числа аргументов переменной x, как функции остальных переменных, если и только если((S f v k) - i) л ((S f v k) + i) = 0.3. Последовательная композиция булевых функцийРассмотрим следующую задачу. На множестве аргументов x = (x1, x2, xn) булевыми n-векторами u, w и v задано разбиение на три непересекающиеся подмножества u, w и v : x = u и w и v. Заданы также две булевы функции h(u, w) и g(x, w, v), представленные соответствующими булевыми векторами h и g. Требуется вычислить их композицию при условии x = h(u, w) и представить полученную при этом булеву функцию fx) 2"-вектором f.Такая композиция, называемая неразделительной последовательной двухблоч-ной, иллюстрируется примером на рис. 2, где n = 6 и множества u = (x1, x2), w = (x3, x4) и v = (x5, x6) заданы шестимерными булевыми векторами u = 110000, w =001100 и v=000011.Положим, что функции h(u, w) и g(x, w, v) заданы соответствующими векторами:h = 1101001001101100,g = 0011010011001001 1010010110101011.Для удобства последующих рассуждений вектор g разбит на две половинки, задающие значения функции g(x, w, v) при значениях 0 и 1 двоичной переменной x.Х2h-4Ix3x6>fРис. 2. Пример неразделительной последовательной двухблочной композицииПредставим булево пространство переменных x = (u, w, v) в следующем виде:Vi V20000 0000 0000 0000 | 0000 0000 0000 0000 | 0000 0000 0000 0000|| 0000 0000 0000 0000U2Затем последовательно отобразим в это пространство функции g, h0 и h1 , вво-дя при этом дополнительные фиктивные переменныеиз множеств v и u и пред-ставляя результаты 2"-векторами a, b и с:h х (u, w) - v = a1000 1000 0000 1000 1111 1111000011110000 0000 1000 0000 0000 0000111100000000 1000 1000 0000 0000 1111111100001000 1000 0000 0000 1111 111100000000g0 х (w, v) - u = b0011 0100 1100 1001 0011 0100110010010000 0000 0000 0000 0011 0100110010010000 0000 0000 0000 0011 0100110010010000 0000 0000 0000 0011 010011001001g1 х (w, v) - u = с1010 0101 1010 1011 1010 0101101010110000 0000 0000 0000 1010 0101101010110000 0000 0000 0000 1010 0101101010110000 0000 0000 0000 1010 010110101011В заключение находим вектор f, представляющий искомуюкомпозициюфункций h(u, w) и g(x, w, v):a b v a c = f0011 0100 0000 1001 0000 0000 1010 00000011 0100101010010000 0000 1100 0000 1010 0101 0000 10111010 0101110010110000 0100 1100 0000 1010 0000 0000 10111010 0100110010110011 0100 0000 0000 0000 0000 1010 10110011 0100101010114. Проверка частичной булевой функции на декомпозируемость по заданному разбиению на множестве аргументовДопустим, что известна частичная булева функция f (x) от n переменных, заданная троичным вектором f -. Требуется проверить ее на разделимость по нестрогому разбиению u/v на множестве x, т.е. узнать, существуют ли такие функции h(u, w) и g(x, w, v) от меньшего числа переменных, что f (x) = g(h(u, w), w, v), где w = x \ (u и v).Заметим, что при положительном ответе на этот вопрос можно упростить логическую схему, реализующую функцию f(x) (например, при логическом синтезе в базисе элементов LUT (look up tables), реализующих функции ограниченного числа переменных).Известно необходимое и достаточное условие декомпозируемости полностью определенной функции f(x) по разбиению u/v, которое должно выполняться для каждого коэффициента f (u, v) дизъюнктивного разложения Шеннона функции f(x) по переменным множества w : коэффициенты дизъюнктивного разложения этих коэффициентов по переменным множества u должны принимать не более двух различных значений.Коэффициенты f (u, v) дизъюнктивного разложения Шеннона частичной булевой функции fx) по переменным множества w будем представлять фрагментами T, - троичными матрицами, строки которых соответствуют различным значениям вектора u, а столбцы - различным значениям вектора v. Элементами фрагментов служат соответствующие компоненты троичного вектора f -. Условие разделимости функции f(x) по разбиению u/v сформулируем теперь следующим образом: для каждого коэффициента f (u, v) возможно такое доопределение соответствующей матрицы T (замена значений «-» на 0 или 1), при котором ее строки примут не более двух различных значений.В работе [7] показано, что проверка этого условия сводится к проверке на би-хроматичность графов ортогональности строк каждой из матриц T,. Там же предложен эвристический алгоритм, гарантирующий получение правильного решения при условии связности рассматриваемых графов (это условие обычно выполняется). Троичный вектор f - представляется в нем соответствующей парой булевых векторов f 1 и f 0. Эффективно используются операции над соседями, обеспечивающие одновременную проверку всех 2w| фрагментов T;.Алгоритм старается разбить множество строк в каждом фрагменте на два класса A и B взаимно совместимых строк. Над исходными векторами f 1 и f 0 реализуется последовательность преобразований, результаты которых представляются булевыми 2"-векторами a 1 и a 0.Алгоритм итеративен. Первая итерация начинается с построения класса A путем включения в него первой строки фрагмента. Эта операция сводится к последовательности подстановок значения 0 на места переменных, образующих множество u:00 a :=f - u,a 1 := f 1 - u.Затем в каждом фрагменте находится множество строк, ортогональных первой строке, и отмечается в булевом векторе b:b := S (h f1 v h 1f0) v v.Полученные множества образуют классы B и проверяются на совместимость:a 0 := S f 0b) v u; a 1 := S (f 1b) v u.Если при этом a 0 a 1 Ф 0, то некоторое из рассматриваемых множеств оказывается несовместимым, откуда следует, что граф ортогональности строк соответствующего фрагмента не бихроматичен и, следовательно, функция f(x) не декомпозируема по разбиению u/v.Если же a 0 a 1 = 0, реализуется следующая итерация. Классы A дополняются строками, ортогональными некоторым из строк классов B, и проверяются на совместимость. Затем аналогичным образом могут быть расширены классы B и т.д. Алгоритм заканчивает работу при выполнении определенного числа итераций.

Скачать электронную версию публикации