# Last example in class on Jan 5

5 Jan 1996 In class on Friday January 5, the last example was a little rushed, and I'm afraid wasn't as clear as it could have been. Here is a more detailed version. We were showing that the following formula was a tautology
• [ ( p v q) ^ ( p -> r ) ^ ( q -> r ) ] -> r

We begin with the formula
[ ( p v q ) ^ ( p -> r ) ^ ( q -> r ) ] -> r
We use the equivalence ( x -> y ) <=> ( ~x v y) to obtain
~[ ( p v q) ^ ( p -> r ) ^ ( q -> r ) ] v r
and twice again to obtain
~[ ( p v q ) ^ ( ~p v r ) ^ ( ~q v r ) ] v r
Applying DeMorgan's law to the outermost parenthesized expression we get
[ ~( p v q ) v ~( ~p v r ) v ~( ~q v r ) ] v r
and then we apply DeMorgan's law to the innermost parenthesized expressions resulting in
[ ( ~p ^ ~q ) v ( p ^ ~r ) v ( q ^ ~r ) ] v r
Using the associative rule for v we get
( ~p ^ ~q ) v [ ( p ^ ~r ) v ( q ^ ~r ) ] v r
and then with the commutative and associative rules for v we get
[ ( ~p ^ ~q ) v r ] v [ ( p ^ ~r ) v ( q ^ ~r ) ]
Applying the distributive law to the right hand side we get
[ ( ~p ^ ~q ) v r ] v [ ( p v q ) ^ ~r ]
We then apply double negation to the left hand side
~ ~[ ( ~p ^ ~q ) v r ] v [ ( p v q ) ^ ~r ]
and apply DeMorgan's law two times
~ [ ~( ~p ^ ~q ) ^ ~r ] v [ ( p v q ) ^ ~r ]
~ [ ( p v q ) ^ ~r ] v [ ( p v q ) ^ ~r ]
We now notice that we have a formula of the form
~z v z
Which must always be true
Computer Science & Engineering Department,
University of Washington,
PO Box 352350
Seattle, WA 98195-2350 USA
walkup@cs.washington.edu