Section 1.4 Predicate Logic
65
The proofs of Example 32 are rather difficult because they require considerably more imagination than most and an unexpected use of a temporary
pRaCtiCe 25 Prove the argument
(4x)[(B(x) ~ C(x)) S A(x)] S (4x)[B(x) S A(x)]
In Section 1.3 we observed that, based on our understanding of negation and
the meaning of the quantifiers, [(E x)A(x)]′ is equivalent to (4x)[A(x)]′. We should
be able to formally prove that
[(E x)A(x)]′ 4 (4x)[A(x)]′
is a valid wff.
eXAMPLe 32
Prove that
[(E x)A(x)]′ 4 (4x)[A(x)]′
is valid. We must prove the implication in each direction.
a. [(E x)A(x)]′ 4 (4x)[A(x)]′
The hypothesis alone gives us little to work with, so we introduce a (somewhat
surprising) temporary hypothesis. A proof sequence is
1. [(E x)A(x)]′
hyp
2. A(x)
temporary hyp
3. (E x)A(x)
2, eg
4. A(x) S (E x)A(x) temporary hyp discharged
5. [A(x)]′
1, 4, mt
6. (4x)[A(x)]′
5, ug
b. (4x)[A(x)]′ S [(E x)A(x)]′
This proof also requires a temporary hypothesis. It is even more surprising than
case (a) because we assume the exact opposite of the conclusion we are trying to
reach.
1. (4x)[A(x)]′
hyp
2. (E x)A(x)
temporary hyp
3. A(a)
2, ei
4. [A(a)]′
1, ui
5. [(4x)[A(x)]′]′
3, 4, inc
6. (E x)A(x) S [(4x)[A(x)]′]′ temporary hyp discharged
7. [((4x)[A(x)]′)′]′
1, dn
8. [(E x)A(x)]′
6, 7, mt