Some wffs have the same meaning even though their expressions are
different. For example, the wffs
and
have the same meaning
because they have the same truth tables. Two wffs
are said to be equivalent if they
have the same meaning. In other words, two wffs are
equivalent if their truth tables have the same values. If A and B are equivalent wffs, we denote this fact by writing
.
For example, we can
write
. The definition of equivalence also allows us to make the
following formulation in terms of conditionals:
if
and only if
is a tautology.
Before we go much
further, let's list a few easy equivalences. See Table 23.1. All these
equivalences are easily verified by truth tables, so we'll leave them as
exercises. Can we do anything with these equivalences? Sure. We can use them to
show that other wffs are equivalent without checking
truth tables. But first we need to observe two general properties of
equivalence.
This property
allows us to write a sequence of equivalences and then conclude that the first wff is equivalent to the last wff,
just the way we do it with ordinary equality of algebraic expressions.
The next thing to
observe is the replacement rule of equivalences, which can be stated as follows:
Any subwff of a wff can be replaced by an equivalent wff
without changing the truth value of the original wff.
It's just like the
old phrase "Substituting equals for equals doesn't change the value of an
expression." Can you see why this is OK for equivalences?
For example,
suppose we want to simplify the wff
. We might notice that one of the laws from (5.2) gives
. Therefore we can apply the replacement rule and write the
following equivalence:
.
Let's do an example
to illustrate the process of showing that two wffs
are equivalent without checking truth tables.
Table 5.2 Some basic equivalences (5.2)
|
Negation |
Disjunction |
Conjunction |
Implication |
|
|
|
|
|
|
Some conversions |
Absorption laws |
||
|
Ú and Ù are associative Ú and Ù are commutative Ú and Ù distribute over
each other:
|
|
||
EXAMPLE. The following
equivalence shows an interesting relationship involving the connective
®:
.
We'll prove it
using equivalences that we already know. Make sure you can give the reason for
each line of the proof.
Proof:
This example illustrates that we can use known equivalences
like (5.2) as rules to transform wffs into other wffs having the same meaning. This justifies the word
"calculus" in the name "propositional calculus".
Now let's look at
another application of equivalences to finding the truth value of a
proposition.