210
правок
Изменения
м
Нет описания правки
|about = 1
|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)\le 2n-1 </tex>.
Приведем пример для конъюнкции <tex> f=\bar{x}_{1}\wedge x_{2}\wedge x_{3} \wedge \bar{x}_{4}</tex> (рис. 1).
Сложность построенной схемы <tex>size(\barsize_{x}_{1}\wedge x_{2}\wedge x_{3} \wedge \bar{x}_{4B}(f)=2+3=5\le 7</tex>. Из доказанной леммы следует, что любой конъюнкт в СДНФ можно представить не более, чем <tex> 2n-1 </tex> элементами.
}}
::<tex> size_{B}(S_{2}) \le (n-m)2^{n-m+1}2^{2^{n-m}} </tex>.
:3. Схема <tex> S_{3} </tex> производит "сборку" в соответствии с разложением функции <tex> f </tex>: для каждого набора <tex> \widetilde{\sigma}=(\sigma_{1},\dotsc,\sigma_{m}) </tex> реализуется конъюнкция
::<tex> x_{1}^{\wedge\overlinesigma_{x1}_{2}\wedge{x}_{3}\wedge ... dotsc\wedgex_{xm}_^{\sigma_{m}f(x_{m+1}\wedgef(\overline{x}_widetilde{m+2}\wedge{xsigma}_,x_{m+31},\wedge ... \wedge{x}_dotsc, x_{n}) </tex> (<tex> 2^{m} </tex> элементов конъюнкции) и образуется дизъюнкция таких конъюнкций (<tex> 2^{m}-1 </tex> элементов дизъюнкции).
Поэтому выполняется неравенство <tex> size_{B}(S_{3}) \le 2^{m} +2^{m} -1 </tex>. Таким образом,
