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)).