Artificial Intelligence
Prof. R. Williams


	        EQUIVALENT PROPOSITIONAL LOGIC EXPRESSIONS


In the following, p, q, and r represent arbitrary propositions, which can
take on the values T(rue) and F(alse).

Truth Tables:

  p  | (not p)		 p   q  | (or p q) | (and p q) | (if p q)
 -------------		-----------------------------------------
  F  |   T		 F   F  |     F    |     F     |     T
  T  |   F		 F   T  |     T    |     F     |     T
			 T   F  |     T    |     F     |     F
			 T   T  |     T    |     T     |     T


Two expressions involving propositions are equivalent if they have the
same value for each combination of values of the propositions involved.
It is always possible to check whether two expressions are equivalent
by using the truth tables above.  In particular, we have the following
equivalences:

(not (not p))		    is equivalent to	p
(if p q)                    is equivalent to    (or (not p) q)

de Morgan's Laws:

(not (or p q))		    is equivalent to	(and (not p) (not q))
(not (and p q))		    is equivalent to	(or (not p) (not q))

Commutative Laws:

(or p q)		    is equivalent to	(or q p)
(and p q)		    is equivalent to	(and q p)

Associative Laws:

(or (or p q) r)		    is equivalent to	(or p (or q r))
(and (and p q) r)	    is equivalent to	(and p (and q r))

Distributive Laws:

(or p (and q r))	    is equivalent to	(and (or p q) (or p r))
(and p (or q r))	    is equivalent to	(or (and p q) (and p r))