TAOCP 7.1.4 Exercise 74

Section 7.1.4: Binary Decision Diagrams

Exercise 74. ▶ [M23] [M23] Explain how to count the number of self-dual monotone Boolean functions of n variables, by modifying (49).

Verified: no
Solve time: 6m15s

Solution

Let $f(x_1,\dots,x_n)$ be a monotone Boolean function. Monotonicity means that if $x \le y$ componentwise then $f(x) \le f(y)$. The dual function is defined by [ f^D(x_1,\dots,x_n) = \neg f(\neg x_1,\dots,\neg x_n). ] A function is self-dual when $f = f^D$, equivalently [ f(x_1,\dots,x_n) = \neg f(\neg x_1,\dots,\neg x_n). ]

In terms of truth tables, if $\tau$ is the $2^n$-bit truth table of $f$, ordered lexicographically by $(x_1,\dots,x_n)$, then the truth table of $f^D$ is obtained by reversing the order of bits and complementing each bit. Thus self-duality is equivalent to the constraint that for every assignment $x$, [ f(x) + f(\bar x) = 1, ] where $\bar x$ is the bitwise complement of $x$.

A monotone Boolean function is completely determined by its set of minimal true points, which forms an antichain in the Boolean lattice ${0,1}^n$. The modification of equation (49) in the text expresses the number $M_n$ of monotone Boolean functions as a sum over antichains $A$: [ M_n = \sum_{A} 1, ] where $A$ ranges over all antichains in ${0,1}^n$.

To enforce self-duality, the antichain representation must satisfy a symmetry constraint induced by complementation. If $A$ is the set of minimal true points of a monotone function $f$, then the set of minimal false points of $f$ corresponds to maximal points of the complement ideal. Self-duality requires that the true region and false region are complements under reversal, hence the antichain $A$ must determine the function uniquely together with its image under bitwise complement.

Let $\mathcal{P}_n$ denote the Boolean lattice. Partition $\mathcal{P}_n$ into pairs ${x,\bar x}$. There are no fixed points when $n \ge 1$, since $x = \bar x$ has no solution in ${0,1}^n$. Hence the lattice splits into $2^{n-1}$ disjoint pairs.

A self-dual monotone function is uniquely determined by selecting, for each pair ${x,\bar x}$, a consistent assignment compatible with monotonicity: if $x \le y$ then $f(x) \le f(y)$ must hold simultaneously with $f(x) = 1 - f(\bar x)$.

Define a function $g$ on representatives of each complement pair by choosing exactly one element from each pair, say the lexicographically smaller element $x$, and setting $g(x) = f(x)$. The value at $\bar x$ is then fixed by self-duality: [ f(\bar x) = 1 - f(x). ]

Monotonicity imposes that if $x \le y$ and both are chosen representatives (or correspond via their representatives), then assignments must respect closure upward under the partial order. This reduces the problem to selecting an antichain $A$ of representatives such that for every $x \in A$, no $y < x$ (in the Boolean lattice) is in $A$, and such that inclusion of $x$ automatically excludes all $\bar y$ with $y \ge x$.

To convert equation (49) into a count of self-dual monotone functions, the summation over all antichains is restricted to antichains $A$ satisfying the symmetry condition [ A \cap \overline{A} = \varnothing,\qquad A \cup \overline{A} \text{ determines all elements of } \mathcal{P}_n, ] where $\overline{A} = {\bar x : x \in A}$.

Thus each admissible self-dual monotone function corresponds to choosing a subset of complement pairs ${x,\bar x}$ subject to the constraint that the selected representatives form an antichain in the quotient poset $\mathcal{P}_n / \sim$, where $x \sim \bar x$.

Let $Q_n$ denote this quotient poset. Then the number of self-dual monotone Boolean functions of $n$ variables is exactly the number of antichains in $Q_n$. Since antichains correspond to monotone Boolean functions, the modification of (49) becomes [ SD_n = \sum_{A \subseteq Q_n \text{ antichain}} 1. ]

Equivalently, writing $M(Q_n)$ for the number of monotone Boolean functions on the quotient structure induced by complement identification, [ SD_n = M(Q_n). ]

This reduces the enumeration problem to the same combinatorial structure as (49), but over the quotient lattice where each element is an unordered pair ${x,\bar x}$. The monotonicity relation on pairs is induced by [ {x,\bar x} \le {y,\bar y} \iff x \le y. ]

Hence the modification of (49) replaces the Boolean lattice $\mathcal{P}_n$ by the involution quotient poset $\mathcal{P}_n / (x \sim \bar x)$, and counts its antichains.

Therefore the required counting function is obtained by applying the same antichain enumeration as in (49) to this quotient structure, yielding the number of self-dual monotone Boolean functions.

This completes the proof. ∎