Introduction to Logic

by
Stefan Waner and Steven R. Costenoble

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

Solution

Example 2 Constructing a Truth Table

Solution

Before we go on...

Example 2P Practice in Constructing a Truth Table

Solution

Example 3 Three Variables

Solution

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

Solution

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:     
    (b) p: "It is not true that no lacrosse players are tall." is the same as:     
    (c) p: "It is not true that my computer has no new software." is the same as:     

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):
    (b) p: "No lacrosse players are short."
    q: "No soccer players are tall."    		 ~(pq):
    (c) p: "All is lost."
    q: "There is no hope."    		 ~(p~q)

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.

Example 9 Contradiction

    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) pthe Double Negative Law
pq qpthe Commutative Law for conjunction
pq qpthe 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
Copyright © 1996 StefanWaner and Steven R. Costenoble

Top of Page