20
правок
Изменения
Нет описания правки
{{Определение
|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> {{---}} индексы переменных.
}}
'''Пример линейной программы'''
'''Длина''' линейной программы {{---}} количество строк.
{{Теорема
|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>.
{{Лемма
|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>K_{n, r} < 2^{2^n} \Rightarrow \exists \; f_n: r> \geq \frac{2^n}{2n} </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>= См. также =* [[Определение булевой функции]]* [[Реализация булевой функции схемой из функциональных элементов]]* [[Представление булевых функций линейными программами]]
