Упорядоченные бинарные диаграммы решений

Доказать, что всякую булеву функцию от $n$ переменных можно реализовать в виде УБДР с не более чем $2^{n / 2+2}-1$ внутренней вершиной. Указание. Показать, как преобразовать полное БДР. $\circledast$

Рассмотрим трёхместные булевы функции $f\left(x_{1}, x_{2}, x_{3}\right)$, зафиксируем порядок переменных $x_{1}<x_{2}<x_{3}$. Определить:

Рис. 20: УБДР \mathfrak {D}_{1}.

Указать, как по УБДР для функции $f$ построить УБДР для двойственной функции $f^{*}$. $\circledast$

Схемы из функциональных элементов естественным образом реализуются в виде линейных программ. Наоборот, для деревьев решений и УБДР естественным программным представлением являются ветвящиеся программы, включающие лишь условные операторы вида if $v$ then $\Pi_{1}$ else $\Pi_{2}$ и присваивания $y \leftarrow 0$ и $y \leftarrow 1$ (см. раздел 22). Они соответствуют внутренним вершинам диаграмм и стокам соответственно. Здесь $\Pi_{1}$ и $\Pi_{2}$ — это снова ветвящиеся программы, а переменная $y$ содержит результат.

Показать, как по УБДР построить ветвящуюся программу, вычисляющую ту же самую функцию.

Написать ветвящиеся программы, вычисляющие функции, представляемые УБДР $\mathfrak {D}_{1}$ на рис. 20 и $\mathfrak {D}_{3}$ на рис. 22 на стр. 125. $\circledast$

Доказать, что каждую УБДР $\mathfrak {D}$ можно представить в виде ациклической программы с метками П (см. раздел 22) и при этом длина П не превосходит количества вершин $\mathfrak {D}$. Программа П ациклическая, если все метки программы П пронумерованы и в каждом операторе метка оператора имеет номер меньший, чем метки перехода (это эквивалентно тому, что в блок-схеме нет циклов. Также можно сказать, что невозможны переходы «назад»). Присваивания имеют такой же вид, как в предыдущей задаче. $\circledast$

Доказать, что по любой УБДР $\mathfrak {D}$ с $n$ вершинами, представляющей функцию $f$, можно построить линейную программу (и, следовательно, схему из функциональных элементов) размера $O(n)$ в базисе $\mathcal{B}_{0}=\left\{ \wedge , \vee , \neg \right\}$, вычисляющую ту же самую функцию $f$. Указание. Использовать индукцию по высоте вершин. Высота вершины $v$ в УБДР — это максимальная длина пути из $v$ в какой-либо из стоков. $\circledast$

Построить минимальные УБДР для двухместных функций: $x \wedge y$, $x \vee y, x \oplus y, x \rightarrow y, x \uparrow y$. $\circledast$

Построить УБДР для функции $\operatorname {odd}\left(x_{1}, \ldots , x_{n}\right)=x_{1} \oplus \cdots \oplus x_{n}$ и оценить её сложность. Сравнить со сложностью ДНФ этой же функции из задачи 170 на стр. 54. $\circledast$

Построить минимальные УБДР для функции

относительно двух упорядочений переменных:

Используя алгоритм сокращения УБДР, построить сокращённую диаграмму, эквивалентную УБДР $\mathfrak {D}_{2}$ на рис. 21 на следующей странице. Определить, какую функцию реализует полученная схема. Построить её таблицу истинности. $\circledast$

Рис. 21: УБДР \mathfrak {D}_{2}.

Пусть $\Phi$ — это совершенная ДНФ для булевой функции $f$. Доказать, что существует УБДР для функции $f$, количество внутренних вершин которой не превосходит длины $\Phi$ независимо от порядка переменных. Под длиной $\Phi$ понимаем общее количество вхождений переменных в $\Phi$. Указание. Применить индукцию по количеству переменных $n$. $\circledast$

Доказать, что для функции

сложность сокращённой УБДР равна

Пусть функция $f^{\prime }$ получена из функции $f$ фиксированием значения переменной $x_{i}$ :

где $\sigma \in \left\{ 0,1\right\}$.

Пороговая функция $T_{k}^{n}$ определена в задаче 406 на стр. 118.

Построить минимальные УБДР, реализующие функции из задач 396, 402 и 403. $\circledast$

Построить УБДР для функций $f_{n}$ и $g_{n}$ из задачи 406 на стр. 118 и оценить их сложность. $\circledast$

Построить УБДР для решения задачи 407 на стр. 119. Определить сложность построенной диаграммы. $\circledast$

Построить УБДР для решения задачи 408 на стр. 119. Определить сложность построенной диаграммы. $\circledast$

Построить УБДР для решения задачи 409 на стр. 119. Определить сложность построенной диаграммы. $\circledast$

Построить УБДР для решения задачи 410 на стр. 119. Определить сложность построенной диаграммы. $\circledast$