Упорядоченные бинарные диаграммы решений

Введение

Данная работа посвящена изучению одного из представлений булевой функции, а именно упорядоченной бинарной диаграмме решений (УБДР).

Булева алгебра появилась в XIX в., но и по сей день является востребованной. Большинство логиков того времени либо игнорировали, либо резко критиковали систему Буля, но ее возможности оказались настолько велики, что она не могла долго оставаться без внимания. Через некоторое время стало понятно, что система Буля хорошо подходит для описания электрических переключателей схем. Это первым из ученых осознал американский логик Чарлз Сандерс Пирс и применил теорию для описания электрических переключательных схем. Ток в цепи может либо протекать, либо отсутствовать, подобно тому, как утверждение может быть либо истинным, либо ложным. А еще несколько десятилетий спустя, уже в ХХ столетии, ученые объединили созданный Джорджем Булем математический аппарат с двоичной системой счисления, заложив тем самым основы для разработки цифрового электронного компьютера.

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

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

Представление должно быть каноническим.

Представление должно быть минимальным.

И чтобы этим представлением можно было легко манипулировать.

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

Безусловно, самый эффективный метод представления булевой алгебры, известный до настоящего времени — это метод УБДР (OBDD метод), разработанный Брайантом, о котором и идёт речь в данной работе.

Данная работа состоит из трёх глав и одного приложения: первая глава посвящена основным понятиям, необходимым для изучения УБДР, в которой кратко описывается булева алгебра, способы представления булевых функций. Вторая глава посвящена непосредственно самим УБДР и состоит из трёх параграфов: в первом параграфе вводится понятие бинарных диаграммах решений, указывается влияние порядка переменных на размер БДР на основании чего вводится понятие УБДР, во втором параграфе рассматриваются операции на УБДР, а в третьем изучается проблема временных и рабочих характеристик УБДР. Третья глава посвящена решению задач при помощи УБДР. Рассматривается задача о сжатии черно-белых изображений, известная шахматная задача о расстановке ферзей на доске, и задача применения УБДР для обработки запросов в реляционных базах данных.

Приложение к данной дипломной работе содержит программные модули на языке Pascal, и носит характер прикладного применения .

Глава 1. Предварительные сведения

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

Базовым понятием булевой алгебры является понятие высказывания, под которым понимается любое утверждение, рассматриваемое только с точки зрения его истинности или ложности. В булевой алгебре не существует истинно-ложных или ложно-истинных высказываний. Высказывание можно рассматривать как логическую переменную, которая может принимать различные значения, например, высказывание «сегодня понедельник» будет истинным в понедельник и ложным во все остальные дни недели. Исчисление высказываний как раз и основано на том, что их можно рассматривать как двоичные переменные, которые могут принимать одно из двух своих значений. Примерами двоичных логических переменных являются разряды чисел, представленных в двоичной системе счисления; замкнутый или разомкнутый контакт; наличие или отсутствие тока в цепи; высокий или низкий потенциал в какой-либо точке схемы и т. п.

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

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

1.1.1 Булева алгебра Булевой алгеброй называется произвольное множество элементов, для которых определены две операции — сложение и умножение[3], сопоставляющие каждым двум элементам a и b их сумму и произведение; определена операция «отрицание», сопоставляющая каждому элементу a новый элемент (-a); имеются два «особых» элементов 0 и 1 и выполняются следующие правила:

· коммутативные законы:

· ассоциативные законы:

· идемпотентные законы:

· дистрибутивные законы:

· отрицание отрицания:

· для 0:

· для 1:

· правила де Моргана:

Замечание 1. Для определения алгебры Буля можно обойтись лишь одной из операцией сложения или умножения вместе с операцией отрицания, например, умножение можно определить: (через правила де Моргана).

Замечание 2. Это определение «неэкономно». Многие свойства могут быть выведены из других, но эта система непротиворечива и удобна для исследования.

1.1.2 Арифметические модели булевых операций Известному немецкому математику и логику Эрнесту Шредеру пришло в голову предложить в качестве знака для обозначения ложного суждения цифру О, что, конечно, привело к обозначению истины цифрой 1. Тогда таблица истинности приобретает некий арифметический вид:

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

Логические идеи Буля в последующие годы получили дальнейшее развитие. Логические исчисления, построенные в соответствии с идеями Буля, находят сейчас широкое применение в приложениях математической логики к технике, в частности к теории релейно-контактных схем. В современной алгебре есть булевы кольца, булевы алгебрыалгебраические системы, законы композиции которых берут свое начало от исчисления Буля. В общей топологии известно булево пространство, в математических проблемах управляющих систем — булев разброс, булево разложение, булева регулярная точка ядра.

Через некоторое время стало понятно, что система Буля хорошо подходит для описания электрических переключателей схем. Ток в цепи может либо протекать, либо отсутствовать, подобно тому, как утверждение может быть либо истинным, либо ложным. А еще несколько десятилетий спустя, уже в ХХ столетии, ученые объединили созданный Джорджем Булем математический аппарат с двоичной системой счисления, заложив тем самым основы для разработки цифрового электронного компьютера.

1.1.3 Булева функция Булева функция, функция алгебры логики, — функция аргументы которой, равно как и сама функция, принимают значения из двухэлементного множества (обычно)[3]. Булева функция является одним из основных объектов дискретной математики, в особенности тех её разделов, которые входят в математическую логику и математическую кибернетику. Булевы функции возникли при математической постановке задач логики и были названы по имени Дж. Буля, положившего начало применению математики в логике.

При решении различных задач, связанных с булевыми функциями, существенным моментом является способ задания (или представления) булевой функции. Имеется целый ряд таких способов: таблицы, формулы, специальные классы формул, называемые нормальными формами, УБДР (упорядоченное бинарное дерево решений).

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

Таблица истинности (валентности).

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

Таблица 1 носит также название сокращённой таблицы истинности. В полной (Таблица 2) также указывается результат выполнения каждой операции, входящей в состав булевой функции). Столбец справа — результат функции.

Таблица 2.

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

Представление булевых функций с помощью формул Определение 4.

Булева формула — композиция любого количества элементарных булевых функций

0, p, p, 1, p q, p q, p q, p q, p q, p q, p q.

Булевы связки — это знаки, ,, ,, , и .

Формулы записываются не в виде обычной композиции функций, например, F7 (F2 (p), q) или p q (p (p), q), а гораздо более просто: с помощью булевых связок. Последние формулы выглядят как p q.

Значение булевой функции зависит от расстановки скобок. Например, формулы (p) q и (p q) имеют разные значения при p q 1. Используя соглашение о приоритете связок, лишние скобки обычно опускают. Перечислим булевы связки в порядке убывания их старшинства: 1), 2), 3), 4), 5). Связки, и имеют одинаковый следующий 6-й. Например, формулы p q и (p) q не различаются.

Совершенные нормальные формы Литерал — переменная p или ее отрицание p. Конъюнкт (дизъюнкт) — конъюнкция (дизъюнкция) n 0 литералов. Простой, или приведенный, конъюнкт (дизъюнкт) не содержит одинаковых переменных. Пары конъюнктов (дизъюнктов) p F и p F (p F и p F), F и F G (F и F G), где F и G — некоторые конъюнкты (дизъюнкты), называются дублирующими.

n_арный простой конъюнкт (дизъюнкт) состоит из n литералов.

Константа 0 (1) называется пустым дизъюнктом (конъюнктом).

Дизъюнктивная нормальная форма (ДНФ) — дизъюнкция конечного числа разных конъюнктов, конъюнктивная нормальная форма (КНФ) — конъюнкция конечного числа разных дизъюнктов.

Простая, или приведенная, ДНФ (КНФ) состоит из простых конъюнктов (дизъюнктов). Простая ДНФ (КНФ) называется минимальной, если она не содержит никаких двух конъюнктов (дизъюнктов), равных по какому-нибудь литералу.

Совершенная ДНФ — СДНФ (СКНФ) состоит из простых конъюнктов (дизъюнктов), имеющих одинаковое число литералов. n-арная СДНФ (СКНФ) имеет n-арные простые конъюнкты (дизъюнкты).

Константа 0 (1) называется пустой ДНФ (КНФ) Существуют также графические методы представления булевых функций в виде графов.

1.2 Деревья и их свойства Связанный ациклический граф называется деревом. Дерево называется корневым, если в нём выделена вершина, которая называется корнем. Из определения дерева выплывает такая теорема.

Теорема 1.3.1

Граф является деревом тогда и только тогда, когда любые две его вершины связаны лишь одним ребром.

Доказательство.

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

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

Следствие1.3.1.1.

Если Т — дерево и и — его конечная вершина, то граф — дерево.

Действительно, граф — подграф дерева Т, для которого выполняются все условия теоремы 1.3.1.

Следствие1.3.1.2.

Всякое непустое дерево имеет как минимум две конечные вершины и одно конечное ребро.

Ребро связанного графа называется важным, если его исключение не ведёт к нарушению связности этого графа.

Следствие1.3.1.3.

В дереве каждое ребро важное.

Доказательство вытекает из того, что если исключить ребро в дереве Т, то поскольку вершины u и v соединяются одним ребром, будем иметь два компонент связности: один содержит вершину и, второй — вершину v. Значит, граф Т не является связанным.

Теорема 1.3.2.

Если — дерево и вершина, то граф, где и — произвольная вершина из V, тоже дерево.

Доказательство.

Поскольку Т — дерево, то существует единственное ребро, которое соединяет произвольную вершину с вершиной. Поскольку вершина, то введение одного конечного ребра приводит к тому, что с каждой вершины имеем только одно ребро, которое соединяет вершины и. Из теоремы 1.3.1 граф является деревом.

Перечисленные выше свойства деревьев подытоживает следующая теорема.

Теорема 1.3.3.

Пусть граф Т имеет п вершин. Тогда эквивалентными являются такие утверждения:

Т является деревом.

Т не имеет циклов и имеет ребро.

Т — связанный граф и имеет ребро.

Т — связанный граф, и каждое его ребро является мостом.

Любые две вершины графа Т соединены ровно одним простым ребром.

Т не имеет ни одного цикла, но введение нового ребра в Т влечёт возникновению ровно одного цикла.

Доказательство.

Случай, когда, очевидный. Пусть .

. Индукция по числу п. Для утверждение очевидно. Поскольку Т не имеет циклов, то исключение любого ребра из Т (согласно следствию) ведёт к разбитию Т на два подграфа, каждый из которых — дерево. По индуктивному предположению у каждого из этих подграфов рёбер на единицу меньше, чем вершин. Значит, число всех рёбер в Т равняется .

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

. Исключение любого ребра из Т ведёт к графу, у которого вершин и ребра. Но такой граф, из следствия, не может быть связным.

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

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

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

Следствие 1.3.3.1.

Пусть — лес с вершинами и компонентами; тогда имеет рёбер.

Доказательство.

Из условия 2 теоремы 1.3.3 следует, что каждый компонент имеет ребро. Но тогда число рёбер в будет:, что и требовалось доказать.

Часто возникает вопрос: сколько можно построить разных деревьев порядка. Ответ на этот вопрос даёт теорема Кели.

Теорема 1.3.4. (Кели) Число разных деревьев, которые можно построить на вершинах, равняется .

Доказательство.

Пусть и — дерево. По следствию из теоремы 1.3.1 в Т должны быть конечные вершины. Пусть — первая из них и — соответственное им ребро. Исключим из Т это ребро и вершину, обозначим в множестве вершину и занесём её в список вершин, который с начала является пустым. По следствию из теоремы 1.3.1 полученный граф снова является деревом. Применим к нему ту же самую процедуру, получим новое дерево и список и т. д. Эту процедуру используем до тех пор пока после исключения ребра не останется единственное ребро. Тогда список однозначно определяется деревом Т, и двум разным деревьям Т и с вершинами отвечают разные списки. Каждая вершина появляется в списке — 1 раз.

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

Поскольку разных элементов в списке может быть не больше, то этим мы и доказали теорему Кели.

Глава 2. Упорядоченные бинарные диаграммы решений (УБДР), их построение и операции над ними

2.1 Упорядоченные бинарные диаграммы решений Рассмотрим одно из современных представлений булевых функций, которое приобрело широкое использование в практическом применении. Упорядоченные бинарные диаграммы решений (УБДР) или в английской транскрипции Odered Binary Decision Diagrams (OBDD) являются достаточно простыми и самое главное эффективными представлениями булевых функций.

Под булевой функцией будем понимать m-арную функцию над множеством, где каждый элемент может принимать одно из двух значений 0 или 1 и называется алфавитом булевых переменных. Из этого следует, что область значений булевой функции от т аргументов конечна и состоит ровно из элементов.

УБДР позволяют манипулировать с булевыми функциями более просто и эффективно с точки зрения сложности вычисления на ЭВМ.

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

Пример.

Пусть булева функция задана такой таблицей истинности.

Тогда дерево решений будет иметь такой вид (см. рис. 2.2.1).

При помощи этой таблицы строим дерево булевой функции, которое называется деревом решений. Каждая вершина дерева решений v обозначается символом переменной и имеет дуги, которые ведут к сыновьям: сын (дуга обозначенная пунктиром) отвечает значению переменной 0 и сын (дуга показана сплошной линией) отвечает значению переменной 1. Все вершины-листки дерева обозначены константами 0 или 1. Для заданного распределения логических значений (интерпретаций) переменных, путь в дереве, который отвечает этому распределению, ведёт от корня дерева к вершине-листку, обозначение которой есть значение функции f. Например, путь отвечает распределению логических значений переменных, для которого значение функции равняется 1.

Из приведённого примера видно, что переменные булевой функции упорядочены относительно такого порядка:

если и некоторая внутренняя вершина дерева решений, а v — её наследник, то .

Лемма 2.1.1.

Для всех, для всех.

Доказательство.

По индукции. Предположим, что лемма верна для всех q таких, что. Для конечных случаев, тривиально. Для нетривиальных случаев, пусть, где. Рассмотрим два случая и. В первом случае и. Эти два равенства эквивалентны по индуктивному предположению для. Для случая, когда, анaлогично.

Эта несложная лемма показывает, что OBDD является каноническим представлением Булевой функции. Это значит, что каждая Булева функция представляется некоторым единственным OBDD.

Теорема 2.1.1.

Если р и р' элементы OBDD (V). Тогда, если.

Доказательство.

Предположим одновременной индукцией для и .Мы предполагаем, что условие теоремы выполняется для всех q и q', где и. Предположим, что .

Рассмотрим первый случай, где. Любые p и q — оба конечные, (в случае, когда или) или они оба не конечные, и. Для не конечных, мы имеем, и подобным образом. Отсюда, по индукции, и, так .

Рассмотрим второй случай, где. Из этого следует, что р это не конечный. Из леммы 1,. Поэтому,, так. По индукции, где. Это — противоречие, однако, если l и h — не различны, то p не находится в OBDD (V).

Симметрично получается и в случае, когда .

Теорема 2.1.2.

Возьмём функцию, существует такое, что.

Доказательство.

По индукции возьмём i очень большое число такое, что. По индуктивной гипотезе, существуют р и r в OBBD (V) такие, что и. Дальше q и r различны, получается из. Т.о. получаем .

Опр. УБДР называется сокращенной, если для любой внутренней вершины v ее 0-сын и 1-сын не совпадают;

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

Теорема 2.1. УБДР D является сокращенной тогда и только тогда, когда к ней не применимо ни преобразование СВВД, ни преобразование ИЛТ.

Доказательство.

Если к D применимо преобразование ИЛТ, то не выполнено условие (1) из определения сокращенной УБДР, а если к D применимо преобразование СВВД, то поддиаграммы с корнями v и w являются изоморфными и не выполнено условие (2).

Пусть к УБДР D нельзя применить преобразование ИЛТ. Тогда в ней нет вершин с совпадающими 0- и 1-сыновьями и выполнено условие (1). Пусть к УБДР D нельзя применить преобразование СВВД. Тогда из следующей леммы можно заключить, что в D нет пары вершин, поддиаграммы которых являются изоморфными, и следовательно, выполнено условие (2).

Лемма 2.1. Если в D есть такая пара вершин u и v, для которых поддиаграммы с корнями v и w являются изоморфными, то в D имеется и пара вершин v', w' с попарно одинаковыми 0- и 1-сыновьями и, следовательно, к D применимо преобразование СВВД.

Доказательство леммы проведем индукцией по высоте h поддиаграмм Dv и Dw с корнями v и w, соответственно (так как Dv и Dw изоморфны, то их высоты, т. е. длины максимальных путей из корней до стоков, одинаковы).

Базис: h=1. В этом случае 0- и 1-сыновьями вершин v и w являются одинаковые листки.

Шаг индукции. Предположим, что утверждение верно для h=k. Пусть Dv и Dw — поддиаграммы высоты h=k+1. Пусть v и w — это 0-сыновья вершин v и w, соответственно, а v и w — их 1-сыновья. Если v= w и v= w, то в качестве v', w' подходят сами v и w. Если же для некоторого i {0,1} vi =wi, то поддиаграммы

и

с корнями vi и wi являются изоморфными и имеют высоту k. Тогда по предположению индукции утверждение леммы выполнено.

Теорема 2.2.

Применение к произвольной УБДР преобразований СВВД и преобразований ИЛТ строит сокращенную УБДР, эквивалентную исходной УБДР D.

Эта сокращенная УБДР является при данном порядке переменных единственной (с точностью до изоморфизма) и минимальной.

Доказательство первого пункта непосредственно следует из выполнения критерия теоремы 2.1, так как к результирующей диаграмме неприменимо ни преобразование СВВД, ни преобразование ИЛТ.

Доказательство второго пункта основано на следующем индуктивном утверждении:

Лемма 2.1. После выполнения i-ой итерации алгоритма в полученной диаграмме для каждой подфункции f (?, ?,…, ?, x, …, x) (?{0, 1} при k=1,2,…, i-1), существенно зависящей от x, имеется ровно одна вершина — корень поддиаграммы, реализующей эту подфункцию.

Напомним, что функция f (x, …, x) существенно зависит от переменной x, если существуют такие два набора значений аргументов (?, …, ?, 0, ?,…, ?) и (?, …, ?, 1, ?,…, ?), различающиеся только значением x, на которых f принимает разные значения: f (?, …, ?, 0,?, …, ?) f (?, …, ?, 1,?, …, ?).

В дереве, изображенном на рис. 2.1.1., переменные упорядочены таким образом:. БДР с заданным порядком на переменные называется упорядоченным БДР. В общем порядок переменных может быть произвольным и алгоритмы обработки таких УБДР будут корректными, но на практике выбор подходящего порядка является существенным, поскольку от порядка зависит эффективность манипуляции с УБДР. Теперь рассмотрим преобразования, при помощи которых выполняется редукция дерева решений в УБДР. Таких преобразований существует три:

Склеивание листов-дубликатов (СЛД): исключаем все листья дерева решений кроме одного, которые обозначены одной и той же константой, и переориентируем все входящие дуги исключенных вершин на вершину-листок, который остался.

Склеивание внутренних вершин дубликатов (СВВД): если внутренние вершин и и v дерева решений такие, что, то исключаем одну из этих вершин и переориентируем все входящие дуги на вторую вершину, которая осталась.

Исключение лишних тестов (ИЛТ): если внутренняя вершина v такая, что, то исключаем вершину v и переориентируем все входящие дуги на вершину .

Начиная с некоторого дерева решений, переменные которого упорядочены относительно некоторого порядка, и применяя преобразования СЛД, СВВД и ИЛТ, всегда можно редактировать это дерево в УБДР. Например, дерево решений, изображённое на рис. 2.1.1., редактируется в такое УБДР.

Следует обратить внимание, на то что правила преобразования нужно выполнять повторно, поскольку после каждого преобразования могут появится условия для выполнения другого условия.

Основные свойства УБДР:

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

Данная булева функция выполняется тогда и только тогда, когда УБДР, которое её представляет, имеет листок, обозначенный 1.

Булева функция представляет собой тавтологию тогда и только тогда, когда УБДР, которое её представляет, имеет единственный листок, обозначенный 1.

Если булева функция не зависит от переменной х, то её УБДР не включает ни одной вершины, обозначенной символом переменной х.

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

Размеры УБДР, как показывает пример УБДР, изображённый на рис. 2.1.2, зависит от выбранного порядка. Если этот порядок выбран неудачно, то УБДР может иметь большие размеры, в то время если для другого порядка размеры УБДР будут небольшими. Ниже на рис. 2.1.2 изображены УБДР, которые представляют булеву функцию относительно порядка и порядка .

Если обобщить данную функцию на переменных, т. е. рассмотреть функцию, то УБДР для этой функции относительно порядка имеет внутренних вершин (а всех) — по одной на каждую переменную. УБДР для этой же самой функции относительно порядка имеет внутренних вершин. Уже для разница в представлении существенная: первая УБДР имеет 8 внутренних вершин, а вторая — 30.

Приведённый факт ставит вопрос: существует ли такой способ выбора подходящего порядка? Ответ на этот вопрос является неоднозначным — в одном случае хорошим является один порядок, в другом случае — хорошим является другой порядок. В большинстве применений УБДР порядок выбирается с самого начала или ручным способом, либо при помощи какого-нибудь эвристического анализа системы, которая представляется УБДР. Следует отметить, что выбор порядка при помощи какой-нибудь эвристики не обязательно будет оптимальным, но каким бы ни был этот порядок, он не влияет на правильность результата. Но если найден такой порядок, который не приводит к экспоненциальному росту УБДР, то операции на УБДР становятся достаточно эффективными.

Существующие методы определения хорошего порядка переменных можно классифицировать на три вида:

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

Методы исчерпывающего поиска. Эти методы дают точный результат — оптимальный порядок (один из оптимальных порядков), при котором структура имеет минимальный из возможных размеров.

2.2 Операции на УБДР Перейдём к традиционным обозначениям операций на множестве булевых функций. Символом + и • обозначаются соответственно операции дизъюнкции и конъюнкции, а символами и обозначают безальтернативную дизъюнкцию и отрицание соответственно. Дополнительно будет использоваться символ для операции дополнения операции безальтернативной дизъюнкции. Символы и обозначают соответственно сумму (дизъюнкция) и произведение (конъюнкция) булевых выражений. Константы 0 и 1 рассматриваются как нольарные операции. Все эти операции определены на множестве булевых функций. Это означает, что когда f и g булевы функции, то, , и являются булевыми функциями над тем же самым множеством булевых функций. Рассмотрим некоторые традиционные и нетрадиционные операции над булевыми функциями.

Сужение функции. Функция, полученная в результате приписывания фиксированного значения некоторому аргументу х, называется сужением функции. Если заданны два сужения функции f относительно переменной х, то для функции f имеет место такое равенство:

.

Пример.

Пусть задана функция, тогда

и .

Тогда, Суперпозиция функций получается в результате подстановки некоторой булевой функции g вместо переменной х в булевой функции f. Тогда, используя равенство (1), можно записать Пример.

Пусть заданы функции:

и

Тогда непосредственная подстановка даёт такую функцию:

.

Теперь воспользуемся равенством:

.

Для вычисления. Как известно из предыдущего примера

и

отсюда получаем Операции квантификации для булевых функций. Эти операции вводятся при помощи таких равенств:

Пример.

Пусть задана такая функция Тогда квантифицированная функция относительно переменной, которая может принимать только два значения 0 и 1, принимает значение 1 тогда и только, когда функции, либо, либо обе вместе принимают значение 1. Отсюда следует, что Аналогично и для квантификации: эта функция принимает значение 1, тогда и только тогда, когда функции и принимают значения 1. Отсюда следует, что:

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

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

Построение и манипуляции с УБДР.

Символьные операции над булевыми функциями с применением УБДР можно рассматривать как соответствующие алгоритмы на графах, которые представляют эти УБДР. Важным свойством этих алгоритмов является то, что они сохраняют порядок на переменных — если аргументами некоторой операции есть УБДР с определённым порядком для переменных, то результат выполнения этой операции будет УБДР, которая сохраняет этот же порядок. Отсюда следует, что можно выполнять произвольные как угодно сложные последовательности операций на УБДР, не нарушая заданного порядка для переменных.

APLY — операция.

APLY — операция строит булеву функцию при помощи применения алгебраических операций к функции-аргументов.

Пусть f и g — функции-аргументы и — некоторая бинарная операция (), тогда APLY — операция строит функцию. APLY — операция является основной при выполнении символьных манипуляций с булевыми функциями. При помощи этой операции можно ввести дополнение функции f — .

Рассмотрим вместе с функциями f и g также «don't care» условия, которые определяются при помощи функции равняется 1 для тех значений х, для которых значение функции несущественно. Для проверки эквивалентности функций f и g для всех «care» условий необходимо вычислить функцию и убедиться в том, что результат есть функция 1.

APLY — алгоритм выполняет соединение двух графов-аргументов глубины 1 при использовании двух хеш-таблиц. Первая из этих таблиц служит для повышения эффективности вычислений, а вторая — для построения максимально редактированного графа-результата. Отметим, что когда другие представления булевых функций требуют приведение редукции к нормальной форме как отдельного шага, УБДР представление позволяет строить каноническую форму сразу.

Для иллюстрации этой операции воспользуемся примером использования APLY — алгоритма для построения УБДР для операции +, применённой к функциям и, каждая из которых представлена УБДР на рис. 2.2.1

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

.

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

Равенство (*) составляет основу рекурсивной процедуры для вычисления УБДР, которая представляет функцию. Например, применение APLY-алгоритма к УБДР, изображённых на рис. 2.2.1., генерирует УБДР, которая изображена ниже на рис. 2.2.2.А (соответствующая ей УБДР — на рис. 2.2.2.В, а редактированная УБДР — на рис. 2.2.2.С).

Это построение выполняется следующим образом. Каждый шаг вычислений определяется корневыми вершинами графов-аргументов. Пусть функции f и g представлены УБДР, корни которых соответственно. В том случае, когда конечные вершины-листки, обозначены константой, рекурсия заканчивается и получаем вершину, которая обозначена этой константой. В рассмотренном выше примере такими вершинами были А4, В3 и А5, В4.

Если какая-нибудь из вершин не являются конечными, то выбираем переменную x, которая связывает эти вершины. Выбор такой переменной выполняется по такому правилу:

.

УБДР для такой функции вычисляются рекурсивно для сужения функций f и g для значения 0 (пунктирная дуга) и для значения 1 (целая дуга) соответственно. В рассмотренном примере начало вычислений для вершин А1, В1 приводит к рекурсивному вычислению для вершин А2, В2 и А6, В5.

Для того, чтобы эффективно использовать APLY-алгоритм необходимо сделать дополнительные некоторые уточнения. Первое уточнение необходимо для генерации результата в случае, когда одна из вершин графиков-аргументов является листком и представляет доминирующее значение (1 для операции + и 0 для операции *). В этом случае вызов рекурсивной процедуры не нужен, поскольку результатом является вершина, обозначенная доминирующим значением. В рассмотренном примере такими были пары вершин А5, В2 и А3, В4.

Второе уточнение необходимо для того, чтобы исключить повторных рекурсивных вызовов для одной и той же пары вершин. С этой целью делаем структуру данных в виде хеш-таблицы для сохранения уже построенных пар. При этом вершины представляют собой ключ, при помощи которого в этой таблице находятся пара вершин и построенная вершина-результат для этой пары. При существовании такой хеш-таблицы начало вычислений начинается с проверки для двух аргументов u и v, есть или нет пара с ключом key (u, v) в таблице. Если такая пара уже существует, то результатом будет построенная вершина, которая отвечает этой паре. Если не существует такой пары, то в таблицу записывается пара вершин (u, v) с ключом key (u, v) и выполняются вычисления, описанные выше для пары (u, v), и после законченных вычислений результат записывается в хеш-таблицу с тем же ключом. В рассмотренном примере повторный вызов APLY-операции возникал для вершин А3, В2 и А5, В2.

Каждый шаг вычислений вычисляет как результат вершину в графе, который строится. Структура рекурсивных вычислений естественным способом определяет граф, который не редактируется. Это делается так, что каждый шаг вычислений вычисляет вершину, обозначенную символом переменной, которая связывает вершины-аргументы, и которая имеет сыновей, которые являются результатами рекурсивных вызовов. В рассмотренном примере это граф, изображённый на рис.5А. Для того, чтобы сгенерировать редактированный граф непосредственно, каждый шаг вычислений пытается избежать возникновения новой вершины путём использования соответствующих правил преобразований (СЛД, СВВД, ИЛТ). Пусть переменная х есть переменная, которая связывает вершину, на некотором шаге вычислений. Потом проверяем, есть ли в уже построенном графе вершина v такая, что. Эта проверка выполняется при помощи другой хеш-таблиц, которая включает все внутренние вершины в уже построенном графе и когда v такая вершина, то она имеет ключ. Если такая вершина в хеш-таблице есть, то она возвращается алгоритмом как результат. В противоположном случае вершина заносится в хеш-таблицу, достраивается до графа и возвращается как результат работы алгоритма. Аналогично и конечные вершины заносится в хеш-таблицу, но ключом является обозначением данной вершины. Новая конечная вершина генерируется только тогда, когда её обозначение отсутствует в таблице. В рассмотренном примере процесс избегает построения вершин-дубликатов для таких пар вершин А5, В2 и А3, В4. А сам граф, представлен на рис.5С, строится непосредственно. Напомним, что этот граф представляет функцию, которая есть результатом применения операции + к двум функциям-аргументам.

Использование хеш-таблицы даёт возможность избежать повторных вычислений для данной пары вершин и ограничить сложность APPLY-алгоритму, а также оценить размеры графа-результата. Действительно, допустим, что функции f и g представлены УБДР, которые имеют соответственно вершин. При этих допущениях может быть как максимум одиночных вызовов алгоритма для пар аргументов и каждый из этих вызовов добавляет максимум одну вершину к графу, который строится. Использование хеш-таблиц даёт возможность каждый шаг вычислений выполнять как константу. Следовательно, как сложность алгоритма, так и размер построенного графа пропорциональна величине .

Операция сужения.

Вычисление суженной булевой функции, которая представлена некоторой УБДР, выполняется чрезвычайно просто. Для того, чтобы ограничить значения переменной до значения, необходимо лишь переориентировать каждую выходную дугу вершины, где, или на для, или на для. На рис. 2.2.3 А показана перестроенная УБДР для сужения функции относительно переменной для. В начальной УБДР (на рис. 2.2.3 В) все входящие дуги вершины обозначенной переориентированы на вершину и вершины обозначенные, убираются. В результате получаем граф, изображённый на рис. 2.2.3 С.

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

Вычисление сужения функции, которая представлена УБДР с вершинами, требует как минимум рекурсивных вызовов. Каждый из этих вызовов создаёт как минимум одну вершину в графе, который строится. Использование хеш-таблиц делает каждый рекурсивный шаг константой. Значит, как сложность алгоритма, так и размер графа, который строится, выражается величиной .

2.3 Временные и рабочие характеристики Как было показано, большое число операций над булевыми функциями можно выразить и вычислить с помощью алгебраических операций и операций сужения. APPLY — алгоритм и алгоритм вычисления сужения дают возможность вычислять и другие операции. Больше того, для каждой из таких операций и сложность алгоритмов и размерность полученных графов ограничены некоторым полиномом от сложности и размеров аргументов-функций. Пусть для функции величина обозначает размер УБДР, которое её представляет. Для заданных двух функций и и условий, выраженных при помощи функции, можно вычислить эквивалентность и для условий за время. Таким способом можно вычислить и суперпозицию функций и при помощи двух вызовов алгоритма для операции сужения и трёх вызовов APPLY — алгоритма. Сложность такого вычисления выражается величиной. Наконец, вычисление операции квантификации относительно переменной для функции можно выполнить за время. Значит, все такие операции можно вычислить таким способом и алгоритмы имеют полиномиальную сложность как во времени, так и в размере УБДР, которое представляет аргументы этих функций.

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

Преимущество первое заключается в том, что поскольку графы имеют приемлемые размеры, то и вычисления остаются в приемлемых рамках .

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

Если сравнивать этот подход с другими подходами представления и манипуляции с булевыми функциями, то практически всем этим подходам не хватает свойства «грациозной деградации». Действительно, даже тогда, когда функция имеет приемлемые размеры своего представления, то её дополнение может иметь экспоненциальные размеры.

Глава 3. Применение УБДР

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

Рассмотрим пример алгоритма компрессии изображений, который нацелен на уменьшение размера изображений путем поиска повторяющихся фрагментов в изображении. Т.о., BDD может оказаться удобной структурой данных для представления сжатых изображений. Представляет интерес реализация такого метода сжатия изображений на основе BDD и сравнение его с другими комбинаторными методами — методом квадродеревьев и др. Необходимо определить, что в случае изображения будет функцией переменных. Mike Starkey и Randy Bryant в статье «Using OBDD for compressing images and image sequences» предложили представить изображение функцией своих координат. Следуя правилу BDD о выборе левой или правой ветви в зависимости от значения бита переменной, для построения BDD используется бинарное представление координат изображения.

На Рис. 1 изображено простое черно-белое изображение и координаты его пикселей. Для построения BDD выбираем порядок переменных для этого 4×4 изображения такой: Х0, Y0, Х1, Y1. Полученная BDD представлены на Рис. 3. Если расширить диапазон значений в листьях, то с помощью BDD можно представлять и цветные изображения. Наиболее эффективен метод для квадратных изображений. Если высота W и ширина H изображения различны, то метод также применим: находится наибольшая координата, прямоугольник достраивается до квадрата, внешние для изображения пиксели закрашиваются некоторым фоновым цветом Теперь пусть мы имеем набор изображений, состоящих из одного образца, многократно повторяющегося, см. Рис. 3. В этом случае их BDD будут одинаковы, т. к. дополнительные переменные, соответствующие новым координатам, не влияют на цвет пикселя и будут выброшены при операции приведения BDD.

Данное представление изображения не вносит в изображение потерь. Алгоритмы без потерь не дают больших коэффициентов сжатия. Требуется рассмотреть возможность сжатия с потерями изображений на основе BDD.

3.2 Задача о восьми ферзях Одной из самых знаменитых математических задач на шахматной доске, наряду с задачей о ходе коня, является задача о восьми ферзях. Если задачей о ходе коня занимался великий математик Леонард Эйлер, то задача о восьми ферзях привлекала внимание другого великого математика — Карла Гаусса.

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

Очевидно, больше восьми мирных ферзей (как и ладей) на обычной доске расставить невозможно. Найти какое-нибудь расположение восьми ферзей, не угрожающих друг другу, легко (на рис. 2.1 представлены четыре искомые расстановки). Значительно труднее подсчитать общее число расстановок, в чем, собственно, и состоит задача.

Рис. 2.1. Задача о восьми ферзях.

Она была впервые поставлена в 1848 г. немецким шахматистом М. Беццелем, который нашел 60 решений. После этого Гаусс заинтересовался задачей и нашел 72 решения. Полный же набор решений, состоящий из 92 позиций, получил все тот же Ф. Наук. Эта хронология установлена известным немецким исследователем математических развлечений В. Аренсом.

Строгое доказательство того, что 92 решения исчерпывают все возможности, было получено лишь в 1874 г. английским математиком Д. Глэшером (при помощи теории определителей). Существенных решений (не совпадающих при отражениях и поворотах доски) имеется только двенадцать.

Известно много способов организовать эффективный поиск расположения восьми мирных ферзей (методы Пермантье, Ла-Ное, Гюнтера, Глэшера, Лакьера и др.).

Из каждого решения задачи о ферзях можно получить ряд других при помощи поворотов (вращений) доски на 90, 180 и 270°, а также при ее зеркальном отражении относительно линий, разделяющих доску пополам.

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

1) см. рис. 1.2.а;

2) см. рис. 1.2.б;

3) a4, b1, c5, d8, e6, f3, g7, h2;

4) a4, b2, c5, d8, e6, f1, g3, h7;

5) a4, b2, c7, d3, e6, f8, g1, h5;

6) a4, b2, c7, d3, e6, f8, g5, h1;

7) a3, b5, c2, d8, e6, f4, g7, h1;

8) a4, b1, c5, d8, e2, f7, g3, h6;

9) a4, b7, c3, d8, e2, f5, g1, h6;

10) a6, b4, c2, d8, e5, f7, g1, h3;

11) a4, b8, c1, d5, e7, f2, g6, h3;

12) a4, b2, c7, d5, e1, f8, g6, h3.

Остальные 80 расстановок получаются из этих двенадцати при помощи поворотов и отражений доски. Основная расстановка на рис. 1.2.б является симметрической, другие одиннадцать основных расстановок — простыми. Итак, всего на доске имеем 11· 8+1·4=92 расстановки восьми ферзей, не угрожающих друг другу.

Нам эта задача интересна с той точки зрения, что её можно представить через логическую формулу. Сопоставим каждой клетке шахматной доски логическую переменную, j, где i — номер строки, j — номер столбца. Переменная принимает значение 1, если ферзь находится на соответствующей позиции. Теперь наложим ограничения. Если ферзь стоит на определенной клетке, то на этой горизонтали, вертикали и диагонали не может быть других ферзей. Запишем это для клетки (i, j):

.

Более того, в любой строке должен быть хотя бы один ферзь:

.

Искомая логическая формула — это конъюнкция всех полученных условий.

2.3 Применения УБДР для обработки запросов в реляционных базах данных Реляционные базы данных (РБД), являясь важнейшей составной частью информационных систем, предназначены для хранения и обработки больших объемов информации, в которых общая структура данных представлена в виде таблицы, где каждая запись содержит информацию, относящуюся только к одному конкретному объекту. Каждая строка (кортеж) соответствует логической записи, а заголовки столбцов являются названиями полей (элементов). Это позволяет описывать данные с их естественной структурой, обеспечивать математическую основу для интерпретации выводимости, избыточности и непротиворечивости отношений. Составление запросов по РБД в традиционном для их создания языке манипулирования данными SQL на данном этапе развития информационных технологий отвечает всем необходимым требованиям к составлению запросов, то есть с его помощью можно найти любую информацию в РБД по любым параметрам. Однако с ростом количества обрабатываемой информации применение SQL-запросов перестаёт удовлетворять одному из главных требований — наиболее быстрому возможному поиску данных. Ведь с ростом размера любой базы данных увеличивается и время поиска в ней необходимых сведений, что связано с возрастанием числа операций необходимых для выполнения. Напомним, что SQL-реализация запроса построена по следующему принципу: запрос составляется в виде некоторого логического выражения, истинность которого проверяется подстановкой имеющихся значений полей в конкретных записях, хранящихся в РБД. Если значение логического выражения — истина, то проверяемая запись соответствует условиям запроса и выносится в результат. Недостатком данного метода является проверка всех условий запроса для любой записи, что приводит к экспоненциальному росту количества операций с увеличением количества полей и записей в РБД.

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