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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Image formatting fixed)
м (rollbackEdits.php mass rollback)
 
(не показано 11 промежуточных версий 2 участников)
Строка 2: Строка 2:
 
Определения и основные понятия, связанные с булевыми функциями описаны в статье [[Определение булевой функции|"определение булевой функции"]].<br>
 
Определения и основные понятия, связанные с булевыми функциями описаны в статье [[Определение булевой функции|"определение булевой функции"]].<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>{\{s_i\}}_{i=n}^t</tex>, в которой <tex>s_i</tex> имеет вид <tex>x_i = F(x_{a_1}, x_{a_2}, \ldots , x_{a_m})</tex>, где <tex>x_i, x_{a_1}, \dots , x_{a_m}</tex> {{---}} переменные, каждое из чисел <tex>a_j</tex> меньше <tex>i</tex>, а <tex>F</tex> {{---}} <tex>m</tex>-местная базисная функция. Такая линейная программа имеет <tex>n</tex> входных переменных, которые не выражаются через операции вычисления.
 
}}
 
}}
 
'''Пример'''<br>
 
'''Пример'''<br>
Для базиса <tex>B_0 = \{\vee, \wedge, \neg \}</tex> линейная программа состоит из присваиваний вида:  
+
Для базиса <tex>B_0 = \{\vee, \wedge, \neg \}</tex> линейная программа может выглядеть следующим образом:  
 
* <tex>A_2 = A_0 \wedge A_1</tex>;
 
* <tex>A_2 = A_0 \wedge A_1</tex>;
 
* <tex>A_2 = A_0 \vee A_1</tex>;
 
* <tex>A_2 = A_0 \vee A_1</tex>;
Строка 12: Строка 12:
 
Линейная программа <tex>P</tex> с выделенными переменными <tex>x_1,\dots , x_n</tex> порождает для каждого набора <tex>\sigma_1, \dots , \sigma_n</tex> значений входных переменных естественный процесс вычисления:
 
Линейная программа <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>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_Z(\sigma_1, \dots , \sigma_n)</tex>.
+
# Последовательно выполняются присваивания программы <tex>P</tex>, в результате чего каждая из переменных <tex>x_i</tex> программы получит итоговое значение <tex>P_i(\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>.
+
|definition='''Программа''' <tex>P</tex> со входными переменными <tex>x_1,\dots , x_n</tex> '''вычисляет''' в выходной переменной <tex>x_m</tex> '''функцию''' <tex>F(x_1, \dots , x_n)</tex>, если для любого набора значений входов <tex>\sigma_1, \dots , \sigma_n</tex> после завершения работы <tex>P_m(\sigma_1, \dots , \sigma_n) = F(\sigma_1, \dots , \sigma_n)</tex>.
 
}}
 
}}
  
Строка 24: Строка 24:
 
|statement=
 
|statement=
 
<br>
 
<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 = 1  + n, \dots , m  + n</tex>, вычисляет функцию <tex>f_{x_i}(x_1, \ldots , x_n)</tex>;<br><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, 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>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>.
+
# По каждой линейной программе <tex>P</tex> со входными переменными <tex>x_1, \dots , x_n</tex>, вычисляющей в выходной переменной <tex>x_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=
 
|proof=
 
'''(1)'''<br>
 
'''(1)'''<br>
Строка 32: Строка 32:
 
* Пусть вершина <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>.
 
* Пусть вершина <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>
 
<br>
Топологическая сортировка вершин гарантирует, что <tex>j < n + i \wedge k < n + i</tex>. Поэтому при вычислении <tex>x_{n + i}</tex> значения аргументов уже получены и индукцией по глубине легко показать, что <tex>\forall i = 1, \dots , m</tex> программа <tex>P_S</tex> вычисляет в переменной <tex>x_i</tex> функцию <tex>f_{x_i}(x_1, \dots, x_n)</tex>.
+
Топологическая сортировка вершин гарантирует, что <tex>j < n + i \wedge k < n + i</tex>. Поэтому при вычислении <tex>x_{n + i}</tex> значения аргументов уже получены и индукцией по глубине легко показать, что для любого <tex>i \in [1, m]</tex> программа <tex>P_S</tex> вычисляет в переменной <tex>x_i</tex> функцию <tex>f_{x_i}(x_1, \dots, x_n)</tex>.
 
}}
 
}}
  

Текущая версия на 19:17, 4 сентября 2022

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

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

Определение:
Линейная программа — последовательность строк вида [math]{\{s_i\}}_{i=n}^t[/math], в которой [math]s_i[/math] имеет вид [math]x_i = F(x_{a_1}, x_{a_2}, \ldots , x_{a_m})[/math], где [math]x_i, x_{a_1}, \dots , x_{a_m}[/math] — переменные, каждое из чисел [math]a_j[/math] меньше [math]i[/math], а [math]F[/math][math]m[/math]-местная базисная функция. Такая линейная программа имеет [math]n[/math] входных переменных, которые не выражаются через операции вычисления.

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

  • [math]A_2 = A_0 \wedge A_1[/math];
  • [math]A_2 = A_0 \vee A_1[/math];
  • [math]A_1 = \neg A_0[/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]x_i[/math] программы получит итоговое значение [math]P_i(\sigma_1, \dots , \sigma_n)[/math].


Определение:
Программа [math]P[/math] со входными переменными [math]x_1,\dots , x_n[/math] вычисляет в выходной переменной [math]x_m[/math] функцию [math]F(x_1, \dots , x_n)[/math], если для любого набора значений входов [math]\sigma_1, \dots , \sigma_n[/math] после завершения работы [math]P_m(\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]x_{n + 1}, \dots , x_{n + m}[/math], которая в любой переменной [math]x_i, i \in [1 + n, m + n][/math] вычисляет функцию [math]f_{x_i}(x_1, \ldots , x_n)[/math];

  2. По каждой линейной программе [math]P[/math] со входными переменными [math]x_1, \dots , x_n[/math], вычисляющей в выходной переменной [math]x_m[/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_{i + n}[/math] помечена [math]\neg[/math], и в нее входит ребро из [math]u_j[/math]. Тогда в качестве [math]i[/math]-ой команды поместим в [math]P_S[/math] присваивание [math]x_{i + n}= \neg x_j[/math];
  • Пусть вершина [math]u_{i + n}[/math] помечена [math]\circ \in \{ \wedge , \vee \}[/math], и в нее входят ребра из [math]u_j[/math] и [math]u_k[/math]. Тогда в качестве [math]i[/math]-ой команды поместим в [math]P_S[/math] присваивание [math]x_{i + n} = x_j \circ x_k[/math].


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

Пример

Пример схемы

Воспользуемся только что доказанной теоремой, и построим на основании этой схемы линейную программу.
Установим соответствие между вершинами схемы и переменными: [math]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[/math].
Результатом топологической сортировки данного графа может стать последовательность вершин: [math]x, y, z, a, b, c, d, e, f[/math]. Тогда программа [math]P_S[/math] будет иметь следующий вид:
[math]x_3 = x_0 \wedge x_1[/math]
[math]x_4 = \neg x_2[/math]
[math]x_5 = \neg x_3[/math]
[math]x_6 = x_5 \wedge x_2[/math]
[math]x_7 = x_3 \wedge x_4[/math]
[math]x_8 = x_6 \vee x_7[/math]

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

См. также

Литература

  1. Дехтярь М.И. Реализация булевых функций с помощью логических схем // Введение в схемы, автоматы и алгоритмы, 2007. URL: https://www.intuit.ru/studies/courses/1030/205/lecture/5306