80-110: The Nature of Mathematical Reasoning

Carnegie Mellon University

Spring 2015

Homework 8

Due Monday, Mar. 23

Do problems 1, 3, 4, 10, and 11 from the chapter 5 lab on OLI, and 1, 3, and 8 from the chapter 6 lab.

Bonus question: We say that a formula is in conjunctive normal form when it is written as a sequence of disjunctions of propositional letters or their negations, connected by conjunctions. That is, it looks like: (_ v _ v _ v _) & (_ v _ v _) & (_ v _ v _ v _). For an example, the formula (P v Q) & (~Q v R v ~S) & (~A v ~B) & (X v Y v Z v W) is in conjunctive normal form, but (P & Q) v (~R v S v T) is not, and neither is ~(P v Q) & (Q v R).

It turns out that for any formula in our language, one can write an equivalent formula in CNF: that is, a CNF formula that is true under exactly the same truth assignments. Describe an algorithm for converting formulas to this form. (Recalling our discusion of recursive functions, this algorithm is a good example of one!)