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>.
===Оценка на количество линейных программ над <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>
{{Лемма
|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>\Rightarrow K_frac{2^n, r} < 2^{2^n2cn}</tex> {{--для какого-}} такого быть не может, следовательно, то <tex>\exists \; f_n: rc > \frac{2^n}{2n} 1</tex>.
===Возвращение к теореме о нижней оценке===<tex>|F_g| \log_2 K_leq 2^{n,r}\leq 2r\log_2(n+r)<\frac{2\cdot 2^n}{2cnc}}\log_2(n+Rightarrow \frac{|F_g|}{2^{2^n}{2cn})\leq \frac{2^\frac{2^n}{cnc}\log_2 }{2^{2^n}} =\frac2^{2^n}(\overset{c} \Rightarrow</tex> <tex>\Rightarrow K_{n,r0}<2^{\frac{2^n1}{c}-1} !!! )}\rightarrow 0</tex>}}= См. также =* [[Определение булевой функции]]* [[Реализация булевой функции схемой из функциональных элементов]]* [[Представление булевых функций линейными программами]]
