![]() | 1. Statements and Logical Operators | ![]() | Section 2 Exercises | ![]() | 3. The Conditional and the Biconditional | ![]() | Main Logic Page | ![]() | "Real World" Page |
We have already hinted in the previous section that certain statements are equivalent; for example, we claimed that (pq)
r and p
(q
r) 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.
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 ~(p
q) column:
![]() | ![]() | ||
Notice how we get the ~(pq) column from the p
q column: we reverse all its the truth values, since that is what negation means.
Construct the truth table for p(p
q).
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:
![]() | ![]() ![]() | ||
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 p
q columns and "or" those together, according to the instructions for "or." Thus, for example, in the second row, we get T
F = T, and in the third row, we get F
F = 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 )
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:
We now add columns for pq, ~(p
q) and ~r, and finally ~(p
q)
(~r) according to the instructions for these logical operators. Here is how the table would grow as you construct it:
![]() | |||
![]() | ![]() | ||||
and finally,
![]() | ![]() | ![]() ![]() | ||||
Show that p~(~p). This is called double negation.
Solution
To demonstrate the logical equivalence of these two statements, we construct a truth table with columns for both p and ~(~p):
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.
Rewrite "It's not true that I'm not happy" in simpler form.
Solution
Let p: "I am happy," so that the given statement is ~(~p). 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.
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).
![]() | ![]() | ![]() | ||||
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."
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.
DeMorgan's Laws
If p and q are statements, then ~(p ~(p ![]() ![]() |
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.
Show that the statement p(~p) is a tautology.
Solution
We look at its truth table to check this:
![]() | ||
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.
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.
Show that (pq)
[(~p)
(~q)] is a tautology.
Solution
Its truth table is the following:
![]() | ![]() | ![]() ![]() ![]() | ||||
Again, since the last column contains only T's, the statement is a tautology.
Show that the statement (pq)
[(~p)
(~q)] is a contradiction.
Solution
Its 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 ...
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 p
q and (~p)
(~q) are true at the same time. (Can you see why this is so from the meaning of p
q?)
Before turning to the exercises, 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 below.) 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.
|
Simplify the statement ~([p(~q)]
r).
Solution
By "simplify" we mean "find a simpler equivalent statement." 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:
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)
(p
r). We can "factor out" the p using one of the distributive laws in reverse:
![]() | 1. Statements and Logical Operators | ![]() | Section 2 Exercises | ![]() | 3. The Conditional and the Biconditional | ![]() | Main Logic Page | ![]() | "Real World" Page |
![]() | Stefan Waner (matszw@hofstra.edu) | ![]() | Steven R. Costenoble (matsrc@hofstra.edu) |