Представление булевых функций линейными программами — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Intro added)
(Intro added)
Строка 2: Строка 2:
  
 
= Линейные программы =
 
= Линейные программы =
 +
Определения и основные понятия, связанные с булевыми функциями описаны в статье [[Определение булевой функции]].<br>
 
{{Определение
 
{{Определение
 
|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>-местная базисная функция.  
 
|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>-местная базисная функция.  
Строка 18: Строка 19:
 
|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>.
 
|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>.
 
}}
 
}}
 +
 
= Связь между схемами и линейными программами =
 
= Связь между схемами и линейными программами =
 
Как известно, [[Реализация булевой функции схемой из функциональных элементов|булевы функции представимы в виде схем из функциональных элементов]]. В данном пункте мы определим связь между такими схемами и линейными программами.<br>
 
Как известно, [[Реализация булевой функции схемой из функциональных элементов|булевы функции представимы в виде схем из функциональных элементов]]. В данном пункте мы определим связь между такими схемами и линейными программами.<br>

Версия 12:13, 3 июня 2020

Эта статья находится в разработке!

Линейные программы

Определения и основные понятия, связанные с булевыми функциями описаны в статье Определение булевой функции.

Определение:
Линейная программа — последовательность присваиваний вида [math]x = F(x_1, x_2, \dots , x_n)[/math], где [math]x, x_1, \dots , x_n[/math] — переменные, а [math]F[/math][math]k[/math]-местная базисная функция.

Пример
Для базиса [math]B_0 = \{\vee, \wedge, \neg \}[/math] линейная программа состоит из присваиваний вида:

  • [math]Z = X \wedge Y[/math];
  • [math]Z = X \vee Y[/math];
  • [math]Z = \neg X[/math].


Линейная программа [math]P[/math] с выделенными переменными [math]x_1,\dots , x_n[/math] порождает для каждого набора [math]\sigma_1, \dots , \sigma_n[/math] значений входных переменных естественный процесс вычисления:

  1. Переменным [math]x_1, \dots , x_n[/math] присваиваются значения [math]\sigma_1, \dots , \sigma_n[/math], соответственно, а каждой из остальных переменных присваивается значение [math]0[/math];
  2. Последовательно выполняются присваивания программы [math]P[/math], в результате чего каждая из переменных [math]Z[/math] программы получит итоговое значение [math]P_Z(\sigma_1, \dots , \sigma_n)[/math].


Определение:
Программа [math]P[/math] со входными переменными [math]x_1,\dots , x_n[/math] вычисляет в выходной переменной [math]Z[/math] функцию [math]F(x_1, \dots , x_n)[/math], если для любого набора значений входов [math]\sigma_1, \dots , \sigma_n[/math] после завершения работы [math]P_Z(\sigma_1, \dots , \sigma_n) = F(\sigma_1, \dots , \sigma_n)[/math].


Связь между схемами и линейными программами

Как известно, булевы функции представимы в виде схем из функциональных элементов. В данном пункте мы определим связь между такими схемами и линейными программами.

Теорема:

  1. По каждой логической схеме [math]S[/math] со входами [math]x_1, \dots , x_n[/math] и функциональными элементами [math]v_1, \dots , v_m[/math] можно эффективно построить линейную программу [math]P_S[/math] со входными переменными [math]x_1, \dots , x_n[/math] и рабочими переменными [math]v_1, \dots , v_m[/math], которая в любой переменной [math]v_i, i = 1, \dots , m[/math], вычисляет функцию [math]f_{v_i}(x_1, \ldots , x_n)[/math];

  2. По каждой линейной программе [math]P[/math] со входными переменными [math]x_1, \dots , x_n[/math], вычисляющей в выходной переменной [math]Z[/math] некоторую функцию [math]F(x_1, \dots , x_n)[/math] можно эффективно построить логическую схему [math]S_P[/math] со входами [math]x_1,\dots , x_n[/math], в которой имеется вершина [math]v[/math] такая, что [math]f_v(x_1, \dots , x_n) = F(x_1, \dots , x_n)[/math].
Доказательство:
[math]\triangleright[/math]

(1)
Пусть [math]S[/math] — схема со входами [math]x_1, \dots , x_n[/math] и функциональными элементами [math]v_1, \dots , v_m[/math]. Построим по ней линейную программу [math]P_S[/math] со входными переменными [math]x_1, \dots , x_n[/math] следующим образом. Топологически отсортируем все входные и функциональные вершины [math]S[/math]: [math]u_1, \dots , u_{n + m}[/math]. Программа [math]P_S[/math] будет последовательностью [math]m[/math] присваиваний.

  • Пусть вершина [math]u_{n + i}[/math] помечена [math]\neg[/math], и в нее входит ребро из [math]u_j[/math]. Тогда в качестве [math]i[/math]ой команды поместим в [math]P_S[/math] присваивание [math]u_{n + i}= \neg u_j[/math];
  • Пусть вершина [math]u_{n + i}[/math] помечена [math]\circ \in \{ \wedge , \vee \}[/math], и в нее входят ребра из [math]u_j[/math] и [math]u_k[/math]. Тогда в качестве [math]i[/math]ой команды поместим в [math]P_S[/math] присваивание [math]u_{n + i} = u_j \circ u_k[/math].


Топологическая сортировка вершин гарантирует, что [math]j \lt n + i \wedge k \lt n + i[/math]. Поэтому при вычислении [math]u_{n + i}[/math] значения аргументов уже получены и индукцией по глубине легко показать, что [math]\forall i = 1, \dots , m[/math] программа [math]P_S[/math] вычисляет в переменной [math]v_i[/math] функцию [math]f_{v_i}(x_1, \dots, x_n)[/math].
[math]\triangleleft[/math]

Пример

Пример схемы

Воспользуемся только что доказанной теоремой, и построим на основании этой схемы линейную программу.
Результатом топологической сортировки данного графа может стать последовательность вершин: [math]x, y, z, a, b, c, d, e, f[/math]. Тогда программа [math]P_S[/math] будет иметь следующий вид:
[math]a = x \wedge y[/math]
[math]b = \neg z[/math]
[math]c = \neg a[/math]
[math]d = c \wedge z[/math]
[math]e = a \wedge b[/math]
[math]f = d \vee e[/math]

Утверждение:
Число команд в линейной программе [math]P_S[/math], т.е. время ее выполнения, совпадает со сложностью [math]L(S)[/math] схемы [math]S[/math]. Глубина схемы [math]D(S)[/math] также имеет смысл с точки зрения времени вычисления. Именно, [math]D(S)[/math] — это время выполнения [math]P_S[/math] на многопроцессорной системе. Действительно, все команды, соответствующие вершинам одинаковой глубины, можно выполнять параллельно на разных процессорах, так как результаты любой из них не используются в качестве аргументов другой.

См. также

Литература