<<

. 33
( 107 .)



>>



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.

<<

. 33
( 107 .)



>>