210
правок
Изменения
Картинка в теорему 2
|id = Lemma2
|about = 2
|statement = Пусть <tex> K_{n}(x_{1},x_{2},\dotsc,x_{n},\dotsc, x_{1}^{\sigma_{1}},x_{2}^{\sigma_{2}},\dotsc, x_{n}^{\sigma_{n}},\dotsc,\bar{x}_{1},\bar{x}_{2},\dotsc, \bar{x}_{n}) </tex> {{---}} система всех <tex> 2^{n} </tex> конъюнкций <tex> x_{1}^{\sigma_{1}}\wedge\dotsc\wedge x_{n}^{\sigma_{n}}</tex>, тогда для <tex> K_{n} </tex> имеет место соотношение <tex> size_{B}(K_{n}) \sim 2^n </tex>
|proof = [[Файл:Synschemes Lemma2.png|250px|thumb|right|Рис. 3]]
Конъюнкции <tex> x_{1}^{\sigma_{1}}\wedge\dotsc\wedge x_{n}^{\sigma_{n}}</tex> соответствуют функциям <tex> g </tex> из определения функции, а <tex> K_{n} </tex> соответствует функции <tex> S </tex>. Разделим цепочки конъюнкций на две части. Каждая конъюнкция <tex> x_{1}^{\sigma_{1}}\wedge\dotsc\wedge x_{n}^{\sigma_{n}} </tex> может быть представлена в виде конъюнкции двух конъюнкций длины <tex> k </tex> и <tex> n-k </tex>(<tex> k </tex> мы выберем позже):
::<tex> x_{1}^{\sigma_{1}}\wedge\dotsc\wedge x_{n}^{\sigma_{n}} = (x_{1}^{\sigma_{1}}\wedge\dotsc\wedge x_{k}^{\sigma_{k}})(x_{k+1}^{\sigma_{k+1}}\wedge\dotsc\wedge x_{n}^{\sigma_{n}}) </tex>.
|about = 2
|statement =Для любой функции <tex> f(x_{1}, ..., 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},...,x_{n}) </tex> {{---}} произвольная булева функция, <tex> f \ne 0 </tex>. Заменим в схеме (рис. 2) верхнюю часть схемы, реализующую конъюнкции <tex> K_{1} \vee K_{2} \vee ... \vee K_{s} </tex>, схемой, реализующей все конъюнкции из <tex> K_{n} </tex>. Тогда для любой такой функции <tex> f(x_{1},...,x_{n}) </tex> (не равной нулю) имеем
::<tex> size_{B}(f) \le size_{B}(K_{n})+s-1 \le size_{B}(K_{n})+2^{n}-1 \lesssim 2^{n+1} </tex>
::<tex> size_{B}(f) \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}} </tex>.
Положим (для упрощения дальнейших выкладок) <tex> k=n-m </tex>. Тогда
::<tex> size_{B}(f) \lesssim 3 \cdot 2^{n-k} +k2^{k+1}2^{2^{k}} </tex>.
