436
правок
Изменения
Image formatting fixed
|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>v_1x_{n + 1}, \dots , v_mx_{n + m}</tex>, которая в любой переменной <tex>v_ix_i, i = 1 + n, \dots , m + n</tex>, вычисляет функцию <tex>f_{v_ix_i}(x_1, \ldots , x_n)</tex>;<br><br>
# По каждой линейной программе <tex>P</tex> со входными переменными <tex>x_1, \dots , x_n</tex>, вычисляющей в выходной переменной <tex>Z</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>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>S</tex>: <tex>u_1, \dots , u_{n + m}</tex>. Программа <tex>P_S</tex> будет последовательностью <tex>m</tex> присваиваний.<br>
* Пусть вершина <tex>u_{i + n + i}</tex> помечена <tex>\neg</tex>, и в нее входит ребро из <tex>u_j</tex>. Тогда в качестве <tex>i</tex>-ой команды поместим в <tex>P_S</tex> присваивание <tex>u_x_{i + n + i}= \neg u_jx_j</tex>;* Пусть вершина <tex>u_{i + n + i}</tex> помечена <tex>\circ \in \{ \wedge , \vee \}</tex>, и в нее входят ребра из <tex>u_j</tex> и <tex>u_k</tex>. Тогда в качестве <tex>i</tex>-ой команды поместим в <tex>P_S</tex> присваивание <tex>u_x_{i + n + i} = u_j x_j \circ u_kx_k</tex>.
<br>
Топологическая сортировка вершин гарантирует, что <tex>j < n + i \wedge k < n + i</tex>. Поэтому при вычислении <tex>u_x_{n + i}</tex> значения аргументов уже получены и индукцией по глубине легко показать, что <tex>\forall i = 1, \dots , m</tex> программа <tex>P_S</tex> вычисляет в переменной <tex>v_ix_i</tex> функцию <tex>f_{v_ix_i}(x_1, \dots, x_n)</tex>.
}}
'''Пример'''
[[Файл:Logic_scheme_sample_boolean_functions_and_linear_programs.gif|300px|thumb|centerleft|Пример схемы]]
Воспользуемся только что доказанной теоремой, и построим на основании этой схемы линейную программу.<br>
Установим соответствие между вершинами схемы и переменными: <tex>x \; — \; x_0, \; y \; — \; x_1, \; z \; — \; x_2, \; a \; — \; x_3, \; b \; — \; x_4, \; c \; — \; x_5, \; d \; — \; x_6, \; e \; — \; x_7, \; f \; — \; x_8</tex>.<br>
Результатом топологической сортировки данного графа может стать последовательность вершин: <tex>x, y, z, a, b, c, d, e, f</tex>. Тогда программа <tex>P_S</tex> будет иметь следующий вид:<br>
<tex>x_3 = x_0 \wedge x_1</tex><br>
