Изменения
Нет описания правки
}}
Приведем несколько простейших алгоритмов синтеза схем, реализующих произвольную функцию от <tex> n </tex> аргументов <tex> f(x_{1}, ...\ldots, x_{n}) </tex>, в случае когда базис <tex> B = \{\neg, \lor, \land\} </tex>.
==Метод синтеза, основанный на [[СДНФ|совершенной ДНФ]]==
|id = Th1
|about = 1
|statement = Для любой функции <tex> f(x_{1}, ...\ldots, x_{n}) </tex> имеет место неравенство <tex> size_{B}(f)\leqslant n2^{n+1} </tex>
|proof = [[Файл:Synschemes Theorem1.png|250px|thumb|right|Рис. 2]]
Пусть <tex> f(x_{1},...\ldots,x_{n}) </tex> {{---}} произвольная [[Определение булевой функции|булева функция]].
Если <tex> f = 0 </tex>, то схема строится в соответствии с представлением <tex> 0=x_{1}\wedge\overline{x}_{1} </tex>, то есть <tex> size_{B}(0) \leqslant 2</tex>.
Если <tex> f \ne 0 </tex>, то <tex> f </tex> может быть задана [[ДНФ|дизъюнктивной нормальной формой]]
::<tex> f(x_{1},...\ldots,x_{n}) = K_{1} \vee K_{2} \vee ... \ldots \vee K_{s} </tex>,
где <tex> s \leqslant 2^{n} </tex> и каждая конъюнкция имеет вид
::<tex> K_{j}=x_{1}\wedge\overline{x}_{2}\wedge{x}_{3}\wedge ... \ldots \wedge{x}_{i} </tex>
Схема <tex> S </tex> для <tex> f </tex> состоит из конъюнкций <tex> K_{j} </tex> (каждая из них в соответствии с [[#Lemma1|леммой 1]] имеет сложность не более <tex> 2n-1 </tex>) и цепочки из <tex> s-1 </tex> элемента дизъюнкции с <tex> s </tex> свободными входами. Свободные входы этой цепочки присоединяются к выходам схем для конъюнкций <tex> K_{j} </tex>.(рис. 2) Имеем
::<tex> size_{B}(f)\leqslant s\cdot(2n-1)+s-1 < s\cdot(2n-1)+s = 2ns \leqslant n2^{n+1} </tex>.
Таким образом, для любой функции <tex> f(x_{1},...\ldots,x_{n}) </tex> выполняется неравенство
::<tex> size_{B}(f(x_{1},...\ldots,x_{n}))\leqslant n2^{n+1} </tex>.
Поэтому <tex> size_{B}(f)\leqslant n2^{n+1} </tex>.
|id = Th2
|about = 2
|statement =Для любой функции <tex> f(x_{1}, ...\ldots, x_{n}) </tex> имеет место соотношение <tex> size_{B}(f)\lesssim 2^{n+1} </tex>.
|proof =
[[Файл:Synschemes_ NewTheorem2.png|400px|thumb|right|В верхней части схемы рис.2 все подсхемы, вычисляющие конъюнкции, заменили на <tex>K_n</tex>]]
Пусть <tex> f(x_{1},...\ldots,x_{n}) </tex> {{---}} произвольная булева функция, <tex> f \ne 0 </tex>. Заменим в схеме (рис. 2) верхнюю часть схемы, реализующую конъюнкции <tex> K_{1} \vee K_{2} \vee ... \ldots \vee K_{s} </tex>, схемой, реализующей все конъюнкции из <tex> K_{n} </tex>. Тогда для любой такой функции <tex> f(x_{1},...\ldots,x_{n}) </tex> (не равной нулю) имеем
::<tex> size_{B}(f) \leqslant size_{B}(K_{n})+s-1 \leqslant size_{B}(K_{n})+2^{n}-1 \lesssim 2^{n+1} </tex>
|id = Th3
|about = 3
|statement =Для любой функции <tex> f(x_{1}, ...\ldots, x_{n}) </tex> имеет место соотношение <tex> size_{B}(f)\lesssim 12\dfrac {2^{n}}{n} </tex>.
|proof = [[Файл:Synschemes-Theorem2.png|300px|thumb|right|Рис. 4]]
Пусть <tex> f(x_{1},...\ldots,x_{n}) </tex> {{---}} произвольная булева функция. Рассмотрим разложение <tex> f </tex> по переменным <tex> x_{1},...\ldots,x_{m} </tex>, где <tex> 1 \leqslant m \leqslant n </tex>:
<tex>f(x_{1},...\ldots,x_{n})=\displaystyle\bigvee_{(\sigma_{1},\dotsc,\sigma_{m})}x_{1}^{\sigma_{1}}\wedge\dotsc\wedge x_{m}^{\sigma_{m}}\wedge f(\sigma_{1},\dotsc,\sigma_{m},x_{m+1},\dotsc,x_{n}) </tex>.
'''Схема для функции <tex> f </tex> строится из трех подсхем: <tex> S_{1},S_{2},S_{3} </tex>. (рис. 4)'''
::<tex> size_{B}(S_{1}) \leqslant size_{B}(K_{m}) \lesssim 2^{m} </tex>.
:2. Схема <tex> S_{2} </tex> реализует систему <tex> F(x_{m+1}^{\sigma_{m+1}},...\ldots,x_{n}^{\sigma_{n}}) </tex> всех булевых функций от всевозможных наборов переменных <tex> x_{m+1},...\ldots,x_{n} </tex>. Другими словами, подсхема <tex> S_{2} </tex> вычисляет все булевы функции, зависящие от последних <tex> n - m </tex> переменных. В силу [[#Th1|теоремы 1]]
::<tex> size_{B}(S_{2}) \leqslant (n-m)2^{n-m+1}2^{2^{n-m}} </tex>.
