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

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

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

Доказать, что в результате применения алгоритма из параграфа 14.3 получается сокращённая УБДР. $\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.