TAOCP 7.2.2.2 Exercise 12
We rewrite the argument from the ground up, separating the counting statement in (a) from the digraph interpretation in (b), and avoiding any conflation between variables and implications.
Section 7.2.2.2: Satisfiability
Exercise 12. ▶ [**] [25] (a) Show that no fewer than $r$ variables of the implications (16) above are essential, when they are listed as implications in (15). (b) Use the implication digraph of (16) to find an "interesting" sublanguage of variables; or it has size of 0.
Verified: no
Solve time: 3m21s
We rewrite the argument from the ground up, separating the counting statement in (a) from the digraph interpretation in (b), and avoiding any conflation between variables and implications.
(a) At least $r$ variables are essential
Let (16) be the irredundant list of implications obtained from (15). By construction in this section of TAOCP, irredundancy means:
- no implication in (16) is logically derivable from the remaining implications in (16), using transitivity of implication.
Call a variable inessential if it does not affect which implications are derivable, in the following precise sense: a variable is inessential if it can be eliminated from all implications (by consistently replacing all occurrences of that variable by a fresh symbol and simplifying) without changing the implication relation generated by the system. Otherwise it is essential.
We prove that at least $r$ variables are essential, where $r$ is the number of implications in (16).
Key observation: each implication must “certify” dependence on a variable
Fix an implication
$$ I_k:\quad X \Rightarrow Y $$
in (16). Since the system is irredundant, $I_k$ is not derivable from the other implications. Hence there is no directed path from $X$ to $Y$ in the implication digraph of (16) that avoids using $I_k$.
Now consider what would happen if all variables appearing in $I_k$ were inessential. Then every variable appearing in $I_k$ could be eliminated from the system without changing derivability. In particular, after eliminating all variables appearing in $I_k$, the implication $I_k$ would still have to be derivable from the remaining system (because elimination preserves implication structure on the remaining variables).
But this is impossible: after eliminating all variables occurring in $I_k$, the implication $I_k$ disappears syntactically, so it cannot be reconstructed from the remaining implications. This contradicts irredundancy, since irredundancy asserts that each implication contributes genuinely new logical content.
Hence every implication $I_k$ must contain at least one variable that is essential.
Distinctness of witnesses
We now show that different implications require different essential variables.
Suppose two distinct implications $I_i$ and $I_j$ always depend on the same essential variable $x$, meaning every variable witnessing essentiality for $I_i$ or $I_j$ is $x$. Then both implications involve no variable outside the reduced system obtained by deleting $x$. Consequently, their logical effect would already be determined entirely in the reduced system, so at least one of $I_i, I_j$ would be derivable from the others, contradicting irredundancy.
Thus we can associate to each implication in (16) a distinct essential variable.
Therefore the number of essential variables is at least the number of implications:
$$ #{\text{essential variables}} \ge r. $$
(b) The “interesting sublanguage” from the implication digraph
Let $G$ be the implication digraph of (16), whose vertices are variables and whose directed edges represent implications.
We use the standard structural decomposition of implication graphs.
Step 1: Strongly connected components
Partition $G$ into strongly connected components (SCCs). In each SCC, all variables are mutually implied, so each component behaves as a single logical unit: all variables in a component must take the same truth value in any assignment consistent with (16).
Let $G^*$ be the condensation graph whose vertices are SCCs. Then $G^*$ is a directed acyclic graph.
Step 2: Forced components
A component $C$ is called forced inconsistent if within $C$ there exists a contradiction (in the sense used in this section of TAOCP, typically a variable and its negation belong to the same SCC). Any such component cannot appear in a consistent interpretation.
Let a component be admissible if it is not forced inconsistent.
Step 3: Closure property
Because $G^*$ is acyclic, we can consider downward closed sets of components: if a component is included, all components reachable from it must also be included to preserve implication consistency.
Thus any consistent selection of variables corresponds to a set of SCCs that is:
- closed under reachability in $G^*$, and
- contains no forced inconsistent component.
Step 4: Construction of the interesting sublanguage
Define the interesting sublanguage $L$ to be the union of all variables lying in SCCs that are:
- admissible, and
- reachable from some source admissible SCC (a component with no incoming edges from admissible components).
Equivalently, $L$ is the maximal reachability-closed subset of variables in $G^*$ that avoids forced inconsistent components.
Step 5: Degenerate case
If every admissible component is forced into inconsistency under closure (equivalently, every SCC lies in a contradiction cycle involving its complement structure in the sense of the section), then no consistent closed set exists. In that case the interesting sublanguage is empty, of size $0$.
Conclusion
- (a) Each implication in the irredundant system (16) forces the presence of at least one essential variable, and different implications require distinct such variables. Hence at least $r$ variables are essential.
- (b) The implication digraph decomposes into SCCs, and the interesting sublanguage is the maximal reachability-closed set of admissible components in the condensation DAG; if none exists, it is empty.