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