Math Problems Vault

Problem 411

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 a complete BDD. $\circledast$

?

Problem 412

(a)(b)

Consider three-place Boolean functions $f\left(x_{1}, x_{2}, x_{3}\right)$ , fixing the order of variables $x_{1}<x_{2}<x_{3}$ . Determine:

$Fig. 20: OBDD \mathfrak {D}_{1}.$ Fig. 20: OBDD \mathfrak {D}_{1}.

?

(a)

the largest possible number of vertices in a reduced OBDD for $f$ ;

(b)

how many functions exist attaining the largest number of vertices in the reduced OBDD. $\circledast$

Problem 413

Indicate how to construct, from an OBDD for a function $f$ , an OBDD for the dual function $f^{*}$ . $\circledast$

?

Problem 414

Circuits of functional elements are naturally realized as linear programs. Conversely, for decision trees and OBDDs, the natural program representation is a branching program, which includes only conditional statements of the form if $v$ then $\Pi_{1}$ else $\Pi_{2}$ and assignments $y \leftarrow 0$ and $y \leftarrow 1$ (see Section 22). These correspond to the internal vertices of the diagrams and to the sinks, respectively. Here $\Pi_{1}$ and $\Pi_{2}$ are again branching programs, and the variable $y$ holds 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. 20 and $\mathfrak {D}_{3}$ in Fig. 22 on p. 125. $\circledast$

?

Problem 415

Prove that every OBDD $\mathfrak {D}$ can be represented as an acyclic program with labels П (see Section 22), and that the length of П does not exceed the number of vertices of $\mathfrak {D}$ . A program П is acyclic if all the labels of the program П are numbered and in every statement the label of the statement has a smaller number than the transition labels (this is equivalent to saying that there are no cycles in the flowchart; equivalently, that no "backward" transitions are possible). Assignments have the same form as in the previous problem. $\circledast$

?

Problem 416

Prove that from any OBDD $\mathfrak {D}$ with $n$ vertices representing a function $f$ , one can construct a linear program (and, consequently, a circuit of functional elements) of size $O(n)$ over the basis $\mathcal{B}_{0}=\left\{ \wedge , \vee , \neg \right\}$ , computing the same function $f$ . Hint. Use induction on the height of the vertices. The height of a vertex $v$ in an OBDD is the maximum length of a path from $v$ to one of the sinks. $\circledast$

?

Problem 417

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

?

Problem 418

Construct an OBDD for the function $\operatorname {odd}\left(x_{1}, \ldots , x_{n}\right)=x_{1} \oplus \cdots \oplus x_{n}$ and estimate its complexity. Compare it with the complexity of the DNF of the same function from Problem 170 on p. 54. $\circledast$

?

Problem 419

(a)(b)

Construct minimal OBDDs for the function

f\left(x_{1}, x_{2}, x_{3}, x_{4}, x_{5}, x_{6}\right)=\left(x_{1} \wedge x_{2}\right) \oplus \left(x_{3} \wedge x_{4}\right) \oplus \left(x_{5} \wedge x_{6}\right)

with respect to two orderings of the variables:

?

(a)

$x_{1}<x_{2}<x_{3}<x_{4}<x_{5}<x_{6}$ and

(b)

$x_{1}<x_{3}<x_{5}<x_{2}<x_{4}<x_{6}$ . $\circledast$

Problem 420

Using the OBDD reduction algorithm, construct the reduced diagram equivalent to the OBDD $\mathfrak {D}_{2}$ in Fig. 21 on the next page. Determine which function the resulting diagram realizes. Construct its truth table. $\circledast$

$Fig. 21: OBDD \mathfrak {D}_{2}.$ Fig. 21: OBDD \mathfrak {D}_{2}.

?

Problem 421

Let $\Phi$ be a perfect DNF for a Boolean function $f$ . Prove that there exists an OBDD for the function $f$ whose number of internal vertices does not exceed the length of $\Phi$ , regardless of the order of the variables. By the length of $\Phi$ we mean the total number of occurrences of variables in $\Phi$ . Hint. Apply induction on the number of variables $n$ . $\circledast$

?

Problem 422

(a)(b)

Prove that for the function

p_{n}\left(x_{1}, \ldots , x_{n}, y_{n}, \ldots , y_{1}\right)=\left(x_{1} \wedge y_{1}\right) \vee \left(x_{2} \wedge y_{2}\right) \vee \ldots \vee \left(x_{n} \wedge y_{n}\right)

the complexity of the reduced OBDD equals

?

(a)

$2 n$ under the variable ordering $\pi_{1}: x_{1}, y_{1}, \ldots , x_{n}, y_{n}$ ;

(b)

$2^{n+1}-2$ under the ordering $\pi_{2}: x_{1}, x_{2}, \ldots , x_{n}, y_{n}, \ldots , y_{2}, y_{1}$ . $\circledast$

Problem 423

(a)(b)

Let the function $f^{\prime }$ be obtained from the function $f$ by fixing the value of the variable $x_{i}$ :

f^{\prime }\left(x_{1}, \ldots , x_{i-1}, x_{i+1}, \ldots , x_{n}\right)=f\left(x_{1}, \ldots , x_{i-1}, \sigma , x_{i+1}, \ldots , x_{n}\right),

where $\sigma \in \left\{ 0,1\right\}$ .

?

(a)

Suppose $\mathfrak {D}$ is a reduced OBDD for the function $f\left(x_{1}, \ldots , x_{n}\right)$ under the given order of variables. Propose a procedure that rebuilds the OBDD $\mathfrak {D}$ into an OBDD $\mathfrak {D}^{\prime }$ for the function $f^{\prime }\left(x_{1}, \ldots , x_{i-1}, x_{i+1}, \ldots , x_{n}\right)$ under the same order. Will the resulting OBDD $\mathfrak {D}^{\prime }$ always be reduced?

(b)

Apply the procedure from part (a) to obtain, from the OBDD $\mathfrak {D}_{3}$ in Fig. 22 on the facing page, diagrams for the following functions: $f\left(0, x_{2}, x_{3}, x_{4}\right), f\left(x_{1}, 1, x_{3}, x_{4}\right), f\left(x_{1}, x_{2}, 0, x_{4}\right)$ . $\circledast$

Problem 424

(a)(b)(c)(d)

The threshold function $T_{k}^{n}$ is defined in Problem 406 on p. 118.

?

(a)

Construct an OBDD for the threshold function $T_{k}^{n}$ in general form.

(b)

Construct a minimal OBDD for the threshold function $T_{4}^{6}$ .

$Fig. 22: OBDD \mathfrak {D}_{3}.$ Fig. 22: OBDD \mathfrak {D}_{3}.

(c)

Does the complexity of the minimal OBDD for threshold functions depend on the order of the variables?

(d)

Estimate the complexity of the minimal OBDD for the threshold function $T_{k}^{n}$ . $\circledast$

Problem 425

Construct minimal OBDDs realizing the functions from Problems 396, 402, and 403. $\circledast$

?

Problem 426

Construct OBDDs for the functions $f_{n}$ and $g_{n}$ from Problem 406 on p. 118 and estimate their complexity. $\circledast$

?

Problem 427

Construct an OBDD for the solution of Problem 407 on p. 119. Determine the complexity of the diagram constructed. $\circledast$

?

Problem 428

Construct an OBDD for the solution of Problem 408 on p. 119. Determine the complexity of the diagram constructed. $\circledast$

?

Problem 429

Construct an OBDD for the solution of Problem 409 on p. 119. Determine the complexity of the diagram constructed. $\circledast$

?

Problem 430

Construct an OBDD for the solution of Problem 410 on p. 119. Determine the complexity of the diagram constructed. $\circledast$

?