8
Formal Logic
This tree structure also tells us how to enumerate all the T–F combinations among the n statement letters when setting up a truth table. If
we read each level of the tree from bottom to top, it says that the T–F
values for statement letter n (which will compose the last column of the
truth table) alternate, those for statement letter n − 1 alternate every
two values, those for statement letter n − 2 alternate every four values,
and so forth. Thus a truth table for three statement letters would begin
as shown in Table 1.8. The values for statement letter C alternate, those
for statement letter B alternate in groups of two, and those for statement letter A alternate in groups of four, resulting in something like a
sideways version of the tree. (Reading the rows from the bottom up and
using 1 for T and 0 for F shows that we are simply counting up from zero
in binary numbers.)
tAbLe 1.8
A
B
C
T
T
T
T
T
F
T
F
T
T
F
F
F
T
T
F
T
F
F
F
T
F
F
F
pRaCtiCe 7 Construct truth tables for the following wffs.
a. (A S B) 4 (B S A) (Remember that C 4 D is true precisely when C and D have the same
truth value.)
b. (A ~ A′) S (B ` B′)
c. [(A ` B′) S C′]′
d. (A S B) 4 (B′S A′)
Tautologies
A wff-like item (d) of Practice 7, whose truth values are always true, is called a
tautology. A tautology is “intrinsically true” by its very structure; it is true no
matter what truth values are assigned to its statement letters. A simpler example
of a tautology is A ~ A′; consider, for example, the statement “Today the sun will
shine or today the sun will not shine,” which must always be true because one
or the other of these must happen. A wff like item (b) of Practice 7, whose truth
values are always false, is called a contradiction. A contradiction is “intrinsically
false” by its very structure. A simpler example of a contradiction is A ` A′; consider “Today is Tuesday and today is not Tuesday,” which is false no matter what
day of the week it is.
Suppose that P and Q represent two wffs, and it happens that the wff
P 4 Q is a tautology. If we did a truth table using the statement letters in P
and Q, then the truth values of the wffs P and Q would agree for every row of
the truth table. In this case, P and Q are said to be equivalent wffs, denoted by
P 3 Q. Thus P 3 Q states a fact, namely, that the particular wff P 4 Q is a
tautology. Practice 7(d) has the form P 4 Q , where P is the wff (A S B) and
Q is the wff (B′ S A′), and P 4 Q was shown to be a tautology. Therefore,
(A S B) 3 (B′ S A′).
We will list some basic equivalences, prove one or two of them by constructing truth tables, and leave the rest as exercises. We represent any contradiction by
0 and any tautology by 1.
ReMIndeR
A, B, C stand for single
statement letters; P, Q,
R, S stand for wffs.
Formal Logic
This tree structure also tells us how to enumerate all the T–F combinations among the n statement letters when setting up a truth table. If
we read each level of the tree from bottom to top, it says that the T–F
values for statement letter n (which will compose the last column of the
truth table) alternate, those for statement letter n − 1 alternate every
two values, those for statement letter n − 2 alternate every four values,
and so forth. Thus a truth table for three statement letters would begin
as shown in Table 1.8. The values for statement letter C alternate, those
for statement letter B alternate in groups of two, and those for statement letter A alternate in groups of four, resulting in something like a
sideways version of the tree. (Reading the rows from the bottom up and
using 1 for T and 0 for F shows that we are simply counting up from zero
in binary numbers.)
tAbLe 1.8
A
B
C
T
T
T
T
T
F
T
F
T
T
F
F
F
T
T
F
T
F
F
F
T
F
F
F
pRaCtiCe 7 Construct truth tables for the following wffs.
a. (A S B) 4 (B S A) (Remember that C 4 D is true precisely when C and D have the same
truth value.)
b. (A ~ A′) S (B ` B′)
c. [(A ` B′) S C′]′
d. (A S B) 4 (B′S A′)
Tautologies
A wff-like item (d) of Practice 7, whose truth values are always true, is called a
tautology. A tautology is “intrinsically true” by its very structure; it is true no
matter what truth values are assigned to its statement letters. A simpler example
of a tautology is A ~ A′; consider, for example, the statement “Today the sun will
shine or today the sun will not shine,” which must always be true because one
or the other of these must happen. A wff like item (b) of Practice 7, whose truth
values are always false, is called a contradiction. A contradiction is “intrinsically
false” by its very structure. A simpler example of a contradiction is A ` A′; consider “Today is Tuesday and today is not Tuesday,” which is false no matter what
day of the week it is.
Suppose that P and Q represent two wffs, and it happens that the wff
P 4 Q is a tautology. If we did a truth table using the statement letters in P
and Q, then the truth values of the wffs P and Q would agree for every row of
the truth table. In this case, P and Q are said to be equivalent wffs, denoted by
P 3 Q. Thus P 3 Q states a fact, namely, that the particular wff P 4 Q is a
tautology. Practice 7(d) has the form P 4 Q , where P is the wff (A S B) and
Q is the wff (B′ S A′), and P 4 Q was shown to be a tautology. Therefore,
(A S B) 3 (B′ S A′).
We will list some basic equivalences, prove one or two of them by constructing truth tables, and leave the rest as exercises. We represent any contradiction by
0 and any tautology by 1.
ReMIndeR
A, B, C stand for single
statement letters; P, Q,
R, S stand for wffs.