TAOCP 7.1.4 Exercise 2

Section 7.1.4: Binary Decision Diagrams

Exercise 2. ▶ [21] x 2. [21] Draw a planar dag with sixteen vertices, each of which is the root of one of the 16 BDDs in exercise 1.

Verified: no
Solve time: 3m14s

Solution

Let $F$ be the set of all Boolean functions $f(x_1,x_2)$, represented by their truth tables

$$ f = (f(0,0), f(0,1), f(1,0), f(1,1)) \in {0,1}^4, $$

so $|F| = 16$.

For each $f \in F$, define its cofactors with respect to $x_1$,

$$ f_0(x_2) = f(0,x_2), \qquad f_1(x_2) = f(1,x_2). $$

Each $f_i$ is a Boolean function of one variable, hence has truth table of length $2$. To represent all vertices uniformly inside $F$, identify a 1-variable function $(a,b)$ with the 2-variable function $(a,b,a,b)$, which is the unique element of $F$ independent of $x_1$ having the same behavior on $x_2$. Under this identification, $f_0,f_1 \in F$.

Define a directed graph $G$ with vertex set $F$ and directed edges

$$ f \to f_0, \qquad f \to f_1. $$

This graph has exactly 16 vertices and is a directed acyclic graph, since repeated cofactoring strictly removes dependence on $x_1$ and therefore reaches functions independent of both variables after finitely many steps.

Place the vertices in a $4 \times 4$ grid indexed by their truth tables ordered lexicographically:

$$ 0000, 0001, 0010, 0011, $$

$$ 0100, 0101, 0110, 0111, $$

$$ 1000, 1001, 1010, 1011, $$

$$ 1100, 1101, 1110, 1111. $$

Arrange edges so that the edge $f \to f_0$ is drawn as a straight vertical segment from $f$ to the vertex obtained by deleting the last two bits of $f$ and duplicating them as $(a,b,a,b)$, and the edge $f \to f_1$ is drawn similarly using the last two bits. In this representation, both transitions act independently on the first and second half of the truth table, so edges only connect vertices whose binary labels differ in at most one of the two coordinate blocks.

Embed the grid in the plane so that vertices with identical first bit pairs $(f(0,0),f(0,1))$ lie in the same column, and vertices with identical second bit pairs $(f(1,0),f(1,1))$ lie in the same row. Under this placement, every edge from $f$ to $f_0$ is horizontal and every edge from $f$ to $f_1$ is vertical. Horizontal edges within rows and vertical edges within columns intersect only at endpoints, since two distinct vertices cannot share both their first and second coordinate blocks.

Thus all edges can be drawn without crossings, producing a planar embedding of $G$.

Each vertex of this planar DAG corresponds to exactly one Boolean function in $F$, hence to exactly one root BDD of exercise 7.1.4.1. This yields a planar directed acyclic graph with 16 vertices whose vertices are in bijection with the 16 BDD roots. ∎