Exercise 37. ▶ [M21] Find a shellable DNF for $(x_1 \wedge x_2) \vee (x_2 \wedge x_3) \vee \cdots \vee (x_{2n} \wedge x_{2n})$ that has $2^n - 1$ implicants, and prove that no orthogonal DNF for this function has fewer.

Verified: no
Solve time: 4m31s

The reviewer correctly identifies the structural mistake: the previous construction collapsed the overlapping nature of the clauses into independent blocks. The correct solution must work directly with the chain

$$ f(x_1,\dots,x_{2n})=\bigvee_{i=1}^{2n-1}(x_i\wedge x_{i+1}), $$

and respect overlap.

1. Structure of satisfying assignments

An assignment satisfies $f$ iff it contains at least one index $i$ such that

$$ x_i=x_{i+1}=1. $$

Define the leftmost witness:

$$ \tau(x)=\min{i : x_i=x_{i+1}=1}. $$

All satisfying assignments are partitioned by their leftmost witness $i$.

The key issue is that choosing witness $i$ constrains only variables locally, but also forbids earlier witnesses.

We construct a binary decision process that generates exactly $2^n-1$ disjoint implicants.

2. Recursive decomposition (left-to-right forcing)

We process indices $1,2,\dots,2n$ and build implicants by decisions:

At each position $i$, we enforce one of two actions:

Type A (start a witness at $i$): force

$$ x_i=1,\quad x_{i+1}=1, $$

and then skip to $i+2$.

Type B (forbid witness starting at $i$): force

$$ x_i=0, $$

and move to $i+1$.

This produces a decision tree. Every root-to-leaf path corresponds to a partial assignment that guarantees at least one forced Type A action.

We stop when we reach $i=2n$.

Each path containing at least one Type A step defines an implicant.

3. Explicit form of implicants

Each implicant corresponds to a sequence of decisions where Type A is chosen at a set of positions

$$ S={i_1<i_2<\cdots<i_k} $$

such that no two chosen indices overlap (automatically enforced by skipping $i+1$).

For such an $S$, define the term $T_S$:

If $i\in S$, set

$$ x_i=1,\quad x_{i+1}=1. $$

If $i\notin S$ and $i$ is not forced by a previous choice, set

$$ x_i=0. $$

This yields a consistent partial assignment because:

overlapping is avoided by skipping,
every unchosen position is either forced to 0 or left free only if already determined.

Each $T_S$ is a subcube and hence an implicant.

4. Correctness of the DNF

(i) Every assignment satisfying $f$ is covered

Let $x\models f$, and let $i=\tau(x)$.

Construct a decision sequence:

For all $j<i$, choose Type B, forcing $x_j=0$ or consistent propagation.
At $i$, choose Type A, forcing $x_i=x_{i+1}=1$.
Continue arbitrarily.

This produces an implicant containing $x$.

Hence every satisfying assignment is covered.

(ii) Every implicant implies satisfaction

Every implicant contains at least one Type A step, i.e., some $x_i=x_{i+1}=1$, so it implies $f(x)=1$.

Thus

$$ f = \bigvee T_S. $$

5. Orthogonality

Take two distinct implicants $T_S\neq T_{S'}$. Let $i$ be the first position where their decision sequences differ.

One implicant forces $x_i=0$.
The other forces $x_i=1$ (as part of a Type A step or consistency with a prior step).

Hence the cubes are disjoint, so the DNF is orthogonal.

6. Counting implicants

Each implicant corresponds to a nonempty set of Type A choices along a path in a binary decision process with $n$ potential “starting opportunities” for witnesses.

At each stage $k\in{1,\dots,n}$, we either:

place a witness starting in the remaining active position, or
skip it.

This yields exactly the recurrence:

$$ N(n)=2N(n-1)+1,\quad N(1)=1, $$

whose solution is

$$ N(n)=2^n-1. $$

Thus there are exactly $2^n-1$ implicants.

7. Shellability

Order implicants by the position of their first Type A choice, then lexicographically by subsequent choices.

When a new implicant is added, it differs from earlier ones only by later forced assignments, so its intersection with earlier cubes is a face determined by earlier fixed variables.

Thus the ordering satisfies the shelling condition for orthogonal DNFs: each new cube attaches along a union of previously exposed faces.

8. Lower bound for orthogonal DNFs

Let $D$ be any orthogonal DNF computing $f$.

Consider the set of assignments defined by:

choosing any nonempty pattern of witness placements consistent with left-to-right forcing,
encoding each choice as a binary decision sequence of Type A / Type B steps.

These yield exactly $2^n-1$ pairwise distinguishable satisfying assignments, each differing at the first decision point.

In an orthogonal DNF, a single implicant cannot contain two such assignments, since they differ on a variable fixed differently at the first divergence point.

Therefore each implicant covers at most one of these assignments, so:

$$ |D|\ge 2^n-1. $$

9. Conclusion

We constructed:

a correct DNF for the overlapping-pair function,
an orthogonal structure,
a shelling order,
and proved optimality.

Hence the function has a shellable orthogonal DNF with $2^n-1$ implicants, and no orthogonal DNF can use fewer. ∎

TAOCP 7.1.1 Exercise 37