Past exam of the logic and set theory course of the University of Oxford / 2007 / A / 1 / iii / Solution

Assume first that $\varphi$ is false on the all-true and all-false Boolean valuations. Use the truth-table normal form from part (ii). Every satisfying Boolean valuation on the finitely many propositional variables must have at least one true propositional variable and at least one false propositional variable. Its minterm therefore has the formwhere $C_s$ conjoins its true propositional variables and $D_s$ disjoins its false propositional variables; both lists are nonempty. This is equivalent to $\neg (C_s\to D_s)$. If the satisfying Boolean valuations are indexed by $1,\dots ,N$, De Morgan's laws givesIf there are no satisfying Boolean valuations, take $N=1$ and $C_1=D_1=p$: the result is $\neg (p\to p)$, again always false.

Conversely, on the all-true Boolean valuation every nonempty $D_i$ is true, so every $C_i\to D_i$ is true. On the all-false Boolean valuation every nonempty $C_i$ is false, so every logical implication is again true. Negating their logical conjunction gives false on both Boolean valuations. Logical equivalence transfers these values to $\varphi$. The usual nonempty meaning of logical conjunction and logical disjunction of propositional variables is used here; allowing empty $C_i$ or $D_i$ without qualification would destroy this converse.