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

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

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

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

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

Схемы из функциональных элементов естественным образом реализуются в виде линейных программ. Наоборот, для деревьев решений и УБДР естественным программным представлением являются ветвящиеся программы, включающие лишь условные операторы вида 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}$. Программа П ациклическая, если все метки программы П пронумерованы и в каждом операторе метка оператора имеет номер меньший, чем метки перехода (это эквивалентно тому, что в блок-схеме нет циклов. Также можно сказать, что невозможны переходы «назад»). Присваивания имеют такой же вид, как в предыдущей задаче.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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