Copyright © Cengage Learning. All rights reserved.
1
Logic
1
Copyright © Cengage Learning. All rights reserved.
1.3
Truth Tables
2
Objectives
3
Truth Tables
The truth value of a statement is the classification of the statement as true or false and is denoted by T or F.
For example, the truth value of the statement “Santa Fe is the capital of New Mexico” is T. (The statement is true.)
In contrast, the truth value of “Memphis is the capital of Tennessee” is F. (The statement is false.)
4
Truth Tables
A convenient way of determining whether a compound statement is true or false is to construct a truth table.
A truth table is a listing of all possible combinations of the individual statements as true or false, along with the resulting truth value of the compound statement.
As we will see, truth tables also allow us to distinguish valid arguments from invalid arguments.
5
The Negation ~p
6
The Negation ~p
The negation of a statement is the denial, or opposite, of the statement. (As was stated earlier, because the truth value of the negation depends on the truth value of the original statement, a negation can be classified as a compound statement.)��To construct the truth table for the negation of a statement, we must first examine the original statement. A statement p may be true or false, as shown in Figure 1.33.
Figure 1.33
Truth values for a statement p.
7
The Negation ~p
If the statement p is true, the negation ~p is false; if p is false, ~p is true. The truth table for the compound statement ~p is given in Figure 1.34.
Row 1 of the table is read “~p is false when p is true.”
Row 2 is read “~p is true when p is false.”
Figure 1.34
Truth table for a negation ~ p.
8
The Conjunction p q
9
The Conjunction p q
A conjunction is the joining of two statements with the word and.
The compound statement “Maria is a doctor and a Republican” is a conjunction with the following symbolic representation:
p: Maria is a doctor.
q: Maria is a Republican.
p q: Maria is a doctor and a Republican.
10
The Conjunction p q
The truth value of a compound statement depends on the truth values of the individual statements that make it up. How many rows will the truth table for the conjunction �p q contain?
Because p has two possible truth�values (T or F) and q has two �possible truth values (T or F), we �need four (2 ● 2) rows in order to �list all possible combinations of �Ts and Fs, as shown in Figure 1.35.
Figure 1.35
Truth values for two statements.
11
The Conjunction p q
For the conjunction p q to be true, the components�p and q must both be true; the conjunction is false otherwise. The completed truth table for the conjunction�p q is given in Figure 1.36.
Figure 1.36
Truth table for a conjunction p q.
12
The Conjunction p q
The symbols p and q can be replaced by any statements.�The table gives the truth value of the statement “p and q,” dependent upon the truth values of the individual statements “p” and “q.”
For instance, row 3 is read “The conjunction p q is false when p is false and q is true.” The other rows are read in a similar manner.
13
The Disjunction p q
14
The Disjunction p q
A disjunction is the joining of two statements with the word or. The compound statement “Maria is a doctor or a Republican” is a disjunction (the inclusive or) with the following symbolic representation:
p: Maria is a doctor.
q: Maria is a Republican.
p q: Maria is a doctor or a Republican.
Even though your friend Maria the doctor is not a Republican, the disjunction “Maria is a doctor or a Republican” is true. For a disjunction to be true, at least one of the components must be true.
15
The Disjunction p q
A disjunction is false only when both components are false. The truth table for the disjunction p q is given in �Figure 1.37.
Figure 1.37
Truth table for a disjunction p q.
16
Example 1 – Constructing a Truth Table
Under what specific conditions is the following compound statement true? “I have a high school diploma, or I have a�full-time job and no high school diploma.”
Solution:
First, we translate the statement into symbolic form, and then we construct the truth table for the symbolic expression.
Define p and q as
p: I have a high school diploma.
q: I have a full-time job.
17
Example 1 – Solution
The given statement has the symbolic representation
p (q ~p).
Because there are two letters, we need 2 ● 2 = 4 rows. We need to insert a column for each connective in the symbolic expression p (q ~p).
As in algebra, we start inside any grouping symbols and work our way out.
cont’d
18
Example 1 – Solution
Therefore, we need a column for ~p, a column for q ~p, and a column for the entire expression �p (q ~p), as shown in Figure 1.38.
cont’d
Figure 1.38
Required columns in the truth table.
19
Example 1 – Solution
In the ~p column, fill in truth values that are opposite those for p. Next, the conjunction q ~p is true only when both components are true; enter a T in row 3 and Fs elsewhere.�
Finally, the disjunction p (q ~p) is false only when both�components p and (q ~p) are false; enter an F in row 4�and Ts elsewhere.
cont’d
20
Example 1 – Solution
The completed truth table is shown in Figure 1.39.
cont’d
Figure 1.39
Truth table for p (q ~p).
21
Example 1 – Solution
As is indicated in the truth table, the symbolic expression�p (q ~p) is true under all conditions except one: row 4; the expression is false when both p and q are false.
Therefore, the statement “I have a high school diploma, or I have a fulltime job and no high school diploma” is true in every case except when the speaker has no high school diploma and no full-time job.
cont’d
22
The Disjunction p q
If the symbolic representation of a compound statement consists of two different letters, its truth table will have�2 ● 2 = 4 rows. How many rows are required if a compound statement consists of three letters—say, p, q, and r?
Because each statement has two possible truth values�(T and F), the truth table must contain 2 ● 2 ● 2 = 8 rows. In general, each time a new statement is added, the number of rows doubles.
23
The Conditional p → q
24
The Conditional p → q
A conditional is a compound statement of the form�“If p, then q” and is symbolized p → q. Under what circumstances is a conditional true, and when is it false?�
Consider the following (compound) statement: “If you give me $50, then I will give you a ticket to the ballet.” This statement is a conditional and has the following�representation:
p: You give me $50.�q: I give you a ticket to the ballet.�p → q: If you give me $50, then I will give you a ticket to the ballet.
25
The Conditional p → q
The conditional can be viewed as a promise: If you give me $50, then I will give you a ticket to the ballet. Suppose you give me $50; that is, suppose p is true.
I have two options: Either I give you a ticket to the ballet�(q is true), or I do not (q is false). If I do give you the ticket, the conditional p → q is true (I have kept my promise);�if I do not give you the ticket, the conditional p → q is false (I have not kept my promise).
26
The Conditional p → q
These situations are shown in rows 1 and 2 of the truth table in Figure 1.44. Rows 3 and 4 require further analysis.
Figure 1.44
What if p is false?
27
The Conditional p → q
Suppose you do not give me $50; that is, suppose p is false. Whether or not I give you a ticket, you cannot say that I broke my promise; that is, you cannot say that the conditional p → q is false. �
Consequently, since a statement is either true or false, the conditional is labeled true (by default). In other words, when the antecedent p of a conditional is false, it does not matter whether the consequent q is true or false.�
In both cases, the conditional p → q is automatically labeled true, because it is not false.
28
The Conditional p → q
The completed truth table for a conditional is given in Figure 1.45. Notice that the only circumstance under which a conditional is false is when the antecedent p is true and the consequent q is false, as shown in row 2.
Figure 1.45
Truth table for p → q.
29
Example 3 – Constructing a Truth Table
Under what conditions is the symbolic expression q → ~p true?
Solution:
Our truth table has 22 = 4 rows and contains a column for p, q, ~p, and q → ~p, as shown in Figure 1.46.
�In the ~p column, fill in truth�values that are opposite �those for p.
Figure 1.46
Required columns in the truth table.
30
Example 3 – Solution
Now, a conditional is false only when its antecedent (in this case, q) is true and its consequent (in this case, ~p) is false.
Therefore, q → ~p is false only in row 1; the conditional q → ~p is true under all conditions except the condition that both p and q are true.�
The completed truth table�is shown in Figure 1.47.
Figure 1.47
Truth table for q → ~p.
cont’d
31
Equivalent Expressions
32
Equivalent Expressions
When you purchase a car, the car is either new or used. If a salesperson told you, “It is not the case that the car is not new,” what condition would the car be in? ��This compound statement consists of one individual statement (“p: The car is new”) and two negations:
33
Equivalent Expressions
Does this mean that the car is new? To answer this question, we will construct a truth table for the symbolic expression ~(~p) and compare its truth values with those of the original p.
Because there is only one letter, we need 21 = 2 rows, as shown in Figure 1.51.
Figure 1.51
Truth values of p.
34
Equivalent Expressions
We must insert a column for ~p and a column for ~(~p). Now, ~p has truth values that are opposite those of p, and ~(~p) has truth values that are opposite those of ~p,�as shown in Figure 1.52.
Figure 1.52
Truth table for ~(~p).
35
Equivalent Expressions
Notice that the values in the column labeled ~(~p) are identical to those in the column labeled p.��Whenever this happens, the expressions are said to be equivalent and may be used interchangeably.��Therefore, the statement “It is not the case that the car is not new” is equivalent in meaning to the statement “The car is new.”
36
Equivalent Expressions
Equivalent expressions are symbolic expressions that have identical truth values in each corresponding entry. ��The expression p ≡ q is read “p is equivalent to q” or�“p and q are equivalent.”��As we can see in Figure 1.52,�an expression and its double �negation are logically equivalent.�This relationship can be expressed�as p ≡ ~(~p).
Figure 1.52
Truth table for ~(~p).
37
Example 5 – Determining whether Statements are Equivalent
Are the statements “If I am a homeowner, then I pay property taxes” and “I am a homeowner, and I do not pay property taxes” equivalent?
Solution:
We begin by defining the statements:
p: I am a homeowner.
q: I pay property taxes.
p → q: If I am a homeowner, then I pay property taxes.
p ~q: I am a homeowner, and I do not pay property taxes.
38
Example 5 – Solution
The truth table contains 22 = 4 rows, and the initial setup is shown in Figure 1.53.
Figure 1.53
Required columns in the truth table.
cont’d
39
Example 5 – Solution
Now enter the appropriate truth values under ~q�(the opposite of q). Because the conjunction p ~q is true only when both p and ~q are true, enter a T in row 2 and Fs elsewhere.
The conditional p → q is false only when p is true and q is false; therefore, enter an F in row 2 and Ts elsewhere.
The completed truth table�is shown in Figure 1.54.
Figure 1.54
Truth table for p → q.
cont’d
40
Example 5 – Solution
Because the entries in the columns labeled p ~q and �p → q are not the same, the statements are not equivalent.�
“If I am a homeowner, then I pay property taxes” is not equivalent to “I am a homeowner and I do not pay property�taxes.”
cont’d
41
Equivalent Expressions
Notice that the truth values in the columns under p ~ q and p → q in Figure 1.54 are exact opposites; when one �is T, the other is F.
Whenever this happens, one statement is the negation of the other. Consequently, p ~q is the negation of p → q (and vice versa).
This can be expressed as � The �negation of a conditional is �logically equivalent to the �conjunction of the antecedent �and the negation of the consequent.
Figure 1.54
Truth table for p → q.
42
De Morgan’s Laws
43
De Morgan’s Laws
Earlier in this section, we saw that the negation of a negation is equivalent to the original statement; that is,�~(~p) ≡ p. ��Another negation “formula” that we discovered was�~(p → q) ≡ p ~q, that is, the negation of a conditional. �Can we find similar “formulas” for the negations of the other basic connectives, namely, the conjunction and the disjunction?��The answer is yes, and the results are credited to the English mathematician and logician Augustus De Morgan.
44
De Morgan’s Laws
45
Example 6 – Applying De Morgan’s Laws
Using De Morgan’s Laws, find the negation of each of the following:
a. It is Friday and I receive a paycheck.
b. You are correct or I am crazy.
46
Example 6(a) – Solution
The symbolic representation of “It is Friday and I receive a paycheck” is
p: It is Friday.
q: I receive a paycheck.
p q: It is Friday and I receive a paycheck.
Therefore, the negation is
~(p q) ≡ ~ p ~q,
that is, “It is not Friday or I do not receive a paycheck.”
47
Example 6(b) – Solution
The symbolic representation of “You are correct or I am crazy” is
p: You are correct.
q: I am crazy.
p q: You are correct or I am crazy.
Therefore, the negation is
~(p q) ≡ ~p ~q,
that is, “You are not correct and I am not crazy.”
cont’d
48