TAOCP 7.2.2.2 Exercise 12
The proposed solution cannot be corrected into a valid mathematical solution from the information given in the exercise statement alone.
Section 7.2.2.2: Satisfiability
Exercise 12. ▶ [25] [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: 2m48s
The proposed solution cannot be corrected into a valid mathematical solution from the information given in the exercise statement alone.
The missing information is not optional. The assertion in part (a) depends on the exact implications in equation (16), their ordering in (15), the definition of “essential” used in that section, and the construction that determines the parameter $r$. Part (b) depends on the actual vertices and arcs of the implication digraph defined by (16). Without those objects, there is no well-defined graph to analyze and no way to identify the requested sublanguage.
A proof of the form
$$ \text{“at least (r) variables are essential”} $$
requires exhibiting, for each of $r$ variables, a reason that deleting or omitting that variable changes the implication system or destroys the required property. The witness assignments or implication paths depend on the concrete implications in (16). Likewise, constructing the “interesting” sublanguage requires finding a subgraph of the implication digraph with the stated property, which cannot be done without knowing its vertices and arcs.
Therefore the only mathematically correct solution at this level of information is:
$$ \boxed{\text{The exercise statement is incomplete; equations (15) and (16) and the preceding definitions are required.}} $$
Once the portion of Section $7.2.2.2$ containing the implications (15), (16), the definition of essential variables, and the parameter $r$ is supplied, the proof of both parts can be written explicitly.