Section 1.1 Statements, Symbolic Representation, and Tautologies
7
tAbLe 1.7
A
B
B′
A ~ B′
A ~ B
( A ~ B)′ A ~ B′ S ( A ~ B)′
T
T
F
T
T
F
F
T
F
T
T
T
F
F
F
T
F
F
T
F
T
F
F
T
T
F
T
T
If we are making a truth table for a wff that contains n different statement
letters, how many rows will the truth table have? From truth tables done so far,
we know that a wff with only one statement letter has two rows in its truth table,
and a wff with two statement letters has four rows. The number of rows equals the
number of true-false combinations possible among the statement letters. The first
statement letter has two possibilities, T and F. For each of these possibilities, the
second statement letter has two possible values. Figure 1.1a pictures this as a twolevel “tree” with four branches showing the four possible combinations of T and F
for two statement letters. For n statement letters, we extend the tree to n levels, as
in Figure 1.1b. The total number of branches then equals 2
n
. The total number of
rows in a truth table for n statement letters is also 2
n
.
eXAMPLe 4
The truth table for the wff A ~ B′ S (A ~ B)′ is given in Table 1.7. The main connective, according to the rules of precedence, is implication.
T
F
T
F
T
F
F
F
T
F
T
T
T
F
Statement letters
1
2
Choices
2 = 2 1 branches
4 = 2 2 branches
(a)
T
F
T
F
T
F
T
F
T
F
T
F
T
F
Statement letters
1
2
Choices
2 = 2 1 branches
4 = 2 2 branches
3
…
…
…
8 = 2 3 branches
n
2 n branches
(b)
Figure 1.1