10
Formal Logic
Each is the dual of the other. De Morgan’s laws help in expressing the negation of
a compound statement, as in Practice 6.
Think of these tautological equivalences as patterns; in order to use one
of them, you must match its pattern exactly. For example, you can’t say that
(A ` B) ~ C 3 A ` (B ~ C ) by either of the associative properties because neither of these properties uses both conjunction and disjunction.
Suppose that P and Q are equivalent wffs. Then in any wff where P appears, P
can be replaced by Q with no change in the overall truth values. It’s like replacing
a $20 bill in your wallet with two $10 bills—the total value of your money hasn’t
changed.
tHeoReM De Morgan’s Laws
(A ~ B)′ 3 A′ ` B′
and
(A ` B)′ 3 A′ ~ B′
Logical Connectives in the real world
Web search engines allow exploration of the vast resources available on the Web,
but a little care in your search query can help focus the results more quickly. For
example, if you enter
used cars
in a Web search engine, you may get back references to any Web site containing
either the word used or the word cars; this could include sites for antique dealers
and sites for the latest auto racing results. Entering the phrase
“used cars”
in quotes restricts the search, on most search engines, to Web sites containing this
exact phrase. Most search engines also allow you to enter an expression using logical connectives as your search query, which can help make the query even more
specific. To further narrow your used car search, for example, you could enter
eXAMPLe 6
From Practice 7(d), A S B is equivalent to B′ S A′. The wff (A S B) S B should
therefore be equivalent to (B′ S A′) S B. This equivalence is verified by Tables
1.10a and 1.10b.
A
B A′ B′ B′ S A′ (B′ S A′) S B
T
T
F
F
T
T
T
F
F
T
F
T
F
T
T
F
T
T
F
F
T
T
T
F
A B A S B (A S B) S B)
T T
T
T
T F
F
T
F T
T
T
F F
T
F
(a)
(b)
tAbLe 1.10
Formal Logic
Each is the dual of the other. De Morgan’s laws help in expressing the negation of
a compound statement, as in Practice 6.
Think of these tautological equivalences as patterns; in order to use one
of them, you must match its pattern exactly. For example, you can’t say that
(A ` B) ~ C 3 A ` (B ~ C ) by either of the associative properties because neither of these properties uses both conjunction and disjunction.
Suppose that P and Q are equivalent wffs. Then in any wff where P appears, P
can be replaced by Q with no change in the overall truth values. It’s like replacing
a $20 bill in your wallet with two $10 bills—the total value of your money hasn’t
changed.
tHeoReM De Morgan’s Laws
(A ~ B)′ 3 A′ ` B′
and
(A ` B)′ 3 A′ ~ B′
Logical Connectives in the real world
Web search engines allow exploration of the vast resources available on the Web,
but a little care in your search query can help focus the results more quickly. For
example, if you enter
used cars
in a Web search engine, you may get back references to any Web site containing
either the word used or the word cars; this could include sites for antique dealers
and sites for the latest auto racing results. Entering the phrase
“used cars”
in quotes restricts the search, on most search engines, to Web sites containing this
exact phrase. Most search engines also allow you to enter an expression using logical connectives as your search query, which can help make the query even more
specific. To further narrow your used car search, for example, you could enter
eXAMPLe 6
From Practice 7(d), A S B is equivalent to B′ S A′. The wff (A S B) S B should
therefore be equivalent to (B′ S A′) S B. This equivalence is verified by Tables
1.10a and 1.10b.
A
B A′ B′ B′ S A′ (B′ S A′) S B
T
T
F
F
T
T
T
F
F
T
F
T
F
T
T
F
T
T
F
F
T
T
T
F
A B A S B (A S B) S B)
T T
T
T
T F
F
T
F T
T
T
F F
T
F
(a)
(b)
tAbLe 1.10