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

Приведем несколько простейших алгоритмов синтеза схем, в случае когда базис состоит из элементов: инвертора, конъюнктора и дизъюнктора.

Метод синтеза, основанный на совершенной ДНФ

Лемма (1):

Для любой конъюнкции [math] x_{1}\wedge ... \wedge x_{n} [/math] [math] Size_{B}(x_{1} ... x_{n})\le 2n-1 [/math]

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

[math]\triangleright[/math]

Данная схема может быть построена их [math] n [/math] элементов отрицания, присоединенных к входам, и цепочки из элементов конъюнкции, имеющих [math] n [/math] "свободных" входов. Каждый [math] i [/math]-й вход этой цепочки присоединяется к входу схемы, если [math] i [/math]-й множитель равен [math] x_{i} [/math], или к выходу [math] i [/math]-го элемента отрицания, если [math] i [/math]-й множитель равен [math] \overline{x}_{i} [/math]. Очевидно, что сложность построенной схемы равна [math] 2n-1 [/math]. Поэтому [math] Size_{B}(x_{1} ...x_{n})\le 2n-1 [/math]. Лемма доказана.

[math]\triangleleft[/math]

Теорема (1):

Имеет место неравенство [math] Size_{B}(n)\le n2^{n+1} [/math]

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

[math]\triangleright[/math]

Пусть [math] f(x_{1},...,x_{n}) [/math] произвольная булева функция. Если [math] f \ne 0 [/math], то [math] f [/math] может быть задана нормальной дизъюнктивной формой [math] f(x_{1},...,x_{n}) = K_{1} \vee K_{2} \vee ... \vee K_{s} [/math], где [math] s \le 2^{n} [/math] и каждая конъюнкция имеет вид [math] K_{j}=x_{1}\wedge\overline{x}_{2}\wedge{x}_{3}\wedge ... \wedge{x}_{i} [/math] Схема [math] S [/math] для [math] f [/math] состоит из конъюнкций [math] K_{j} [/math] (каждая из них в соответствии с Леммой 1 имеет сложность не более [math] 2n-1 [/math]) и цепочки из [math] s-1 [/math] элемента дизъюнкции с [math] s [/math] свободными входами. Свободные входы этой цепочки присоединяются к выходам схем для конъюнкций [math] K_{j} [/math]. Имеем [math] Size_{B}(n)\le s(2n-1)+s-1 \lt s(2n-1)+s = 2ns \le n2^{n+1} [/math]. Если [math] f = 0 [/math], то схема строится в соответствии с представлением [math] 0=x_{1}\wedge\overline{x}_{1} [/math], то есть[math] Size_{B}(0) \le 2[/math]. Таким образом, для любой функции [math] f(x_{1},...,x_{n}) [/math] выполняется неравенство [math] Size_{B}(f(x_{1},...,x_{n}))\le n2^{n+1} [/math]. Поэтому [math] Size_{B}(n)\le n2^{n+1} [/math]. Теорема доказана.

[math]\triangleleft[/math]

Метод синтеза, основанный на более компактной реализации множества всех конъюнкций

Лемма (2):

Имеет место соотношение [math] Size_{B}(K_{n}) \sim 2^n [/math]

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

[math]\triangleright[/math]

Каждая конъюнкция [math] x_{1}\wedge\overline{x}_{2}\wedge{x}_{3}\wedge ... \wedge{x}_{i} [/math] может быть представлена в виде конъюнкции двух конъюнкций длины [math] k [/math] и [math] n-k [/math]: [math] x_{1}\wedge\overline{x}_{2}\wedge{x}_{3}\wedge ... \wedge{x}_{n} = (x_{1}\wedge\overline{x}_{2}\wedge{x}_{3}\wedge ... \wedge{x}_{k})(x_{k+1}\wedge\overline{x}_{k+2}\wedge{x}_{k+3}\wedge ... \wedge{x}_{n}) [/math]. Поэтому схема для [math] K_{n} [/math] может быть образована из схем для [math] K_{k}(x_{1}\wedge\overline{x}_{2}\wedge{x}_{3}\wedge ... \wedge{x}_{n}) [/math] и [math] K_{n-k}(x_{k+1}\wedge\overline{x}_{k+2}\wedge{x}_{k+3}\wedge ... \wedge{x}_{n}) [/math] и системы из [math] 2^n [/math] элементов конъюнкции, осуществляющих вышеприведенную операцию. Следовательно, [math] Size_{B}(K_{n}) \le Size_{B}(K_{k}) + Size_{B}(K_{n-k}) + 2^n [/math]. Так как по Теореме 1 [math] Size_{B}(K_{n}) \le k2^{k+1} [/math] , [math] Size_{B}(K_{n-k}) \le (n-k)2^{n-k+1} [/math],то [math] Size_{B}(K_{n}) \le k2^{k+1} + (n-k)2^{n-k+1} + 2^n [/math]. Положим [math] k=[\frac{n}{2}][/math]. Тогда [math] k \le \frac{n}{2} [/math], [math] n-k \le \frac{n}{2}+1 [/math] и [math] Size_{B}(K_{n}) \le \frac{n}{2}2^{\frac{n}{2}+1} + (\frac{n}{2}+1)\frac{n}{2}2^{\frac{n}{2}+2} + 2^n =2^n+O(n2^{\frac{n}{2}})[/math]. С другой стороны, при [math] n \ge 2 [/math] каждая конъюнкция реализуется на выходе некоторого элемента, то есть при [math] n \ge 2 [/math] выполняется неравенство [math] Size_{B}(K_{n}) \ge 2^{n} [/math]. Таким образом, [math] Size_{B}(K_{n}) \sim 2^n [/math]. Лемма доказана.

[math]\triangleleft[/math]

Теорема (2):

Имеет место соотношение [math] Size_{B}(n)\lesssim 2^{n+1} [/math].

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

[math]\triangleright[/math]

Пусть [math] f(x_{1},...,x_{n}) [/math] произвольная булева функция,[math] f \ne 0 [/math]. Заменим в схеме верхнюю часть схемы, реализующую конъюнкции [math] K_{1} \vee K_{2} \vee ... \vee K_{s} [/math], схемой, реализующей все конъюнкции из [math] K_{n} [/math]. Тогда для любой такой функции [math] f(x_{1},...,x_{n}) [/math] (не равной нулю) имеем [math] Size_{B}(f) \le L(K_{n})+s-1 \le L(K_{n})+2^{n}-1 \lesssim 2^{n+1} [/math] Таким образом, [math] Size_{B}(n)\lesssim 2^{n+1}. [/math] Теорема доказана.

[math]\triangleleft[/math]

Метод синтеза схем, предложенный К.Э.Шенноном

Теорема (3):

Имеет место соотношение [math] Size_{B}(n)\lesssim 12\frac {2^{n}}{2} [/math].

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

[math]\triangleright[/math]

Пусть [math] f(x_{1},...,x_{n}) [/math] произвольная булева функция. Рассмотрим разложение [math] f [/math] по переменным [math] x_{1},...,x_{n} [/math], где [math] 1 \le m \le n [/math]: [math] f(x_{1},...,x_{n})= \bigvee x_{1}\wedge\overline{x}_{2}\wedge{x}_{3}\wedge ... \wedge{x}_{m} f(x_{m+1}\wedge\overline{x}_{m+2}\wedge{x}_{m+3}\wedge ... \wedge{x}_{n}) [/math]. Схема для функции [math] f [/math] строится из трех подсхем: [math] S_{1},S_{2},S_{3} [/math]. 1. Схема [math] S_{1} [/math] реализует все конъюнкции из множества [math] K_{m} (x_{1},...,x_{m}) [/math]. В силу Леммы 2 выполняется неравенство [math] Size_{B}(S_{1}) \le Size_{B}(K_{m}) \lesssim 2^{m} [/math]. 2. Схема [math] S_{2} [/math] реализует [math] F(x_{m+1},...,x_{n}) [/math] всех булевых функций от переменных [math] x_{m+1},...,x_{n} [/math]. В силу Теоремы 1 [math] Size_{B}(S_{2}) \le (n-m)2^{n-m+1}2^{2^{n-m}} [/math]. 3. Схема [math] S_{3} [/math] производит "сборку" в соответствии с разложением функции [math] f [/math]: для каждого набора реализуется конъюнкция [math] x_{1}\wedge\overline{x}_{2}\wedge{x}_{3}\wedge ... \wedge{x}_{m}f(x_{m+1}\wedge\overline{x}_{m+2}\wedge{x}_{m+3}\wedge ... \wedge{x}_{n}) [/math] ([math] 2^{m} [/math] элементов конъюнкции) и образуется дизъюнкция таких конъюнкций ([math] 2^{m}-1 [/math] элементов дизъюнкции). Поэтому выполняется неравенство [math] Size_{B}(S_{3}) \le 2^{m} +2^{m} -1 [/math]. Таким образом, [math] Size_{B}(S) \le Size_{B}(S_{1})+Size_{B}(S_{2})+Size_{B}(S_{3}) \lesssim 3 \cdot 2^{m} +(n-m)2^{n-m+1}2^{2^{n-m}} [/math]. Положим (для упрощения дальнейших выкладок) [math] k=n-m [/math]. Тогда [math] Size_{B}(n) \lesssim 3 \cdot 2^{n-k} +k2^{k+1}2^{2^{k}} [/math]. Заметим, что второе слагаемое "очень быстро" растет с ростом [math] k [/math], а первое слагаемое убывает с ростом [math] k [/math] медленней. Поэтому следует взять такое значение [math] k [/math], при котором первое и второе слагаемые приблизительно равны, и потом немного уменьшить [math] k [/math]. Тогда второе слагаемое "сильно" уменьшится, а первое "не очень сильно" возрастет. Возьмем, например, [math] k=\log_{2}n [/math]. Тогда [math] 3 \cdot 2^{n-k} = 3 \cdot \frac{2^{n}}{n} [/math], [math] k \cdot 2^{k+1} \cdot 2^{2^{k}}=\log_{2}n\cdot (2n)\cdot 2^{\frac{n}{2}}[/math], то есть получили "слишком много". Возьмем [math] k [/math] на единицу меньше: [math] k=\log_{2}n-1 [/math]. Тогда [math] 3 \cdot 2^{n-k} = 3 \cdot \frac{2^{n}}{n} \cdot 2 [/math], [math] k \cdot 2^{k+1} \cdot 2^{2^{k}}=(\log_{2}n-1)\cdot n\cdot 2^{\frac{n}{2}}[/math]. Вспомним теперь, что [math] k [/math] должно быть целым числом, и положим [math] k=[\log_{2}n-1] [/math]. Тогда [math] n-k \lt n- \log_{2} + 2[/math], [math] 3 \cdot 2^{n-k} \lt 12 \cdot \frac {2^{n}}{n} [/math], [math] k\cdot 2^{k+1}\cdot 2^{2^{k}} \le (\log_{2}-1)\cdot n\cdot 2^{\frac{n}{2}} [/math]. При этом выборе [math] k [/math] окончательно имеем [math] Size_{B}(n)\lesssim 12\frac {2^{n}}{2} [/math]. Теорема доказана. Литература Яблонский С.В. Введение в дискретную математику. — 4-е изд. — М.: Высшая школа, 2003. — 384 с. — ISBN 5-06-004681-8

[math]\triangleleft[/math]