Artificial Intelligence
Prof. R. Williams


	     EQUIVALENT PREDICATE CALCULUS 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))


In addition, we have the following equivalences involving the quantifiers
forall and exists, where P is an arbitrary predicate:

(and (forall (x) (P x)) q)  is equivalent to    (forall (x) (and (P x) q))
(and (exists (x) (P x)) q)  is equivalent to    (exists (x) (and (P x) q))
(or (forall (x) (P x)) q)   is equivalent to    (forall (x) (or (P x) q))
(or (exists (x) (P x)) q)   is equivalent to    (exists (x) (or (P x) q))
(not (forall (x) (P x)))    is equivalent to    (exists (x) (not (P x)))
(not (exists (x) (P x)))    is equivalent to    (forall (x) (not (P x)))


As an example of the use of some of these equivalences to transform
an expression into another one, consider the sentence

  "Somebody loves nobody."

We may translate this into predicate calculus as

  (exists (x) (and (person x)
		   (forall (y) (if (person y)
				   (not (loves x y))))))

If we apply the equivalence involving "if" above, this becomes

  (exists (x) (and (person x)
		   (forall (y) (or (not (person y))
				   (not (loves x y))))))

whose English interpretation is quite awkward to express.  If we then
apply one of de Morgan's laws to the "or" expression, this becomes

  (exists (x) (and (person x)
		   (forall (y) (not (and (person y) (loves x y))))))

which has the awkward English interpretation

  "There is somebody such that everything fails to have the properties of
   being both a person and loved by that somebody."

Now we may apply the very last equivalence listed above to the "forall"
expression to obtain

  (exists (x) (and (person x)
		   (not (exists (y) (and (person y) (loves x y))))))

whose English interpretation is something like 

  "There is somebody such that there is nothing which is both a person
   and loved by that somebody."

Continuing on, and omitting the detailed English interpretations, we
apply one equivalence at a time to obtain the following sequence of
transformed versions:

  (exists (x) (and (not (not (person x)))
		   (not (exists (y) (and (person y) (loves x y))))))

  (exists (x) (not (or (not (person x)))
		       (exists (y) (and (person y) (loves x y))))))

  (exists (x) (not (if (person x)
		       (exists (y) (and (person y) (loves x y))))))

  (not (forall (x) (if (person x)
		       (exists (y) (and (person y) (loves x y))))))

This last version has the English interpretation

  "It is not true that everybody loves somebody."