TAOCP 7.2.2.2 Exercise 2

We restart the analysis from the logical structure rather than a one-model construction.

taocpmathematicsalgorithmsvolume-4medium

Section 7.2.2.2: Satisfiability

Exercise 2. [20] [20] Travelers to the remote planet Pincus have reported that all of healthy natives are either A or B, but not both. Sane natives are happy, and many are healthy though hairless. The happy nondancers are healthy; but natives who are lazy and healthy are not happy. Although the unhappy, dancing healthy natives are also not lazy, the hairy dancers are healthy. What can we conclude from the unsane observed of native Pincus?

Verified: no
Solve time: 3m14s

We restart the analysis from the logical structure rather than a one-model construction.

Let the predicates be $S, H, He, D, L, Ha$ and the partition condition

$$ He \to (A \oplus B). $$

The given implications are:

$$ S \to H, \quad H \wedge \neg D \to He, \quad L \wedge He \to \neg H, \quad \neg H \wedge D \wedge He \to \neg L, \quad Ha \wedge D \to He. $$

We are asked what can be concluded about individuals satisfying $\neg S$ (unsane natives).

1. Identify the logical role of $S$

The key structural observation is that $S$ appears only once in the entire system, and only as an antecedent:

$$ S \to H. $$

No other axiom mentions $S$. In particular:

  • There is no rule of the form $H \to S$, $He \to S$, etc.
  • No constraint involves $\neg S$ directly.
  • No existential statement depends on $S$.

Thus $S$ is a purely one-directional trigger and does not interact with any other predicate except by possibly forcing $H$.

Taking the contrapositive of $S \to H$, we get:

$$ \neg H \to \neg S, $$

but this still does not constrain $\neg S$; it only explains when someone must be unsane.

So $S$ is not a controlling variable in the system.

2. Effect of setting $S = \text{false}$

Fix any individual $x$ with $\neg S(x)$.

Now check whether any rule becomes active because of this assumption.

The only rule involving $S$ is $S \to H$, whose antecedent is false at $x$. Hence:

$$ S(x) = \text{false} ;\Rightarrow; (S \to H)\text{ is automatically satisfied.} $$

Therefore, assigning $\neg S(x)$ imposes no constraint whatsoever on:

$$ H(x), He(x), D(x), L(x), Ha(x), A(x), B(x). $$

Any restrictions on those predicates come only from the other axioms, none of which mention $S$.

3. Interaction with the rest of the system

The remaining constraints