210
правок
Изменения
м
Нет описания правки
|id = Lemma2
|about = 2
|statement = Для функции Пусть <tex> K_{n}(x_{1},\dotsc,x_{n}) </tex> {{---}} система всех <tex> 2^{n} </tex> конъюнкций <tex> x_{1}\wedge\dotsc\wedge x_{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\overline{x}_{2}\wedge{x}_{3}\wedge ... \wedge{x}_{i} </tex> может быть представлена в виде конъюнкции двух конъюнкций длины <tex> k </tex> и <tex> n-k </tex>:
