next up previous
Next: Tuesday, Jan 25: Lab Up: Lecture Notes Previous: Friday, January 21

Monday, January 24

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).



Randall Holmes
2000-05-05