Exercise 120. [23] What is the shortest DNF for the symmetric functions (a) $x_1 \oplus x_2 \oplus \cdots \oplus x_7$? (b) $S_{0,1,3,5,7}(x_1, \ldots, x_7)$? (c) Prove that every Boolean function of $n$ variables can be expressed as a DNF with at most $2^{n-1}$ prime implicants.

Verified: no
Solve time: 7m06s

(a) $x_1 \oplus x_2 \oplus \cdots \oplus x_7$

This function is $1$ exactly on inputs of odd Hamming weight.

Every satisfying assignment $a \in {0,1}^7$ with $|a|$ odd determines a minterm

$$ M_a=\bigwedge_{i:a_i=1} x_i ;\wedge; \bigwedge_{i:a_i=0} \bar{x}_i. $$

Each such minterm is a prime implicant: deleting any literal produces a cube containing both an even- and an odd-weight assignment, hence it is not contained in the true set.

There are exactly

$$ \sum_{k\ \text{odd}} \binom{7}{k} = 2^6 = 64 $$

such assignments.

Thus the shortest DNF consists of $64$ minterms.

(b) $S_{0,1,3,5,7}(x_1,\dots,x_7)$

This function depends only on Hamming weight and is true exactly for

$$ A={0,1,3,5,7}. $$

We classify all implicants (subcubes) contained in the true set.

Step 1: Structure of a general implicant

Fixing $k$ variables with $r$ ones and leaving $m=7-k$ free variables produces a cube whose weights range over the interval

$$ [r, r+m]. $$

Such a cube is an implicant iff every integer in this interval lies in $A$.

Since $A={0,1,3,5,7}$, the only intervals contained in $A$ are:

$$ {0},\ {1},\ {3},\ {5},\ {7},\ {0,1}. $$

Hence the only nontrivial cube (with free variables) corresponds to the interval $[0,1]$.

Step 2: All implicants

Minterms (all variables fixed):

All assignments with weights $0,1,3,5,7$. 2. One-variable cubes for weight $0,1$:

For each $i$,

$$ C_i := (\bar x_1 \wedge \cdots \wedge \bar x_{i-1} \wedge \bar x_{i+1} \wedge \cdots \wedge \bar x_7), $$

with $x_i$ free.

This cube contains exactly the two assignments:

weight $0$: $0^7$,
weight $1$: $e_i$.

Thus each $C_i$ is an implicant.

No larger cube exists: any interval of length $\ge 2$ would contain $2,4,$ or $6$, which are not in $A$.

Step 3: Prime implicants

The cubes $C_i$ are prime: fixing any additional variable reduces them to minterms.
Minterms of weight $0$ and $1$ are not prime, since they lie inside some $C_i$.
Minterms of weights $3,5,7$ are prime: any relaxation introduces assignments of forbidden weights.

Thus the prime implicants are:

$7$ cubes $C_i$,
all minterms of weights $3,5,7$.

Step 4: Count

$$ #\text{prime implicants}

7 + \binom{7}{3} + \binom{7}{5} + \binom{7}{7} = 7 + 35 + 21 + 1 = 64. $$

Since the $C_i$ cover exactly the weight $0$ and $1$ minterms, replacing those minterms by $C_i$ yields a DNF of the same size, and no further combination is possible.

Hence the shortest DNF has $64$ terms.

(c) Every Boolean function on $n$ variables has at most $2^{n-1}$ prime implicants

Let $f:{0,1}^n \to {0,1}$. We construct an injection from prime implicants into ${0,1}^{n-1}$.

Step 1: Boundary edge associated with a prime implicant

Let $P$ be a prime implicant (a maximal subcube contained in $f^{-1}(1)$).

Then there exists an assignment $a \in P$ and a variable $x_i$ such that:

flipping $x_i$ in $a$ produces a $0$-value of $f$,
and $a$ and its neighbor differ only in coordinate $i$.

Among all such pairs, choose the lexicographically smallest $a$, and among all valid $i$ for this $a$, choose the smallest index. Call this index $i(P)$.

This choice is canonical, hence well-defined.

Step 2: Encoding

Define a map

$$ \phi(P) \in {0,1}^{n-1} $$

by deleting coordinate $i(P)$ from the chosen vector $a$.

So $\phi(P)$ records the boundary point of $P$ with its critical coordinate removed.

Step 3: Injectivity

Suppose $\phi(P)=\phi(Q)$.

Then the chosen boundary assignments $a \in P$, $b \in Q$ agree on all coordinates except possibly $i(P)$ and $i(Q)$.

If $i(P)\neq i(Q)$, then one of these indices is smaller, say $i(P)<i(Q)$.

But then the lexicographically minimal construction forces both implicants to select the same boundary direction at coordinate $i(P)$, contradicting the minimality of $a$ for $Q$.

Hence $i(P)=i(Q)=i$.

Now both implicants contain assignments agreeing on all coordinates except possibly $x_i$, and both are maximal cubes containing that boundary edge. A maximal subcube containing a given edge is unique, hence $P=Q$.

Thus $\phi$ is injective.

Step 4: Bound

Since $\phi$ maps into ${0,1}^{n-1}$,

$$ #{\text{prime implicants}} \le 2^{n-1}. $$

Final answers

(a) $64$ prime implicants (all minterms of odd weight).
(b) $64$ prime implicants:
$7$ cubes covering weights $0$ and $1$,
all minterms of weights $3,5,7$.
(c) Every Boolean function of $n$ variables has at most $2^{n-1}$ prime implicants.

TAOCP 7.1.1 Exercise 120