20
правок
Изменения
→Теорема о нижней оценке на число элементов в схеме
<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 \; \exists</tex> линейная программа длины <tex>r \Leftrightarrow \exists </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>. Алабудай балабулабудай. тудудумПостроение функциональной схемы по линейной программе очевидно.
}}
