210
правок
Изменения
м
Нет описания правки
|id = Lemma2
|about = 2
|statement = Пусть <tex> K_{n}(x_{1},x_{2},\dotsc,x_{n},\dotsc, lbrace x_{1}^{\sigma_{1}},x_{2}^{\sigma_{2}},\dotsc,x_{n}^{\sigma_{n}},\dotsc,\barrbrace^{x2^n}_{i=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> i </tex> соответствует свой набор <tex> \lbrace \sigma_{1},\dotsc,\sigma_{n} \rbrace </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> f </tex> строится из трех подсхем: <tex> S_{1},S_{2},S_{3} </tex>. (рис. 4)'''
:1. Схема <tex> S_{1} </tex> реализует все конъюнкции из множества Множество <tex> K_{m} (x_{1},...,x_{m}) </tex>, которое содержит всевозможные конъюнкции <tex>x_{1}^{\sigma_{1}}\wedge\dotsc\wedge x_{m}^{\sigma_{m}}</tex>. И схема <tex> S_{1} </tex> реализует все эти конъюнкции. В силу [[#Lemma2|леммы 2]] выполняется неравенство
::<tex> size_{B}(S_{1}) \le size_{B}(K_{m}) \lesssim 2^{m} </tex>.
