<<

. 40
( 107 .)



>>

6. When you are done, save your proof as Proof Conditional 3.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Congratulations

Exercises


8.17 If you skipped any of the You try it sections, go back and do them now. Submit the ¬les
‚ Proof Conditional 1, Proof Conditional 2, and Proof Conditional 3.

In the following exercises we return to the patterns of inference discussed in Exercise 8.1. Some of
these are valid, some invalid. For each valid pattern, construct a formal proof in Fitch. For each invalid
pattern, give a counterexample using Tarski™s World. To give a counterexample in these cases, you will
have to come up with sentences of the blocks language that ¬t the pattern, and a world that makes
those speci¬c premises true and the conclusion false. Submit both the world and the sentence ¬le. In the
sentence ¬le, list the premises ¬rst and the conclusion last.

8.18 8.19
A¬rming the Consequent: Modus Tollens:
‚ ‚
From A ’ B and B, infer A. From A ’ B and ¬B, infer ¬A.

8.20 8.21
Strengthening the Antecedent: Weakening the Antecedent:
‚ ‚
From B ’ C, infer (A § B) ’ C. From B ’ C, infer (A ∨ B) ’ C.

8.22 8.23
Strengthening the Consequent: Weakening the Consequent:
‚ ‚
From A ’ B, infer A ’ (B § C). From A ’ B, infer A ’ (B ∨ C).

8.24 8.25
Constructive Dilemma: Transitivity of the Biconditional:
‚ ‚
From A ∨ B, A ’ C, and B ’ D, From A ” B and B ” C,
infer C ∨ D. infer A ” C.
Use Fitch to construct formal proofs for the following arguments. In two cases, you may ¬nd yourself
re-proving an instance of the law of Excluded Middle, P ∨ ¬P, in order to complete your proof. If you™ve
forgotten how to do that, look back at your solution to Exercise 6.33. Alternatively, with the permission
of your instructor, you may use Taut Con to justify an instance of Excluded Middle.

8.26 8.27
‚ ‚
P ’ (Q ’ P) (P ’ (Q ’ R)) ” ((P § Q) ’ R)

8.28 8.29
P ” ¬P
‚ ‚
⊥ (P ’ Q) ” (¬P ∨ Q)




Chapter 8
Formal rules of proof for ’ and ” / 213



8.30

¬(P ’ Q) ” (P § ¬Q)

The following arguments are translations of those given in Exercises 8.3“8.9. (For simplicity we have
assumed “the unicorn” refers to a speci¬c unicorn named Charlie. This is less than ideal, but the best we
can do without quanti¬ers.) Use Fitch to formalize the proofs you gave of their validity. You will need
to use Ana Con to introduce ⊥ in two of your proofs.

8.31 8.32
(¬Mythical(c) ’ Mammal(c)) Horned(c) ’ (Elusive(c)
‚ ‚
§ (Mythical(c) ’ ¬Mortal(c)) § Dangerous(c))
(¬Mortal(c) ∨ Mammal(c)) ’ Horned(c) (Elusive(c) ∨ Mythical(c)) ’ Rare(c)
Horned(c) ’ Magical(c) Mammal(c) ’ ¬Rare(c)
Magical(c) Horned(c) ’ ¬Mammal(c)

8.33 8.34
(Horned(c) ’ (Elusive(c) § Magical(c))) (Tet(a) § Large(a)) ∨ (Cube(a)
‚ ‚
§ (¬Horned(c) ’ (¬Elusive(c) § Small(a))
§ ¬Magical(c))) ¬Small(b)
¬Horned(c) ’ ¬Mythical(c) (Tet(a) ∨ Cube(a)) ’ (Large(b)
∨ Small(b))
Horned(c) ” (Magical(c) ∨ Mythical(c))
Tet(a) ’ Medium(b)
Small(a) § Large(b)

8.35 8.36
¬Cube(b) ’ Small(b) SameRow(d, a) ∨ SameRow(d, b)
‚ ‚
Small(c) ’ (Small(d) ∨ Small(e)) ∨ SameRow(d, c)
Small(d) ’ ¬Small(c) SameRow(d, b) ’ (SameRow(d, a)
Cube(b) ’ ¬Small(e) ’ ¬SameRow(d, c))
SameRow(d, a) ” SameRow(d, c)
Small(c) ’ Small(b)
SameRow(d, a) ” ¬SameRow(d, b)

8.37 Cube(a) ∨ Dodec(a) ∨ Tet(a)
‚ Small(a) ∨ Medium(a) ∨ Large(a)
Medium(a) ” Dodec(a)
Tet(a) ” Large(a)
Cube(a) ” Small(a)

8.38 Use Fitch to give formal proofs of both (P § Q) ’ P and the equivalent sentence ¬(P § Q) ∨ P.
‚ (You will ¬nd the exercise ¬les in Exercise 8.38.1 and Exercise 8.38.2.) Do you see why it is
convenient to include ’ in fol, rather than de¬ne it in terms of the Boolean connectives?



Section 8.2
214 / The Logic of Conditionals


Section 8.3
Soundness and completeness
We have now introduced formal rules for all of our truth-functional connec-
tives. Let™s step back for a minute and ask two important questions about the
formal system F. The questions get at two desirable properties of a deductive
system, which logicians call soundness and completeness. Don™t be confused
by the names, however. These uses of sound and complete are di¬erent from
their use in the notions of a sound argument and a truth-functionally complete
set of connectives.

Soundness
We intend our formal system F to be a correct system of deduction in the
sense that any argument that can be proven valid in F should be genuinely
valid. The ¬rst question that we will ask, then, is whether we have succeeded
in this goal. Does the system F allow us to construct proofs only of genuinely
soundness of a
deductive system valid arguments? This is known as the soundness question for the deductive
system F.
The answer to this question may seem obvious, but it deserves a closer look.
After all, consider the rule of inference suggested in Exercise 7.32 on page 196.
Probably, when you ¬rst looked at this rule, it seemed pretty reasonable, even
though on closer inspection you realized it was not (or maybe you got the
problem wrong). How can we be sure that something similar might not be the
case for one of our o¬cial rules? Maybe there is a ¬‚aw in one of them but we
just haven™t thought long enough or hard enough to discover it.
Or maybe there are problems that go beyond the individual rules, some-
thing about the way the rules interact. Consider for example the following
argument:

¬(Happy(carl) § Happy(scru¬y))
¬Happy(carl)

We know this argument isn™t valid since it is clearly possible for the premise to
be true and the conclusion false. But how do we know that the rules of proof
we™ve introduced do not allow some very complicated and ingenious proof
of the conclusion from the premise? After all, there is no way to examine all
possible proofs and make sure there isn™t one with this premise and conclusion:
there are in¬nitely many proofs.
To answer our question, we need to make it more precise. We have seen that



Chapter 8
Soundness and completeness / 215



there is a certain vagueness in the notion of logical consequence. The concept
of tautological consequence was introduced as a precise approximation of the
informal notion. One way to make our question more precise is to ask whether
the rules for the truth-functional connectives allow us to prove only arguments
that are tautologically valid. This question leaves out the issue of whether the
identity rules are legitimate, but we will address that question later.
Let™s introduce some new symbols to make it easier to express the claim
we want to investigate. We will use FT to refer to the portion of our deductive FT
system that contains the introduction and elimination rules for ¬, ∨, §, ’, ”,
and ⊥. You can think of the subscript t as standing for either “tautology” or
“truth-functional.” We will also write P1 , . . . , Pn T S to indicate that there T

is a formal proof in FT of S from premises P1 , . . . , Pn . (The symbol is
commonly used in logic to indicate the provability of what™s on the right from
what™s on the left. If you have trouble remembering what this symbol means,
just think of it as a tiny Fitch bar.) We can now state our claim as follows.
Theorem (Soundness of FT ) If P1 , . . . , Pn S then S is a tautological con- Soundness of FT
T

sequence of P1 , . . . , Pn .

Proof: Suppose that p is a proof constructed in the system FT . We
will show that any sentence that occurs at any step in proof p is
a tautological consequence of the assumptions in force at that step.
This claim applies not just to sentences at the main level of p, but also
to sentences appearing in subproofs, no matter how deeply nested.
The assumptions in force at a step always include the main premises
of the proof, but if we are dealing with a step inside some nested
subproofs, they also include all the assumptions of these subproofs.
The soundness theorem follows from our claim because if S appears
at the main level of p, then the only assumptions in force are the
premises P1, . . . , Pn . So S is a tautological consequence of P1 , . . . , Pn .
To prove this claim we will use proof by contradiction. Suppose that
there is a step in p containing a sentence that is not a tautological
consequence of the assumptions in force at that step. Call this an
invalid step. The idea of our proof is to look at the ¬rst invalid step
in p and show that none of the twelve rules of FT could have justi¬ed
that step. In other words, we will apply proof by cases to show that,
no matter which rule of FT was applied at the invalid step, we get a
contradiction. (Actually, we will only look at three of the cases and
leave the remaining rules as exercises.) This allows us to conclude
that there can be no invalid steps in proofs in FT .




Section 8.3
216 / The Logic of Conditionals


’ Elim: Suppose the ¬rst invalid step derives the sentence R by an
application of ’ Elim to sentences Q ’ R and Q appearing earlier
in the proof. Let A1 , . . . , Ak be a list of all the assumptions in force
at R. If this is an invalid step, R is not a tautological consequence of
A1 , . . . , Ak . But we will show that this leads us to a contradiction.
Since R is the ¬rst invalid step in p, we know that Q ’ R and Q
are both valid steps, that is, they are tautological consequences of
the assumptions in force at those steps. The crucial observation is
that since FT allows us to cite sentences only in the main proof or
in subproofs whose assumptions are still in force, we know that the
assumptions in force at steps Q ’ R and Q are also in force at R.
Hence, the assumptions for these steps are among A1 , . . . , Ak . An
illustration may help. Suppose our proof takes the following form:

A1
.
.
.
Q’R
.
.
.
A2
.
.
.
Q
.
.
.
A3
.
.
.
R
.
.
.


As should be clear, the restrictions on citing earlier steps guarantee
that all the assumptions in force at the cited steps will still be in
force at the step containing R. In the example shown, assumption
A1 is in force at the step containing Q ’ R, assumptions A1 and A2
are in force at the step containing Q, and assumptions A1 , A2 and
A3 are in force at the step containing R.
Suppose, now, we construct a joint truth table for the sentences
A1 , . . . , Ak , Q, Q ’ R, and R. By the assumption that R is an invalid



Chapter 8
Soundness and completeness / 217



step, there must be a row h of this table in which A1 , . . . , Ak all come
out true, but R comes out false. However, since Q and Q ’ R are
tautological consequences of A1 , . . . , Ak , both of these sentences are
true in row h. But this contradicts the truth table for ’.

<<

. 40
( 107 .)



>>