Ordered Binary Decision Diagrams

Prove Lemma 92 on p. 277 by backward induction on $i$.

Lemma 92: After executing the step for $i$ in the algorithm СокрУБДР (OBDD reduction), in the resulting diagram, for every $j = i-1, \ldots , n$ and for every subfunction $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)$, where $\sigma_{k} \in \left\{ 0,1\right\}$ for $k = 1, 2, \ldots , j$, there is exactly one vertex — a source of a subdiagram realizing that subfunction.

Using Lemma 92 on p. 277, prove statement 2) of Theorem 91 on p. 276. $\square$

Theorem 91: if the algorithm СокрУБДР applied to an OBDD $D$ returns an OBDD $D'$, then (statement 2) $D'$ is, for the given variable ordering, the unique reduced (up to isomorphism) OBDD of minimal size.

Lemma 92: After executing the step for $i$ in the algorithm СокрУБДР, in the resulting diagram, for every $j = i-1, \ldots , n$ and for every subfunction $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)$, where $\sigma_{k} \in \left\{ 0,1\right\}$ for $k = 1, 2, \ldots , j$, there is exactly one vertex — a source of a subdiagram realizing that subfunction.

Prove that applying the algorithm from Section 14.3 yields a reduced OBDD.

The algorithm referred to (Section 14.3) builds an OBDD for $f(x_{1}, \ldots , x_{n})$ top-down, by recursion on $n$. If $n = 0$, $f$ is a constant and the OBDD consists of the two sinks $0$ and $1$. Otherwise, form the two residual functions $f_{0}(x_{2}, \ldots , x_{n}) = f(0, x_{2}, \ldots , x_{n})$ and $f_{1}(x_{2}, \ldots , x_{n}) = f(1, x_{2}, \ldots , x_{n})$, recursively build (a shared) OBDD realizing the distinct functions among $\left\{ f_{0}, f_{1}\right\}$ (duplicates among them are identified, so at most one vertex is built per distinct residual function), and then: if $f_{0} = f_{1}$, let the vertex for $f$ be the same vertex that already realizes $f_{0} = f_{1}$; otherwise add one new vertex labeled $x_{1}$ whose 0-child and 1-child are the (already-built, possibly shared) vertices realizing $f_{0}$ and $f_{1}$ respectively. $\square$

Prove that every Boolean function of $n$ variables can be realized as an OBDD with no more than $2^{n / 2+2}-1$ internal vertices. Hint. Show how to transform the complete BDD.

Circuits made of functional elements are naturally realized as linear programs. Conversely, for decision trees and OBDDs, the natural program representation is branching programs, which include only conditional statements of the form If $v$ then $\Pi_{1}$ Else $\Pi_{2}$ and assignments $y \leftarrow 0$ and $y \leftarrow 1$ (see Chapter 18). These correspond to internal vertices of the diagrams and to sinks, respectively. Here $\Pi_{1}$ and $\Pi_{2}$ are again branching programs, and the variable $y$ contains the result.

Show how to construct, from an OBDD, a branching program computing the same function.

Write branching programs computing the functions represented by the OBDDs $\mathfrak {D}_{1}$ in Fig. 69 on p. 272 and $\mathfrak {D}_{3}$ in Fig. 74 on the previous page.

Construct minimal OBDDs for the two-argument functions: $x \wedge y, x \vee y$, $x \oplus y, x \rightarrow y, x \uparrow y$.

Construct minimal OBDDs for the function

with respect to two orderings of the variables:

The value of the threshold function $T_{k}^{n}$ of $n$ variables with threshold $k$ equals 1 if and only if the input tuple contains at least $k$ ones:

Construct minimal OBDDs realizing the functions from Problems 221 and 224 on p. 266.