Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]


Схемы из функциональных элементов

Схемы из функциональных элементов


Представлению булевых функций формулами можно придать следующий "инженерно-конструктивный" смысл. Будем рассматривать формулу [math]\Phi(x_1,\ldots,x_n)[/math] над каким-то произвольно фиксированным множеством [math]F[/math] как "черный ящик", некое устройство, на вход которого подаются всевозможные наборы значений переменных, а на выходе появляются соответствующие этим наборам значения функции [math]f[/math], представляемой формулой [math]\Phi[/math] (рис. 6.22).


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

Чтобы понять, как устроен "черный ящик", мы должны разобрать процесс построения формулы из подформул. Добираясь до "базисных" подформул, т.е. элементов множества [math]F[/math], мы приходим к "кирпичикам", структурным элементам, из которых собран "черный ящик", вычисляющий функцию [math]f[/math]. Каждая функция "базиса" [math]F[/math] вычисляется соответствующим "узлом", который рассматривается как мельчайшая структурная единица нашего "черного ящика", и его внутренняя структура уже не анализируется.


Пример 6.22. Выберем в качестве множества [math]F[/math] стандартный базис. Тогда формула над стандартным базисом, представляющая функцию [math]\sim[/math] (эквивалентность), строится следующим образом:


[math]x_1\sim x_2=\overline{x_1 \overline{x}_2\lor \overline{x}_1x_2}.[/math]
(6.21)

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


Процесс построения формулы из элементов стандартного базиса

Переменное [math]x_1[/math] (точнее, значение этого переменного) подается на вход структурного элемента, называемого инвертором (рис. 6.24, а) и вычисляющего отрицание. Снимаемое с выхода инвертора отрицание [math]x_1[/math], т.е. функция [math]\overline{x_1}[/math], подается на один из входов конъюнктора (рис. 6.24,5), на второй вход которого подается переменное [math]x_2[/math]. На выходе конъюнктора появляется функция [math]\overline{x}_1x_2[/math]. Аналогично прослеживается вычисление функции [math]x_1\overline{x}_2[/math]. Обе эти функции подаются на входы дизъюнктора (рис. 6.24, в), с выхода которого снимается функция [math]x_1 \overline{x}_2\lor \overline{x}_1x_2[/math] (это не что иное, как сумма по модулю 2: [math]x_1\oplus x_2[/math]). И наконец, эта функция подается на вход инвертора, на выходе которого уже получается функция [math]\sim[/math] (эквивалентность).


Инвертор, конъюнктор и дизъюнктор



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


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


Введем обозначение: если [math]F[/math] — какое-то множество булевых функций, то через [math]F^{(n)}[/math] обозначаем подмножество [math]F[/math], состоящее из всех функций от [math]n[/math] переменных [math](n\geqslant0)[/math].


Определение 6.14. Пусть фиксированы множества: [math]F[/math] (булевых функций) и [math]X[/math] (булевых переменных).


Схемой из функциональных элементов над базисом [math]F\cup X[/math] (СФЭ), или просто схемой над базисом [math]F\cup X[/math], также (F,X)-схемой, называют бесконтурный ориентированный граф (т.е. сеть), каждая вершина которого помечена одним из элементов множества [math]F\cup X[/math] так, что выполняются следующие требования:


1) каждый вход сети помечен либо некоторым переменным из [math]X[/math], либо некоторой константой из [math]F^{(0)}[/math];


2) если вершина v сети помечена функцией [math]f[/math] от [math]n[/math] переменных (т.е. [math]f\in F^{(n)}[/math]), то ее полустепень захода равна [math]n[/math], причем на множестве дуг, заходящих в вершину [math]{v}[/math], задана (взаимно однозначная) нумерация, при которой каждая дуга получает номер от 1 до [math]n[/math].


При изображении схем входы обозначаются кружочками, а вершины, не являющиеся входами, — треугольниками, внутри которых записано обозначение функции, помечающей данную вершину. Выходы отмечаются "выходными" стрелками. На рис. 6.25 приведена СФЭ над базисом [math]\{\mid,x,y\}[/math].


СФЭ над базисом

Если базис подразумевается, то мы будем говорить просто "схема". Кроме того, если множество переменных фиксировано "раз и навсегда" и при рассмотрении различных схем мы меняем только множество функций [math]F[/math], то, как это мы делали, вводя понятия формулы и суперпозиции над заданным базисом, будем говорить о СФЭ над базисом [math]F[/math], полагая каждый раз, что подразумевается однажды фиксированное множество переменных [math]X[/math], которое (если это не вредит точности) не упоминается.


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


Определение 6.15. Пусть задана СФЭ [math]S[/math] над базисом [math]F\cup X[/math], множество вершин которой есть [math]V[/math].


1. Принимается, что каждый вход СФЭ вычисляет булеву функцию, которой он помечен (т.е. некоторое переменное или константу).


2. Если вершина [math]v\in V[/math] помечена функцией [math]f\in F^{(n)}[/math] заходящая в нее дуга с номером [math]i~(1\leqslant i\leqslant n)[/math] исходит из вершины [math]v_i\in V[/math], которая вычисляет функцию [math]g_i[/math], то вершина v вычисляет суперпозицию [math]f(g_1,\ldots,g_n)[/math].


Таким образом, если каждая вершина СФЭ над [math]F[/math] вычисляет некоторую функцию, то порядок, в котором перечисляются функции [math]g_1,\ldots,g_n[/math], подставляемые на места переменных функции [math]f[/math], в общем случае существен. Естественно назвать булеву функцию [math]f[/math] от [math]n[/math] переменных коммутативной, если она сохраняет значение при произвольной перестановке ее переменных. В этом случае мы можем не заботиться о нумерации дуг, заходящих в вершину схемы, помеченную такой функцией.


Пример 6.23. Рассмотрим СФЭ на рис. 6.25. Вершины [math]v_1[/math] и [math]v_2[/math] — входы СФЭ. Эти вершины вычисляют соответственно функции [math]x[/math] и [math]y[/math]. Тогда вершина [math]v_3[/math], равно как и вершина [math]v_4[/math], согласно определению 6.15, вычисляет функцию [math]x|y[/math] (штрих Шеффера), а вершина [math]v_5[/math] (выход сети) — функцию [math](x|y)|(x|y)[/math], которая, как известно, равна конъюнкции [math]x\cdot y[/math].


СФЭ, изображенная на рис. 6.26, имеет два выхода, вычисляющие функции [math](x|x)|(y|y)=x\lor y[/math] и [math](x|y)|(x|y)=x\cdot y[/math].


Определение 6.16. Булева функция, вычисляемая СФЭ над базисом [math]F\cup X[/math], — это функция, вычисляемая каким-либо из ее выходов.


Таким образом, СФЭ вычисляет ровно столько булевых функций, сколько имеет выходов. СФЭ на рис. 6.25 вычисляет одну функцию, а СФЭ на рис. 6.26 — две.


Пример СФЭ

В общем случае, если [math]\{x_1,\ldots,x_n\}[/math] — множество всех переменных, которые служат метками входов схемы [math]\mathcal{S}[/math] над базисом [math]F\cup X[/math], имеющей га выходов, СФЭ [math]\mathcal{S}[/math] определяет отображение булева куба [math]\mathbb{B}^n[/math] в булев куб [math]\mathbb{B}^m[/math], т.е. булев оператор.


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


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


Можно доказать и обратное: по любому булеву оператору может быть построена СФЭ над базисом [math]F[/math], где [math]F[/math] — полное множество, вычисляющая данный оператор.


Пример 6.24. Зададим таблицей булев оператор, отображающий [math]\mathbb{B}^3[/math] в [math]\mathbb{B}^2[/math] (табл. 6.9).


[math]\begin{array}{|c|c|c||c|c|} \multicolumn{5}{r}{\mathit{Table~6.9}}\\\hline x_1& x_2& x_3& y_1& y_2\\\hline 0&0&0&0&0\\ 0&0&1&0&1\\ 0&1&0&0&1\\ 0&1&1&1&0\\ 1&0&0&0&1\\ 1&0&1 &1&0\\ 1&1&0&1&0\\ 1&1&1&1&1\\\hline \end{array}[/math]

Из таблицы легко увидеть, что [math]y_1=x_1x_2\lor x_1x_3\lor x_2x_3,~ y_2=x_1\oplus x_2\oplus x_3[/math] (функция [math]y_1[/math] есть не что иное, как мажоритарная функция от переменных [math]x_1,\,x_2,\,x_3[/math], и выше написана минимальная ДНФ для нее, см. пример 6.12). Представим функцию [math]y_1[/math] в базисе Жегалкина. Используя законы де Моргана, получим


[math]x_1x_2\lor x_1x_3\lor x_2x_3= \overline{\overline{x_1x_2}\cdot \overline{x_1x_2}\cdot \overline{x_2x_3}}.[/math]

Учитывая, что [math]\overline{x}=x\oplus1[/math], будем иметь


[math]\begin{aligned}\overline{\overline{x_1x_2}\cdot \overline{x_1x_2}\cdot \overline{x_2x_3}}&= (x_1x_2\oplus1) (x_1x_3\oplus1) (x_2x_3\oplus1)\oplus1=\\[2pt] &=x_1x_2x_3\oplus x_1x_2x_3\oplus x_1x_2x_3\oplus x_1x_2\oplus x_1x_2x_3\oplus x_1x_3\oplus x_2x_3\oplus1\oplus1=\\[2pt] &= x_1x_2\oplus x_1x_3\oplus x_2x_3 \end{aligned}[/math]

(напомним, что сумма по модулю 2 любого четного числа равных слагаемых равна 0). Итак,
[math]y_1= x_1x_2\oplus x_1x_3\oplus x_2x_3= x_1x_2\oplus x_3(x_1\oplus x_2).[/math]

СФЭ для булева оператора, заданного в табл. 6.9, над базисом Жегалкина приведена на рис. 6.27.
При проектировании СФЭ полезно иметь в виду числовой параметр, называемый ее сложностью.
Сложность СФЭ — это число ее вершин, не являющихся входами.
Приведенная на рис. 6.27 СФЭ над базисом Жегалкина имеет сложность 5.

СФЭ для булева оператора над базисом Жегалкина

Рассмотрим теперь СФЭ для того же оператора над стандартным базисом. По таблице (см. табл. 6.9) строим СДНФ для функции [math]y_2:[/math]


[math]y_2= \overline{x}_1\overline{x}_2x_3\lor \overline{x}_1x_2\overline{x}_3\lor x_1 \overline{x}_2\overline{x}_3\lor x_1x_2x_3\,.[/math]

Карта Карно для этой функции, изображенная на рис. 6.28, показывает, что ее нельзя минимизировать (точнее, записанная выше СДНФ и есть минимальная ДНФ для этой функции).


Таблицы булевых функций

Но можно пойти по другому пути. Мы можем рассматривать табл. 6.9 как таблицу, определяющую частичную булеву Функцию [math]y_2=y_2(x_1,x_2,x_3,y_1)[/math]. Минимизируя эту функцию по карте Карно*, изображенной на рис. 6.29, получаем


[math]y_2=x_1x_2x_3\lor \overline{y}_1(x_1\lor x_2\lor x_3).[/math]

*На этой карте мы явно обозначили наборы, на которых функция принимает значение 0, проставив нули в соответствующих клетках. Тем самым мы хотим еще раз зафиксировать внимание на том, что не следует путать нули с прочерками: прочерк в клетке карты, задающей частичную функцию, означает, что на данном наборе значение функции не определено, т.е. не равно ни 0, ни 1.


СФЭ над стандартным базисом для рассматриваемого булева оператора приведена на рис. 6.30. Сложность этой СФЭ составляет 11. Заметим, что вершина, вычисляющая функцию [math]y_1[/math], не является выходом.


СФЭ над стандартным базисом для булева оператора

Булев оператор, рассмотренный в этом примере, вычисляет двухразрядную сумму (по модулю 2) трех одноразрядных слагаемых. Его можно считать также одноразрядным двоичным сумматором — функциональным блоком многоразрядного двоичного сумматора — для двух слагаемых. Тогда функция г/1 интерпретируется как "сигнал переноса" в старший разряд. На рис. 6.31 изображено "соединение" трех СФЭ (таких, как показано на рис. 6.30), с помощью которого вычисляется сумма двух трехразрядных двоичных чисел. На третий вход сумматора для младшего разряда подается константа 0, а "сигнал переноса" старшего разряда есть старший разряд суммы, которая в общем случае будет четырехразрядным числом.


Соединение трех СФЭ

Замечание 6.11. Если мы проектируем СФЭ над стандартным базисом и хотим минимизировать ее сложность, то нам необходимо прежде всего построить соответствующую минимальную ДНФ. В этом случае мы можем принять во внимание еще один критерий, по которому минимизируется сама ДНФ, — число отрицаний. Среди всех минимальных (в смысле определения 6.6) ДНФ следует отобрать те, в которых число вхождений переменных под знаком отрицания является наименьшим. С точки зрения сложности СФЭ, которая будет построена по минимальной ДНФ, это означает, что в ней минимизируется число "инверторов" — вершин СФЭ, помеченных функцией отрицания.


Булева функция, заданная картой Карно

Например, для функции, заданной картой Карно (рис. 6.32), к ядру, состоящему из простых импликант [math]x_1x_2x_4[/math] и [math]\overline{x}_1x_3\overline{x}_4[/math], следует добавить простую импликанту [math]x_2x_3x_4[/math], а не [math]\overline{x_1}x_2x_3[/math], поскольку она не содержит отрицаний.


Часовой пояс: UTC + 4 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved