20
правок
Изменения
Нет описания правки
Построение функциональной схемы по линейной программе очевидно.
}}
===Оценка на количество линейных программ над <tex>\{\downarrow\}</tex> (стрелка Пирса является базисом) длины <tex>r</tex>===
<tex>n</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>
