Solution

ID: past-exam-of-the-logic-and-set-theory-course-of-the-university-of-oxford/2007/a/1/ii/solution

Let include all propositional variables appearing in . For each Boolean valuation , put
The minterm is true exactly for Boolean valuations whose restrictions to these propositional variables are . Consequently
Indeed, an Boolean valuation making true makes its own minterm true, while a true minterm in the displayed logical disjunction certifies the truth of . There are only finitely many Boolean valuations, so this is a finite disjunctive normal form. If there are no satisfying Boolean valuations, use for any propositional variable ; this is a disjunctive normal form for falsity without needing an empty logical disjunction convention.

New to topics? Read the docs here!