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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


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

Информация:

Тип работы: Диплом. Предмет: Математика. Добавлен: 21.01.2010. Сдан: 2010. Уникальность по antiplagiat.ru: --.

Описание (план):


59
Введение
Данная работа посвящена изучению одного из представлений булевой функции, а именно упорядоченной бинарной диаграмме решений (УБДР).
Булева алгебра появилась в XIX в., но и по сей день является востребованной. Большинство логиков того времени либо игнорировали, либо резко критиковали систему Буля, но ее возможности оказались настолько велики, что она не могла долго оставаться без внимания. Через некоторое время стало понятно, что система Буля хорошо подходит для описания электрических переключателей схем. Это первым из ученых осознал американский логик Чарлз Сандерс Пирс и применил теорию для описания электрических переключательных схем. Ток в цепи может либо протекать, либо отсутствовать, подобно тому, как утверждение может быть либо истинным, либо ложным. А еще несколько десятилетий спустя, уже в ХХ столетии, ученые объединили созданный Джорджем Булем математический аппарат с двоичной системой счисления, заложив тем самым основы для разработки цифрового электронного компьютера.
В конце ХХ столетия появляются так называемые экспертные системы. Экспертная система - это программа (на современном уровне развития человечества), которая заменяет эксперта в той или иной области. Экспертные системы предназначены, главным образом, для решения практических задач, возникающих в слабо структурированной и трудно формализуемой предметной области. Экспертные системы были первыми системами, которые привлекли внимание потенциальных потребителей продукции искусственного интеллекта. И в экспертных системах применяется булева алгебра.
Но с ростом мощности персональных компьютеров, возрастает сложность описания его схемы, его процессора. А экспертные системы решают более сложные задачи. Всё это приводит к сложным булевым функциям. И возникает вопрос как удобней представить булеву функцию:
Представление должно быть каноническим.
Представление должно быть минимальным.
И чтобы этим представлением можно было легко манипулировать.
Существует несколько представлений булевой функции (например, дизъюнктивная нормальная форма и конъюнктивная нормальная форма, таблица истинности и др.). Но данные представления перестали удовлетворять выше изложенным требованиям в связи со сложностью самих булевых функций.
Безусловно, самый эффективный метод представления булевой алгебры, известный до настоящего времени - это метод УБДР (OBDD метод), разработанный Брайантом, о котором и идёт речь в данной работе.
Данная работа состоит из трёх глав и одного приложения: первая глава посвящена основным понятиям, необходимым для изучения УБДР, в которой кратко описывается булева алгебра, способы представления булевых функций. Вторая глава посвящена непосредственно самим УБДР и состоит из трёх параграфов: в первом параграфе вводится понятие бинарных диаграммах решений, указывается влияние порядка переменных на размер БДР на основании чего вводится понятие УБДР, во втором параграфе рассматриваются операции на УБДР, а в третьем изучается проблема временных и рабочих характеристик УБДР. Третья глава посвящена решению задач при помощи УБДР. Рассматривается задача о сжатии черно-белых изображений, известная шахматная задача о расстановке ферзей на доске, и задача применения УБДР для обработки запросов в реляционных базах данных.
Приложение к данной дипломной работе содержит программные модули на языке Pascal, и носит характер прикладного применения .
Глава 1.Предварительные сведения
1.1 Булева алгебра
Теоретической базой при проектировании современных цифровых устройств, предназначенных для целей числовых вычислений, решения логических задач и задач управления, являются булева алгебра, двоичная арифметика и теория конечных автоматов. Логика - это наука о законах и формах мышления, математическая же логика занимается применением формальных математических методов для решения логических задач.
Базовым понятием булевой алгебры [2] является понятие высказывания, под которым понимается любое утверждение, рассматриваемое только с точки зрения его истинности или ложности. В булевой алгебре не существует истинно-ложных или ложно-истинных высказываний. Высказывание можно рассматривать как логическую переменную, которая может принимать различные значения, например, высказывание “сегодня понедельник” будет истинным в понедельник и ложным во все остальные дни недели. Исчисление высказываний как раз и основано на том, что их можно рассматривать как двоичные переменные, которые могут принимать одно из двух своих значений. Примерами двоичных логических переменных являются разряды чисел, представленных в двоичной системе счисления; замкнутый или разомкнутый контакт; наличие или отсутствие тока в цепи; высокий или низкий потенциал в какой-либо точке схемы и т.п.
Высказывание называется простым, если значение его истинности не зависит от значений истинности других высказываний, и сложным, если значение его истинности зависит от других высказываний[2]. Сложное высказывание можно рассматривать логической функцией, зависящей от простых высказываний и принимающей также два значения (истина, ложь). В свою очередь сложные высказывания могут служить переменными (аргументами) более сложных функций, т.е. при построении логических функций справедлив принцип суперпозиции.
Огромное значение для развития современной вычислительной техники сыграли работы английского ученого Джорджа Буля. Его теоретическая работа и введенные им операции над двоичными данными (логическое сложение, умножение и отрицание) стали теперь называться булевской (булевой) алгеброй. Современные микросхемы, использующиеся в компьютерах, выполняют с данными именно такие операции.
1.1.1 Булева алгебра
Булевой алгеброй называется произвольное множество элементов , для которых определены две операции - сложение и умножение[3], сопоставляющие каждым двум элементам a и b их сумму и произведение ; определена операция "отрицание", сопоставляющая каждому элементу a новый элемент (-a); имеются два "особых" элементов 0 и 1 и выполняются следующие правила:
· коммутативные законы:
· ассоциативные законы:
· идемпотентные законы:
· дистрибутивные законы:
· отрицание отрицания:
· для 0:
· для 1:
· правила де Моргана:
Замечание 1. Для определения алгебры Буля можно обойтись лишь одной из операцией сложения или умножения вместе с операцией отрицания, например, умножение можно определить: (через правила де Моргана).
Замечание 2. Это определение "неэкономно". Многие свойства могут быть выведены из других, но эта система непротиворечива и удобна для исследования.
1.1.2 Арифметические модели булевых операций
Известному немецкому математику и логику Эрнесту Шредеру пришло в голову предложить в качестве знака для обозначения ложного суждения цифру О, что, конечно, привело к обозначению истины цифрой 1 [4]. Тогда таблица истинности приобретает некий арифметический вид:
А
В
0
0
1
0
0
1
1
0
1
1
0
1
1
0
1
0
0
0
1
0
0
1
1
0
1
1
1
1
Оценивая суждения таким образом, мы находимся в двоичной системе исчисления. Т.к. теперь имеем дело с цифрами, естественно предположить, что и логические действия можно заменить арифметическими.
Отрицание
&
Конъюнкция
или
Дизъюнкция
или
Импликация
или
Эквиваленция
или
Ещё одно определение конъюнкции и дизъюнкции:
;
Логические идеи Буля в последующие годы получили дальнейшее развитие. Логические исчисления, построенные в соответствии с идеями Буля, находят сейчас широкое применение в приложениях математической логики к технике, в частности к теории релейно-контактных схем. В современной алгебре есть булевы кольца, булевы алгебры- алгебраические системы, законы композиции которых берут свое начало от исчисления Буля. В общей топологии известно булево пространство, в математических проблемах управляющих систем - булев разброс, булево разложение, булева регулярная точка ядра.
Через некоторое время стало понятно, что система Буля хорошо подходит для описания электрических переключателей схем. Ток в цепи может либо протекать, либо отсутствовать, подобно тому, как утверждение может быть либо истинным, либо ложным. А еще несколько десятилетий спустя, уже в ХХ столетии, ученые объединили созданный Джорджем Булем математический аппарат с двоичной системой счисления, заложив тем самым основы для разработки цифрового электронного компьютера.
1.1.3 Булева функция
Булева функция, функция алгебры логики, - функция аргументы которой, равно как и сама функция, принимают значения из двухэлементного множества (обычно )[3]. Булева функция является одним из основных объектов дискретной математики, в особенности тех её разделов, которые входят в математическую логику и математическую кибернетику. Булевы функции возникли при математической постановке задач логики и были названы по имени Дж. Буля, положившего начало применению математики в логике.
При решении различных задач, связанных с булевыми функциями, существенным моментом является способ задания ( или представления) булевой функции. Имеется целый ряд таких способов: таблицы, формулы, специальные классы формул, называемые нормальными формами, УБДР (упорядоченное бинарное дерево решений).
1.1.4. Способы представления булевых функций
Существуют различные способы представления булевых функций, которые более или менее удобны для применения, в зависимости от типа решаемой задачи. Ниже приведены различные способы представления булевых функций.
Таблица истинности (валентности).
(,,)
0
0
0
0
0
0
1
0
0
1
0
0
0
1
1
1
1
0
0
0
1
0
1
1
1
1
0
0
1
1
1
1
В таблице истинности указываются переменные булевой функции и результат самой функции от набора переменных, стоящих в соответствующей этому набору строке. Например, набору переменных (1,0,1) соответствует шестая строка, следовательно, значение функции для этого набора равно 1. Заметим, что наборы переменных не должны повторяться в таблице.
Таблица 1 носит также название сокращённой таблицы истинности. В полной (Таблица 2) также указывается результат выполнения каждой операции, входящей в состав булевой функции). Столбец справа - результат функции.
Таблица 2.
0
0
1
1
0
1
1
1
1
0
0
0
1
1
0
1
В целом такие таблицы удобны для наглядного представления, но с ростом количества переменных их построение становится весьма затруднительным.
Представление булевых функций с помощью формул
Определение 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
Граф является деревом тогда и только тогда, когда любые две его вершины связаны лишь одним ребром [2].
Доказательство.
Пусть граф является деревом. Если допустить существование больше одной связи, которая связывает любые две его вершины, то в таком графе существует цикл, т.е. данный граф не является деревом.
Наоборот, поскольку любые две вершины графа соединены ребром, то граф связанный, а из-за того, что это ребро единственно, то граф не имеет циклов. Следовательно, данный граф является деревом.
Следствие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) являются достаточно простыми и самое главное эффективными представлениями булевых функций [7].
Под булевой функцией будем понимать m-арную функцию над множеством , где каждый элемент может принимать одно из двух значений 0 или 1 и называется алфавитом булевых переменных. Из этого следует, что область значений булевой функции от т аргументов конечна и состоит ровно из элементов.
УБДР позволяют манипулировать с булевыми функциями более просто и эффективно с точки зрения сложности вычисления на ЭВМ.
Бинарная диаграмма решений (БДР) представляет булеву функцию в виде корневого ацикличного графа. Для пояснения этого представления воспользуемся примером.
Пример.
Пусть булева функция задана такой таблицей истинности.
0
0
0
0
0
0
1
0
0
1
0
0
0
1
1
1
1
0
0
0
1
0
1
1
1
1
0
0
1
1
1
1
Тогда дерево решений будет иметь такой вид (см. рис.2.2.1).
59
При помощи этой таблицы строим дерево булевой функции, которое называется деревом решений. Каждая вершина дерева решений v обозначается символом переменной и имеет дуги, которые ведут к сыновьям: сын (дуга обозначенная пунктиром) отвечает значению переменной 0 и сын (дуга показана сплошной линией) отвечает значению переменной 1. Все вершины-листки дерева обозначены константами 0 или 1. Для заданного распределения логических значений (интерпретаций) переменных, путь в дереве, который отвечает этому распределению, ведёт от корня дерева к вершине-листку, обозначение которой есть значение функции f. Например, путь отвечает распределению логических значений переменных , для которого значение функции равняется 1.
Из приведённого примера видно, что переменные булевой функции упорядочены относительно такого порядка:
если и некоторая внутренняя вершина дерева решений, а v - её наследник, то .
Лемма 2.1.1.
Для всех , для всех [5].
Доказательство.
По индукции . Предположим, что лемма верна для всех q таких, что . Для конечных случаев, тривиально. Для нетривиальных случаев, пусть , где . Рассмотрим два случая и . В первом случае и . Эти два равенства эквивалентны по индуктивному предположению для . Для случая, когда , анaлогично.
Эта несложная лемма показывает, что OBDD является каноническим представлением Булевой функции. Это значит, что каждая Булева функция представляется некоторым единственным OBDD.
Теорема 2.1.1.
Если р и р' элементы OBDD(V). Тогда , если [5].
Доказательство.
Предположим одновременной индукцией для и .Мы предполагаем, что условие теоремы выполняется для всех q и q' , где и . Предположим, что .
Рассмотрим первый случай, где . Любые p и q - оба конечные, (в случае, когда или ) или они оба не конечные, и . Для не конечных, мы имеем , и подобным образом . Отсюда, по индукции , и , так .
Рассмотрим второй случай, где . Из этого следует, что р это не конечный . Из леммы 1, . Поэтому, , так . По индукции, где . Это - противоречие, однако, если l и h - не различны, то p не находится в OBDD (V).
Симметрично получается и в случае, когда .
Теорема 2.1.2.
Возьмём функцию , существует такое, что [5].
Доказательство.
По индукции возьмём i очень большое число такое, что . По индуктивной гипотезе, существуют р и r в OBBD(V) такие, что и . Дальше q и r различны, получается из . Т.о. получаем .
Опр. УБДР называется сокращенной, если
для любой внутренней вершины v ее 0-сын и 1-сын не совпадают;
нет такой пары внутренних вершин u и v, для которых поддиаграммы с корнями u и v являются изоморфными (т.е. взаимно однозначно отображаются друг на друга с сохранением всех меток).
Теорема 2.1. УБДР D является сокращенной тогда и только тогда, когда к ней не применимо ни преобразование СВВД , ни преобразование ИЛТ.
Доказательство.
59
Если к 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, то поддиаграммы
59
и
59
с корнями 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., редактируется в такое УБДР.
59
59
59
Следует обратить внимание, на то что правила преобразования нужно выполнять повторно, поскольку после каждого преобразования могут появится условия для выполнения другого условия.
Основные свойства УБДР:
УБДР является канонической формой булевой функции, поскольку для заданного порядка две УБДР, которые представляют одну и ту же булеву функцию, изоморфны между собой.
Данная булева функция выполняется тогда и только тогда, когда УБДР, которое её представляет, имеет листок, обозначенный 1.
Булева функция представляет собой тавтологию тогда и только тогда, когда УБДР, которое её представляет, имеет единственный листок, обозначенный 1.
Если булева функция не зависит от переменной х, то её УБДР не включает ни одной вершины, обозначенной символом переменной х.
Из этих свойств вытекает, что при помощи УБДР легко разрешить некоторые важные вопросы для булевых функций. На рисунках изображённых выше показаны как по таблице истинности строится дерев о решений и как это дерево решений преобразуется в УБДР. Как известно, таблица истинности и дерево решений имеют экспоненциальную сложность относительно числа переменных булевой функции, в тот час как представление булевой функции при помощи УБДР в некоторых случаях приводит к намного более экономичному представлению этой функции.
Размеры УБДР, как показывает пример УБДР, изображённый на рис.2.1.2, зависит от выбранного порядка. Если этот порядок выбран неудачно, то УБДР может иметь большие размеры, в то время если для другого порядка размеры УБДР будут небольшими. Ниже на рис.2.1.2 изображены УБДР, которые представляют булеву функцию относительно порядка и порядка .
59
Если обобщить данную функцию на переменных, т.е. рассмотреть функцию , то УБДР для этой функции относительно порядка имеет внутренних вершин (а всех ) - по одной на каждую переменную. УБДР для этой же самой функции относительно порядка имеет внутренних вершин. Уже для разница в представлении существенная: первая УБДР имеет 8 внутренних вершин, а вторая - 30.
59
Приведённый факт ставит вопрос: существует ли такой способ выбора подходящего порядка? Ответ на этот вопрос является неоднозначным - в одном случае хорошим является один порядок, в другом случае - хорошим является другой порядок. В большинстве применений УБДР порядок выбирается с самого начала или ручным способом, либо при помощи какого-нибудь эвристического анализа системы, которая представляется УБДР. Следует отметить, что выбор порядка при помощи какой-нибудь эвристики не обязательно будет оптимальным, но каким бы ни был этот порядок, он не влияет на правильность результата. Но если найден такой порядок, который не приводит к экспоненциальному росту УБДР, то операции на УБДР становятся достаточно эффективными.
Существующие методы определения хорошего порядка переменных можно классифицировать на три вида:
Эвристические методы нахождения порядков по информации о комбинаторных цепях, реализующих булевы функции. Эти методы основаны на топологии цепей
Эвристики пошагового улучшения, основанные на перестановке местами переменных.
Методы исчерпывающего поиска. Эти методы дают точный результат - оптимальный порядок (один из оптимальных порядков), при котором структура имеет минимальный из возможных размеров.
2.2 Операции на УБДР
Перейдём к традиционным обозначениям операций на множестве булевых функций. Символом + и • обозначаются соответственно операции дизъюнкции и конъюнкции, а символами и обозначают безальтернативную дизъюнкцию и отрицание соответственно. Дополнительно будет использоваться символ для операции дополнения операции безальтернативной дизъюнкции [7]. Символы и обозначают соответственно сумму (дизъюнкция) и произведение (конъюнкция) булевых выражений. Константы 0 и 1 рассматриваются как нольарные операции. Все эти операции определены на множестве булевых функций. Это означает, что когда f и g булевы функции, то , , и являются булевыми функциями над тем же самым множеством булевых функций. Рассмотрим некоторые традиционные и нетрадиционные операции над булевыми функциями.
Сужение функции. Функция, полученная в результате приписывания фиксированного значения некоторому аргументу х, называется сужением функции . Если заданны два сужения функции f относительно переменной х, то для функции f имеет место такое равенство:
.
Пример.
Пусть задана функция , тогда
и .
Тогда,
Суперпозиция функций получается в результате подстановки некоторой булевой функции g вместо переменной х в булевой функции f. Тогда, используя равенство (1), можно записать
Пример.
Пусть заданы функции:
и
Тогда непосредственная подстановка даёт такую функцию:
.
Теперь воспользуемся равенством:
.
Для вычисления . Как известно из предыдущего примера
и
отсюда получаем
Операции квантификации для булевых функций. Эти операции вводятся при помощи т и т.д.................


Перейти к полному тексту работы



Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.