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