Реализация булевых функций с помощью логических схем

В этой и следующей лекциях мы свяжем два основных предыдущих раздела нашего курса: булевы функции и графы. В курсе "Основы дискретной математики" мы рассматривали два основных представления булевых функций: табличное и с помощью формул общего вида или формул специального вида, в частности, дизъюнктивных или конъюнктивных нормальных форм и многочленов Жегалкина. К сожалению, эти способы не позволяют эффективно представлять функции от большого числа переменных: таблица для функции от n переменных всегда содержит 2n строк, многочлен Жегалкина может включать до 2n слагаемых (и для большинства функций по порядку столько и включает). Такие представления нельзя реализовать на практике уже для n порядка нескольких десятков. Могло показаться, что сокращенные ДНФ, которые мы научились эффективно строить с помощью метода Блейка, и минимальные ДНФ, которые можно получить, удаляя из сокращенных "лишние" конъюнкции (впрочем, хороший алгоритм для такого удаления неизвестен), дают существенно более экономные представления. булевых функций. Но в общем случае это не так. Для большинства булевых функций от n переменных минимальные ДНФ имеют экспоненциальный от n размер. В качестве примера конкретной простой функции с длинной ДНФ можно рассмотреть линейную функцию, определяющую нечетность суммы аргументов: odd(X1,X2,..., Xn)= X1 +X2 +... + Xn (см. задачу 3.1).

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

Логические схемы (схемы из функциональных элементов)

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

Чтобы не усложнять определение, зафиксируем конкретный базис $$B_{0}=\{ \wedge , \vee , \neg \}$$ и определим схемы в этом базисе.

Определение 2.1. Логической схемой ( схемой из функциональных элементов ) в базисе B0 называется размеченный ориентированный граф без циклов S=(V,E), в котором

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

Определение 2.2. Глубина вершины $$v \in V$$ в схеме S=(V,E) - это максимальная длина пути из входов S в v .

Глубиной D(S) схемы S назовем максимальную из глубин ее вершин.

Пусть входы схемы S помечены переменными x1, ... , xn. С каждой вершиной $$v \in V$$ схемы S свяжем булеву функцию fv(x1,... , xn), реализуемую в этой вершине. Определим fv индукцией по глубине v.

Определение 2.3.

Базис: v имеет глубину 0. Тогда это входная вершина, которая помечена некоторой переменной xi. Положим fv(x1,... , xn) = xi.

Шаг индукции. Пусть всем вершинам w глубины <= k уже сопоставлены функции fw и пусть v - произвольная вершина глубины k+1. Тогда

Нетрудно понять, что шаг индукции в этом определении корректен, так как, если в схеме S имеется ребро (w,v) и глубина вершины v равна k+1, то глубина вершины w не превосходит k и для нее fw уже определена по индукционному предположению.

Определение 2.4. Схема S реализует набор булевых функций g1, g2, ... , gm, если для каждого $$i \in [1,m]$$ в схеме существует такая вершина vi, что $$f_{v_i} = g_i$$.

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

Определение 2.5. Сложность L(S) схемы S - это число функциональных элементов в S. Сложность L(f) булевой функции f(x1, ..., xn) - это наименьшая из сложностей схем, реализующих эту функцию.

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

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

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

Пример 2.1. Рассмотрим схему S1 с тремя входными переменными x, y и z, изображенную на рис. 2.1 и решим для нее проблему анализа.

В соответствии с данным выше определением вершины схемы S1 реализуют следующие функции:

$$f_{a}(x,y,z) = x \wedge y$$, $$f_{b}(x,y,z) = \neg z$$, $$f_{c}(x,y,z) = \neg f_{a}(x,y,z)=\neg ( x \wedge y)$$, $$f_{d}(x,y,z) = f_{c}(x,y,z) \wedge z = \neg ( x \wedge y) \wedge z$$, $$f_{e}(x,y,z) =f_{a}(x,y,z) \wedge f_{b}(x,y,z)= x \wedge y \wedge \neg z$$ и, наконец, $$f_{f}(x,y,z) =f_{d}(x,y,z) \vee f_{e}(x,y,z) = (\neg ( x \wedge y) \wedge z) \vee ((x \wedge y )\wedge \neg z)$$.

Глубина этой схемы D(S1)= 4, а ее сложность L(S1)=6. В то же время формула для результирующей функции ff содержит 7 функциональных знаков. За счет чего достигнута экономия? За счет того, что функция $$(x \wedge y)$$ в схеме S1 вычисляется один раз в вершине a, а в формуле приходится вычислять ее дважды.

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

Схемы и линейные программы

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

где X, X1, ... , Xk - переменные, F - имя k -местной базисной функции.

В случае нашего базиса $$B_{0}=\{ \wedge , \vee , \neg \}$$ линейная программа состоит из присваиваний вида: $$Z = X \wedge Y$$, $$Z = X \vee Y$$ и $$Z = \neg X$$.

Линейная программа P с выделенными входными переменными X1, ... , Xn порождает для каждого набора $$\sigma _{1}, \dots , \sigma _{n}$$ значений входных переменных естественный процесс вычисления: вначале переменным X1, ... , Xn присваиваются значения $$\sigma _{1}, \dots , \sigma _{n}$$, соответственно, а каждой из остальных переменных присваивается значение 0. Затем последовательно выполняются присваивания программы P, в результате чего каждая из переменных Z программы получит заключительное значение $$P_{Z}(\sigma _{1}, \dots , \sigma _{n})$$.

Определение 2.6. Скажем, что программа P со входными переменными X1, ... , Xn вычисляет в выходной переменной Z функцию F(X1, ..., Xn), если для любого набора значений входов $$\sigma _{1}, \dots , \sigma _{n}$$ после завершения работы $$P_{Z}(\sigma _{1}, \dots , \sigma _{n})=F(\sigma _{1}, \dots , \sigma _{n})$$.

Между схемами и линейными программами имеется тесная связь.

Теорема 2.1.

Доказательство. (1) Пусть S - схема со входами x1, ... , xn и функциональными элементами v1, ..., vm. Построим по ней линейную программу PS со входными переменными x1, ... , xn следующим образом. Упорядочим все входные и функциональные вершины S по глубине (вершины одной глубины в любом порядке): u1, ..., un+m. Программа PS будет последовательностью m присваиваний.

Упорядочение вершин по глубине гарантирует, что j <n+ i и k <n+ i. Поэтому при вычислении u_{n+i} значения аргументов уже получены и индукцией по глубине легко показать, что для каждого i=1,...,m программа PS вычисляет в переменной vi функцию $$f_{v_i}(x_1, \dots, x_n)$$.

Доказательство пункта (2) проведите самостоятельно (см. задачу 2.1).

Пример 2.1. Применим конструкцию теоремы к схеме S1, представленной на рис.2.1. Ее вершины можно упорядочить по глубине так: x, y, z, a, b, c, d, e, f. Порождая команды по описанным выше правилам, получим следующую линейную программу P_{S1}:

Замечание. Число команд в линейной программе PS, т.е. время ее выполнения, совпадает со сложностью L(S) схемы S. Глубина схемы D(S) также имеет смысл с точки зрения времени вычисления. Именно, D(S) - это время выполнения PS на многопроцессорной системе. Действительно, все команды, соответствующие вершинам одинаковой глубины, можно выполнять параллельно на разных процессорах, так как результаты любой из них не используются в качестве аргументов другой.

Примеры схем

Сложение по модулю 2

Рассмотрим схему S+ на рис. 2.2.

В соответствии с определением вершины этой схемы реализуют следующие функции:

$$f_{a}(x,y) = x \wedge y$$, $$f_{b}(x,y) = x \vee y$$, $$f_{c}(x,y) = \neg f_{a}(x,y)=\neg ( x \wedge y)$$, $$f_{d}(x,y) = f_{c}(x,y) \wedge f_{b}(x,y) = \neg ( x \wedge y) \wedge ( x \vee y) = x +y$$.

Таким образом, схема S+ реализует (в вершине d ) функцию + сложения по модулю 2.

Из приведенного выше примера следует, что L(S+)=4 и L(+) <= 4.

Используя схему S+, нетрудно построить схему Sodd для реализации линейной функции-суммы n аргументов по модулю 2 odd(X1,X2,..., Xn)= X1 +X2 +... + Xn (см. рис. 2.3).

На этой схеме прямоугольники S+(1), S+(2), ... ,S+(n) содержат копии схемы S+. При этом входами S+(1) являются переменные x1 и x2, а входами S+(i+1) являются выход схемы S+(i) и переменная xi+1. По индукции легко показать, что вершина d в S+(i) реализует функцию (x1 + x2 + ... + xi+1). Таким образом, нами установлена

Теорема 2.2. Существует схема Sodd, реализующая функцию odd(X1,X2,..., Xn)= X1 +X2 +... + Xn со сложностью L(Sodd)= 4 (n-1).

Сумматор

Сумматором порядка n называют схему, вычисляющую результат сложения двух n -разрядных двоичных чисел $$a = \sum_{i=0}^{n-1} a_i 2^i$$ и $$b = \sum_{i=0}^{n-1} b_i 2^i$$. Пусть $$c= a+b = \sum_{i=0}^{n} c_i 2^i$$ ( здесь $$a_{i}, b_{i}, c_{i} \in \{ 0, 1\}$$ - соответствующие двоичные разряды этих чисел).

Сумматор должен вычислять набор из (n+1) -ой результирующей функции:

задающих соответствующие разряды суммы c.

Обозначим через pi бит переноса из (i-1) -го разряда в i -ый. Тогда нетрудно видеть, что при i =0

c0 = a0 + b0 и $$p_{1} = a_{0} \wedge b_{0}$$,

а при 1 <= i <= n-1

ci= pi + ai + bi и $$p_{i+1} = (a_{i} \wedge b_{i}) \vee (p_{i} \wedge a_{i}) \vee (p_{i} \wedge b_{i})$$.

Старший разряд c совпадает с последним переносом: cn=pn.

Рассмотрим теперь построенную выше схему S+ как схему, вычисляющую набор из двух функций: $$x \wedge y$$ (в вершине a ) и x+y (в вершине d ). Используя два экземпляра этой схемы S+(1) и S+(2), можно легко реализовать схему одноразрядного сумматора SUM1 (см. рис. 2.4) , которая имеет три входа ai, b_ i и pi ( 1 <= i <= n-1 ) и вычисляет ci и pi+1.

Действительно, из построения следует, что в вершине p этой схемы вычисляется функция $$f_{p} = (a_{i} \wedge b_{i}) \vee ((a_{i} + b_{i}) \wedge p_{i}) =(a_{i} \wedge b_{i}) \vee (p_{i} \wedge a_{i}) \vee (p_{i} \wedge b_{i}) = p_{i+1}$$. Из представленной схемы видно, что сложность одноразрядного сумматора L(SUM1)= 9.

Теперь из S+ и одноразрядных сумматоров SUM1 соберем схему SUMn для n -разрядного сумматора.

Таким образом мы установили следующее утверждение.

Теорема 2.3.

Для каждого n >= 1 cуществует схема SUM, реализующая операцию суммирования двух n -разрядных двоичных чисел и имеющая сложность L(SUMn)= 9n -5.

Замечание Логические схемы интенсивно исследовались 50-х-70-х годах прошлого столетия. В частности, К. Шеннон и О.Б. Лупанов установили оценки сложности схем для булевых функций от n аргументов. Оказалось, что любую такую функцию можно реализовать со сложностью не большей (по порядку) 2n/n и что "почти все" они имеют не меньшую сложность. При этом до сих пор не известна ни одна последовательность "конкретных" функций fn, сложность которых по порядку превосходила бы линейную функцию.

Задачи

Задача 2.1. Докажите пункт (2) теоремы 2.1.

Задача 2.2. Докажите, что минимальная схема для сложения имеет сложность L(+) = 4.

Задача 2.3. Используя схему SUMn, постройте схему, реализующую операцию вычитания двух n -разрядных двоичных чисел: d =a - b (при условии, что a >= b ). Оцените сложность полученной схемы.

Задача 2.4. Определите глубину схем S+, Sodd, SUM1 и SUMn.

Задача 2.5. Два игрока независимо выбирают одно из четырех чисел от 0 до 3. Первый игрок выигрывает, если выбранные числа совпадают. Постройте схему, определяющую выигрыш 1-го игрока. Ее входы x1,x2 представляют число, выбранное 1-ым игроком, а y1,y2 - число, выбранное 2-ым игроком. Реализуемая функция F(x1,x2,y1,y2) равна 1 тогда и только тогда, когда x1=y1 и x2 =y2.

Задача 2.6. Постройте схему, определяющую результат голосования в комитете, состоящем из трех членов и председателя. В случае равенства голосов, голос председателя является решающим.

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