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