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

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.