Section 1.1 Statements, Symbolic Representation, and Tautologies
9
Some Tautological Equivalences
1a. A ~ B 3 B ~ A
1b. A ` B 3 B ` A
(commutative properties)
2a. (A ~ B) ~ C 3 A ~ (B ~ C )
2b. (A ` B) ` C 3 A ` (B ` C )
(associative properties)
3a. A ~ (B ` C ) 3
3b. A ` (B ~ C ) 3
(distributive properties)
(A ~ B) ` (A ~ C )
(A ` B) ~ (A ` C )
4a. A ~ 0 3 A
4b. A ` 1 3 A
(identity properties)
5a. A ~ A′ 3 1
5b. A ` A′ 3 0
(complement properties)
Note that 2a allows us to write A ~ B ~ C with no need for parentheses because
the grouping doesn’t matter; similarly, 2b allows us to write A ` B ` C.
eXAMPLe 5
The truth table in Table 1.9a verifies equivalence 1a, the commutative property for
disjunction, and that in Table 1.9b verifies 4b, the identity property for conjunction. Note that only two rows are needed for Table 1.9b because 1 (a tautology)
cannot take on false truth values.
The equivalences in the list are grouped into five pairs. In each pair, one
equivalence can be obtained from the other by replacing ` with ~ , ~ with `, 0
with 1, or 1 with 0. Each equivalence in a pair is called the dual of the other. Thus,
1a and 1b (commutativity of disjunction and commutativity of conjunction) are
duals of each other. This list of equivalences appears in a more general setting in
Chapter 8.
Two additional equivalences that are very useful are De Morgan’s laws,
named for the nineteenth-century British mathematician Augustus De Morgan,
who first stated them. This theorem is easy to prove (see Exercises 26e and 26f).
A
1
A ` 1
A ` 1 4 A
T
T
T
T
F
T
F
T
tAbLe 1.9
A
B
A ~ B
B ~ A
A ~ B 4 B ~ A
T
T
T
T
T
T
F
T
T
T
F
T
T
T
T
F
F
F
F
T
(a)
(b)
pRaCtiCe 8 Verify equivalence 5a.