# Introduction to Logic

## 2. Logical Equivalence, Tautologies, and Contradictions

We have already hinted in the previous section that certain statements are equivalent. For example, we claimed that (pq)r and p(qr) are equivalent — a fact we called the associative law for conjunction. In this section, we use truth tables to say precisely what we mean by logical equivalence, and we also study certain statements that are either "self-evident" ("tautological"), or "evidently false" ("contradictory").

We start with some more examples of truth tables of compound statements.

### Example 1 Constructing a Truth Table

Construct the truth table for ~(pq).

### Solution

Whenever we encounter a complex formula like this, we work from the inside out, just as we might do if we had to evaluate an algebraic expression, like -(a+b). Thus, we start with the p and q columns, then construct the pq column, and finally, the ~(pq) column:

 p q pq ~(pq) T T T F T F F T F T F T F F F T

Notice how we get the ~(pq) column from the pq column: we reverse all its the truth values, since that is what negation means.

### Example 2 Constructing a Truth Table

Construct the truth table for p(pq).

### Solution

Since there are two variables, p and q, we again start with the p and q columns. Working from inside the parentheses, we then evaluate pq, and finally take the disjunction of the result with p:

 p q pq p(pq) T T T T T F F T F T F F F F F F

### Before we go on...

How did we get the last column from the others? Since we are "or-ing" p with pq, we must look at the values in the p and pq columns and "or" those together, according to the instructions for "or." Thus, for example, in the second row, we get TF = T, and in the third row, we get FF = F. (If you look at the second row of the truth table for "or" you will see T | F | T, and in the last row you will see F | F | F )

### Example 2P Practice in Constructing a Truth Table

Construct the truth table for ~p(pq).

### Solution

As before, we start with with two initial columns showing the four possibilities for p and q.

 p q T T T F F T F F

Since the expression involves the negation, ~p, of p, we add a column for ~p. (Type "T" or "F" in each slot and press "Check". You can use the Tab key to get from cell to cell.)

 p q ~p T T T F F T F F

Since our expression, ~p(pq)., also involves pq, we also add a column for pq. Before filling in the values, notice that the truth values of this new column depend only on the columns for p and q (you can ignore the "~p" column for this step).

 p q ~p pq T T F T F F F T T F F T

We can now complete the truth table for the entire expression: ~p(pq) by taking the conjunction of the last two columns above:

 p q ~p pq ~p(pq) T T F T T F F T F T T T F F T F

This gives the completed truth table.

### Example 3 Three Variables

Construct the truth table for ~(pq)(~r).

### Solution

Here, there are three variables: p, q and r. Thus we start with three initial columns showing all eight possibilities:

 p q r T T T T T F T F T T F F F T T F T F F F T F F F

We now add columns for pq, ~(pq) and ~r, and finally ~(pq)(~r) according to the instructions for these logical operators. Here is how the table would grow as you construct it:

 p q r pq T T T T T T F T T F T F T F F F F T T F F T F F F F T F F F F F

 p q r pq ~(pq) ~r T T T T F F T T F T F T T F T F T F T F F F T T F T T F T F F T F F T T F F T F T F F F F F T T

and finally,

 p q r pq ~(pq) ~r ~(pq)(~r) T T T T F F F T T F T F T F T F T F T F F T F F F T T T F T T F T F F F T F F T T T F F T F T F F F F F F T T T

Now we say that two statements are logically equivalent if, for all possible truth values of the variables involved, both statements are true or both are false. If s and t are equivalent, we write s t. This is not another logical statement. It is simply the claim that the two statements s and t are equivalent. Here are some examples to explain what we mean.

### Example 4 Double Negation

(a) Show that p ~(~p). This is called double negation.
(b) Rewrite "It's not true that I'm not happy" in simpler form.

### Solution

(a) To demonstrate the logical equivalence of these two statements, we construct a truth table with columns for both p and ~(~p):

 Same values
 p ~p ~(~p) T F T F T F

The p column gives the two possible truth values for p, while the ~p column gives the corresponding values for its negation as before. We get the values in the ~(~p) column from those in the ~p column by reversing the truth values: if ~p is false, then its negation, ~(~p), must be true, and vice-versa. Since the p and ~(~p) columns now contain the same truth values in all rows ("for all possible truth values of the variables involved"), they are logically equivalent.

(b) Let p: "I am happy," so that the given statement is ~(~p). By part (a), this is equivalent to p, in other words, to the statement "I am happy."

### Before we go on...

Unlike French ("Ceci n'est pas une pipe") and colloquial English ("This ain't no pipe"), a double negative in logic always means a positive statement.

### Example 5 Practice with Double Negation

 (a) p: "It is not true that there is no life on Mars." is the same as: Select one "There is life on Mars." "There is no life on Mars." "There may be life on Mars." "There may not be life on Mars." "There is probably life on Mars." (b) p: "It is not true that no lacrosse players are tall." is the same as: Select one "No lacrosse players are short." "No lacrosse players are tall." "All lacrosse players are tall." "Some lacrosse players are tall." "Lacrosse players are not tall." (c) p: "It is not true that my computer has no new software." is the same as: Select one "My computer has no software." "My computer has all new software." "My computer has no software at all." "My computer has some old software." "My computer has some new software."

### Example 6 One of De Morgan's Laws

Show that ~(pq) (~p)(~q). This is one of DeMorgan's Laws.

### Solution

We again construct a truth table showing both ~(pq) and (~p)(~q).

 Same values
 p q pq ~(pq) ~p ~q (~p)(~q) T T T F F F F T F F T F T T F T F T T F T F F F T T T T

Since the ~(pq) column and (~p)(~q) column agree, we conclude that they are equivalent.

### Before we go on...

The statement ~(pq) can be read as "It is not the case that both p and q are true" or "p and q are not both true." We have just shown that this is equivalent to "Either p is false or q is false."

### Example 7 Applying DeMorgan's Law

Let p: "The President is a Democrat," and q: "The President is a Republican." Then ~(pq): "The President is not both a Democrat and a Republican." This is the same as saying: "Either the President is not a Democrat, or he is not a Republican, or he is neither," which is (~p)(~q).

### Before we go on...

This is not the same as "The President is a Republican or a Democrat," which would be qp.

Here are the two equivalences known as DeMorgan's Laws:

 DeMorgan's Laws If p and q are statements, then ~(pq) (~p)(~q) ~(pq) (~p)(~q) Mechanically speaking, this means that, when we distribute a negation sign, it reverses and , and the negation applies to both parts.

### Example 7P Practice with DeMorgan's Laws

 (a) p: "There is life on Mars." q: "There is life on Jupiter." ~(pq): Select one "There is no life on Mars or there is no life on Jupiter." "There is neither life on Mars nor on Jupiter." "There is no life on Mars or there is life on Jupiter." "There is life on at most one of Mars or Jupiter." "There is life on Mars or there is no life on Jupiter." (b) p: "No lacrosse players are short." q: "No soccer players are tall." ~(pq): Select one "All lacrosse players are short or all soccer players are tall." "All lacrosse players are short and all soccer players are tall." "Some lacrosse players are short and some soccer players are tall." "Some lacrosse players are short or some soccer players are tall." "Some lacrosse players are short and all soccer players are short." (c) p: "All is lost." q: "There is no hope." ~(p~q) Select one "All is not lost and there is hope." "All is not lost but there is no hope." "All is not lost or there is no hope." "All is not lost or there is hope." "All is lost but there is hope."

A compound statement is a tautology if its truth value is always T, regardless of the truth values of its variables. It is a contradiction if its truth value is always F, regardless of the truth values of its variables. Notice that these are properties of a single statement, while logical equivalence always relates two statements.

### Example 8 Tautologies

Show that the following are tautologies:
(a) p(~p).
(b) (pq)[(~p)(~q)]

### Solution

(a) We look at its truth table to check this:

 p ~p p(~p) T F T F T T

All T

Since there are only T's in the p(~p) column, we conclude that p(~p) is a tautology. We can think of this as saying that the truth value of the statement p(~p) is independent of the value of the "input" variable p.

(b) The given statement has the following truth table.

 p q ~p ~q pq ~(p)(~q) (pq) [ (~p)(~q) ] T T F F T F T T F F T T F T F T T F T F T F F T T F T T

All T

### Before we go on...

"You are sad," the Knight said in an anxious tone: "let me sing you a song to comfort you. . . Everybody that hears me sing it — either it brings the tears into their eyes, or else —"
"Or else what?" said Alice, for the Knight had made a sudden pause.
"Or else it doesn't, you know."

When a statment is a tautology, we also say that the statement is tautological. In common usage this sometimes means simply that the statement is convincing. We are using it for something stronger: the statement is always true, under all circimstances. In contrast, a contradiction, or contradictory statement, is never true, under any circumstances.

Show that the statement (pq)[(~p)(~q)] is a contradiction.

### Solution

Its truth table is the following:

 p q ~p ~q pq ~(p)(~q) (pq) [ (~p)(~q) ] T T F F T F F T F F T T F F F T T F T F F F F T T F T F

Since there are all F's in the last column, we conclude that (pq)[(~p)(~q)] is a contradiction.

### Before We Go On ...

In common usage we sometimes say that two statement are contradictory. By this we mean that their conjunction is a contradiction: they cannot both be true. For example, the statements pq and (~p)(~q) are contradictory, since we've just shown that their conjunction is a contradiction. In other words, no matter what the truth values of p and q, it is never true that both pq and (~p)(~q) are true at the same time. (Can you see why this is so from the meaning of pq?)

Note that most statements are neither tautologies nor contradictions, as in the first three examples in this section.

Sometimes we can "recognize" a tautology or contradiction immediately. Roughly speaking, tautologies are statements that are "obviously true" while contradictions are "obviously false".

### Example 10 Practice in Spotting Tautologies and Contradictions

Answer the following. If in doubt, use a truth table. (The truth tables for these examples appear in the exercises.)
 p(~p)   is a tautology a contradiction neither . p(~q)   is a tautology a contradiction neither . p(~q)   is a tautology a contradiction neither . [p(~p)] [q(~q)]   is a tautology a contradiction neither .

Before turning to the exercises for this section, we give a list of some important logical equivalences, most of which we have already encountered. (The verification of some of these appear as exercises.) We shall add to this list as we go along.

Important Logical Equivalences: First List

The following logical equivalences apply to any statements; the p's, q's and r' s can stand for atomic statements or compound statements.

 ~(~p) p the Double Negative Law pq qp the Commutative Law for conjunction pq qp the Commutative Law for disjunction (pq)r p(qr) the Associative Law for conjunction (pq)r p(qr) the Associative Law for disjunction ~(pq) (~p)(~q) DeMorgan's Laws ~(pq) (~p)(~q) p(qr) (pq)(pr) the Distributive Laws p(qr) (pq)(pr) pp p Absorption Laws pp p

### Example 11 Simplifying Expressions

Simplify the following statements
(a) p~(~q)
(b) ~([p(~q)]r)
(c) p[~(~pq)]

### Solution

By "simplify" we mean "find a simpler equivalent statement."

(a) We immediately recognize a double negation ~(~q). By the Double Negative Law, this is the same as q. Thus, the given expression can be written more simply as

pq.

(b) We can analyze this statement from the outside in. It is first of all a negation, but further it is the negation ~(AB), where A is (p(~q)) and B is r. To see this, look for the "principal connective," the last logical operator you would evaluate in forming the truth table. Now one of De Morgan's Laws is:

~(AB) (~A)(~B).
Applying this here gives:
~([p(~q)]r) (~[p(~q)])(~r).
We can apply DeMorgan's law again, this time to the statement ~(p(~q)). Doing this gives us:
~[p(~q)] (~p)~(~q) (~p)q.
Notice that we've also used the Double Negative law. Finally, this gives
~([p(~q)]r) (~[p(~q)])(~r) ((~p)q)(~r),
or just
(~p)q(~r),
since the Associative Law tells us that we can forget about which two expressions we "or" first.

(c) The expression ~(~pq) on the right is a negation of the form ~(AB) where A is ~p and B is q. Let us start with that.

 ~(~pq) ~(~p)(~q) De Morgan p(~q) Double Negative
We can now complete the simplification of the entire given statement:
 p[~(~pq)] p[p(~q)] From above [pp](~q) Associateive Law p(~q) Absorption Law

### Example 11P Practice with Simplifying

For each of the given statements, supply a simpler equivalent statement. To enter them, use "AND" for and "OR" for . For instance, you could enter
(pq)(~r)
as
(p OR q) AND ~r
or
(p OR q) AND (~r)
 (a) ~(~(~p)) (b) p(~qp) (c) p(qp)

### Example 12 Simplifying a Statement

Consider: "You will get an A if either you are clever and the sun shines, or you are clever and it rains." Rephrase the condition more simply.

### Solution

The condition is "you are clever and the sun shines, or you are clever and it rains." Let's analyze this symbolically: Let p: "you are clever," q: "The sun shines," and r: "It rains." The condition is then (pq)(pr). We can "factor out" the p using one of the distributive laws in reverse:

(pq)(pr) p(qr).
Notice that the logical equivalences we listed can be read from right to left as well as from left to right. Putting p(qr) back into English, we can rephrase the given sentence as "You will get an A if you are clever and either the sun shines or it rains."

Last Updated: September, 2001