TAOCP 5.3.4 Exercise 30

Section 5.3.4: Networks for Sorting

Exercise 30. [HM22] Prove that any formula involving $\wedge$ and $\vee$ and the independent variables ${x_1, \ldots, x_n}$ can be reduced using the identities in exercise 28 to a "canonical" form $\tau_1 \vee \tau_2 \vee \cdots \vee \tau_n$, where $k \ge 1$, each $\tau_i$ has the form $\bigwedge {x_j \mid j \in S_i}$ where $S_i$ is a subset of ${1, 2, \ldots, n}$, and no set $S_i$ is included in $S_j$ for $i \ne j$. Prove also that two such canonical forms are equal for all $x_1, \ldots, x_n$ if and only if they are identical (up to order).

Verified: no
Solve time: 1m20s

We need to solve Exercise 30 from TAOCP Volume 3, Section 5.3.4. The exercise:

30. [HM22] Prove that any formula involving $\wedge$ and $\vee$ and the independent variables ${x_1, \ldots, x_n}$ can be reduced using the identities in exercise 28 to a "canonical" form $\tau_1 \vee \tau_2 \vee \cdots \vee \tau_k$, where $k \ge 1$, each $\tau_i$ has the form $\bigwedge {x_j \mid j \in S_i}$ where $S_i$ is a subset of ${1, 2, \ldots, n}$, and no set $S_i$ is included in $S_j$ for $i \ne j$. Prove also that two such canonical forms are equal for all $x_1, \ldots, x_n$ if and only if they are identical (up to order).

We need to prove two statements:

Every formula built from variables using $\wedge$ and $\vee$ (with identities from exercise 28: commutative, associative, distributive, absorption, idempotent) can be reduced to a canonical form: a disjunction of conjunctions of variables (i.e., a sum of products in Boolean algebra), where each conjunction corresponds to a subset of variables, and the subsets form an antichain under inclusion (no subset is contained in another).
Two such canonical forms are equivalent (equal for all assignments of variables) iff they are identical up to order.

This is essentially about representing monotone Boolean functions in terms of their minterms (or rather, their prime implicants). Since we only have $\wedge$ and $\vee$ and variables (no negation, no constants), these are monotone Boolean functions. The canonical form described is the disjunction of the minimal (under inclusion) subsets that evaluate to 1. This is the "irredundant disjunctive normal form" for monotone Boolean functions, also known as the set of prime implicants.

We need to prove this using the identities given in exercise 28. The identities are exactly the axioms of a distributive lattice with the absorption and idempotent laws. In fact, the set of formulas modulo these identities forms the free distributive lattice generated by $n$ variables. The canonical form is the representation as a join of meet-irreducible elements? Actually, in a distributive lattice, every element can be represented as a join of meet-irreducible elements, but here we have the condition that no $\tau_i$ is included in another, which corresponds to the join of the minimal subsets (i.e., the antichain of minimal elements of the order ideal representing the function). This is the unique minimal representation.

We need to prove existence and uniqueness.

Existence: Starting from any formula, we can apply distributive laws to push $\vee$ over $\wedge$ to get a disjunction of conjunctions. Then we can use absorption: if one conjunction's set of variables is a subset of another's, we can eliminate the larger one because $A \vee (A \wedge B) = A$ (absorption). Also idempotent removes duplicates. Commutative and associative allow reordering and regrouping. This yields a canonical form with antichain property.

Uniqueness: Suppose we have two antichains $S$ and $T$ of subsets such that $\bigvee_{i} \bigwedge_{j\in S_i} x_j = \bigvee_{k} \bigwedge_{j\in T_k} x_j$ for all boolean assignments. We need to show that the sets of subsets are identical. This is a known fact: the minimal sets of variables that make the function true are uniquely determined. We can prove by considering assignments where some variables are 1 and others 0. Since the function is monotone, if a conjunction is in the canonical form, setting all variables in that conjunction to 1 and all others to 0 makes the function true, and any other conjunction that is not a subset of it will evaluate to 0 (if it contains a variable outside the subset, that variable is 0, so the conjunction is 0). Actually careful: If we set variables in $S_i$ to 1 and others to 0, then the term $\bigwedge_{j\in S_i} x_j = 1$. Any other term $\bigwedge_{j\in S_k} x_j$ evaluates to 1 iff $S_k \subseteq S_i$ (since variables in $S_k$ are 1 only if $S_k \subseteq S_i$). But by antichain property, no $S_k$ is a proper subset of $S_i$. Could there be $S_k = S_i$? No, because duplicates removed. So only $S_i$ itself evaluates to 1. Hence the function value is 1 exactly for assignments that make at least one $S_i$ all 1's. This characterizes the sets $S_i$ as the minimal sets of variables that make the function true. So they are uniquely determined.

We need to write a rigorous proof.

Let's structure:

Existence:

By induction on formula structure, we can show every formula is equivalent to a disjunction of conjunctions of variables (i.e., a sum of products). Base case: single variable $x_i$ is $\bigwedge {x_i}$.
Inductive steps: $\wedge$ and $\vee$ of two disjunctions of conjunctions. For $\vee$, just take union of disjunctions. For $\wedge$, use distributivity: $(\bigvee_i A_i) \wedge (\bigvee_j B_j) = \bigvee_{i,j} (A_i \wedge B_j)$. Each $A_i \wedge B_j$ is a conjunction of variables (since $A_i$ and $B_j$ are conjunctions of variables). So we get a disjunction of conjunctions.
Then we have a disjunction of conjunctions. Each conjunction corresponds to a set of variables. Remove duplicate variables in each conjunction (idempotent). Then we have a set of subsets. If one subset $S$ is contained in another $T$, then $\bigwedge_{j\in S} x_j \vee \bigwedge_{j\in T} x_j = \bigwedge_{j\in S} x_j$ by absorption: $A \vee (A \wedge B) = A$ where $A = \bigwedge_{j\in S} x_j$, $B = \bigwedge_{j\in T \setminus S} x_j$. So we can eliminate $T$. After removing all such inclusions, we get an antichain.
Also if $k=0$ (empty disjunction), but exercise says $k \ge 1$. Actually, can a formula be identically 0? With only variables and $\wedge$, $\vee$, and no constants, the formula is monotone and not identically 0 unless it's an empty conjunction? But we start from variables; the only way to get constant 0 is if we had constants. Since we don't have constants, every formula evaluates to 1 when all variables are 1. So it's not identically 0. Also the formula could be empty? Not in our construction. So $k \ge 1$ holds.

Uniqueness:

Let $\bigvee_{i=1}^k \bigwedge_{j\in S_i} x_j$ and $\bigvee_{i=1}^m \bigwedge_{j\in T_i} x_j$ be two canonical forms (antichains). Suppose they are equivalent as functions.
For each $S_i$, consider the assignment $x_j = 1$ if $j \in S_i$, else $0$. Then the first expression evaluates to 1 because the term for $S_i$ is 1. By antichain property, no other $S_{i'}$ is a subset of $S_i$, so all other terms are 0. Hence the function value is 1.
Since the second expression is equivalent, it must also evaluate to 1 under this assignment. So there exists some $T_p$ such that $T_p \subseteq S_i$ (because all variables in $T_p$ must be 1, i.e., $T_p \subseteq S_i$).
By symmetry, for each $T_p$ there exists some $S_i$ with $S_i \subseteq T_p$.
This gives a matching between the two antichains such that $S_i \subseteq T_p \subseteq S_i$, so $S_i = T_p$. Hence the sets of subsets are identical (up to order).

We need to be careful: The assignment argument requires that the variables are independent (0/1 valued). The identities hold for all values in any distributive lattice, but to prove uniqueness we can use the fact that the free distributive lattice on $n$ generators is isomorphic to the lattice of antichains of subsets of ${1,\ldots,n}$ ordered by... Actually, the standard proof uses the fact that the functions are monotone Boolean functions, and the canonical form corresponds to the set of minimal true assignments.

We should also note that the identities in exercise 28 are exactly the axioms of a distributive lattice with idempotent, commutative, associative, absorption. So we can apply them freely.

Now, write the solution.

We'll produce a solution with clear steps, using LaTeX.

We need to "Make the verification visible. State the invariant, independent check, boundary case, matching bound, or counterexample test that is appropriate for this particular exercise." For this proof, the verification is the assignment argument showing uniqueness. Also existence is constructive.

We'll end with "This completes the proof." and ∎.

Let's draft.

Solution

We work with formulas built from variables $x_1,\dots,x_n$ using the binary operations $\wedge$ (meet) and $\vee$ (join). The allowed identities are those of Exercise 28: commutativity, associativity, distributivity, absorption, and idempotence. These are exactly the axioms of a distributive lattice.

Existence of a canonical form

We prove by structural induction that every formula $\phi$ is equivalent to a disjunction of conjunctions of distinct variables, i.e., [ \phi \equiv \bigvee_{i=1}^k \bigwedge_{j \in S_i} x_j, ] where each $S_i \subseteq {1,\dots,n}$, $k \ge 1$, and the sets $S_i$ form an antichain under inclusion (no $S_i$ is properly contained in another $S_j$).

Base case. A single variable $x_i$ is already of the required form with $k=1$ and $S_1={i}$.

Inductive step. Assume $\phi_1 \equiv \bigvee_{i=1}^{k_1} \bigwedge_{j \in S_i} x_j$ and $\phi_2 \equiv \bigvee_{i=1}^{k_2} \bigwedge_{j \in T_i} x_j$ are in canonical form.

For $\phi_1 \vee \phi_2$ we simply take the union of the two disjunctions. The resulting sets may violate the antichain condition or contain duplicates; we clean them up in the normalization step below.
For $\phi_1 \wedge \phi_2$, distributivity gives [ \phi_1 \wedge \phi_2 \equiv \bigvee_{i=1}^{k_1} \bigvee_{j=1}^{k_2} \left( \bigwedge_{p \in S_i} x_p \wedge \bigwedge_{q \in T_j} x_q \right) = \bigvee_{i,j} \bigwedge_{r \in S_i \cup T_j} x_r, ] where we used idempotence to remove duplicate variables inside each conjunction.

Thus any formula reduces to a disjunction of conjunctions of distinct variables. We now normalize such a disjunction:

Remove duplicate conjunctions: If $S_i = S_j$, idempotence $A \vee A = A$ lets us keep only one copy.
Absorb supersets: If $S_i \subsetneq S_j$, then by absorption [ \bigwedge_{p \in S_i} x_p ;\vee; \bigwedge_{q \in S_j} x_q = \bigwedge_{p \in S_i} x_p ;\vee; \left( \bigwedge_{p \in S_i} x_p \wedge \bigwedge_{q \in S_j \setminus S_i} x_q \right) = \bigwedge_{p \in S_i} x_p, ] so the term corresponding to $S_j$ can be deleted. After exhaustively applying these two rules we obtain a disjunction $\bigvee_{i=1}^k \bigwedge_{j \in S_i} x_j$ with $k \ge 1$ (the formula is not identically $0$ because setting all variables to $1$ makes it $1$) and with the $S_i$ pairwise incomparable under inclusion.

Uniqueness of the canonical form

Suppose two canonical forms are equivalent: [ \bigvee_{i=1}^k \bigwedge_{j \in S_i} x_j \equiv \bigvee_{i=1}^m \bigwedge_{j \in T_i} x_j, ] where ${S_i}$ and ${T_i}$ are antichains of subsets of ${1,\dots,n}$.

For each $i \in {1,\dots,k}$ consider the assignment [ x_j = \begin{cases} 1 & j \in S_i,\ 0 & j \notin S_i. \end{cases} ] Under this assignment the term $\bigwedge_{j \in S_i} x_j$ evaluates to $1$. For any $i' \ne i$, because $S_{i'}$ is not a subset of $S_i$ (antichain property), there exists $j \in S_{i'} \setminus S_i$; then $x_j = 0$ and the term $\bigwedge_{j \in S_{i'}} x_j = 0$. Hence the left-hand side evaluates to $1$.

By equivalence, the right-hand side must also evaluate to $1$. Therefore there exists some $p$ such that $\bigwedge_{j \in T_p} x_j = 1$, which means $T_p \subseteq S_i$.

Symmetrically, for each $T_p$ there is an $S_i$ with $S_i \subseteq T_p$. Combining these two inclusions yields $S_i \subseteq T_p \subseteq S_i$, so $S_i = T_p$. This establishes a bijection between ${S_i}$ and ${T_p}$; consequently the two canonical forms are identical up to order.

This completes the proof. ∎