210
правок
Изменения
Добавление картинок
Данная схема может быть построена их <tex> n </tex> элементов отрицания, присоединенных к входам, и цепочки из элементов конъюнкции, имеющих <tex> n </tex> "свободных" входов.
Каждый <tex> i </tex>-й вход этой цепочки присоединяется к входу схемы, если <tex> i </tex>-й множитель равен <tex> x_{i} </tex>, или к выходу <tex> i </tex>-го элемента отрицания, если <tex> i </tex>-й множитель равен <tex> \overline{x}_{i} </tex>.(рис. 1)
Очевидно, что сложность построенной схемы равна <tex> 2n-1 </tex>.
|about = 1
|statement = Имеет место неравенство <tex> Size_{B}(n)\le n2^{n+1} </tex>
|proof = [[Файл:Synschemes Theorem1.png|250px|thumb|right|Рис. 2]]Пусть <tex> f(x_{1},...,x_{n}) </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}(n)\le s(2n-1)+s-1 < s(2n-1)+s = 2ns \le n2^{n+1} </tex>.
|about = 2
|statement = Имеет место соотношение <tex> Size_{B}(K_{n}) \sim 2^n </tex>
|proof = [[Файл:Synschemes Lemma2.png|250px|thumb|right|Рис. 3]]Каждая конъюнкция <tex> x_{1}\wedge\overline{x}_{2}\wedge{x}_{3}\wedge ... \wedge{x}_{i} </tex> может быть представлена в виде конъюнкции двух конъюнкций длины <tex> k </tex> и <tex> n-k </tex>:
::<tex> 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}) </tex>.
Поэтому схема для <tex> K_{n} </tex> может быть образована из схем для <tex> K_{k}(x_{1}\wedge\overline{x}_{2}\wedge{x}_{3}\wedge ... \wedge{x}_{n}) </tex> и <tex> K_{n-k}(x_{k+1}\wedge\overline{x}_{k+2}\wedge{x}_{k+3}\wedge ... \wedge{x}_{n}) </tex> и системы из <tex> 2^n </tex> элементов конъюнкции, осуществляющих вышеприведенную операцию. (рис. 3) Следовательно,
::<tex> Size_{B}(K_{n}) \le Size_{B}(K_{k}) + Size_{B}(K_{n-k}) + 2^n </tex>.
|about = 3
|statement = Имеет место соотношение <tex> Size_{B}(n)\lesssim 12\frac {2^{n}}{2} </tex>.
|proof = [[Файл:Synschemes Theorem2.png|300px|thumb|right|Рис. 4]]Пусть <tex> f(x_{1},...,x_{n}) </tex> произвольная булева функция. Рассмотрим разложение <tex> f </tex> по переменным <tex> x_{1},...,x_{n} </tex>, где <tex> 1 \le m \le n </tex>:
<tex> 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}) </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]] выполняется неравенство
