436
правок
Изменения
Добавлено: теорема о связи между схемами и линейными программами, пример
{{В разработке}}
=Линейные программы ={{Определение|definition='''Линейная программа''' {{---}} последовательность присваиваний вида <tex>x = F(x_1, x_2, \dots , x_n)</tex>, где <tex>x, x_1, \dots , x_n</tex> {{---}} переменные, а <tex>F</tex> {{---}} <tex>k</tex>-местная базисная функция. }}'''Пример'''<br>Для базиса <tex>B_0 = \{\vee, \wedge, \neg \}</tex> линейная программа состоит из присваиваний вида: * <tex>Z = X \wedge Y</tex>;* <tex>Z = X \vee Y</tex>;* <tex>Z = \neg X</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>Z</tex> программы получит итоговое значение <tex>P_Z(\sigma_1, \dots , \sigma_n)</tex>. {{Определение|definition='''Программа''' <tex>P</tex> со входными переменными <tex>x_1,\dots , x_n</tex> '''вычисляет''' в выходной переменной <tex>Z</tex> '''функцию''' <tex>F(x_1, \dots , x_n)</tex>, если для любого набора значений входов <tex>\sigma_1, \dots , \sigma_n</tex> после завершения работы <tex>P_Z(\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>v_1, \dots , v_m</tex>, которая в любой переменной <tex>v_i, i = 1, \dots , m</tex>, вычисляет функцию <tex>f_{v_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_{n + i}</tex> помечена <tex>\neg</tex>, и в нее входит ребро из <tex>u_j</tex>. Тогда в качестве <tex>i</tex>ой команды поместим в <tex>P_S</tex> присваивание <tex>u_{n + i}= \neg u_j</tex>;* Пусть вершина <tex>u_{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_{n + i} = u_j \circ u_k</tex>.<br>Топологическая сортировка вершин гарантирует, что <tex>j < n + i \wedge k < n + i</tex>. Поэтому при вычислении <tex>u_{n + i}</tex> значения аргументов уже получены и индукцией по глубине легко показать, что <tex>\forall i = 1, \dots , m</tex> программа <tex>P_S</tex> вычисляет в переменной <tex>v_i</tex> функцию <tex>f_{v_i}(x_1, \dots, x_n)</tex>.}} '''Пример'''[[Файл:Logic_scheme_sample_boolean_functions_and_linear_programs.gif|300px|thumb|center|Пример схемы]]Воспользуемся только что доказанной теоремой, и построим на основании этой схемы линейную программу.<br>Результатом топологической сортировки данного графа может стать последовательность вершин: <tex>x, y, z, a, b, c, d, e, f</tex>. Тогда программа <tex>P_S</tex> будет иметь следующий вид:<tex>a = x \wedge y</tex><br><tex>b = \neg z</tex><br><tex>c = \neg a</tex><br><tex>d = c \wedge z</tex><br><tex>e = a \wedge b</tex><br><tex>f = d \vee e</tex><br> = См. также ==
* [[Определение булевой функции]]
* [[Реализация булевой функции схемой из функциональных элементов]]
[[Категория: Дискретная математика]]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Булевы функции ]]
