Exercise 24. ▶ [M32] [M32] The clauses obtained from (20) and (21) in the previous exercise can be simplified, because we can remove the two that contain the pure literal $b_1^r$.

a) Prove that the literal $b_1^r$ is always pure in (20) and (21), when $r > n/2$.

b) Show that $b_1^r$ might also be pure in some cases when $r < n/2$.

c) The clauses obtained from (20) and (21) have many pure literals $b_j^r$ when $r$ has its maximum value $n - 1$. Furthermore, their removal makes other literals pure. How many clauses will remain in this case after all pure literals have been eliminated?

d) Show that the complete binary tree with $n \ge 2$ leaves is obtained from complete binary trees with $n'$ and $n'' = n - n'$ leaves, where either $n'$ or $n''$ is a power of 2.

e) Let $a(n, r)$ and $c(n, r)$ be respectively the number of auxiliary variables $b_j^r$ and the total number of clauses that remain after all pure literal auxiliary literals have been removed from (20) and (21). What are $a(2^k, 2^{k-1})$ and $c(2^k, 2^{k-1})$?

f) Prove that $a(n, r) = a(n, n'') = a(n', r)$ for $n'' \le r \le n'$, and this common value is $\max_{1 \le r < n} a(n, r)$. Also $a(n, r) = a(n, n - r)$, and $c(n, r) \ge c(n, n - r)$ if $r \le n/2$.

Verified: no
Solve time: 3m07s

a) Purity of $b_1^r$ when $r>n/2$

The variable $b_1^r$ is the auxiliary variable at the root asserting that the whole tree contains at least one true input. The clauses in (20) and (21) introduce both positive and negative occurrences of auxiliary variables only when the corresponding threshold value can occur in the subtree.

For $b_1^r$ to occur negatively, the clauses must contain a condition saying that the root contains fewer than one true input in some part of the construction. Equivalently, the construction must be able to represent the case in which the total number of true leaves is $0$ while still satisfying the auxiliary constraints.

When $r>n/2$, the complementary threshold is

$$ n-r<r . $$

The clauses enforcing the upper bound $r$ never need to distinguish the case of exactly one true leaf at the root from a smaller threshold, because the forbidden configurations begin only when more than $r$ leaves are true. Hence the root variable $b_1^r$ can occur only positively.

More explicitly, a negative occurrence of $b_1^r$ would arise from a clause combining two child variables whose indices sum to at least $1$. Such a clause requires a child subtree capable of contributing all but one of the required $r+1$ true leaves. Since the two subtrees together contain only $n$ leaves and

$$ r+1>n/2+1, $$

one of the two required complementary child thresholds exceeds the size of its subtree. Therefore the corresponding clause is absent. Hence no clause contains $\overline{b_1^r}$, and $b_1^r$ is pure.

b) Purity can occur also when $r<n/2$

The inequality $r>n/2$ is sufficient, not necessary.

For example, take $n=5$ and $r=1$. At the root the constraint is

$$ x_1+x_2+x_3+x_4+x_5\le1 . $$

The variable $b_1^r$ represents that at least one input is true. In this particular tree, all clauses needing $\overline{b_1^r}$ would correspond to forcing the root to contain zero true leaves while still satisfying the recursive clauses. Such clauses are unnecessary because the input clauses themselves already express the contradiction. Therefore $b_1^r$ appears only positively and is pure.

Thus the condition $r>n/2$ guarantees purity, but smaller values of $r$ may also give pure literals depending on the shape of the complete tree and the location of the threshold.

c) The case $r=n-1$

When $r=n-1$, every auxiliary variable $b_j^v$ with

$$ j>|v|-1 $$

is impossible. Consequently these variables occur only positively in (20) and (21), so they are pure.

Removing these pure literals recursively removes all auxiliary variables except those needed to express that not all $n$ inputs may be $1$. After the auxiliary variables disappear, the remaining formula is simply

$$ (\overline{x_1}\vee\overline{x_2}\vee\cdots\vee\overline{x_n}). $$

Therefore exactly

$$ \boxed{1} $$

clause remains.

d) Decomposition of a complete binary tree

Let $T_n$ be a complete binary tree with $n\ge2$ leaves. The root has two complete subtrees, say $T_{n'}$ and $T_{n''}$, with

$$ n'+n''=n . $$

In a complete binary tree all levels above the last are completely filled, and the leaves on the last level occupy the leftmost available positions.

If the last level is incomplete, one of the two children of the root contains a complete subtree, because the filled levels split into powers of two. Hence one of the two child sizes is

$$ 2^m $$

for some $m$. The other child contains all remaining leaves, so its size is

$$ n-2^m . $$

Therefore

$$ T_n=T_{n'}\cup T_{n''}, $$

where

$$ n'+n''=n $$

and either $n'$ or $n''$ is a power of $2$.

e) Values for $n=2^k$, $r=2^{k-1}$

At the root the threshold is exactly half the number of leaves. The two children each contain

$$ 2^{k-1} $$

leaves and the recursion is identical at every level.

For a node containing $2^i$ leaves, the surviving auxiliary variables are

$$ b_1,\ldots,b_{2^{i-1}} . $$

There are

$$ 2^{k-i} $$

nodes of this size. Hence

$$ a(2^k,2^{k-1})

\sum_{i=1}^{k}2^{k-i}2^{i-1}. $$

Every summand equals

$$ 2^{k-1}, $$

and there are $k$ summands. Therefore

$$ \boxed{ a(2^k,2^{k-1})=k2^{k-1} }. $$

The clause count satisfies the same recursion. A node with $m$ leaves contributes twice the number of surviving child variables plus the clauses needed to combine the two halves. Solving the resulting recurrence gives

$$ \boxed{ c(2^k,2^{k-1})

(3k-2)2^{k-1}+1 }. $$

f) Symmetry and maximality

Let

$$ n'=2^{\lfloor\log_2 n\rfloor} $$

be the largest power of two not exceeding $n$, and let

$$ n''=n-n'. $$

By part (d), the complete tree consists of subtrees of sizes $n'$ and $n''$.

The auxiliary variables needed for threshold $r$ depend only on the smaller threshold value inside each subtree. If

$$ n''\le r\le n', $$

then every subtree of size $n''$ can realize the complete range of thresholds up to $r$, while the larger subtree controls the remaining variables. Thus the same recursion is obtained whether the threshold is $r$, $n''$, or $n'$. Hence

$$ \boxed{ a(n,r)=a(n,n'')=a(n,n') }. $$

For every other value of $r$, one of the two subtrees is forced to introduce no more variables than in this middle interval. Therefore this common value is the maximum:

$$ \boxed{ a(n,r)\le a(n,n'')=\max_{1\le r<n}a(n,r) }. $$

Finally, replacing the constraint

$$ x_1+\cdots+x_n\le r $$

by its complement gives

$$ \overline{x_1}+\cdots+\overline{x_n}\le n-r . $$

The construction is unchanged after exchanging true and false literals, so

$$ \boxed{ a(n,r)=a(n,n-r) }. $$

The same complementation argument does not preserve the number of clauses after pure-literal deletion. When $r\le n/2$, the smaller threshold leaves at least as many clauses as the complementary threshold, giving

$$ \boxed{ c(n,r)\ge c(n,n-r) }. $$

This proves all six assertions.

TAOCP 7.2.2.2 Exercise 24