PMATH 330 Assignment III due Sept 30th This document will get longer after each lecture! Answer each problem with justification, except where indicated. That means writing actual sentences. 1. Compute a disjunctive normal form for (P R) (Q R). 2. There is a notion called conjunctive normal form which is related to disjunctive normal form, essentially by swapping the roles of conjunction and disjunction in the definition. In this problem you will study it. If is a formula which uses the propositional variables Pi1 , , Pin , we say that is in conjunctive normal form if is a conjunction 1 k each j is a disjunction 1j nj and for each j, and each l n, there is exactly one m for which m j is either Pil or Pil and none of the j can be obtained from any of the others by reordering the literals that make them up Also for each i we say Pi Pi is in conjunctive normal form. If and are truth equivalent and is in conjunctive normal form we say is a conjunctive normal form of . The first part of this problem gives an example of what a conjunctive normal form looks like. (a) The formula = (P1 P2 P3 ) (P1 P2 P3 ) (P1 P2 P3 ) is in conjunctive normal form. Give its truth table. (b) Referring to the previous part: explain a relationship between the conjuncts which make up and the rows of the truth table which correspond to truth assignments for which v() = F . (c) Let be the formula (P Q) (R P ). Give a disjunctive normal form of and a conjunctive normal form of . (d) Formulate a conjecture about how the disjunctive normal form for a formula and the conjunctive normal form for are related. Your conjecture should be stated precisely and should convey the strongest relationship you can identify. You don't need to prove your conjecture. 3. Show that {, } is adequate. 1 4. Determine whether {, } is adequate. HINT: let C = {, }. You may assume any formula built using the connectives in C has one of the following forms: Pi for some i () where and are built using only the connectives in C ( ) where and are built using only the connectives in C This definition allows you to do induction on the set of formulas built using the connectives in C. This idea works for any set C of connectives. 5. Decide whether each of the following sets of formulas is satisfiable. If it is satisfiable, give a choice of truth assignment which satisfies it, by saying what v(P ), v(Q), v(R), and v(S) should each be. (a) {P Q, (b) {P Q, Q R, R S, Q R, S P, R S, P R, S P, Q S} S Q, S Q} 6. Let be the set of formulas: {P Q, Q R, P Q, Q R, R P, R Q} Show is not satisfiable. Find the size of the largest subset of which is satisfiable. 2