TAOCP 7.1.4 Exercise 91

Section 7.1.4: Binary Decision Diagrams

Exercise 91. ▶ [26] [26] In practice we often want to simplify a Boolean function f with respect to a “care set” g, by finding a function ˆf with small B( ˆf) such that f(x) ∧g(x) ≤ˆf(x) ≤f(x) ∨¯g(x) for all x. In other words, ˆf(x) must agree with f(x) whenever x satisfies g(x) = 1, but we don’t care what value ˆf(x) assumes when g(x) = 0. An appealing candidate for such an ˆf is provided by the function f ↓g, “f constrained by g,” defined as follows: If g(x) is identically 0, f ↓g = 0. Otherwise (f ↓g)(x) = f(y), where y is the first element of the sequence x, x ⊕1, x ⊕2, . . . , such that g(y) = 1. (Here we think of x and y as n-bit numbers (x1 . . . xn)2 and (y1 . . . yn)2. Thus x ⊕1 = x ⊕0 . . . 01 = x1 . . . xn−1¯xn; x ⊕2 = x ⊕0 . . . 010 = x1 . . . xn−2¯xn−1xn; etc.) a) What are f ↓1, f ↓xj, and f ↓¯xj? b) Prove that (f ∧f ′) ↓g = (f ↓g) ∧(f ′ ↓g). c) True or false: ¯f ↓g = f ↓g. d) Simplify the formula f(x1, . . . , xn) ↓(x2 ∧¯x3 ∧¯x5 ∧x6). e) Simplify the formula f(x1, . . . , xn) ↓(x1 ⊕x2 ⊕· · · ⊕xn). f) Simplify the formula f(x1, . . . , xn) ↓((x1 ∧· · · ∧xn) ∨(¯x1 ∧· · · ∧¯xn)). g) Simplify the formula f(x1, . . . , xn) ↓(x1 ∧g(x2, . . . , xn)).

7.1.4 BINARY DECISION DIAGRAMS 265 h) Find functions f(x1, x2) and g(x1, x2) such that B(f ↓g) > B(f). i) Devise a recursive way to compute f ↓g, analogous to (55).

Verified: no
Solve time: 8m34s

---

Setup

Let $f, g$ be Boolean functions on $n$ variables, and let the operator $f \downarrow g$ be defined by the ordering $x, x \oplus 1, x \oplus 2, \ldots$ on $n$-bit vectors, where $x \oplus k$ denotes bitwise XOR of $x=(x_1,\ldots,x_n)_2$ with the binary representation of $k$. For each $x$, let $\pi_g(x)$ be the least $k \ge 0$ such that $g(x \oplus k)=1$, assuming such a $k$ exists, and define $(f \downarrow g)(x)=f(x \oplus \pi_g(x))$. If $g \equiv 0$, then $f \downarrow g \equiv 0$.

The goal is to simplify this operator in special cases and verify algebraic properties.

Solution

(a) $f \downarrow 1$, $f \downarrow x_j$, $f \downarrow \bar{x}_j$

If $g \equiv 1$, then $\pi_g(x)=0$ for all $x$, hence $(f \downarrow 1)(x)=f(x)$ and therefore $f \downarrow 1 = f$.

Let $g=x_j$. For each $x$, the condition $g(x \oplus k)=1$ is equivalent to the $j$th bit of $x \oplus k$ being $1$. The least $k$ achieving this is $k=0$ if $x_j=1$, and $k=2^{n-j}$ if $x_j=0$, since XOR with $2^{n-j}$ flips exactly the $j$th bit and no smaller index alters it. Hence

$$ (f \downarrow x_j)(x)= \begin{cases} f(x), & x_j=1,\ f(x \oplus 2^{n-j}), & x_j=0. \end{cases} $$

For $g=\bar{x}_j$, the same argument applies with roles reversed. The least $k$ such that $(x \oplus k)_j=0$ is $k=0$ if $x_j=0$, and $k=2^{n-j}$ if $x_j=1$. Hence

$$ (f \downarrow \bar{x}_j)(x)= \begin{cases} f(x), & x_j=0,\ f(x \oplus 2^{n-j}), & x_j=1. \end{cases} $$

(b) $(f \wedge f') \downarrow g = (f \downarrow g) \wedge (f' \downarrow g)$

For each $x$, let $y=x \oplus \pi_g(x)$. The definition of $\pi_g(x)$ depends only on $g$, hence $y$ is identical in all occurrences of $\downarrow g$. Then

$$ ((f \wedge f') \downarrow g)(x)=(f \wedge f')(y)=f(y)\wedge f'(y), $$

while

$$ ((f \downarrow g)\wedge(f' \downarrow g))(x)=f(y)\wedge f'(y). $$

Both expressions agree pointwise, hence the identity holds.

(c) $\bar{f} \downarrow g = f \downarrow g$

For any $x$ with $g(x\oplus \pi_g(x))=1$, one has

$$ (\bar{f} \downarrow g)(x)=\bar{f}(y)=\neg f(y), \qquad (f \downarrow g)(x)=f(y). $$

Equality would require $f(y)=\neg f(y)$ for all relevant $y$, which is impossible unless $f$ is undefined or degenerate. Taking $f\equiv 0$ gives $(f \downarrow g)\equiv 0$ and $(\bar{f} \downarrow g)\equiv 1$ whenever $g\not\equiv 0$. Hence the statement is false.

(d) $f(x_1,\ldots,x_n)\downarrow (x_2 \wedge \bar{x}_3 \wedge \bar{x}_5 \wedge x_6)$

Let $g$ enforce the constraints

$$ x_2=1,\quad x_3=0,\quad x_5=0,\quad x_6=1. $$

For each $x$, the value $y=x\oplus \pi_g(x)$ is the first vector in the enumeration satisfying these fixed coordinate constraints. Since XOR flips coordinates independently, the minimal $k$ is obtained by flipping exactly the coordinates where $x$ violates the constraint, without affecting the others.

Let $c$ be the bit mask with 1s in positions $2,3,5,6$ where the constraint differs from $x$. Then

$$ y = x \oplus c, $$

where $c$ depends on $x$ by

$$ c_j = \begin{cases} 1, & (j\in{2,6}\ \wedge x_j=0)\ \text{or}\ (j\in{3,5}\ \wedge x_j=1),\ 0, & \text{otherwise}. \end{cases} $$

Hence

$$ (f \downarrow g)(x)=f(x \oplus c). $$

(e) $f(x_1,\ldots,x_n)\downarrow (x_1 \oplus \cdots \oplus x_n)$

Let $g(x)=x_1 \oplus \cdots \oplus x_n$. The set $g^{-1}(1)$ consists of odd-parity vectors.

If $x$ has odd parity, then $\pi_g(x)=0$ and $y=x$. If $x$ has even parity, the least $k$ producing odd parity is $k=1$, since $x\oplus 1$ flips $x_n$ and changes parity. Hence

$$ (f \downarrow g)(x)= \begin{cases} f(x), & x_1\oplus\cdots\oplus x_n=1,\ f(x\oplus 1), & x_1\oplus\cdots\oplus x_n=0. \end{cases} $$

(f) $f(x_1,\ldots,x_n)\downarrow ((x_1\wedge\cdots\wedge x_n)\vee(\bar{x}_1\wedge\cdots\wedge\bar{x}_n))$

Let $g$ be true only at $0^n$ and $1^n$. For each $x$, the value $y$ is whichever of these two points is encountered first in the sequence $x, x\oplus 1, x\oplus 2,\ldots$.

Thus $(f \downarrow g)(x)$ equals $f(0^n)$ if the first reachable special point is $0^n$, and equals $f(1^n)$ if it is encountered first. The result is a function taking only the two values $f(0^n)$ and $f(1^n)$, with the boundary determined by the minimal XOR distance from $x$ to either $0^n$ or $1^n$ under increasing $k$.

(g) $f(x_1,\ldots,x_n)\downarrow (x_1 \wedge g(x_2,\ldots,x_n))$

Let $g'(x_2,\ldots,x_n)=g(x_2,\ldots,x_n)$. The care set requires $x_1=1$ and $g'=1$.

If $x_1=0$, the least $k$ achieving $x_1=1$ is $k=2^{n-1}$, hence the first step forces

$$ y_1=1,\quad y' = (x_2,\ldots,x_n)\oplus 0. $$

If $x_1=1$, no change is needed in the first coordinate.

After fixing $x_1=1$, the remaining selection is governed by $g'$. Hence the operation decomposes recursively:

$$ (f \downarrow g)(x_1,x')= \begin{cases} (f \downarrow g)(1,x'), & x_1=1,\ (f \downarrow g)(1,x'), & x_1=0, \end{cases} $$

with the second component computed as $(f(1,\cdot)\downarrow g')$ on $x'$. Thus the operator reduces to a forced projection onto $x_1=1$ followed by a $(n-1)$-variable constraint application.

(h) Existence of $f,g$ with $B(f \downarrow g) > B(f)$

Let $f(x_1,x_2)=x_1$, which has a BDD of size $B(f)=2$. Define $g$ to select a sparse alternating care set that depends on both variables, for instance

$$ g(x_1,x_2)= (x_1\wedge x_2)\ \vee\ (\bar{x}_1\wedge \bar{x}_2). $$

The care set consists of two diagonally opposite points, and the ordering induced by $x, x\oplus 1, x\oplus 2, x\oplus 3$ forces different projections depending on $x$.

Then $(f \downarrow g)$ becomes a function that distinguishes all four inputs because the nearest-care-point map splits