Изменения
Исправил ошибки
Построим данную схему следующим образом: возьмем <tex> n </tex> элементов отрицания, присоединенных к выходам, и цепочки из элементов конъюнкции, имеющих <tex> n </tex> "свободных" входов.
Очевидно, что сложность построенной схемы равна <tex> size_{B}(f)= n+n-1 = 2n-1 </tex>.
Поэтому <tex> size_{B}(f)\le 2n-1 </tex>.
|statement = Для любой функции <tex> f(x_{1}, ..., x_{n}) </tex> имеет место неравенство <tex> size_{B}(f)\le n2^{n+1} </tex>
|proof = [[Файл:Synschemes Theorem1.png|250px|thumb|right|Рис. 2]]
Пусть <tex> f(x_{1},...,x_{n}) </tex> {{---}} произвольная [[Определение булевой функции|булева функция]]. Если <tex> f = 0 </tex>, то схема строится в соответствии с представлением <tex> 0=x_{1}\wedge\overline{x}_{1} </tex>, то есть <tex> size_{B}(0) \le 2</tex>. Если <tex> f \ne 0 </tex>, то <tex> f </tex> может быть задана [[ДНФ|дизъюнктивной нормальной формой]]
::<tex> f(x_{1},...,x_{n}) = K_{1} \vee K_{2} \vee ... \vee K_{s} </tex>,
::<tex> K_{j}=x_{1}\wedge\overline{x}_{2}\wedge{x}_{3}\wedge ... \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)\le s\cdot(2n-1)+s-1 < s\cdot(2n-1)+s = 2ns \le n2^{n+1} </tex>.
Таким образом, для любой функции <tex> f(x_{1},...,x_{n}) </tex> выполняется неравенство
{{Определение
|definition= <tex> f(n) \sim g(n) </tex> означает, что <tex>f</tex> асимптотически эквивалентна <tex>g</tex>, то есть <tex>\lim_lim\limits_{n \to \infty}\frac{f(n)}{g(n)} = 1</tex>
}}
{{Определение
|definition= <tex> f(n) \lesssim g(n) </tex> означает, что <tex>\overline{varlimsup\lim}_limits_{n \to \infty}\frac{f(n)}{g(n)} \le 1</tex>
}}
::<tex> size_{B}(K_{n}) \le size_{B}(K_{k}) + size_{B}(K_{n-k}) + 2^n </tex>.
Так как по [[#Th1|Теореме теореме 1]] <tex> size_{B}(K_{nk}) \le k2^{k+1} </tex> , <tex> size_{B}(K_{n-k}) \le (n-k)2^{n-k+1} </tex>,то
::<tex> size_{B}(K_{n}) \le k2^{k+1} + (n-k)2^{n-k+1} + 2^n </tex>.
|statement =Для любой функции <tex> f(x_{1}, ..., x_{n}) </tex> имеет место соотношение <tex> size_{B}(f)\lesssim 12\frac {2^{n}}{n} </tex>.
|proof = [[Файл:Synschemes-Theorem2.png|300px|thumb|right|Рис. 4]]
Пусть <tex> f(x_{1},...,x_{n}) </tex> {{---}} произвольная булева функция. Рассмотрим разложение <tex> f </tex> по переменным <tex> x_{1},...,x_{nm} </tex>, где <tex> 1 \le m \le n </tex>: Введем функцию <tex> x^{\sigma} = \begin{cases} x, \sigma =1;\\ \overline{x}, \sigma =0\end{cases}</tex> Тогда
<tex> f(x_{1},...,x_{n})= \bigvee x_displaystyle\bigvee_{(\sigma_{1},\wedgedotsc,\overlinesigma_{xm}_)}x_{21}^{\wedgesigma_{x1}_{3}\wedge ... \dotsc\wedgex_{xm}_^{\sigma_{m} }\wedge f(x_\sigma_{m+1},\wedgedotsc,\overlinesigma_{xm}_,x_{m+21},\wedgedotsc,x_{xn}_) </tex>. (Дизъюнкция берется по всевозможным наборам значений переменных <tex> (x_{m+31},\wedge ... \wedgedotsc,x_{x}_{nm}) </tex>.
'''Схема для функции <tex> f </tex> строится из трех подсхем: <tex> S_{1},S_{2},S_{3} </tex>. (рис. 4)'''
:1. Схема <tex> S_{1} </tex> реализует все конъюнкции из множества <tex> K_{m} (x_{1},...,x_{m}) </tex>. В силу [[#Lemma2|Леммы леммы 2]] выполняется неравенство
::<tex> size_{B}(S_{1}) \le size_{B}(K_{m}) \lesssim 2^{m} </tex>.
:2. Схема <tex> S_{2} </tex> реализует систему <tex> F(x_{m+1},...,x_{n}) </tex> всех булевых функций от переменных <tex> x_{m+1},...,x_{n} </tex>. Другими словами, подсхема <tex> S_{2} </tex> вычисляет все булевы функции, зависящие от последних <tex> n - m </tex> переменных. В силу [[#Th1|Теоремы теоремы 1]]
::<tex> size_{B}(S_{2}) \le (n-m)2^{n-m+1}2^{2^{n-m}} </tex>.
