At least look over sections 5.1 and 5.2 before the Wednesday lecture. Definition of ``disjunctive normal form'': a propositional formula containing no propositional connective other than negation, conjunction and disjunction is in disjunctive normal form (DNF) if it a. contains no subformula of the form ~(A&B) or ~(A|B) (any subformulas which are negations are simply negations of propositional letters) b. contains no subformula of the forms (A|B)&C or A&(B|C) (it contains no conjunctions with conjuncts which are themselves disjunctions) A positive way of putting this is that a DNF formula is a disjunction of conjunctions of propositional letters and negations of propositional letters. But one needs to allow ``conjunctions'' and ``disjunctions'' of one letter. For example, P|(Q&R) is in DNF, where P can be thought of as a ``conjunction of one term'', and P& ~Q & R is in DNF (the whole thing can be thought of as a disjunction of one conjunction. An extreme example of a ``degenerate'' DNF formula is ~Q. Notice that these bad examples satisfy my ``negative'' definition above without any special comment. The definition of formulas in ``conjunctive normal form'' (CNF) is precisely dual to the definition of DNF: interchange the roles of conjunction and disjunction in the definitions. A formula like (P|Q) & (~R | S) is in CNF; it is a conjunction of disjunctions of propositional letters and their negations. We now discuss conversions to DNF and CNF. We start by converting the formula (P|Q) & (~R | S), which is in CNF, to DNF. The algebraic rules we will apply are left and right distributivity of conjunction over disjunction: A & (B | C) = (A & B) | (A & C) (distribution on the right) (A | B) & C = (A & C) | (B & C) (distribution on the left) We apply distribution on the right first to get ((P|Q) & ~R) | ((P|Q) & S) It is worth noting that this expression is neither in DNF or CNF; it contains both conjunctions as part of disjunctions (so it is not in CNF) and disjunctions as part of conjunctions (so it is not in DNF). Now we apply distribution on the left twice (to the left and right disjuncts of this term) to get ((P & ~R) | (Q & ~R)) | ((P & S) | (Q & S)) This is in DNF. We probably want to apply associativity of disjunction to clean up parentheses: (P & ~R) | (Q & ~R) | (P & S) | (Q & S) Notice that this is in DNF but not in full DNF: it is not the case that each disjunct contains all of the letters in the formula. The big example we did was the following: Convert (P <+> Q) -> (R <-> S) to CNF. This turned out to be quite an exercise! The first thing we need to do is eliminate the connectives other than negation, conjunction and disjunction: (P <+> Q) -> (R <-> S) == ~(P<+>Q) | (R <->S) (eliminate the top implication) == ~~(P<->Q) | (R<->S) (eliminate the xor) == (P<->Q) | (R<->S) (double negation) == ((P->Q) & (Q->P)) | ((R->S) & (S->R)) (eliminate two biconditionals) == ((~P | Q) & (~Q | P)) |((~R | S) & (~S | R)) (eliminate four implications) Now we pause to plan our strategy. This expression is ``bad'' from the standpoint of CNF because it is a disjunction of two conjunctions. Notice that the left and right disjuncts are already in CNF, though; this makes things easier. We list the two distributive laws that we will use: A | (B & C) = (A | B) & (A | C) (distribution on the right) (A & B) | C = (A | C) & (B | C) (distribution on the left) These are the two distributive laws of disjunction over conjunction (``dual'' to the distributive laws we used in the previous example). We start by distributing on the left. The role of A is played by the term ~P | Q, that of B by the term ~Q | P, and that of C by the term (~R | S) & (~S | R). The result is == ((~P | Q) | ((~R | S) & (~S | R))) & ((~Q | P) | ((~R | S) & (~S | R))) We then distribute on the right in the left conjunct to get == (((~P | Q) | (~R | S)) & ((~P | Q) | (~S | R))) & ((~Q | P) | ((~R | S) & (~S | R))) and distribute on the right in the right conjunct to get == (((~P | Q) | (~R | S)) & ((~P | Q) | (~S | R))) & (((~Q | P) | (~R | S)) & ((~Q | P) | (~S | R))) This is in CNF. Regrouping with commutative and associative laws allows us to put this in a prettier CNF form: == (~P | Q | ~R | S) & (~P | Q | R | ~S) & (P | ~Q | ~ R | S) & (P | ~Q | R | ~S) The meaning of a CNF term, as in this case, is generally harder to see than the meaning of a DNF term (which can be easily converted to a truth table).