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

A Boolean valuation is an arbitrary function $v$ assigning one of the two truth values to each propositional variable. It extends uniquely to all propositional formulas by following the construction of the propositional formula:For logical implication, $\tilde{v}(A\to B)$ is false exactly when $\tilde{v}(A)$ is true and $\tilde{v}(B)$ is false; otherwise it is true. Here the operations on the right are Boolean operations on truth values. Structural recursion gives existence, and structural induction gives uniqueness: once the immediate subformulas have their values, the outer connective fixes the resulting value.

Two propositional formulas are logically equivalent if every Boolean valuation gives them the same truth value. A disjunctive normal form is a logical disjunction of logical conjunctions of literals, with a literal being a propositional variable or its negation.

Let $p_1,\dots ,p_n$ include all propositional variables appearing in $\varphi$. For each Boolean valuation $s\in \{T,F{\}}^n$, putThe minterm $M_s$ is true exactly for Boolean valuations whose restrictions to these propositional variables are $s$. ConsequentlyIndeed, an Boolean valuation making $\varphi$ true makes its own minterm true, while a true minterm in the displayed logical disjunction certifies the truth of $\varphi$. There are only finitely many Boolean valuations, so this is a finite disjunctive normal form. If there are no satisfying Boolean valuations, use $p\wedge \neg p$ for any propositional variable $p$; this is a disjunctive normal form for falsity without needing an empty logical disjunction convention.

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.