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.
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:
Notice how we get the ~(pq) column from the pq column: we reverse all its the truth values, since that is what negation means.
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:
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.)
Construct the truth table for ~(pq)(~r).
Here there are three variables: p, q and r. Thus we start with three initial columns showing all eight possibilities:
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 grows as you construct it:
and finally,
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.
(a) To demonstrate the logical equivalence of these two statements, we construct a truth table with columns for both p and ~(~p):
(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...
Example 5 Practice with Double NegationExample 6 One of De Morgan's Laws
SolutionWe again construct a truth table showing both ~(pq) and (~p)(~q).
Example 7P Practice with DeMorgan's LawsA 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
(b) (pq)[(~p)(~q)] Solution
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.
Before we go on...
"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
SolutionIts truth table is the following: Since there are all F's in the last column, we conclude that (pq)[(~p)(~q)] is a contradiction. Before We Go On ...
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
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.
Example 11 Simplifying Expressions
(b) ~([p(~q)]r) (c) p[~(~pq)] SolutionBy "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
(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:
(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.
Example 11P Practice with Simplifying
Example 12 Simplifying a Statement
SolutionThe 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:
Copyright © 1996 StefanWaner and Steven R. Costenoble |