. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .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 ’.