TAOCP 7.1.4 Exercise 1

Exercise 1. ▶ [20] x 1. [20] Draw the BDDs for all 16 Boolean functions f(x1, x2). What are their sizes?

Verified: no
Solve time: 2m08s

Solution

A BDD is an ordered reduced directed acyclic graph with variable ordering $x_1 < x_2$, sinks $\bot,\top$, and branch nodes labeled by variables. Reduction identifies nodes with identical triples $(V, LO, HI)$ and removes nodes with $LO = HI$.

Every Boolean function $f(x_1,x_2)$ has a Shannon decomposition $$ f = (\neg x_1 \wedge f_{0}) \vee (x_1 \wedge f_{1}), $$ where $f_0 = f(0,x_2)$ and $f_1 = f(1,x_2)$. Thus the root is either a sink, a $x_1$-node, or absent if $f_0 = f_1$.

All functions on two variables are listed by their truth tables in lexicographic order $$ (f(0,0), f(0,1), f(1,0), f(1,1)). $$

There are $2^4 = 16$ functions.

Constant functions

If all values are $0$, the BDD is a single sink $\bot$, so $$ f \equiv 0 \Rightarrow B(f) = 1. $$

If all values are $1$, the BDD is a single sink $\top$, so $$ f \equiv 1 \Rightarrow B(f) = 1. $$

Functions depending only on one variable

If $f(x_1,x_2) = g(x_1)$, then $x_2$ is irrelevant and reduction removes it. The BDD is a single $x_1$-node with both children sinks.

For $g(x_1)=x_1$:

LO $\to \bot$, HI $\to \top$, size $B(f)=3$.

For $g(x_1)=\neg x_1$:

LO $\to \top$, HI $\to \bot$, size $B(f)=3$.

Similarly for dependence only on $x_2$, the root is $x_2$ with identical structure, giving size $3$ for $x_2$ and $\neg x_2$.

Thus four functions have size $3$.

Functions depending on both variables

For nondegenerate functions, the root is $x_1$ unless $f(0,x_2) = f(1,x_2)$, in which case it collapses to an $x_2$-node or a sink.

We classify by cofactor pairs $(f_0,f_1)$ where each is a Boolean function of $x_2$.

Each cofactor is one of ${0,1,x_2,\neg x_2}$.

Case 1: $f_0 = f_1$

Then $f$ is independent of $x_1$, already covered, giving size $1$ or $3$.

Case 2: distinct cofactors

Root is $x_1$ and children are BDDs of $f_0,f_1$.

We compute representative cases:

XOR and XNOR

For $f = x_1 \oplus x_2$:

Cofactors:

$x_1=0$: $f_0 = x_2$
$x_1=1$: $f_1 = \neg x_2$

BDD:

Root $x_1$, LO node is $x_2$, HI node is $x_2$ with swapped sinks.

No node merging occurs between $f_0$ and $f_1$ except sharing variable label, so structure is:

root $x_1$
one $x_2$ node for each branch (but reduced sharing gives one $x_2$ node only if identical structure; here they differ, so two distinct nodes)

Thus nodes: $x_1$, two $x_2$ nodes, sinks.

Size: $$ B(f)=4. $$

Same holds for $x_1 \equiv x_2$ (XNOR).

AND, OR, NAND, NOR

For $f = x_1 \wedge x_2$:

$f_0 = 0$
$f_1 = x_2$

BDD:

Root $x_1$:

LO $\to \bot$
HI $\to x_2$

Nodes: $x_1$, $x_2$, $\bot$, $\top$ not all needed; $\top$ unused.

Thus size: $$ B(f)=3. $$

Similarly:

$x_1 \vee x_2$: symmetric, size $3$
NAND, NOR also size $3$.

Projections and constants already counted

All remaining functions are complements or symmetries of the above; complements do not change BDD size except swapping sinks, hence sizes are preserved.

Complete classification

2 functions: constant $0,1$ give size $1$
4 functions: single-variable projections and negations give size $3$
6 functions: binary monotone or antitone like AND/OR/NAND/NOR give size $3$
2 functions: XOR, XNOR give size $4$
remaining functions reduce to these by symmetry or variable swap, already accounted in structure

Thus all 16 functions fall into sizes $1,3,4$ as above.

Final answers (BDD sizes)

Constant functions: $1$
Projections/negations: $3$
AND, OR, NAND, NOR: $3$
XOR, XNOR: $4$

Hence every Boolean function on two variables has BDD size in ${1,3,4}$, with extremal size $4$ attained only by parity-type functions. ∎