210
правок
Изменения
м
Нет описания правки
Схема <tex> S </tex> для <tex> f </tex> состоит из конъюнкций <tex> K_{j} </tex> (каждая из них в соответствии с [[#Lemma1|Леммой 1]] имеет сложность не более <tex> 2n-1 </tex>) и цепочки из <tex> s-1 </tex> элемента дизъюнкции с <tex> s </tex> свободными входами. Свободные входы этой цепочки присоединяются к выходам схем для конъюнкций <tex> K_{j} </tex>.(рис. 2) Имеем
::<tex> size_{B}(f)\le s\cdot(2n-1)+s-1 < s\cdot(2n-1)+s = 2ns \le n2^{n+1} </tex>.
Если <tex> f = 0 </tex>, то схема строится в соответствии с представлением <tex> 0=x_{1}\wedge\overline{x}_{1} </tex>, то есть<tex> size_{B}(0) \le 2</tex>.
}}
==Метод синтеза схем, предложенный К.Э.ШеннономШеннона==
{{Теорема
|id = Th3
|about = 3
|statement =Для любой функции <tex> f(x_{1}, ..., x_{n}) </tex> имеет место соотношение <tex> size_{B}(f)\lesssim 12\frac {2^{n}}{2n} </tex>.
|proof = [[Файл:Synschemes Theorem2.png|300px|thumb|right|Рис. 4]]
Пусть <tex> f(x_{1},...,x_{n}) </tex> произвольная булева функция. Рассмотрим разложение <tex> f </tex> по переменным <tex> x_{1},...,x_{n} </tex>, где <tex> 1 \le m \le n </tex>:
