1632
правки
Изменения
м
rollbackEdits.php mass rollback
Определения и основные понятия, связанные с булевыми функциями описаны в статье [[Определение булевой функции|"определение булевой функции"]].<br>
{{Определение
|definition='''Линейная программа''' {{---}} последовательность строк вида <tex>{\{s_i\}}_{i=mn}^t</tex>, в которой <tex>s_i</tex> имеет вид <tex>x_i = F(x_{a_1}, x_{a_2}, \ldots , x_{a_na_m})</tex>, где <tex>x_i, x_{a_1}, \dots , x_{a_na_m}</tex> {{---}} переменные, каждое из чисел <tex>a_ia_j</tex> меньше <tex>i</tex>, а <tex>F</tex> {{---}} <tex>nm</tex>-местная базисная функция. Такая линейная программа имеет <tex>mn</tex> входных переменных, которые не выражаются через операции вычисления.
}}
'''Пример'''<br>
Линейная программа <tex>P</tex> с выделенными переменными <tex>x_1,\dots , x_n</tex> порождает для каждого набора <tex>\sigma_1, \dots , \sigma_n</tex> значений входных переменных естественный процесс вычисления:
# Переменным <tex>x_1, \dots , x_n</tex> присваиваются значения <tex>\sigma_1, \dots , \sigma_n</tex>, соответственно, а каждой из остальных переменных присваивается значение <tex>0</tex>;
# Последовательно выполняются присваивания программы <tex>P</tex>, в результате чего каждая из переменных <tex>x_i \; \forall i = 1 .. n</tex> программы получит итоговое значение <tex>P_ZP_i(\sigma_1, \dots , \sigma_n)</tex>.
{{Определение
|definition='''Программа''' <tex>P</tex> со входными переменными <tex>x_1,\dots , x_n</tex> '''вычисляет''' в выходной переменной <tex>Zx_m</tex> '''функцию''' <tex>F(x_1, \dots , x_n)</tex>, если для любого набора значений входов <tex>\sigma_1, \dots , \sigma_n</tex> после завершения работы <tex>P_ZP_m(\sigma_1, \dots , \sigma_n) = F(\sigma_1, \dots , \sigma_n)</tex>.
}}
|statement=
<br>
# По каждой логической схеме <tex>S</tex> со входами <tex>x_1, \dots , x_n</tex> и функциональными элементами <tex>v_1, \dots , v_m</tex> можно эффективно построить линейную программу <tex>P_S</tex> со входными переменными <tex>x_1, \dots , x_n</tex> и рабочими переменными <tex>x_{n + 1}, \dots , x_{n + m}</tex>, которая в любой переменной <tex>x_i, i = \in [1 + n, \dots , m + n]</tex>, вычисляет функцию <tex>f_{x_i}(x_1, \ldots , x_n)</tex>;<br><br># По каждой линейной программе <tex>P</tex> со входными переменными <tex>x_1, \dots , x_n</tex>, вычисляющей в выходной переменной <tex>Zx_m</tex> некоторую функцию <tex>F(x_1, \dots , x_n)</tex> можно эффективно построить логическую схему <tex>S_P</tex> со входами <tex>x_1,\dots , x_n</tex>, в которой имеется вершина <tex>v</tex> такая, что <tex>f_v(x_1, \dots , x_n) = F(x_1, \dots , x_n)</tex>.
|proof=
'''(1)'''<br>
* Пусть вершина <tex>u_{i + n}</tex> помечена <tex>\circ \in \{ \wedge , \vee \}</tex>, и в нее входят ребра из <tex>u_j</tex> и <tex>u_k</tex>. Тогда в качестве <tex>i</tex>-ой команды поместим в <tex>P_S</tex> присваивание <tex>x_{i + n} = x_j \circ x_k</tex>.
<br>
Топологическая сортировка вершин гарантирует, что <tex>j < n + i \wedge k < n + i</tex>. Поэтому при вычислении <tex>x_{n + i}</tex> значения аргументов уже получены и индукцией по глубине легко показать, что для любого <tex>i \forall i = in [1, \dots , m]</tex> программа <tex>P_S</tex> вычисляет в переменной <tex>x_i</tex> функцию <tex>f_{x_i}(x_1, \dots, x_n)</tex>.
}}
