210
правок
Изменения
м
Нет описания правки
|statement = Пусть <tex> K_{n}(x_{1}^{\sigma_{1}},\dotsc, x_{n}^{\sigma_{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}^{\wedge\overlinesigma_{x1}_{2}\wedge\dotsc\wedge x_{xn}_^{3}\wedge ... \wedgesigma_{xn}_{i} </tex> может быть представлена в виде конъюнкции двух конъюнкций длины <tex> k </tex> и <tex> n-k </tex>:
::<tex> x_{1}^{\wedge\overlinesigma_{x1}_{2}\wedge{x}_{3}\wedge ... dotsc\wedgex_{xn}_^{\sigma_{n}} = (x_{1}^{\wedge\overlinesigma_{x1}_{2}\wedge{x}_{3}\wedge ... dotsc\wedgex_{xk}_^{\sigma_{k}})(x_{k+1}^{\wedge\overline{x}_sigma_{k+21}}\wedge{x}_{k+3}\wedge ... dotsc\wedgex_{xn}_^{\sigma_{n}}) </tex>.
Поэтому схема для <tex> K_{n} </tex> может быть образована из схем для <tex> K_{k}(x_{1}^{\wedge\overlinesigma_{x1}_{2},\wedgedotsc,x_{xk}_^{3}\wedge ... \wedgesigma_{xk}_{n}) </tex> и <tex> K_{n-k}(x_{k+1}^{\wedge\overline{x}_sigma_{k+21}},\wedgedotsc,x_{xn}_^{k+3}\wedge ... \wedgesigma_{xn}_{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>.
