Изменения
Нет описания правки
|id = Lemma1
|about = 1
|statement =Для любой функции<tex>f(x_{1}, ..., x_{n})</tex>, реализующей конъюнкцию <tex> n </tex> аргументовЛюбой конъюнкт в СДНФ можно представить не более, чем <tex> size_{B}(f)\le2n2n-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>size_{B}(f)=2+3=5\le 7</tex>.]]
Построим данную схему следующим образом: если <tex> i </tex>-й множитель равен <tex> \bar{x}_{i} </tex>, то присоединяем к выходу <tex> i </tex> элемент отрицания и последовательно присоединяем к элементу конъюнкции, иначе просто присоединяем к "свободному" входу элемента конъюнкции.
Приведем пример для <tex> f=\bar{x}_{1}\wedge x_{2}\wedge x_{3} \wedge \bar{x}_{4}</tex> (рис. 1).
}}
|definition= <tex> f(n) \lesssim g(n) </tex> означает, что <tex>\varlimsup\limits_{n \to \infty}\frac{f(n)}{g(n)} \le 1</tex>
}}
::Будем считать,что схема <tex>S</tex> вычисляет систему булевых функций, если на каждый вход схемы подаются всевозможные наборы аргументов функции, а в выходах вычисляется функция от соответствующего набора аргументов. Также будем считать, что <tex> size_{B}(S)</tex> {{---}} это сложность схемы, вычисляющей систему булевых функций.
{{Лемма
Тогда
<tex>f(x_{1},...,x_{n})=\displaystyle\bigvee_{(\sigma_{1},\dotsc,\sigma_{m})}x_{1}^{\sigma_{1}}\wedge\dotsc\wedge x_{m}^{\sigma_{m}}\wedge f(\sigma_{1},\dotsc,\sigma_{m},x_{m+1},\dotsc,x_{n}) </tex>. (Дизъюнкция берется по всевозможным наборам значений переменных <tex> (x_{1},\dotsc,x_{m}) </tex>.
'''Схема для функции <tex> f </tex> строится из трех подсхем: <tex> S_{1},S_{2},S_{3} </tex>. (рис. 4)'''
