Equivalent Formulas

 

In this section we'll discuss the important notion of equivalence for wffs of the first-order predicate calculus.

Two wffs A and B are equivalent if they both have the same truth value with respect to every interpretation of both A and B. By an interpretation of both A and B, we mean that all free variables, constants, functions, and predicates that occur in either A or B are interpreted with respect to a single domain. We denote the fact that A and B are equivalent by writing

A º B.

We can describe equivalence in terms of a single valid wff as follows:

A º B if and only if (A ® B) Ù (Â ® A) is valid.

To start things off, let's see how propositional equivalences give rise to predicate calculus equivalences. A wff W is an instance of a propositional wff  V if W is obtained from V by replacing each propositional letter of V by a wff, where all occurrences of each propositional letter in V are replaced by the same wff. For example, the wff

" x p(x) ® " x p(x) Ú q(x)

is an instance of P ® P Ú Q because Q is replaced by q(x) and both occurrences of P are replaced by " x p(x).

If W is an instance of a propositional wff V, then the truth value of W for any interpretation can be obtained by assigning truth values to the letters of V. For example, suppose we define an interpretation with domain D = {a, b} and we set p(a) = p(b) = true and q(a) = q(b) = false. For this interpretation, the truth value of the wff " x p(x)® "xp(x) Ú q(x) is the same as the truth value of the propositional wff P ® P Ú Q, where P = true and Q = false.

So we can say that two wffs are equivalent if they are instances of two equivalent propositional wffs, where both instances are obtained by using the same replacement of propositional letters. For example, we have

" x p(x) ® q(x) º Ø " x p(x) Ú q(x)

because the left and right sides are instances of the left and right sides of the propositional equivalence P ® Q º Ø P Ú Q, where both occurrences of P are replaced by " x p(x) and both occurrences of Q are replaced by q(x). We'll state the result again for emphasis:

Two wffs are equivalent whenever they are instances of two equivalent propositional wffs, where both instances are obtained by using the same replacement of propositional letters.

Let's see whether we can find some more equivalences to make our logical life easier. We'll start by listing two equivalences that relate the two quantifiers by negation. For any wff W we have the two equivalences

 

               Ø (" x W) º $ x Ø W and  Ø ($ x  W) º " x Ø W.                         (6.1)

 

It's easy to believe that these two equivalences are true. For example, we can illustrate the equivalence Ø (" x W) º $ x Ø W  by observing that the negation of the statement "Something is true for all possible cases" has the same meaning as the statement "There is some case for which the something is false." Similarly, we can illustrate the equivalence Ø ($ x  W) º " x Ø W  by observing that the negation of the statement "There is some case for which something is true" has the same meaning as the statement "Every case of the something is false."

Another way to demonstrate these equivalences is to use De Morgan's laws. For example, let W = p(x) and suppose that we have an interpretation with domain D = {0, 1, 2, 3}. Then no matter what values we assign top, we can apply De Morgan's laws to obtain the following propositional equivalence:

Ø (" x p(x)) = Ø (p(0) Ù p(1) Ù p(2) Ù p(3))

                             = Ø p(0) Ú Ø p(1) Ú Ø p(2) Ú Ø p(3)

                                                       = $ x Ø p(x).

We also get the following equivalence:

Ø ($ x p(x)) = Ø (p(0) Ú p(1) Ú p(2) Ú p(3))

                             = Ø p(0) Ù Ø p(1) Ù Ø p(2) Ù Ø p(3)

                                                       = " x Ø p(x).

Now let's look at two equivalences that allow us to interchange universal quantifiers if they are next to each other and similarly for existential quantifiers.

                 "x"y W º"y"x W   and    $x $y W º $y $x W                           (6.2)

Again, this is easy to believe. For example, suppose that W = p(x, y) and we have an interpretation with domain D = {0, 1}. Then we have the following equivalences:

"x"y  p(x, y) º "y p(0, y)Ù p(1, y)º (p(0, 0)Ù p(0,1)) Ù (p(1, 0)Ù p(1, 1)) º

º (p(0, 0)Ù p(1,0)) Ù (p(0, 1)Ù p(1, 1)) º "x p(x, 0) Ù "x p(x, 1)  º"y"x p(x, y)

We also have the following equivalences:

$x$y  p(x, y) º $y p(0, y) Ú p(1, y)º (p(0, 0) Ú p(0,1)) Ú (p(1, 0) Ú p(1, 1)) º

º (p(0, 0) Ú p(1,0)) Ú (p(0, 1) Ú p(1, 1)) º $x p(x, 0) Ú $x p(x, 1)  º $y$x p(x, y)

We leave the proofs of equivalences (6.3) as exercises.

Next we'll look at some equivalences that hold under certain restrictions. We'll start with the simple idea of name replacement. With certain restrictions we can rename variables in a quantified wff without changing its meaning. For example, suppose we are given the wff

"x (p(x) ® p(w)).

We can replace all occurrences of x by y to obtain the equivalence

"x (p(x) ® p(w)) º "y (p(y) ® p(w)).

But we can't replace all occurrences of x by w because "x (p(x) ® p(w)) is not equivalent to"w (p(w) ® p(w)).