6.30 6.31

¬(¬Cube(a) § Cube(b)) Dodec(b) ∨ Cube(b)

‚ ‚

¬(¬Cube(b) ∨ Cube(c)) Small(b) ∨ Medium(b)

¬(Small(b) § Cube(b))

Cube(a)

Medium(b) § Dodec(b)

6.32 Dodec(b) ∨ Cube(b)

‚ Small(b) ∨ Medium(b)

¬Small(b) § ¬Cube(b))

Medium(b) § Dodec(b)

Section 6.6

Proofs without premises

Not all proofs begin with the assumption of premises. This may seem odd,

but in fact it is how we use our deductive system to show that a sentence is

a logical truth. A sentence that can be proven without any premises at all is

necessarily true. Here™s a trivial example of such a proof, one that shows that demonstrating

logical truth

a = a § b = b is a logical truth.

1. a = a = Intro

2. b = b = Intro

3. a = a § b = b § Intro: 1, 2

The ¬rst step of this proof is not a premise, but an application of = Intro.

You might think that any proof without premises would have to start with

this rule, since it is the only one that doesn™t have to cite any supporting steps

earlier in the proof. But in fact, this is not a very representative example of

such proofs. A more typical and interesting proof without premises is the

following, which shows that ¬(P § ¬P) is a logical truth.

Section 6.6

174 / Formal Proofs and Boolean Logic

1. P § ¬P

2. P § Elim: 1

3. ¬P § Elim: 1

4. ⊥ ⊥ Intro: 2, 3

5. ¬(P § ¬P) ¬ Intro: 1“4

Notice that there are no assumptions above the ¬rst horizontal Fitch bar,

indicating that the main proof has no premises. The ¬rst step of the proof is

the subproof ™s assumption. The subproof proceeds to derive a contradiction,

based on this assumption, thus allowing us to conclude that the negation

of the subproof™s assumption follows without the need of premises. In other

words, it is a logical truth.

When we want you to prove that a sentence is a logical truth, we will use

Fitch notation to indicate that you must prove this without assuming any

premises. For example the above proof shows that the following “argument”

is valid:

¬(P § ¬P)

We close this section with the following reminder:

Remember

A proof without any premises shows that its conclusion is a logical truth.

Exercises

6.33 (Excluded Middle) Open the ¬le Exercise 6.33. This contains an incomplete proof of the law

‚ of excluded middle, P ∨ ¬P. As it stands, the proof does not check out because it™s missing

some sentences, some support citations, and some rules. Fill in the missing pieces and submit

the completed proof as Proof 6.33. The proof shows that we can derive excluded middle in F

without any premises.

Chapter 6

Proofs without premises / 175

In the following exercises, assess whether the indicated sentence is a logical truth in the blocks language.

If so, use Fitch to construct a formal proof of the sentence from no premises (using Ana Con if

necessary, but only applied to literals). If not, use Tarski™s World to construct a counterexample. (A

counterexample here will simply be a world that makes the purported conclusion false.)

6.34 6.35

‚ ‚

¬(a = b § Dodec(a) § ¬Dodec(b)) ¬(a = b § Dodec(a) § Cube(b))

6.36 6.37

‚ ‚

¬(a = b § b = c § a = c) ¬(a = b § b = c § a = c)

6.38

‚

¬(SameRow(a, b) § SameRow(b, c) § FrontOf(c, a))

6.39

‚

¬(SameCol(a, b) § SameCol(b, c) § FrontOf(c, a))

The following sentences are all tautologies, and so should be provable in F . Although the informal proofs

are relatively simple, F makes fairly heavy going of them, since it forces us to prove even very obvious

steps. Use Fitch to construct formal proofs. You may want to build on the proof of Excluded Middle

given in Exercise 6.33. Alternatively, with the permission of your instructor, you may use Taut Con,

but only to justify an instance of Excluded Middle. The Grade Grinder will indicate whether you used

Taut Con or not.

6.40 6.41

‚ ‚

A ∨ ¬(A § B) (A § B) ∨ ¬A ∨ ¬B

6.42

‚

¬A ∨ ¬(¬B § (¬A ∨ B))

Section 6.6

Chapter 7

Conditionals

There are many logically important constructions in English besides the Boolean

connectives. Even if we restrict ourselves to words and phrases that connect

two simple indicative sentences, we still ¬nd many that go beyond the Boolean

operators. For example, besides saying:

Max is home and Claire is at the library,

and

Max is home or Claire is at the library,

we can combine these same atomic sentences in the following ways, among

others:

Max is home if Claire is at the library,

Max is home only if Claire is at the library,

Max is home if and only if Claire is at the library,

Max is not home nor is Claire at the library,

Max is home unless Claire is at the library,

Max is home even though Claire is at the library,

Max is home in spite of the fact that Claire is at the library,

Max is home just in case Claire is at the library,

Max is home whenever Claire is at the library,

Max is home because Claire is at the library.

And these are just the tip of the iceberg. There are also constructions that

combine three atomic sentences to form new sentences:

If Max is home then Claire is at the library, otherwise Claire is

concerned,

and constructions that combine four:

If Max is home then Claire is at the library, otherwise Claire is

concerned unless Carl is with him,

and so forth.

Some of these constructions are truth functional, or have important truth-

functional uses, while others do not. Recall that a connective is truth func-

tional if the truth or falsity of compound statements made with it is completely

176

Material conditional symbol: ’ / 177

determined by the truth values of its constituents. Its meaning, in other words,

can be captured by a truth table.

Fol does not include connectives that are not truth functional. This is non-truth-functional

connectives

not to say that such connectives aren™t important, but their meanings tend to

be vague and subject to con¬‚icting interpretations. The decision to exclude

them is analogous to our assumption that all the predicates of fol have precise

interpretations.

Whether or not a connective in English can be, or always is, used truth

functionally is a tricky matter, about which we™ll have more to say later in

the chapter. Of the connectives listed above, though, there is one that is very

clearly not truth functional: the connective because. This is not hard to prove.

Proof: To show that the English connective because is not truth

functional, it su¬ces to ¬nd two possible circumstances in which the

sentence Max is home because Claire is at the library would have

di¬erent truth values, but in which its constituents, Max is home

and Claire is at the library, have the same truth values.

Why? Well, suppose that the meaning of because were captured by a

truth table. These two circumstances would correspond to the same

row of the truth table, since the atomic sentences have the same

values, but in one circumstance the sentence is true and in the other

it is false. So the purported truth table must be wrong, contrary to

our assumption.

For the ¬rst circumstance, imagine that Max learned that Claire

would be at the library, hence unable to feed Carl, and so rushed

home to feed him. For the second circumstance, imagine that Max

is at home, expecting Claire to be there too, but she unexpectedly

had to go the library to get a reference book for a report. In both

circumstances the sentences Max is home and Claire is at the library

are true. But the compound sentence Max is home because Claire

is at the library is true in the ¬rst, false in the second.

The reason because is not truth functional is that it typically asserts some

sort of causal connection between the facts described by the constituent sen-

tences. This is why our compound sentence was false in the second situation:

the causal connection was missing.

In this chapter, we will introduce two new truth-functional connectives,

known as the material conditional and the material biconditional, both stan-

dard features of fol. It turns out that, as we™ll show at the end of the chapter,

these new symbols do not actually increase the expressive power of fol. They

Section 7.1

178 / Conditionals

do, however, make it much easier to say and prove certain things, and so are

valuable additions to the language.

Section 7.1

Material conditional symbol: ’

The symbol ’ is used to combine two sentences P and Q to form a new

sentence P ’ Q, called a material conditional. The sentence P is called the

antecedent of the conditional, and Q is called the consequent of the conditional.

We will discuss the English counterparts of this symbol after we explain its

meaning.

Semantics and the game rule for the conditional

The sentence P ’ Q is true if and only if either P is false or Q is true (or

both). This can be summarized by the following truth table.

P Q P’Q

T

t t

truth table for ’ F

t f

T

f t

T

f f

A second™s thought shows that P ’ Q is really just another way of saying

¬P ∨ Q. Tarski™s World in fact treats the former as an abbreviation of the

latter. In particular, in playing the game, Tarski™s World simply replaces a

game rule for ’

statement of the form P ’ Q by its equivalent ¬P ∨ Q.

Remember

1. If P and Q are sentences of fol, then so is P ’ Q.

2. The sentence P ’ Q is false in only one case: if the antecedent P is

true and the consequent Q is false. Otherwise, it is true.