Теория Автоматов Конечные функциональные преобразователи Конечные функциональные преобразователи

Формы представления булевых функций Семантические деревья Семантическое дерево это двоичное дерево, корень которого помечен двоичной функцией от m переменных, из каждого узла идут по два ребра, соответствующих двум значениям очередной переменной, а 2 т листьев помечены соответствующи­ми значениями функции. Удобство этого представления в том, что для многих функций значения у всех листьев некоторых поддеревьев совпадают и построение некоторых ветвей быстро заканчивается, не доходя до самого нижнего уровня.

Формы представления булевых функций Бинарные диаграммы решений БДР Бинарная диаграмма решений (Binary Decision Diagrams, BDD) [2] это граф, являющийся модификацией семантического дерева. В БДР узлы с известным зна­чением функции объединены. Если на каждом уровне БДР все вершины имеют одну и ту же метку (одинаковые переменные), то такая БДР называется упорядо­ченной (в англоязычной литературе такое представление называется Ordered Bi­nary Decision Diagrams, или сокращенно OBDD). Будем называть такое представ­ление УБДР. Вершины УБДР расположены по уровням, каждому уровню соот­ветствует одна переменная, которая помечает вершины, находящиеся на этом уров­не. Из каждой вершины выходят два ребра: одно соответствует нулевому значе­нию соответствующей переменной (будем его изображать штриховой линией), а другое единичному значению этой переменной

Формы представления булевых функций Бинарные диаграммы решений используются как компактная форма представле­ния булевой функции. Такое представление полезно во многих случаях, например когда нужно многократно вычислять значения функции при различных наборах значений ее аргументов. Для того чтобы получить значение функции 1.2, например, на языке С, вместо хранения громоздкой таблицы истинности мож­но вычислить оператор: f = q?(r?0:l):(p?0:l), который построен на основании БДР (см. рис. 1.12). В этом примере использование УБДР позволяет вычислить значение булевой функции, выполнив всего две операции, в то время как при ее вычислении по аналитическому представлению требуется не менее 5 операций.

Формы представления булевых функций Формулы Таблица истинности Семантическое дерево Бинарная диаграмма решений f(p,q,r)=-1pvqerq(pvr) f(p,q,r)=(-.pvq)(-iqv-,r)f(p,q,r)=iep®pqeqr pqrf

Формы представления булевых функций

Рис Четыре формы представления двоичной функции Сложность представления функции с помощью УБДР существенно зависит от порядка переменных. Так, например, УБДР для иного порядка переменных, чем на рис. 1.12, содержит четыре вершины, а не три (рис. 1.13). Интересной пробле­мой теоретической информатики является нахождение алгоритма, дающего опти­мальный порядок переменных булевой функции с точки зрения представления этой функции упорядоченной БДР. В работе [5] представлен один из таких алго­ритмов, имеющий, однако, экспоненциальную сложность.

Формы представления булевых функций

Рис УБДР для функции примера 1.2 с порядком переменных [p,q,r] Рассмотрим алгоритм, по которому из семантического дерева можно построить УБДР. Алгоритм состоит из трех шагов. 1. Выбрасывание дублирующих значений функции. На рис. 1.14, а в семантичес­ком дереве оставляем только два листа, помеченных соответственно 0 и 1. Ре­зультат представлен на рис. 1.14, б. 2. Выбрасывание дублирующих тестовых у злое. Если два различных промежуточ­ных узла в диаграмме являются корнями структурно-идентичных под диаграмм,

Формы представления булевых функций то заменяем их одним эквивалентным. На рис. 1.14, в три промежуточных узл помеченные переменной z, объединены в один.

Формы представления булевых функций

3. Выбрасывание избыточных тестовых у злое. Если оба исходящих из узла t реб­ра указывают на один и тот же следующий узел, скажем, и, то узел t можно выбросить, связав все входящие в t ребра с узлом и. На рис. 1.14, г выброшен один из узлов, помеченных у.

Булевы алгебры (М,й), где М множество элементов алгебры, а и множество операций алгебры над ее элементами (называющееся сигнатурой). Ре­зультаты операций всегда принадлежат М. Пусть В алгебра с произвольным множеством М элементов, сигнатура которой содержит две бинарные операции «+» и «», одну унарную операцию «'» и две нуль-парных операции (константы) 0 и I. Такая алгебра В называется булевой алгеброй тогда и только тогда, когда для любых x,y,ze M в ней справедливы следующие законы:

Булевы алгебры С1. Идемпотентность:х + х = х, х-х^х; С2. Коммутативность:х + у = у + х, х у в у х; СЗ. Ассоциативность: х + (у + z) - (х + у) + z, х (у z) - (х у) z; Булевы алгебры 35 Поглощение: х (х + у) - х, х + (х у) = х; Дистрибутивность: х + (у z) - (х + у) (х + z), х (у + z) - (х у) + (х z); 0 аях, x-I-x, x + I-I; Универсальные границы: х-0 яв 0;х Дополнение: х х' = 0, х + х' = I; Законы де Моргана: (х у)1 = х' + у', (х + у)' = х 1 у'; Инволютивность: (х 1)' - х.

Булевы алгебры Очевидна связь булевых алгебр и двоичных функций. Множество М составляют все двоичные функции, множество операций Q дизъюнкция, конъюнкция и от­рицание, а нульарные операции тождественные функции 0 и 1. Но интересно, что и многие другие модели являются булевыми алгебрами и для них можно ин­терпретировать многие свойства двоичных функций. Например, булеву алгебру представляет собой любое множество всех подмножеств произвольного множе­ ства А с операциями объединения, пересечения и дополнения множеств, а нульар­ные операции это пустое подмножество и полное множество А.

Булевы алгебры Множество тождеств С1С9 является избыточным в том смысле, что, например, аксиомы С1, С8 и С9 следуют из остальных шести С2С7. Покажем это для С1. Соответствующее утверждение доказано Дедекиндом. Теорема Законы идемпотентности С1 следуют из законов поглощения С4. Доказательство. Свойство С4: справедливо для любых элементов х и у. Положим в первом тождестве С4 у - х х. Тогда это тождество свойства С4 перепишется так: х [х + (х х)] ж х. Из второго тождества, в котором положим у - х, получим: х + (х х) - х. Левая часть этого тождества как раз совпадает с выражением в квад­ратных скобках первого тождества. Заменив ее на х, в соответствии с правой час­тью этого тождества, получим один из законов идемпотентности х х = х. Другой закон идемпотентности доказывается аналогично, если мы заменим в предыдущем рассуждении операцию «+» на «», и наоборот. Это является частным проявлени­ем так называемого «принципа двойственности» в булевой алгебре

Булевы алгебры Теорема Любая общезначимая теорема о булевых алгебрах, в формулировке которой участвуют только операции «+», «» и «'», остается общезначимой, если в ее формулировке всюду заменить «+» на «», и наоборот. Доказательство этой теоремы весьма просто. Все свойства С1С9 сохраняются при такой замене. Поскольку любые доказательства в булевой алгебре базируются только на этих свойствах, то любое такое доказательство при вышеуказанной за­ мене превращается в доказательство двойственного утверждения.

Пороговая логика В 1943 году Уоррен Мак-Каллок и Уолтер Питтс предложили формальную мо­дель нейрона (нервной клетки мозга) как переключающей функции {9,1}" > {9,1} в виде логической схемы, имеющей конечное число двоичных входов и один двоич­ный выход. Каждый вход х, учитывается в нейроне с некоторым приписанным ему весом Wj. Нейрон возбуждается, если суммарное взвешенное возбуждение его вхо­дов не меньше некоторого порога срабатывания 9. Иными словами, выход нейро­на равен 1, если I^Wj *x{ > 9. С изменением порога и весов входов логические функции, реализуемые этим ней­роном, изменяются. Рассмотрим формальный нейрон с двумя входами {xl, х 2}, изображенный на рис. 1.15

Пороговая логика Суммарное возбуждение Z для этой схемы рассчиты­вается так: S = wl*xl + w2*x2. Пусть wl = w2 = l; тогда Z = xl + x2. Если 0 = 1, эта схема реализует дизъюнкцию xl v х 2; при 0 = 2 она реализует конъюнкцию xl&x2. Поставим обратную задачу: для заданного нейрона найти такие веса входов и по­рог его срабатывания, что этот нейрон реализует заданную двоичную функцию, например конъюнкцию &. Очевидно, что для решения задачи для конкретного нейрона рис нужно просто решить систему 4-х неравенств: ^ 4 ;.^^ для набора, I = wl * xl + w2 * х 2 = 9, I = wl * xl + w2 * х 2 = 9 < 9 (поскольку 9&9 = 9) для набора, S = wl * xl + w2 * х 2 = w2, S = wl * xl + w2 * х 2 = w2 < 9 (поскольку 9&1 = для набора, I = wl * xl + w2*x2 = wl, Z = wl*xl + w2*x2 = wl + w2>9 (поскольку 1&1 = 1).

Пороговая логика Рис Пример формального нейрона Очевидно, что этой системе неравенств удовлетворяет решение 0 = 2, wl = w2 = 1. Покажем, что в пороговой логике не существует элемента с двумя входами, реали­ зующего функцию сложения по модулю 2. Действительно,

Пороговая логика Из второго и третьего неравенства имеем wl + w2 > и, учитывая последнее неравенство, 0>wl+w2> Это, однако, противоречит первому неравенству 0>0.