436
правок
Изменения
Ref added
|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>.
= Литература =
# Дехтярь М.И. Реализация булевых функций с помощью логических схем // Введение в схемы, автоматы и алгоритмы, 2007. URL: https://www.intuit.ru/studies/courses/1030/205/lecture/5306
[[Категория: Дискретная математика]]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Булевы функции ]]
