Equivalences

 

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.