210
правок
Изменения
м
Данная схема может быть построена их Построим данную схему следующим образом: возьмем <tex> n </tex> элементов отрицания, присоединенных к входамвыходам, и цепочки из элементов конъюнкции, имеющих <tex> n </tex> "свободных" входов.
Незначительные исправления
Для любой конъюнкции <tex> x_{1}\wedge ... \wedge x_{n} </tex> <tex> Size_{B}(x_{1} ... x_{n})\le 2n-1 </tex>
|proof = [[Файл:Synschemes Lemma1.png|250px|thumb|right|Рис. 1]]
Каждый <tex> i </tex>-й вход этой цепочки присоединяется к входу схемы, если <tex> i </tex>-й множитель равен <tex> x_{i} </tex>, или к выходу <tex> i </tex>-го элемента отрицания, если <tex> i </tex>-й множитель равен <tex> \overline{x}_{i} </tex>.(рис. 1)
|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>.
