Просмотр исходного текста страницы Нижняя оценка размера схем из функциональных элементов

== Теорема о нижней оценке на число элементов в схеме из функциональных элементов ==

{{Теорема
|statement=Большинство [[Определение_булевой_функции | булевых функций]] требуют для реализации порядка <tex>\Omega(\frac{2^n}{n})</tex> [[Реализация_булевой_функции_схемой_из_функциональных_элементов | функциональных элементов]], где <tex>n</tex> — количество аргументов функции. 
Формальная запись теоремы:
<tex>f(n) = \frac{2^n}{n} \; \; \; g(n): \frac{g}{f} \longrightarrow 0</tex>

<tex>F_g = \{\text{Булевы функции, } size \leq g(n)\}</tex>
Тогда <tex>\frac{|F_g|}{2^{2^n}} \longrightarrow 0</tex>
}}
Для доказательства этой теоремы нам понадобится доказать несколько вспомогательных утверждений.
{{Определение
|definition=
'''[[Представление_булевых_функций_линейными_программами#Линейные_программы|Линейная программа]]''' {{---}} список строк вида <tex>(a, (i_1, \ldots, i_k))</tex>, где <tex>a \in B</tex> (базис), <tex>a: \mathbb B^k \rightarrow \mathbb B</tex>, <tex>i_j</tex> {{---}} индексы переменных.
}}
'''Пример линейной программы'''

Линейная программа для функции <tex>x_1 \oplus x_2</tex> над базисом <tex>\{ \land, \lor, \lnot \}</tex>

<tex>y_1 = \lnot x_1</tex>

<tex>y_2 = \lnot x_2</tex>

<tex>y_3 = x_1 \land y_2</tex>

<tex>y_4 = x_2 \land y_1</tex>

<tex>y_5 = y_3 \lor y_4</tex>

'''Длина''' линейной программы {{---}} количество строк.
{{Теорема
|statement= Для булевой функции <tex>f </tex> существует линейная программа длины <tex>r</tex> тогда и только тогда, когда существует схема, использующая <tex>r</tex> функциональных элементов.
|proof=Чтобы построить по схеме программу, можно занумеровать элементы схемы в порядке [[Использование_обхода_в_глубину_для_топологической_сортировки#Топологическая_сортировка|топологической сортировки]], и для каждого элемента <tex>m</tex> с функцией <tex>a</tex> и входами <tex>i_1, \ldots, i_k</tex> сопоставить строчку линейной программы с номером <tex>m</tex> вида <tex>(a, (i_1, \ldots, i_k))</tex>. 

Построение функциональной схемы по линейной программе очевидно.
}}
===Оценка на количество линейных программ над <tex>\{\downarrow\}</tex> длины <tex>r</tex>===
<tex>n</tex> {{---}} количество аргументов булевой функции.

<tex>\downarrow</tex> {{---}} стрелка Пирса, является сама по себе базисом булевых функций.

В первой строчке мы можем выбрать одну из <tex>n</tex> переменных (<tex>x_1, \ldots, x_n</tex>) и применить к ней <tex>\downarrow</tex>. Получим еще одну переменную <tex>y_1</tex>. Во второй строчке программы нам на выбор доступны уже <tex>n+1</tex> переменных (<tex>x_1, \ldots, x_n, y_1</tex>). В общем случае на <tex>i</tex>-й строчке (нумерация с единицы) мы можем применить стрелку Пирса к одной из <tex>n+i-1</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>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>K_{n, r} < 2^{2^n} \Rightarrow \exists \; f_n: r \geq \frac{2^n}{2n} </tex>

Теперь возьмем все булевы функции, размер которых не превышает <tex>\frac{2^n}{2cn}</tex> для какого-то <tex>c > 1</tex>.

Тогда
<tex>\log_2 K_{n,r}\leq 2r\log_2(n+r) \leq \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} \leq 2^{\frac{2^n}{c}} \Rightarrow \exists \; f_n: r> \frac{2^n}{2cn} </tex>
}}
Таким образом, количество линейных программ длины <tex>\leq \frac{2^n}{2cn}</tex> не больше <tex>2^{\frac{2^n}{c}}</tex>

===Возвращение к теореме о нижней оценке===
<tex>|F_g| \leq 2^{\frac{2^n}{c}} \Rightarrow \frac{|F_g|}{2^{2^n}} \leq \frac{2^\frac{2^n}{c}}{2^{2^n}} = 2^{2^n (\overset{< 0}{\frac{1}{c}-1})}\rightarrow 0</tex>
= См. также =
* [[Определение булевой функции]]
* [[Реализация булевой функции схемой из функциональных элементов]]
* [[Представление булевых функций линейными программами]]