210
правок
Изменения
м
Нет описания правки
|id = Lemma1
|about = 1
|statement = Для любой функции <tex> f(x_{1}, ..., x_{n}) </tex>, реализующей конъюнкцию <tex> n </tex> аргументов, <tex> size_{B}(f)\le 2nle2n-1 </tex>|proof = [[Файл:Synschemes Lemma1.png|250px|thumb|right|Рис. 1]] Построим данную схему следующим образом: возьмем <tex> n </tex> элементов отрицания, присоединенных к выходам, и цепочки из элементов конъюнкции, имеющих <tex> n </tex> "свободных" входов. Если <tex> i </tex>-й множитель равен Схема для <tex> \bar{x}_{1}\wedge x_{2}\wedge x_{i3} \wedge \bar{x}_{4} </tex>, то <tex> i </tex>-й вход этой цепочки присоединяется к входу схемы. А ]] Построим данную схему следующим образом: если <tex> i </tex>-й множитель равен <tex> \bar{x}_{i} </tex>,то присоединяется присоединяем к выходу <tex> i </tex>-го элемент отрицания и присоединяем к элементу конъюнкции, иначе просто присоединяем к "свободному" входу элемента отрицанияконъюнкции.(рис. 1)
Очевидно, что сложность построенной схемы <tex> size_{B}(f)= n+n-1 = 2n-1 </tex>.
Поэтому <tex> size_{B}(f)\le 2n-1 </tex>.
Приведем пример для конъюнкции <tex> \bar{x}_{1}\wedge x_{2}\wedge x_{3} \wedge \bar{x}_{4}</tex> (рис. 1).
Сложность построенной схемы <tex>size(\bar{x}_{1}\wedge x_{2}\wedge x_{3} \wedge \bar{x}_{4})=2+3=5\le 7.
}}
