20
правок
Изменения
→Теорема о нижней оценке на число элементов в схеме
Построение функциональной схемы по линейной программе очевидно.
}}
===Оценка на количество линейных программ над <tex>\{\downarrow\}</tex> длины <tex>r</tex>===
<tex>n</tex> {{---}} количество аргументов булевой функции.
Количество линейных программ <tex>= K_{n, r} = n^2 \cdot (n+1)^2 \cdot (n+2)^2 \cdot \ldots \cdot (n+r-1)^2 \leq (n+r)^{2r}</tex>
<tex>\log_2{K_{n, r}} \leq \log_2 {(n+r)^{2r}} = 2r \log_2 {(n+r)}</tex>
{{Лемма
|id=Лемма1
|statement=<tex>\exists</tex> булева функция <tex>f: size_B(f) \geq \frac{2^n}{2n}</tex>
|proof=Предположим противное, пусть размер всех линейных программ <tex>r < \frac{2^n}{2n} </tex>
<tex>\log_2{K_{n, r}} \leq 2 r \log_2 {(n+r)} < \frac{2 \cdot 2^n}{2n} \log_2{(n+ \frac{2^n}{2n})} \leq \frac{2^n}{n} \log_2 {2^n} = 2^n \Rightarrow</tex>
<tex>\Rightarrow K_{n, r} < 2^{2^n}</tex> {{---}} такого быть не может, следовательно, <tex>\exists \; f_n: r> \frac{2^n}{2n} </tex>
Обобщим для произвольного <tex>c</tex>
<tex>r<\frac{2^n}{2cn}</tex>
<tex>\log_2 K_{n,r}\leq 2r\log_2(n+r)<\frac{2\cdot 2^n}{2cn}\log_2(n+\frac{2^n}{2cn})\leq \frac{2^n}{cn}\log_2 2^n=\frac{2^n}{c} \Rightarrow</tex>
<tex>\Rightarrow K_{n,r}<2^{\frac{2^n}{c}} !!! </tex>
}}
