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

Доказать лемму 92 на стр. 277 обратной индукцией по $i$.

Лемма 92: После выполнения шага для $i$ в алгоритме СокрУБДР (сокращение УБДР) в полученной диаграмме для каждого $j = i-1, \ldots , n$ и для каждой подфункции $f_{\sigma_{1}, \ldots , \sigma_{j}}\left(x_{j+1}, \ldots , x_{n}\right) = f\left(\sigma_{1}, \ldots , \sigma_{j}, x_{j+1}, \ldots , x_{n}\right)$, где $\sigma_{k} \in \left\{ 0,1\right\}$ при $k = 1, 2, \ldots , j$, имеется ровно одна вершина — исток поддиаграммы, реализующей эту подфункцию.

Используя лемму 92 на стр. 277, доказать утверждение 2) теоремы 91 на стр. 276. $\square$

Теорема 91: если алгоритм СокрУБДР на входе УБДР $D$ возвращает УБДР $D'$, то (утверждение 2) УБДР $D'$ является при данном порядке переменных единственной сокращённой (с точностью до изоморфизма) и минимальной.

Лемма 92: После выполнения шага для $i$ в алгоритме СокрУБДР в полученной диаграмме для каждого $j = i-1, \ldots , n$ и для каждой подфункции $f_{\sigma_{1}, \ldots , \sigma_{j}}\left(x_{j+1}, \ldots , x_{n}\right) = f\left(\sigma_{1}, \ldots , \sigma_{j}, x_{j+1}, \ldots , x_{n}\right)$, где $\sigma_{k} \in \left\{ 0,1\right\}$ при $k = 1, 2, \ldots , j$, имеется ровно одна вершина — исток поддиаграммы, реализующей эту подфункцию.

Доказать, что в результате применения алгоритма из параграфа 14.3 получается сокращённая УБДР.

Имеется в виду алгоритм параграфа 14.3, строящий УБДР для $f(x_{1}, \ldots , x_{n})$ «сверху-вниз», рекурсией по $n$. Если $n = 0$, то $f$ — константа, и УБДР состоит из двух стоков $0$ и $1$. Иначе строятся две остаточные функции $f_{0}(x_{2}, \ldots , x_{n}) = f(0, x_{2}, \ldots , x_{n})$ и $f_{1}(x_{2}, \ldots , x_{n}) = f(1, x_{2}, \ldots , x_{n})$, рекурсивно строится (общая) УБДР, реализующая все различные функции среди $\left\{ f_{0}, f_{1}\right\}$ (повторяющиеся среди них отождествляются, так что на каждую различную остаточную функцию строится не более одной вершины), а затем: если $f_{0} = f_{1}$, вершиной для $f$ считается уже построенная вершина, реализующая $f_{0} = f_{1}$; иначе добавляется одна новая вершина с меткой $x_{1}$, 0-сыном и 1-сыном которой являются (уже построенные, возможно общие) вершины, реализующие $f_{0}$ и $f_{1}$ соответственно. $\square$

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

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

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

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

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

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

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

Значение пороговой функции $T_{k}^{n}$ от $n$ переменных с порогом $k$ равно 1 тогда и только тогда, когда во входном наборе имеется не менее $k$ единиц:

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