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:
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 Negation
Example 6 One of De Morgan's Laws
We again construct a truth table showing both ~(pq) and (~p)(~q).