66
Formal Logic
hypothesis. As a result, however, we do have the following equivalence, to which
we’ve given a name:
[(E x)A(x)]′ 4 (4x)[A(x)]′ (Negation—neg)
This equivalence might be useful in a proof sequence. As an extension of the
equivalence rules, whenever P 4 Q is valid, Q can be substituted for P within an
expression in a proof sequence.
eXAMPLe 34
Is the wff
(E x)P(x) ` (E x)Q(x) S (E x)[P(x) ` Q(x)]
a valid argument? Prove or disprove.
If something in a domain has property P and something has property Q, that
does not mean that some one thing has both property P and Q. For example, in the
domain of integers, if P(x) means “x is even” and Q(x) means “x is odd,” then the
hypotheses are true, but the conclusion is false because there is no single integer
that is both even and odd. One interpretation in which the wff is false is enough to
disprove it.
eXAMPLe 33
Is the wff
(4x)[P(x) ~ Q(x)] S (E x)P(x) ~ (4x)Q(x)
a valid argument? Prove or disprove.
Let’s first consider whether the wff seems valid. If so, we should try to find a
proof sequence for it; if not, we should try to find an interpretation in which it is
not true. This wff says that if every element of the domain has either property P
or property Q, then at least one element must have property P or else all elements
have property Q. This seems very reasonable, so we’ll try to find a proof.
First we’ll use an equivalence to rewrite the conclusion in a more useful form.
Changing the ~ to an implication will allow use of the deduction method. Thus we
want to prove
(4x)[P(x) ~ Q(x)] S [ [(E x)P(x)]′ S (4x)Q(x)]
A proof sequence is
1. (4x)[P(x) ~ Q(x)] hyp
2. [(E x)P(x)]′
hyp
3. (4x)[P(x)]′
2, neg
4. [P(x)]′
3, ui
5. P(x) ~ Q(x)
1, ui
6. Q(x)
4, 5, ds
7. (4x)Q(x)
6, ug