Forall X Calgary. An Introduction To Formal Logic - P.D. Magnus, T. Button Fall 2019 PDF
Forall X Calgary. An Introduction To Formal Logic - P.D. Magnus, T. Button Fall 2019 PDF
Forall X Calgary. An Introduction To Formal Logic - P.D. Magnus, T. Button Fall 2019 PDF
CALGARY
An Introduction to
Formal Logic
P. D. Magnus
Tim Button
with additions by
J. Robert Loftis
Robert Trueman
remixed and revised by
Aaron Thomas-Bolduc
Richard Zach
Fall 2019
forall x : Calgary
An Introduction to
Formal Logic
By P. D. Magnus
Tim Button
with additions by
J. Robert Loftis
Robert Trueman
remixed and revised by
Aaron Thomas-Bolduc
Richard Zach
Fall 2019
This book is based on forallx: Cambridge, by Tim Button (University
College London), used under a CC BY 4.0 license, which is based in
turn on forallx, by P.D. Magnus (University at Albany, State Univer-
sity of New York), used under a CC BY 4.0 license, and was remixed,
revised, & expanded by Aaron Thomas-Bolduc & Richard Zach (Uni-
versity of Calgary). It includes additional material from forallx by
P.D. Magnus and Metatheory by Tim Button, used under a CC BY 4.0
license, from forallx: Lorain County Remix, by Cathal Woods and J.
Robert Loftis, and from A Modal Logic Primer by Robert Trueman, used
with permission.
This work is licensed under a Creative Commons Attribution 4.0 license. You
are free to copy and redistribute the material in any medium or format, and
remix, transform, and build upon the material for any purpose, even commer-
cially, under the following terms:
▷ You must give appropriate credit, provide a link to the license, and
indicate if changes were made. You may do so in any reasonable manner,
but not in any way that suggests the licensor endorses you or your use.
▷ You may not apply legal terms or technological measures that legally
restrict others from doing anything the license permits.
1 Arguments 2
2 The scope of logic 7
3 Other logical notions 18
II Truth-functional logic 26
iii
CONTENTS iv
VI Interpretations 242
27 Extensionality 243
28 Truth in FOL 250
29 Semantic concepts 260
30 Using interpretations 262
31 Reasoning about interpretations 269
IX Metatheory 342
Appendices 363
Glossary 384
Preface
As the title indicates, this is a textbook on formal logic. For-
mal logic concerns the study of a certain kind of language which,
like any language, can serve to express states of affairs. It is a
formal language, i.e., its expressions (such as sentences) are de-
fined formally. This makes it a very useful language for being
very precise about the states of affairs its sentences describe. In
particular, in formal logic it is impossible to be ambiguous. The
study of these languages centres on the relationship of entailment
between sentences, i.e., which sentences follow from which other
sentences. Entailment is central because by understanding it bet-
ter we can tell when some states of affairs must obtain provided
some other states of affairs obtain. But entailment is not the only
important notion. We will also consider the relationship of be-
ing satisfiable, i.e., of not being mutually contradictory. These
notions can be defined semantically, using precise definitions of
entailment based on interpretations of the language—or proof-
theoretically, using formal systems of deduction.
Formal logic is of course a central sub-discipline of philoso-
phy, where the logical relationship of assumptions to conclusions
reached from them is important. Philosophers investigate the
consequences of definitions and assumptions and evaluate these
definitions and assumptions on the basis of their consequences.
It is also important in mathematics and computer science. In
mathematics, formal languages are used to describe not “every-
vi
PREFACE vii
Key notions of
logic
1
CHAPTER 1
Arguments
Logic is the business of evaluating arguments; sorting the good
from the bad.
In everyday language, we sometimes use the word ‘argument’
to talk about belligerent shouting matches. If you and a friend
have an argument in this sense, things are not going well between
the two of you. Logic is not concerned with such teeth-gnashing
and hair-pulling. They are not arguments, in our sense; they are
just disagreements.
An argument, as we will understand it, is something more
like this:
Either the butler or the gardner did it.
The butler didn’t do it.
.̇. The gardner did it.
We here have a series of sentences. The three dots on the third
line of the argument are read ‘therefore.’ They indicate that the
final sentence expresses the conclusion of the argument. The two
sentences before that are the premises of the argument. If you be-
lieve the premises, and you think the conclusion follows from the
premises—that the argument, as we will say, is valid—then this
(perhaps) provides you with a reason to believe the conclusion.
This is the sort of thing that logicians are interested in. We
will say that an argument is any collection of premises, together
with a conclusion.
2
CHAPTER 1. ARGUMENTS 3
The gardner did it. After all, it was either the butler
or the gardner. And the gardner didn’t do it.
1.1 Sentences
To be perfectly general, we can define an argument as a series
of sentences. The sentences at the beginning of the series are
premises. The final sentence in the series is the conclusion. If
the premises are true and the argument is a good one, then you
have a reason to accept the conclusion.
In logic, we are only interested in sentences that can figure as
a premise or conclusion of an argument, i.e., sentences that can
be true or false. So we will restrict ourselves to sentences of this
sort, and define a sentence as a sentences that can be true or
false.
You should not confuse the idea of a sentence that can be
true or false with the difference between fact and opinion. Often,
sentences in logic will express things that would count as facts—
such as ‘Kierkegaard was a hunchback’ or ‘Kierkegaard liked al-
monds.’ They can also express things that you might think of as
matters of opinion—such as, ‘Almonds are tasty.’ In other words,
a sentence is not disqualified from being part of an argument be-
cause we don’t know if it is true or false, or because its truth
or falsity is a matter of opinion. If it is the kind of sentence that
could be true or false it can play the role of premise or conclusion.
Also, there are things that would count as ‘sentences’ in a
linguistics or grammar course that we will not count as sentences
in logic.
CHAPTER 1. ARGUMENTS 5
Practice exercises
At the end of some chapters, there are exercises that review and
explore the material covered in the chapter. There is no substitute
for actually working through some problems, because learning
logic is more about developing a way of thinking than it is about
memorizing facts.
So here’s the first exercise. Highlight the phrase which ex-
presses the conclusion of each of these arguments:
The scope of
logic
2.1 Consequence and validity
In §1, we talked about arguments, i.e., a collection of sentences
(the premises), followed by a single sentence (the conclusion).
We said that some words, such as “therefore,” indicate which
sentence in is supposed to be the conclusion. “Therefore,” of
course, suggests that there is a connection between the premises
and the conclusion, namely that the conclusion follows from, or is
a consequence of, the premises.
This notion of consequence is one of the primary things logic
is concerned with. One might even say that logic is the science of
what follows from what. Logic develops theories and tools that
tell us when a sentence follows from some others.
What about the main argument discussed in §1?
We don’t have any context for what the sentences in this argu-
ment refer to. Perhaps you suspect that “did it” here means “was
7
CHAPTER 2. THE SCOPE OF LOGIC 8
We still have no idea what is being talked about here. But, again,
you probably agree that this argument is different from the pre-
vious one in an important respect. If the premises are true, it is
not guaranteed that the conclusion is also true. The premises of
this argument do not rule out, by themselves, that someone other
than the maid or the driver “did it.” So there is a case where both
premises are true, and yet the driver didn’t do it, i.e., the conclu-
sion is not true. In this second argument, the conclusion does not
follow from the premises. If, like in this argument, the conclusion
does not follow from the premises, we say it is invalid.
Priya is an ophtalmologist.
.̇. Priya is an eye doctor.
about whether it is possible for all the premises to be true and the
conclusion to be not true at the same time (in some hypothetical
case). What is in fact the case has no special role to play; and
what the facts are does not determine whether an argument is
valid or not.2 Nothing about the way things are can by itself de-
termine if an argument is valid. It is often said that logic doesn’t
care about feelings. Actually, it doesn’t care about facts, either.
When we use an argument to prove that its conclusion is true,
then, we need two things. First, we need the argument to be valid,
i.e., we need the conclusion to follow from the premises. But we
also need the premises to be true. We will say that an argument
is sound if and only if it is both valid and all of its premises are
true.
The flip side of this is that when you want to rebut an argu-
ment, you have two options: you can show that (one or more of)
the premises are not true, or you can show that the argument is
not valid. Logic, however, will only help you with the latter!
is a case where the premises of the argument are true but the
conclusion is not, making the argument invalid.
The point of all this is that inductive arguments—even good
inductive arguments—are not (deductively) valid. They are not
watertight. Unlikely though it might be, it is possible for their con-
clusion to be false, even when all of their premises are true. In
this book, we will set aside (entirely) the question of what makes
for a good inductive argument. Our interest is simply in sorting
the (deductively) valid arguments from the invalid ones.
So: we are interested in whether or not a conclusion follows
from some premises. Don’t, though, say that the premises infer
the conclusion. Entailment is a relation between premises and
conclusions; inference is something we do. So if you want to
mention inference when the conclusion follows from the premises,
you could say that one may infer the conclusion from the premises.
Practice exercises
A. Which of the following arguments are valid? Which are in-
valid?
1. Socrates is a man.
2. All men are carrots.
.̇. Socrates is a carrot.
1. If the world ends today, then I will not need to get up to-
morrow morning.
2. I will need to get up tomorrow morning.
.̇. The world will not end today.
1. A valid argument that has one false premise and one true
premise?
2. A valid argument that has only false premises?
3. A valid argument with only false premises and a false con-
clusion?
4. An invalid argument that can be made valid by the addition
of a new premise?
5. A valid argument that can be made invalid by the addition
of a new premise?
Other logical
notions
In §2, we introduced the ideas of consequence and of valid argu-
ment. This is one of the most important ideas in logic. In this
section, we will introduce are some similarly important ideas.
They all rely, as did validity, on the idea that sentences are true
(or not) in cases. For the rest of this section, we’ll take cases
in the sense of conceivable scenario, i.e., in the sense in which
we used them to define conceptual validity. The points we made
about different kinds of validity can be made about our new no-
tions along similar lines: if we use a different idea of what counts
as a “case” we will get different notions. And as logicians we will,
eventually, consider a more permissive definition of case than we
do here.
18
CHAPTER 3. OTHER LOGICAL NOTIONS 19
G1. There are at least four giraffes at the wild animal park.
G2. There are exactly seven gorillas at the wild animal park.
G3. There are not more than two martians at the wild animal
park.
G4. Every giraffe at the wild animal park is a martian.
1. It is raining.
2. Either it is raining here, or it is not.
3. It is both raining here and not raining here.
Necessary equivalence
We can also ask about the logical relations between two sentences.
For example:
These two sentences are both contingent, since John might not
have gone to the store or washed dishes at all. Yet they must have
the same truth-value. If either of the sentences is true, then they
both are; if either of the sentences is false, then they both are.
When two sentences have the same truth value in every case, we
say that they are necessarily equivalent.
Practice exercises
A. For each of the following: Is it a necessary truth, a necessary
falsehood, or contingent?
1. Caesar crossed the Rubicon.
2. Someone once crossed the Rubicon.
3. No one has ever crossed the Rubicon.
4. If Caesar crossed the Rubicon, then someone has.
5. Even though Caesar crossed the Rubicon, no one has ever
crossed the Rubicon.
6. If anyone has ever crossed the Rubicon, it was Caesar.
B. For each of the following: Is it a necessary truth, a necessary
falsehood, or contingent?
1. Elephants dissolve in water.
2. Wood is a light, durable substance useful for building
things.
3. If wood were a good building material, it would be useful
for building things.
4. I live in a three story building that is two stories tall.
5. If gerbils were mammals they would nurse their young.
C. Which of the following pairs of sentences are necessarily equiv-
alent?
G3 There are not more than two Martians at the wild animal
park.
M2 Socrates is a person.
M4 Socrates is mortal.
1. A valid argument that has one false premise and one true
premise
2. A valid argument that has a false conclusion
3. A valid argument, the conclusion of which is a necessary
falsehood
4. An invalid argument, the conclusion of which is a necessary
truth
5. A necessary truth that is contingent
6. Two necessarily equivalent sentences, both of which are
necessary truths
7. Two necessarily equivalent sentences, one of which is a nec-
essary truth and one of which is contingent
8. Two necessarily equivalent sentences that together are
jointly impossible
9. A jointly possible collection of sentences that contains a
necessary falsehood
10. A jointly impossible set of sentences that contains a neces-
sary truth
Truth-
functional
logic
26
CHAPTER 4
First steps to
symbolization
4.1 Validity in virtue of form
Consider this argument:
It is raining outside.
If it is raining outside, then Jenny is miserable.
.̇. Jenny is miserable.
Jenny is an anarcho-syndicalist.
If Jenny is an anarcho-syndicalist, then Dipan is an avid
reader of Tolstoy.
.̇. Dipan is an avid reader of Tolstoy.
A
If A, then C
.̇. C
27
CHAPTER 4. FIRST STEPS TO SYMBOLIZATION 28
A, P, P 1, P 2, A234
A: It is raining outside
C : Jenny is miserable
In doing this, we are not fixing this symbolization once and for
all. We are just saying that, for the time being, we will think of
the sentence letter of TFL, ‘A’, as symbolizing the English sen-
tence ‘It is raining outside’, and the sentence letter of TFL, ‘C ’,
as symbolizing the English sentence ‘Jenny is miserable’. Later,
when we are dealing with different sentences or different argu-
ments, we can provide a new symbolization key; as it might be:
A: Jenny is an anarcho-syndicalist
C : Dipan is an avid reader of Tolstoy
Connectives
In the previous chapter, we considered symbolizing fairly basic
English sentences with sentence letters of TFL. This leaves us
wanting to deal with the English expressions ‘and’, ‘or’, ‘not’,
and so forth. These are connectives—they can be used to form new
sentences out of old ones. In TFL, we will make use of logical
connectives to build complex sentences from atomic components.
There are five logical connectives in TFL. This table summarises
them, and they are explained throughout this section.
32
CHAPTER 5. CONNECTIVES 33
5.1 Negation
Consider how we might symbolize these sentences:
1. Mary is in Barcelona.
2. It is not the case that Mary is in Barcelona.
3. Mary is not in Barcelona.
B: Mary is in Barcelona.
7. Jane is happy.
8. Jane is unhappy.
5.2 Conjunction
Consider these sentences:
9. Adam is athletic.
10. Barbara is athletic.
11. Adam is athletic, and Barbara is also athletic.
A: Adam is athletic.
B: Barbara is athletic.
need another symbol, to deal with ‘and’. We will use ‘∧’. Thus
we will symbolize it as ‘(A ∧ B)’. This connective is called con-
junction. We also say that ‘A’ and ‘B’ are the two conjuncts
of the conjunction ‘(A ∧ B)’.
Notice that we make no attempt to symbolize the word ‘also’
in sentence 11. Words like ‘both’ and ‘also’ function to draw our
attention to the fact that two things are being conjoined. Maybe
they affect the emphasis of a sentence, but we will not (and can-
not) symbolize such things in TFL.
Some more examples will bring out this point:
16. It’s not the case that you will get both soup and salad.
17. You will not get soup but you will get salad.
CHAPTER 5. CONNECTIVES 37
We would symbolize ‘both you will get soup and you will get
salad’ as ‘(S 1 ∧ S 2 )’. To symbolize sentence 16, then, we simply
negate the whole sentence, thus: ‘¬(S 1 ∧ S 2 )’.
Sentence 17 is a conjunction: you will not get soup, and you
will get salad. ‘You will not get soup’ is symbolized by ‘¬S 1 ’. So
to symbolize sentence 17 itself, we offer ‘(¬S 1 ∧ S 2 )’.
These English sentences are very different, and their symbol-
izations differ accordingly. In one of them, the entire conjunction
is negated. In the other, just one conjunct is negated. Brackets
help us to keep track of things like the scope of the negation.
5.3 Disjunction
Consider these sentences:
20. Either you will not have soup, or you will not have salad.
21. You will have neither soup nor salad.
22. You get either soup or salad, but not both.
5.4 Conditional
Consider these sentences:
P : Jean is in Paris.
F : Jean is in France
5.5 Biconditional
Consider these sentences:
D: Laika is a dog
M : Laika is a mammal
5.6 Unless
We have now introduced all of the connectives of TFL. We can
use them together to symbolize many kinds of sentences. An
especially difficult case is when we use the English-language con-
nective ‘unless’:
Both sentences mean that if you do not wear a jacket, then you
will catch a cold. With this in mind, we might symbolize them as
‘¬ J → D’.
CHAPTER 5. CONNECTIVES 43
Practice exercises
A. Using the symbolization key given, symbolize each English
sentence in TFL.
E1 : Ava is an electrician.
E2 : Harrison is an electrician.
F1 : Ava is a firefighter.
F2 : Harrison is a firefighter.
S1: Ava is satisfied with her career.
S2: Harrison is satisfied with his career.
water shortage. But the only way to solve the water short-
age is to divert almost all the water from the Yangzi river
northward. Therefore the Chinese government will go with
the project to divert water from the south to the north.
Sentences of
TFL
The sentence ‘either apples are red, or berries are blue’ is a sen-
tence of English, and the sentence ‘(A ∨ B)’ is a sentence of TFL.
Although we can identify sentences of English when we encounter
them, we do not have a formal definition of ‘sentence of English’.
But in this chapter, we will offer a complete definition of what
counts as a sentence of TFL. This is one respect in which a for-
mal language like TFL is more precise than a natural language
like English.
6.1 Expressions
We have seen that there are three kinds of symbols in TFL:
Connectives ¬, ∧, ∨, →, ↔
Brackets (,)
49
CHAPTER 6. SENTENCES OF TFL 50
6.2 Sentences
Of course, many expressions of TFL will be total gibberish. We
want to know when an expression of TFL amounts to a sentence.
Obviously, individual sentence letters like ‘A’ and ‘G 13 ’ should
count as sentences. (We’ll also call them atomic sentences.) We
can form further sentences out of these by using the various con-
nectives. Using negation, we can get ‘¬A’ and ‘¬G 13 ’. Using
conjunction, we can get ‘(A ∧ G 13 )’, ‘(G 13 ∧ A)’, ‘(A ∧ A)’, and
‘(G 13 ∧G 13 )’. We could also apply negation repeatedly to get sen-
tences like ‘¬¬A’ or apply negation along with conjunction to get
sentences like ‘¬(A ∧G 13 )’ and ‘¬(G 13 ∧¬G 13 )’. The possible com-
binations are endless, even starting with just these two sentence
letters, and there are infinitely many sentence letters. So there is
no point in trying to list all the sentences one by one.
Instead, we will describe the process by which sentences can
be constructed. Consider negation: Given any sentence A of TFL,
¬A is a sentence of TFL. (Why the funny fonts? We return to this
in §7.3.)
We can say similar things for each of the other connectives.
For instance, if A and B are sentences of TFL, then (A ∧ B)
is a sentence of TFL. Providing clauses like this for all of the
connectives, we arrive at the following formal definition for a
sentence of tfl:
CHAPTER 6. SENTENCES OF TFL 51
(P ∧ (¬(R ∧ B) ↔ Q ))
meaning the same thing as ‘(¬Q ∧ R)’, but as we saw in §5.2, this
is very different from ‘¬(Q ∧ R)’.
Strictly speaking, then, ‘Q ∧ R’ is not a sentence. It is a mere
expression.
When working with TFL, however, it will make our lives eas-
ier if we are sometimes a little less than strict. So, here are some
convenient conventions.
First, we allow ourselves to omit the outermost brackets of a
sentence. Thus we allow ourselves to write ‘Q ∧ R’ instead of
the sentence ‘(Q ∧ R)’. However, we must remember to put the
brackets back in, when we want to embed the sentence into a
more complicated sentence!
Second, it can be a bit painful to stare at long sentences with
many nested pairs of brackets. To make things a bit easier on
the eyes, we will allow ourselves to use square brackets, ‘[’ and
‘]’, instead of rounded ones. So there is no logical difference
between ‘(P ∨ Q )’ and ‘[P ∨ Q ]’, for example.
Combining these two conventions, we can rewrite the un-
wieldy sentence
(((H → I ) ∨ (I → H )) ∧ ( J ∨ K ))
Practice exercises
A. For each of the following: (a) Is it a sentence of TFL, strictly
speaking? (b) Is it a sentence of TFL, allowing for our relaxed
bracketing conventions?
1. (A)
2. J 374 ∨ ¬ J 374
3. ¬¬¬¬F
CHAPTER 6. SENTENCES OF TFL 55
4. ¬∧S
5. (G ∧ ¬G )
6. (A → (A ∧ ¬F )) ∨ (D ↔ E)
7. [(Z ↔ S ) → W ] ∧ [ J ∨ X ]
8. (F ↔ ¬D → J ) ∨ (C ∧ D)
Use and
mention
In this Part, we have talked a lot about sentences. So we should
pause to explain an important, and very general, point.
56
CHAPTER 7. USE AND MENTION 57
says that some expression is the Prime Minister. That’s false. The
man is the Prime Minister; his name isn’t. Conversely, this sen-
tence:
7.3 Metavariables
However, we do not just want to talk about specific expressions of
TFL. We also want to be able to talk about any arbitrary sentence
of TFL. Indeed, we had to do this in §6.2, when we presented
the inductive definition of a sentence of TFL. We used uppercase
script letters to do this, namely:
A, B, C, D, . . .
CHAPTER 7. USE AND MENTION 59
and similarly, for expressions like ‘(A∧ B)’, ‘(A∨ B)’, etc.
abbreviates:
Truth tables
61
CHAPTER 8
Characteristic
truth tables
Any sentence of TFL is composed of sentence letters, possibly
combined using sentential connectives. The truth value of the
compound sentence depends only on the truth value of the sen-
tence letters that comprise it. In order to know the truth value of
‘(D ∧ E)’, for instance, you only need to know the truth value of
‘D’ and the truth value of ‘E’.
We introduced five connectives in chapter 5, so we simply
need to explain how they map between truth values. For con-
venience, we will abbreviate ‘True’ with ‘T’ and ‘False’ with ‘F’.
(But just to be clear, the two truth values are True and False; the
truth values are not letters!)
A ¬A
T F
F T
62
CHAPTER 8. CHARACTERISTIC TRUTH TABLES 63
A B A∧ B
T T T
T F F
F T F
F F F
Note that conjunction is symmetrical. The truth value for A ∧ B
is always the same as the truth value for B ∧ A.
A B A∨ B
T T T
T F T
F T T
F F F
Like conjunction, disjunction is symmetrical.
Conditional. We’re just going to come clean and admit it: Con-
ditionals are a right old mess in TFL. Exactly how much of a mess
they are is philosophically contentious. We’ll discuss a few of the
subtleties in §§9.3 and 11.5. For now, we are going to stipulate
the following: A → B is false if and only if A is true and B is
false. We can summarize this with a characteristic truth table for
the conditional.
CHAPTER 8. CHARACTERISTIC TRUTH TABLES 64
A B A→ B
T T T
T F F
F T T
F F T
The conditional is asymmetrical. You cannot swap the antecedent
and consequent without changing the meaning of the sentence,
because A → B has a very different truth table from B → A.
Truth-
functional
connectives
9.1 The idea of truth-functionality
Let’s introduce an important idea.
65
CHAPTER 9. TRUTH-FUNCTIONAL CONNECTIVES 66
1. 2 + 2 = 4
2. Shostakovich wrote fifteen string quartets
All of the above sentences will be symbolized with the same TFL
sentence, perhaps ‘L ∧ N ’.
We keep saying that we use TFL sentences to symbolize English
sentences. Many other textbooks talk about translating English
sentences into TFL. However, a good translation should preserve
certain facets of meaning, and—as we have just pointed out—
TFL just cannot do that. This is why we will speak of symbolizing
English sentences, rather than of translating them.
This affects how we should understand our symbolization
keys. Consider a key like:
L: Dana is a logician.
N : Dana is a nice person.
ditional in §8, we did not say anything to justify it. Let’s now offer
a justification, which follows Dorothy Edgington.1
Suppose that Lara has drawn some shapes on a piece of pa-
per, and coloured some of them in. We have not seen them, but
nevertheless claim:
A C D
In this case, our claim is surely true. Shapes C and D are not grey,
and so can hardly present counterexamples to our claim. Shape A
is grey, but fortunately it is also circular. So our claim has no
counterexamples. It must be true. That means that each of the
following instances of our claim must be true too:
A B C D
Complete
truth tables
So far, we have considered assigning truth values to TFL sen-
tences indirectly. We have said, for example, that a TFL sentence
such as ‘B’ is to take the same truth value as the English sentence
‘Big Ben is in London’ (whatever that truth value may be), but
we can also assign truth values directly. We can simply stipulate
that ‘B’ is to be true, or stipulate that it is to be false.
70
CHAPTER 10. COMPLETE TRUTH TABLES 71
H I (H ∧I ) →H
T T
T F
F T
F F
A ∧B
H I (H ∧ I ) →H
T T T TT T
T F T FF T
F T F FT F
F F F FF F
Now, the entire sentence that we are dealing with is a conditional,
A → B, with ‘(H ∧ I )’ as A and with ‘H ’ as B. On the second
row, for example, ‘(H ∧ I )’ is false and ‘H ’ is true. Since a con-
ditional is true when the antecedent is false, we write a ‘T’ in the
CHAPTER 10. COMPLETE TRUTH TABLES 72
A →B
H I (H ∧ I ) →H
T T T TT
T F F TT
F T F T F
F F F T F
The conditional is the main logical operator of the sentence, so
the column of ‘T’s underneath the conditional tells us that the
sentence ‘(H ∧ I ) → H ’ is true regardless of the truth values of
‘H ’ and ‘I ’. They can be true or false in any combination, and
the compound sentence still comes out true. Since we have con-
sidered all four possible assignments of truth and falsity to ‘H ’
and ‘I ’—since, that is, we have considered all the different valua-
tions—we can say that ‘(H ∧ I ) → H ’ is true on every valuation.
In this example, we have not repeated all of the entries in
every column in every successive table. When actually writing
truth tables on paper, however, it is impractical to erase whole
columns or rewrite the whole table for every step. Although it is
more crowded, the truth table can be written in this way:
H I (H ∧ I ) →H
T T T TT T T
T F T FFTT
F T F FTT F
F F F FFTF
Most of the columns underneath the sentence are only there for
bookkeeping purposes. The column that matters most is the col-
umn underneath the main logical operator for the sentence, since
this tells you the truth value of the entire sentence. We have em-
phasized this, by putting this column in bold. When you work
through truth tables yourself, you should similarly emphasize it
(perhaps by highlighting).
CHAPTER 10. COMPLETE TRUTH TABLES 73
M N P M ∧ (N ∨P )
T T T TT T TT
T T F TT T TF
T F T TT F TT
T F F TF F F F
F T T FF T TT
F T F FF T TF
F F T FF F TT
F F F FF F F F
((A ∧ B) ∧ C )
(A ∧ (B ∧ C ))
which is all that TFL cares about (see §9) – which of the two sen-
tences we assert (or deny). Even though the order of the brackets
does not matter as to their truth, we should not just drop them.
The expression
A ∧B ∧C
((A ∨ B) ∨ C )
(A ∨ (B ∨ C ))
A ∨B ∨C
((A → B) → C )
(A → (B → C ))
So if we were to write:
A →B →C
((A ∨ B) ∧ C )
(A ∨ (B ∧ C ))
CHAPTER 10. COMPLETE TRUTH TABLES 76
So if we were to write:
A ∨B ∧C
Practice exercises
A. Offer complete truth tables for each of the following:
1. A→A
2. C → ¬C
3. (A ↔ B) ↔ ¬(A ↔ ¬B)
4. (A → B) ∨ (B → A)
5. (A ∧ B) → (B ∨ A)
6. [︁ ∨ B) ↔ (¬A ∧ ¬B)
¬(A
7.
]︁
(A ∧ B) ∧ ¬(A ∧ B) ∧ C
8. [(A[︁ ∧ B) ∧ C ] →
]︁ B
9. ¬ (C ∨ A) ∨ B
B. Check all the claims made in introducing the new notational
conventions in §10.3, i.e. show that:
1. ‘((A ∧ B) ∧ C )’ and ‘(A ∧ (B ∧ C ))’ have the same truth table
2. ‘((A ∨ B) ∨ C )’ and ‘(A ∨ (B ∨ C ))’ have the same truth table
3. ‘((A ∨ B) ∧ C )’ and ‘(A ∨ (B ∧ C ))’ do not have the same
truth table
4. ‘((A → B) → C )’ and ‘(A → (B → C ))’ do not have the
same truth table
Also, check whether:
5. ‘((A ↔ B) ↔ C )’ and ‘(A ↔ (B ↔ C ))’ have the same truth
table
C. Write complete truth tables for the following sentences and
mark the column that represents the possible truth values for the
whole sentence.
CHAPTER 10. COMPLETE TRUTH TABLES 77
1. ¬(S ↔ (P → S ))
2. ¬[(X ∧ Y ) ∨ (X ∨ Y )]
3. (A → B) ↔ (¬B ↔ ¬A)
4. [C ↔ (D ∨ E)] ∧ ¬C
5. ¬(G ∧ (B ∧ H )) ↔ (G ∨ (B ∨ H ))
1. (D ∧ ¬D) → G
2. (¬P ∨ ¬M ) ↔ M
3. ¬¬(¬A ∧ ¬B)
4. [(D ∧ R) → I ] → ¬(D ∨ R)
5. ¬[(D ↔ O ) ↔ A] → (¬D ∧ O )
Semantic
concepts
In the previous section, we introduced the idea of a valuation and
showed how to determine the truth value of any TFL sentence,
on any valuation, using a truth table. In this section, we will
introduce some related ideas, and show how to use truth tables
to test whether or not they apply.
78
CHAPTER 11. SEMANTIC CONCEPTS 79
11.2 Equivalence
Here is a similar useful notion:
Look at the columns for the main logical operators; negation for
the first sentence, conjunction for the second. On the first three
rows, both are false. On the final row, both are true. Since they
match on every row, the two sentences are equivalent.
11.3 Satisfiability
In §3, we said that sentences are jointly possible iff it is possible
for all of them to be true at once. We can offer a surrogate for
this notion too:
J L ¬ L → ( J ∨ L) ¬L J
T T FTT T T T FT T
T F TF T T T F TF T
F T FTT F T T FT F
F F TF F F F F TF F
The only row on which both‘¬L → ( J ∨ L)’ and ‘¬L’ are true is
the second row, and that is a row on which ‘ J ’ is also true. So
‘¬L → ( J ∨ L)’ and ‘¬L’ entail ‘ J ’.
We now make an important observation:
1. Daisy has four legs. So Daisy has more than two legs.
3. It’s not the case that, if God exists, She answers malevolent
prayers.
A1, A2, . . . , An ⊨ C
The symbol ‘⊨’ is known as the double turnstile, since it looks like
a turnstile with two horizontal beams.
Let’s’ be clear. ‘⊨’ is not a symbol of TFL. Rather, it is a
symbol of our metalanguage, augmented English (recall the dif-
ference between object language and metalanguage from §7). So
the metalanguage sentence:
• P, P → Q ⊨ Q
⊨ C
CHAPTER 11. SEMANTIC CONCEPTS 84
This says that there is no valuation which makes all the sentences
mentioned on the left hand side of ‘⊨’ true whilst making C false.
Since no sentences are mentioned on the left hand side of ‘⊨’ in
this case, this just means that there is no valuation which makes
C false. Otherwise put, it says that every valuation makes C true.
Otherwise put, it says that C is a tautology. Equally:
A⊨
Indeed, when ‘→’ is flanked with two TFL sentences, the re-
sult is a longer TFL sentence. By contrast, when we use ‘⊨’, we
form a metalinguistic sentence that mentions the surrounding TFL
sentences.
CHAPTER 11. SEMANTIC CONCEPTS 85
Practice exercises
A. Revisit your answers to §10A. Determine which sentences
were tautologies, which were contradictions, and which were nei-
ther tautologies nor contradictions.
1. A → A, ¬A → ¬A, A ∧ A, A ∨ A
2. A ∨ B, A → C , B → C
3. B ∧ (C ∨ A), A → B, ¬(B ∨ C )
4. A ↔ (B ∨ C ), C → ¬A, A → ¬B
1. A → A .̇. A
2. A → (A ∧ ¬A) .̇. ¬A
3. A ∨ (B → A) .̇. ¬A → ¬B
4. A ∨ B, B ∨ C, ¬A .̇. B ∧ C
5. (B ∧ A) → C, (C ∧ A) → B .̇. (C ∧ B) → A
1. ¬B ∧ B
2. ¬D ∨ D
3. (A ∧ B) ∨ (B ∧ A)
4. ¬[A → (B → A)]
5. A ↔ [A → (B ∧ ¬B)]
6. [(A ∧ B) ↔ B] → (A → B)
1. A and ¬A
2. A ∧ ¬A and ¬B ↔ B
3. [(A ∨ B) ∨ C ] and [A ∨ (B ∨ C )]
4. A ∨ (B ∧ C ) and (A ∨ B) ∧ (A ∨ C )
5. [A ∧ (A ∨ B)] → B and A → B
F. Determine whether each the following sentences are logically
equivalent using complete truth tables. If the two sentences really
are equivalent, write “equivalent.” Otherwise write, “not equiva-
lent.”
1. A → A and A ↔ A
2. ¬(A → B) and ¬A → ¬B
3. A ∨ B and ¬A → B
4. (A → B) → C and A → (B → C )
5. A ↔ (B ↔ C ) and A ∧ (B ∧ C )
G. Determine whether each collection of sentences is jointly sat-
isfiable or jointly unsatisfiable using a complete truth table.
1. A ∧ ¬B, ¬(A → B), B → A
2. A ∨ B, A → ¬A, B → ¬B
3. ¬(¬A ∨ B), A → ¬C , A → (B → C )
4. A → B, A ∧ ¬B
5. A → (B → C ), (A → B) → C , A → C
1. A → B, B .̇. A
2. A ↔ B, B ↔ C .̇. A ↔ C
3. A → B, A → C .̇. B → C
4. A → B, B → A .̇. A ↔ B
J. Determine whether each argument is valid or invalid, using a
complete truth table.
1. A ∨ A → (A ↔ A) .̇. A
[︁ ]︁
2. A ∨ B, B ∨ C , ¬B .̇. A ∧ C
3. A → B, ¬A .̇. ¬B
4. A, B .̇. ¬(A → ¬B)
5. ¬(A ∧ B), A ∨ B, A ↔ B .̇. C
Truth table
shortcuts
With practice, you will quickly become adept at filling out truth
tables. In this section, we want to give you some permissible
shortcuts to help you along the way.
P Q (P ∨Q ) ↔ ¬ P
T T T FF
T F T FF
F T T TT
F F F FT
You also know for sure that a disjunction is true whenever one
of the disjuncts is true. So if you find a true disjunct, there is no
need to work out the truth values of the other disjuncts. Thus
you might offer:
89
CHAPTER 12. TRUTH TABLE SHORTCUTS 90
P Q (¬P ∨ ¬Q ) ∨ ¬ P
T T F FF FF
T F F TT T F
F T TT
F F TT
Equally, you know for sure that a conjunction is false whenever
one of the conjuncts is false. So if you find a false conjunct, there
is no need to work out the truth value of the other conjunct. Thus
you might offer:
P Q ¬ (P ∧ ¬Q ) ∧ ¬ P
T T FF
T F FF
F T T F TT
F F T F TT
A similar short cut is available for conditionals. You immediately
know that a conditional is true if either its consequent is true, or
its antecedent is false. Thus you might present:
P Q ((P →Q )→P ) →P
T T T
T F T
F T T F T
F F T F T
So ‘((P → Q ) → P ) → P ’ is a tautology. In fact, it is an instance
of Peirce’s Law, named after Charles Sanders Peirce.
Since all we are doing is looking for bad lines, we should bear
this in mind. So: if we find a line where the conclusion is true,
we do not need to evaluate anything else on that line: that line
definitely isn’t bad. Likewise, if we find a line where some premise
is false, we do not need to evaluate anything else on that line.
With this in mind, consider how we might test the following
for validity:
¬L → ( J ∨ L), ¬L .̇. J
The first thing we should do is evaluate the conclusion. If we find
that the conclusion is true on some line, then that is not a bad
line. So we can simply ignore the rest of the line. So at our first
stage, we are left with something like:
J L ¬L → ( J ∨L) ¬L J
T T T
T F T
F T ? ? F
F F ? ? F
where the blanks indicate that we are not going to bother do-
ing any more investigation (since the line is not bad) and the
question-marks indicate that we need to keep investigating.
The easiest premise to evaluate is the second, so we next do
that:
J L ¬L → ( J ∨L) ¬L J
T T T
T F T
F T F F
F F ? T F
Note that we no longer need to consider the third line of the table:
it will not be a bad line, because (at least) one of premises is false
on that line. Finally, we complete the truth table:
CHAPTER 12. TRUTH TABLE SHORTCUTS 92
J L ¬ L → ( J ∨L) ¬L J
T T T
T F T
F T F F
F F T F F T F
The truth table has no bad lines, so the argument is valid. (Any
valuation on which all the premises are true is a valuation on
which the conclusion is true.)
It might be worth illustrating the tactic again. Let us check
whether the following argument is valid
A B C D A∨B ¬ (A ∧C ) ¬ (B ∧ ¬ D) (¬C ∨ D)
T T T T T
T T T F T F T F F
T T F T T
T T F F T T
T F T T T
T F T F T F T F F
T F F T T
T F F F T T
F T T T T
F T T F T T F F TT F F
F T F T T
F T F F T T
F F T T T
F F T F F F F
F F F T T
F F F F T T
Practice exercises
A. Using shortcuts, determine whether each sentence is a tautol-
ogy, a contradiction, or neither.
1. ¬B ∧ B
2. ¬D ∨ D
CHAPTER 12. TRUTH TABLE SHORTCUTS 94
3. (A ∧ B) ∨ (B ∧ A)
4. ¬[A → (B → A)]
5. A ↔ [A → (B ∧ ¬B)]
6. ¬(A ∧ B) ↔ A
7. A → (B ∨ C )
8. (A ∧ ¬A) → (B ∨ C )
9. (B ∧ D) ↔ [A ↔ (A ∨ C )]
CHAPTER 13
Partial truth
tables
Sometimes, we do not need to know what happens on every line
of a truth table. Sometimes, just a line or two will do.
S T U W (U ∧T ) → (S ∧W )
F
We have only left space for one line, rather than 16, since we are
only looking for one line on which the sentence is false. For just
that reason, we have filled in ‘F’ for the entire sentence.
95
CHAPTER 13. PARTIAL TRUTH TABLES 96
To make the sentence true, it will suffice to ensure that the an-
tecedent is false. Since the antecedent is a conjunction, we can
just make one of them false. For no particular reason, we choose
to make ‘U ’ false; and then we can assign whatever truth value
we like to the other sentence letters.
S T U W (U ∧T ) → (S ∧W )
F T F F F FT T FF F
Yes No
tautology? complete one-line partial
contradiction? complete one-line partial
equivalent? complete one-line partial
satisfiable? one-line partial complete
valid? complete one-line partial
entailment? complete one-line partial
Practice exercises
A. Use complete or partial truth tables (as appropriate) to deter-
mine whether these pairs of sentences are logically equivalent:
1. A, ¬A
2. A, A ∨ A
3. A → A, A ↔ A
4. A ∨ ¬B, A → B
5. A ∧ ¬A, ¬B ↔ B
6. ¬(A ∧ B), ¬A ∨ ¬B
7. ¬(A → B), ¬A → ¬B
8. (A → B), (¬B → ¬A)
1. A ∧ B, C → ¬B, C
2. A → B, B → C , A, ¬C
3. A ∨ B, B ∨ C , C → ¬A
4. A, B, C , ¬D, ¬E, F
5. A ∧ (B ∨ C ), ¬(A ∧ C ), ¬(B ∧ C )
6. A → B, B → C , ¬(A → C )
1. A ∨ A → (A ↔ A) .̇. A
[︁ ]︁
CHAPTER 13. PARTIAL TRUTH TABLES 99
2. A ↔ ¬(B ↔ A) .̇. A
3. A → B, B .̇. A
4. A ∨ B, B ∨ C, ¬B .̇. A ∧ C
5. A ↔ B, B ↔ C .̇. A ↔ C
1. A → ¬A
2. A → (A ∧ (A ∨ B))
3. (A → B) ↔ (B → A)
4. A → ¬(A ∧ (A ∨ B))
5. ¬B → [(¬A ∧ A) ∨ B]
6. ¬(A ∨ B) ↔ (¬A ∧ ¬B)
7. [(A ∧ B) ∧ C ] → B
8.
[︁ ]︁
¬ (C ∨ A) ∨ B
9.
[︁ ]︁
(A ∧ B) ∧ ¬(A ∧ B) ∧ C
10. (A ∧ B)] → [(A ∧ C ) ∨ (B ∧ D)]
1. ¬(A ∨ A)
2. (A → B) ∨ (B → A)
3. [(A → B) → A] → A
4. ¬[(A → B) ∨ (B → A)]
5. (A ∧ B) ∨ (A ∨ B)
6. ¬(A ∧ B) ↔ A
7. A → (B ∨ C )
8. (A ∧ ¬A) → (B ∨ C )
9. (B ∧ D) ↔ [A ↔ (A ∨ C )]
CHAPTER 13. PARTIAL TRUTH TABLES 100
1. A and A ∨ A
2. A and A ∧ A
3. A ∨ ¬B and A → B
4. (A → B) and (¬B → ¬A)
5. ¬(A ∧ B) and ¬A ∨ ¬B
6. ((U → (X ∨ X )) ∨ U ) and ¬(X ∧ (X ∧ U ))
7. ((C ∧ (N ↔ C )) ↔ C ) and (¬¬¬N → C )
8. [(A ∨ B) ∧ C ] and [A ∨ (B ∧ C )]
9. ((L ∧ C ) ∧ I ) and L ∨ C
1. A → A, ¬A → ¬A, A ∧ A, A ∨ A
2. A → ¬A, ¬A → A
3. A ∨ B, A → C , B → C
4. A ∨ B, A → C , B → C , ¬C
5. B ∧ (C ∨ A), A → B, ¬(B ∨ C )
6. (A ↔ B) → B, B → ¬(A ↔ B), A ∨ B
7. A ↔ (B ∨ C ), C → ¬A, A → ¬B
8. A ↔ B, ¬B ∨ ¬A, A → B
9. A ↔ B, A → C , B → D, ¬(C ∨ D)
10. ¬(A ∧ ¬B), B → ¬A, ¬B
1. A → (A ∧ ¬A) .̇. ¬A
2. A ∨ B, A → B, B → A .̇. A ↔ B
CHAPTER 13. PARTIAL TRUTH TABLES 101
3. A ∨ (B → A) .̇. ¬A → ¬B
4. A ∨ B, A → B, B → A .̇. A ∧ B
5. (B ∧ A) → C , (C ∧ A) → B .̇. (C ∧ B) → A
6. ¬(¬A ∨ ¬B), A → ¬C .̇. A → (B → C )
7. A ∧ (B → C ), ¬C ∧ (¬B → ¬A) .̇. C ∧ ¬C
8. A ∧ B, ¬A → ¬C , B → ¬D .̇. A ∨ B
9. A → B .̇. (A ∧ B) ∨ (¬A ∧ ¬B)
10. ¬A → B,¬B → C ,¬C → A .̇. ¬A → (¬B ∨ ¬C )
1. A ↔ ¬(B ↔ A) .̇. A
2. A ∨ B, B ∨ C , ¬A .̇. B ∧ C
3. A → C , E → (D ∨ B), B → ¬D .̇. (A ∨ C ) ∨ (B → (E ∧ D))
4. A ∨ B, C → A, C → B .̇. A → (B → C )
5. A → B, ¬B ∨ A .̇. A ↔ B
PART IV
Natural
deduction for
TFL
102
CHAPTER 14
103
CHAPTER 14. THE VERY IDEA OF NATURAL DEDUCTION 104
A1 → C 1 .̇. (A1 ∧ A2 ∧ A3 ∧ A4 ∧ A5 ) → (C 1 ∨ C 2 ∨ C 3 ∨ C 4 ∨ C 5 )
To test this argument for validity, you might use a 1024-line truth
table. If you do it correctly, then you will see that there is no line
on which all the premises are true and on which the conclusion
is false. So you will know that the argument is valid. (But, as just
mentioned, there is a sense in which you will not know why the
argument is valid.) But now consider:
¬(A ∨ B) .̇. ¬A ∧ ¬B
1 ¬(A ∨ B)
106
CHAPTER 15. BASIC RULES FOR TFL 107
n ¬A ∧ ¬B
1 A∨B
2 ¬(A ∧ C )
3 ¬(B ∧ ¬D)
n ¬C ∨ D
15.2 Reiteration
The very first rule is so breathtakingly obvious that it is surprising
we bother with it at all.
If you already have shown something in the course of a proof,
the reiteration rule allows you to repeat it on a new line. For
example:
4 A∧B
.. ..
. .
10 A∧B R4
m A
A Rm
the rule, we use variables like ‘m’ to underscore the point that
the rule may be applied at any point.
15.3 Conjunction
Suppose we want to show that Ludwig is both reactionary and
libertarian. One obvious way to do this would be as follows: first
we show that Ludwig is reactionary; then we show that Ludwig
is libertarian; then we put these two demonstrations together, to
obtain the conjunction.
Our natural deduction system will capture this thought
straightforwardly. In the example given, we might adopt the fol-
lowing symbolization key:
R: Ludwig is reactionary
L: Ludwig is libertarian
8 R
15 L
R ∧L ∧I 8, 15
8 R
15 L
L ∧R ∧I 15, 8
CHAPTER 15. BASIC RULES FOR TFL 110
m A
n B
A∧ B ∧I m, n
m A∧ B
A ∧E m
and equally:
CHAPTER 15. BASIC RULES FOR TFL 111
m A∧ B
B ∧E m
From the premise, we can get each of the conjuncts by ∧E. The
proof now looks like this:
This is a very simple proof, but it shows how we can chain rules
of proof together into longer proofs. In passing, note that investi-
gating this argument with a truth table would have required 256
lines; our formal proof required only four lines.
It is worth giving another example. Back in §10.3, we noted
that this argument is valid:
A ∧ (B ∧ C ) .̇. (A ∧ B) ∧ C
1 A ∧ (B ∧ C )
1 A ∧ (B ∧ C )
2 A ∧E 1
3 B ∧C ∧E 1
4 B ∧E 3
5 C ∧E 3
1 A ∧ (B ∧ C )
2 A ∧E 1
3 B ∧C ∧E 1
4 B ∧E 3
5 C ∧E 3
6 A∧B ∧I 2, 4
7 (A ∧ B) ∧ C ∧I 6, 5
1 A
2 A∧A ∧I 1, 1
15.4 Conditional
Consider the following argument:
If Jane is smart then she is fast.
Jane is smart.
.̇. Jane is fast.
This argument is certainly valid, and it suggests a straightforward
conditional elimination rule (→E):
CHAPTER 15. BASIC RULES FOR TFL 114
m A→ B
n A
B →E m, n
1 R
CHAPTER 15. BASIC RULES FOR TFL 115
1 R
2 L
Note that we are not claiming, on line 2, to have proved ‘L’ from
line 1, so we do not write in any justification for the additional
assumption on line 2. We do, however, need to mark that it is
an additional assumption. We do this by drawing a line under it
(to indicate that it is an assumption) and by indenting it with a
further vertical line (to indicate that it is additional).
With this extra assumption in place, we are in a position to
use ∧I. So we can continue our proof:
1 R
2 L
3 R ∧L ∧I 1, 2
1 R
2 L
3 R ∧L ∧I 1, 2
4 L → (R ∧ L) →I 2–3
i A
j B
A→ B →I i – j
P → Q ,Q → R .̇. P → R
1 P →Q
2 Q →R
3 P
1 P →Q
2 Q →R
3 P
4 Q →E 1, 3
5 R →E 2, 4
6 P →R →I 3–5
1 A
2 B
3 B R2
4 B →B →I 2–3
1 A
2 B
3 B R2
4 B →B →I 2–3
5 B naughty attempt
to invoke →E 4, 3
1. the line must come before the line where the rule is
applied, but
1 A
2 B
3 C
4 A∧B ∧I 1, 2
5 C → (A ∧ B) →I 3–4
6 B → (C → (A ∧ B)) →I 2–5
Notice that the citation on line 4 refers back to the initial assump-
tion (on line 1) and an assumption of a subproof (on line 2).
This is perfectly in order, since neither assumption has been dis-
charged at the time (i.e., by line 4).
Again, though, we need to keep careful track of what we are
assuming at any given moment. Suppose we tried to continue the
proof as follows:
1 A
2 B
3 C
4 A∧B ∧I 1, 2
5 C → (A ∧ B) →I 3–4
6 B → (C → (A ∧ B)) →I 2–5
7 C → (A ∧ B) naughty attempt
to invoke →I 3–4
This would be awful. If we tell you that Anne is smart, you should
not be able to infer that, if Cath is smart (symbolized by ‘C ’) then
both Anne is smart and Queen Boudica stood 20-feet tall! But this
is just what such a proof would suggest, if it were permissible.
The essential problem is that the subproof that began with
the assumption ‘C ’ depended crucially on the fact that we had
CHAPTER 15. BASIC RULES FOR TFL 121
1 A
2 B
3 C
4 B ∧C ∧I 2, 3
5 C ∧E 4
6 B →C naughty attempt
to invoke →I 2–5
3. its last line of the cited subproof must not occur in-
side a nested subproof.
1 A
2 B
3 C
4 B ∧C ∧I 2, 3
5 C ∧E 4
6 C naughty attempt
to invoke R 3–5
7 B →C →I 2–6
15.6 Biconditional
The rules for the biconditional will be like double-barrelled ver-
sions of the rules for the conditional.
In order to prove ‘W ↔ X ’, for instance, you must be able
to prove ‘X ’ on the assumption ‘W ’ and prove ‘W ’ on the as-
sumption ‘X ’. The biconditional introduction rule (↔I) there-
fore requires two subproofs. Schematically, the rule works like
this:
CHAPTER 15. BASIC RULES FOR TFL 124
i A
j B
k B
l A
A↔ B ↔I i – j , k –l
m A↔ B
n A
B ↔E m, n
and equally:
m A↔ B
n B
A ↔E m, n
Note that the biconditional, and the right or left half, can be
separated from one another, and they can appear in any order.
CHAPTER 15. BASIC RULES FOR TFL 125
15.7 Disjunction
Suppose Ludwig is reactionary. Then Ludwig is either reac-
tionary or libertarian. After all, to say that Ludwig is either reac-
tionary or libertarian is to say something weaker than to say that
Ludwig is reactionary.
Let’s emphasize this point. Suppose Ludwig is reactionary. It
follows that Ludwig is either reactionary or a kumquat. Equally, it
follows that either Ludwig is reactionary or that kumquats are the
only fruit. Equally, it follows that either Ludwig is reactionary or
that God is dead. Many of these are strange inferences to draw,
but there is nothing logically wrong with them (even if they maybe
violate all sorts of implicit conversational norms).
Armed with all this, we present the disjunction introduction
rule(s):
m A
A∨ B ∨I m
and
m A
B∨ A ∨I m
1 M
2 M ∨ ([(A ↔ B) → (C ∧ D)] ↔ [E ∧ F ]) ∨I 1
CHAPTER 15. BASIC RULES FOR TFL 126
Using a truth table to show this would have taken 128 lines.
The disjunction elimination rule is, though, slightly trickier.
Suppose that either Ludwig is reactionary or he is libertarian.
What can you conclude? Not that Ludwig is reactionary; it might
be that he is libertarian instead. Equally, not that Ludwig is liber-
tarian; for he might merely be reactionary. Disjunctions, just by
themselves, are hard to work with.
But suppose that we could somehow show both of the fol-
lowing: first, that Ludwig’s being reactionary entails that he is
an Austrian economist: second, that Ludwig’s being libertarian
entails that he is an Austrian economist. Then if we know that
Ludwig is either reactionary or libertarian, then we know that,
whichever he is, Ludwig is an Austrian economist. This insight
can be expressed in the following rule, which is our disjunction
elimination (∨E) rule:
m A∨ B
i A
j C
k B
l C
C ∨E m, i – j , k –l
1 (P ∧ Q ) ∨ (P ∧ R)
2 P ∧Q
3 P ∧E 2
4 P ∧R
5 P ∧E 4
6 P ∨E 1, 2–3, 4–5
A ∧ (B ∨ C ) .̇. (A ∧ B) ∨ (A ∧ C )
1 A ∧ (B ∨ C )
2 A ∧E 1
3 B ∨C ∧E 1
4 B
5 A∧B ∧I 2, 4
6 (A ∧ B) ∨ (A ∧ C ) ∨I 5
7 C
8 A ∧C ∧I 2, 7
9 (A ∧ B) ∨ (A ∧ C ) ∨I 8
10 (A ∧ B) ∨ (A ∧ C ) ∨E 3, 4–6, 7–9
CHAPTER 15. BASIC RULES FOR TFL 128
Don’t be alarmed if you think that you wouldn’t have been able
to come up with this proof yourself. The ability to come up with
novel proofs comes with practice, and we’ll cover some strategies
for finding proofs in §16. The key question at this stage is whether,
looking at the proof, you can see that it conforms to the rules that
we have laid down. That just involves checking every line, and
making sure that it is justified in accordance with the rules we
have laid down.
m ¬A
n A
⊥ ¬E m, n
It does not matter what order the sentence and its negation
appear in, and they do not need to appear on adjacent lines.
However, we always cite the line number of the negation first,
followed by that of the sentence it is a negation of.
There is obviously a tight link between contradiction and
negation. The rule ¬E lets us proceed from two contradictory
CHAPTER 15. BASIC RULES FOR TFL 129
i A
j ⊥
¬A ¬I i – j
CHAPTER 15. BASIC RULES FOR TFL 130
1 D
2 ¬D
3 ⊥ ¬E 2, 1
4 ¬¬D ¬I 2–3
i ¬A
j ⊥
A IP i – j
1 ¬¬D
2 ¬D
3 ⊥ ¬E 1, 2
4 D IP 2–3
m ⊥
A Xm
Practice exercises
A. The following two ‘proofs’ are incorrect. Explain the mistakes
they make.
1 (¬L ∧ A) ∨ L
2 ¬L ∧ A
3 ¬L ∧E 3
4 A ∧E 1
5 L
6 ⊥ ¬E 3, 5
7 A X6
8 A ∨E 1, 2–4, 5–7
3 There are some logicians who don’t buy this. They think that if A entails
B, there must be some relevant connection between A and B—and there isn’t
one between ⊥ and some arbitrary sentence B. So these logicians develop
other, “relevant” logics in which you aren’t allowed the explosion rule.
CHAPTER 15. BASIC RULES FOR TFL 133
1 A ∧ (B ∧ C )
2 (B ∨ C ) → D
3 B ∧E 1
4 B ∨C ∨I 3
5 D →E 4, 2
1 P ∧S 1 ¬L → ( J ∨ L)
2 S →R 2 ¬L
3 P 3 J ∨L
4 S 4 J
5 R 5 J ∧ J
6 R ∨E 6 J
7 L
1 A→D
8 ⊥
2 A∧B
9 J
3 A
10 J
4 D
5 D ∨E
6 (A ∧ B) → (D ∨ E)
1. J → ¬ J .̇. ¬ J
CHAPTER 15. BASIC RULES FOR TFL 134
2. Q → (Q ∧ ¬Q ) .̇. ¬Q
3. A → (B → C ) .̇. (A ∧ B) → C
4. K ∧ L .̇. K ↔ L
5. (C ∧ D) ∨ E .̇. E ∨ D
6. A ↔ B, B ↔ C .̇. A ↔ C
7. ¬F → G, F → H .̇. G ∨ H
8. (Z ∧ K ) ∨ (K ∧ M ), K → D .̇. D
9. P ∧ (Q ∨ R), P → ¬R .̇. Q ∨ E
10. S ↔ T .̇. S ↔ (T ∨ S )
11. ¬(P → Q ) .̇. ¬Q
12. ¬(P → Q ) .̇. P
CHAPTER 16
Constructing
proofs
There is no simple recipe for finding proofs, and there is no sub-
stitute for practice. Here, though, are some rules of thumb and
strategies to keep in mind.
135
CHAPTER 16. CONSTRUCTING PROOFS 136
1 P1
..
.
k Pk
..
.
n A
..
.
m B
m+1 A∧ B ∧I n, m
For ∧I, we need to prove A first, then prove B. For the last line,
we have to cite the lines where we (will have) proved A and B,
.
and use ∧I. The parts of the proof labelled .. have to still be filled
in. We’ll mark the line numbers m, n for now. When the proof is
complete, these placeholders can be replaced by actual numbers.
CHAPTER 16. CONSTRUCTING PROOFS 137
n A
..
.
m B
m+1 A→ B →I n–m
n A
..
.
m ⊥
m+1 ¬A ¬I n–m
However, you may not be able to prove the disjunct you picked.
.
In that case you have to backtrack. When you can’t fill in the ..,
delete everything, and try with the other disjunct:
..
.
n B
n+1 A∨ B ∨I n
rules for the main operators of these sentences. The form of the
rules will tell you what you’ll have to do.
n A∧ B
n+1 A ∧E n
n+2 B ∧E n
n A∨ B
n+1 A
..
.
m C
m+1 B
..
.
k C
k +1 C ∨E n, (n + 1)–m, (m + 1)–k
The first subproof starts with the first disjunct, A, and ends with
the sentence we’re looking for, C. The second subproof starts
with the other disjunct, B, and also ends with the goal sen-
tence C. Each of these subproofs have to be filled in further.
We can then justify the goal sentence C by using ∨E, citing the
line with A∨ B and the two subproofs.
n A→ B
..
.
m A
m+1 B →E n, m
CHAPTER 16. CONSTRUCTING PROOFS 141
n ¬A
..
.
m A
m+1 ⊥ ¬E n, m
1 (A ∧ B) ∨ (A ∧ C )
...
n A ∧ (B ∨ C )
We now have two options: either work backward from the con-
clusion, or work forward from the premise. We’ll pick the sec-
ond strategy: we use the disjunction on line 1, and set up the
subproofs we need for ∨E. The disjunction on line 1 has two dis-
juncts, A ∧ B and A ∧ C . The goal sentence you want to prove
is A ∧ (B ∨ C ). So in this case you have to set up two subproofs,
CHAPTER 16. CONSTRUCTING PROOFS 142
1 (A ∧ B) ∨ (A ∧ C )
2 A∧B
..
.
n A ∧ (B ∨ C )
n+1 A ∧C
..
.
m A ∧ (B ∨ C )
m+1 A ∧ (B ∨ C ) ∨E 1, 2–n, n + 1–m
You now have two separate tasks, namely to fill in each of the two
subproofs. In the first subproof, we now work backward from the
conclusion A ∧ (B ∨ C ). That is a conjunction, so inside the first
subproof, you will have two separate subgoals: proving A, and
proving B ∨C . These subgoals will let you justify line n using ∧I.
Your proof now looks like this:
CHAPTER 16. CONSTRUCTING PROOFS 143
1 (A ∧ B) ∨ (A ∧ C )
2 A∧B
..
.
i A
..
.
n−1 B ∨C
n A ∧ (B ∨ C ) ∧I i , n − 1
n+1 A ∧C
..
.
m A ∧ (B ∨ C )
m+1 A ∧ (B ∨ C ) ∨E 1, 2–n, (n + 1)–m
1 (A ∧ B) ∨ (A ∧ C )
2 A∧B
3 A ∧E 2
4 B ∧E 2
5 B ∨C ∨I 4
6 A ∧ (B ∨ C ) ∧I 3, 5
7 A ∧C
..
.
m A ∧ (B ∨ C )
m+1 A ∧ (B ∨ C ) ∨E 1, 2–6, 7–m
1 (A ∧ B) ∨ (A ∧ C )
2 A∧B
..
.
k A
k +1 A ∧C
..
.
n−1 A
n A ∨E 1, 2–k , (k + 1)–(n − 1)
n+1 A∧B
..
.
l B ∨C
l +1 A ∧C
..
.
m−1 B ∨C
m B ∨C ∨E 1, (n + 1)–l , (l + 1)–(m − 1)
m+1 A ∧ (B ∨ C ) ∧I n, m
.
We’ll leave you to fill in the missing pieces indicated by ...
Let’s give another example to illustrate how to apply the
strategies to deal with conditionals and negation. The sentence
(A → B) → (¬B → ¬A) is a tautology. Let’s see if we can find a
proof of it, from no premises, using the strategies. We first write
the sentence at the bottom of a sheet of paper. Since working
forward is not an option (there is nothing to work forward from),
we work backward, and set up a subproof to establish the sen-
tence we want (A → B) → (¬B → ¬A) using →I. Its assumption
CHAPTER 16. CONSTRUCTING PROOFS 146
1 A→B
..
.
n ¬B → ¬A
n+1 (A → B) → (¬B → ¬A) →I 1–n
1 A→B
2 ¬B
..
.
n−1 ¬A
n ¬B → ¬A →I 2–(n − 1)
n+1 (A → B) → (¬B → ¬A) →I 1–n
1 A→B
2 ¬B
3 A
..
.
n−2 ⊥
n−1 ¬A ¬I 3–(n − 2)
n ¬B → ¬A →I 2–(n − 1)
n+1 (A → B) → (¬B → ¬A) →I 1–n
1 A→B
2 ¬B
3 A
4 B →E 1, 3
5 ⊥ ¬E 2, 4
6 ¬A ¬I 3–5
7 ¬B → ¬A →I 2–6
8 (A → B) → (¬B → ¬A) →I 1–7
1 A∨B
2 ¬A
3 A
..
.
m B
m+1 B
..
.
k B
k +1 B ∨E 1, 3–m, (m + 1)–k
1 A∨B
2 ¬A
3 A
4 ⊥ ¬E 2, 3
5 B X4
6 B
7 B R6
8 B ∨E 1, 3–5, 6–7
CHAPTER 16. CONSTRUCTING PROOFS 150
n ¬A
..
.
m ⊥
m+1 A IP n–m
n ¬A
..
.
m−1 A
m ⊥ ¬E n, m − 1
m+1 A IP n–m
CHAPTER 16. CONSTRUCTING PROOFS 151
1 ¬(A ∨ ¬A)
..
.
m ⊥
m+1 A ∨ ¬A IP 1–m
1 ¬(A ∨ ¬A)
..
.
m−1 A ∨ ¬A
m ⊥ ¬E 1, m − 1
m+1 A ∨ ¬A IP 1–m
CHAPTER 16. CONSTRUCTING PROOFS 152
1 ¬(A ∨ ¬A)
2 A
..
.
m−3 ⊥
m−2 ¬A ¬I 2–(m − 3)
m−1 A ∨ ¬A ∨I m − 2
m ⊥ ¬E 1, m − 1
m+1 A ∨ ¬A IP 1–m
Inside this new subproof, we again need to justify ⊥. The best way
to do this is to work forward from a negated sentence; ¬(A ∨ ¬A)
on line 1 is the only negated sentence we can use. The corre-
sponding unnegated sentence, A ∨ ¬A, however, directly follows
from A (which we have on line 2) by ∨I. Our complete proof is:
CHAPTER 16. CONSTRUCTING PROOFS 153
1 ¬(A ∨ ¬A)
2 A
3 A ∨ ¬A ∨I 2
4 ⊥ ¬E 1, 3
5 ¬A ¬I 2–4
6 A ∨ ¬A ∨I 5
7 ⊥ ¬E 1, 6
8 A ∨ ¬A IP 1–7
Practice exercises
A. Use the strategies to find proofs for each of the following ar-
guments:
1. A → B, A → C .̇. A → (B ∧ C )
2. (A ∧ B) → C .̇. A → (B → C )
3. A → (B → C ) .̇. (A → B) → (A → C )
4. A ∨ (B ∧ C ) .̇. (A ∨ B) ∧ (A ∨ C )
5. (A ∧ B) ∨ (A ∧ C ) .̇. A ∧ (B ∨ C )
6. A ∨ B, A → C, B → D .̇. C ∨ D
7. ¬A ∨ ¬B .̇. ¬(A ∧ B)
8. A ∧ ¬B .̇. ¬(A → B)
1. ¬A → (A → ⊥)
2. ¬(A ∧ ¬A)
3. [(A → C ) ∧ (B → C )] → [(A ∨ B) → C ]
4. ¬(A → B) → (A ∧ ¬B)
CHAPTER 16. CONSTRUCTING PROOFS 154
5. (A ∨ ¬B) → (A → B)
1. ¬¬A → A
2. ¬A → ¬B .̇. B → A
3. A → B .̇. ¬A ∨ B
4. ¬(A ∧ B) → (¬A ∨ ¬B)
5. A → (B ∨ C ) .̇. (A → B) ∨ (A → C )
6. (A → B) ∨ (B → A)
7. ((A → B) → A) → A
These all will require the IP strategy. The last three especially
are quite hard!
CHAPTER 17
Additional
rules for TFL
In §15, we introduced the basic rules of our proof system for TFL.
In this section, we will add some additional rules to our system.
Our extended proof system is a bit easier to work with. (However,
in §19 we will see that they are not strictly speaking necessary.)
m A∨ B
n ¬A
B DS m, n
155
CHAPTER 17. ADDITIONAL RULES FOR TFL 156
and
m A∨ B
n ¬B
A DS m, n
m A→ B
n ¬B
¬A MT m, n
m ¬¬A
A DNE m
i A
j B
k ¬A
l B
B LEM i – j , k –l
P .̇. (P ∧ D) ∨ (P ∧ ¬D)
1 P
2 D
3 P ∧D ∧I 1, 2
4 (P ∧ D) ∨ (P ∧ ¬D) ∨I 3
5 ¬D
6 P ∧ ¬D ∧I 1, 5
7 (P ∧ D) ∨ (P ∧ ¬D) ∨I 6
8 (P ∧ D) ∨ (P ∧ ¬D) LEM 2–4, 5–7
1 A → ¬A
2 A
3 ¬A →E 1, 2
4 ¬A
5 ¬A R4
6 ¬A LEM 2–3, 4–5
m ¬(A∧ B)
¬A∨ ¬B DeM m
m ¬A∨ ¬B
¬(A∧ B) DeM m
m ¬(A∨ B)
¬A∧ ¬B DeM m
m ¬A∧ ¬B
¬(A∨ B) DeM m
These are all of the additional rules of our proof system for TFL.
Practice exercises
A. The following proofs are missing their citations (rule and line
numbers). Add them wherever they are required:
CHAPTER 17. ADDITIONAL RULES FOR TFL 161
1 W → ¬B
2 A ∧W
3 B ∨ ( J ∧ K)
1. 4 W
5 ¬B
6 J ∧K
7 K
1 L ↔ ¬O
2 L ∨ ¬O
3 ¬L
4 ¬O
2.
5 L
6 ⊥
7 ¬¬L
8 L
CHAPTER 17. ADDITIONAL RULES FOR TFL 162
1 Z → (C ∧ ¬N )
2 ¬Z → (N ∧ ¬C )
3 ¬(N ∨ C )
4 ¬N ∧ ¬C
5 ¬N
6 ¬C
7 Z
8 C ∧ ¬N
3.
9 C
10 ⊥
11 ¬Z
12 N ∧ ¬C
13 N
14 ⊥
15 ¬¬(N ∨ C )
16 N ∨C
1. E ∨ F , F ∨ G , ¬F .̇. E ∧ G
2. M ∨ (N → M ) .̇. ¬M → ¬N
3. (M ∨ N ) ∧ (O ∨ P ), N → P , ¬P .̇. M ∧ O
4. (X ∧ Y ) ∨ (X ∧ Z ), ¬(X ∧ D), D ∨ M .̇.M
CHAPTER 18
Proof-theoretic
concepts
In this chapter we will introduce some new vocabulary. The fol-
lowing expression:
A1, A2, . . . , An ⊢ C
means that there is some proof which starts with assumptions
among A1, A2, . . . , An and ends with C (and contains no undis-
charged assumptions other than those we started with). Deriva-
tively, we will write:
⊢A
to mean that there is a proof of A with no assumptions.
The symbol ‘⊢’ is called the single turnstile. We want to em-
phasize that this is not the double turnstile symbol (‘⊨’) that we
introduced in chapter 11 to symbolize entailment. The single
turnstile, ‘⊢’, concerns the existence of proofs; the double turn-
stile, ‘⊨’, concerns the existence of valuations (or interpretations,
when used for FOL). They are very different notions.
Armed with our ‘⊢’ symbol, we can introduce some more ter-
minology. To say that there is a proof of A with no undischarged
assumptions, we write: ⊢ A. In this case, we say that A is a
theorem.
163
CHAPTER 18. PROOF-THEORETIC CONCEPTS 164
A is a theorem iff ⊢ A
1 A ∧ ¬A
2 A ∧E 1
3 ¬A ∧E 1
4 ⊥ ¬E 3, 2
5 ¬(A ∧ ¬A) ¬I 1–4
Yes No
theorem? one proof all possible proofs
inconsistent? one proof all possible proofs
equivalent? two proofs all possible proofs
consistent? all possible proofs one proof
Practice exercises
A. Show that each of the following sentences is a theorem:
1. O →O
2. N ∨ ¬N
3. J ↔ [ J ∨ (L ∧ ¬L)]
4. ((A → B) → A) → A
1. C → (E ∧ G ), ¬C → G ⊢ G
2. M ∧ (¬N → ¬M ) ⊢ (N ∧ M ) ∨ ¬M
3. (Z ∧ K ) ↔ (Y ∧ M ), D ∧ (D → M ) ⊢ Y → Z
4. (W ∨ X ) ∨ (Y ∨ Z ), X → Y, ¬Z ⊢ W ∨ Y
1. R ↔ E, E ↔ R
2. G , ¬¬¬¬G
3. T → S , ¬S → ¬T
4. U → I , ¬(U ∧ ¬I )
5. ¬(C → D),C ∧ ¬D
6. ¬G ↔ H , ¬(G ↔ H )
Derived rules
In this section, we will see why we introduced the rules of our
proof system in two separate batches. In particular, we want to
show that the additional rules of §17 are not strictly speaking
necessary, but can be derived from the basic rules of §15.
m A
You now want to repeat yourself, on some line k . You could just
invoke the rule R. But equally well, you can do this with other
basic rules of §15:
m A
k A∧ A ∧I m, m
k +1 A ∧E k
167
CHAPTER 19. DERIVED RULES 168
m A∨ B
n ¬A
You now want, on line k , to prove B. You can do this with the
rule of DS, introduced in §17, but equally well, you can do this
with the basic rules of §15:
CHAPTER 19. DERIVED RULES 169
m A∨ B
n ¬A
k A
k +1 ⊥ ¬E n, k
k +2 B Xk +1
k +3 B
k +4 B Rk +3
k +5 B ∨E m, k –k + 2, k + 3–k + 4
So the DS rule, again, can be derived from our more basic rules.
Adding it to our system did not make any new proofs possible.
Anytime you use the DS rule, you could always take a few extra
lines and prove the same thing using only our basic rules. It is a
derived rule.
m A→ B
n ¬B
You now want, on line k , to prove ¬A. You can do this with the
rule of MT, introduced in §17. Equally well, you can do this with
the basic rules of §15:
CHAPTER 19. DERIVED RULES 170
m A→ B
n ¬B
k A
k +1 B →E m, k
k +2 ⊥ ¬E n, k + 1
k +3 ¬A ¬I k –k + 2
Again, the rule of MT can be derived from the basic rules of §15.
m ¬¬A
k ¬A
k +1 ⊥ ¬E m, k
k +2 A IP k –k + 1
Again, we can derive the DNE rule from the basic rules of §15.
m A
n B
k ¬A
l B
You now want, on line l + 1, to prove B. The rule LEM from §17
would allow you to do it. But can do this with the basic rules of
§15?
One option is to first prove A ∨ ¬A, and then apply ∨E, i.e.
proof by cases:
m A
n B
k ¬A
l B
..
.
i A∨ ¬A
i +1 B ∨E i , m–n, k –l
m ¬B
m+1 A
..
.
n B
n+1 ⊥ ¬E m, n
n+2 ¬A
..
.
l B
l +1 ⊥ ¬E m, l
l +2 ¬A ¬I (m + 1)–(n + 1)
l +3 ¬¬A ¬I (n + 2)–(l + 1)
l +4 ⊥ ¬E l + 3, l + 2
l +5 B IP m–(l + 4)
m ¬(A∧ B)
k A
k +1 B
k +2 A∧ B ∧I k , k + 1
k +3 ⊥ ¬E m, k + 2
k +4 ¬B ¬I k + 1–k + 3
k +5 ¬A∨ ¬B ∨I k + 4
k +6 ¬A
k +7 ¬A∨ ¬B ∨I k + 6
k +8 ¬A∨ ¬B LEM k –k + 5, k + 6–k + 7
m ¬A∨ ¬B
k A∧ B
k +1 A ∧E k
k +2 B ∧E k
k +3 ¬A
k +4 ⊥ ¬E k + 3, k + 1
k +5 ¬B
k +6 ⊥ ¬E k + 5, k + 2
k +7 ⊥ ∨E m, k + 3–k + 4, k + 5–k + 6
k +8 ¬(A∧ B) ¬I k –k + 7
CHAPTER 19. DERIVED RULES 174
Practice exercises
A. Provide proof schemes that justify the addition of the third
and fourth De Morgan rules as derived rules.
C. Give a proof of A ∨ ¬A. Then give a proof that uses only the
basic rules.
D. Show that if you had LEM as a basic rule, you could justify
IP as a derived rule. That is, suppose you had the proof:
m ¬A
...
n ⊥
How could you use it to prove A without using IP but with using
LEM as well as all the other basic rules?
E. Give a proof of the first De Morgan rule, but using only the
basic rules, in particular, without using LEM. (Of course, you can
combine the proof using LEM with the proof of LEM. Try to find
a proof directly.)
CHAPTER 20
Soundness
and
completeness
In §18, we saw that we could use derivations to test for the same
concepts we used truth tables to test for. Not only could we use
derivations to prove that an argument is valid, we could also use
them to test if a sentence is a tautology or a pair of sentences are
equivalent. We also started using the single turnstile the same
way we used the double turnstile. If we could prove that A was a
tautology with a truth table, we wrote ⊨ A, and if we could prove
it using a derivation, we wrote ⊢ A.
You may have wondered at that point if the two kinds of turn-
stiles always worked the same way. If you can show that A is a
tautology using truth tables, can you also always show that it is a
theorem using a derivation? Is the reverse true? Are these things
also true for valid arguments and pairs of equivalent sentences?
As it turns out, the answer to all these questions and many more
like them is yes. We can show this by defining all these concepts
separately and then proving them equivalent. That is, we imag-
175
CHAPTER 20. SOUNDNESS AND COMPLETENESS 176
ine that we actually have two notions of validity, valid⊨ and valid⊢
and then show that the two concepts always work the same way.
To begin with, we need to define all of our logical concepts
separately for truth tables and derivations. A lot of this work has
already been done. We handled all of the truth table definitions in
§11. We have also already given syntactic definitions for tautolo-
gies (theorems) and pairs of logically equivalent sentences. The
other definitions follow naturally. For most logical properties we
can devise a test using derivations, and those that we cannot test
for directly can be defined in terms of the concepts that we can
define.
For instance, we defined a theorem as a sentence that can
be derived without any premises (p. 164). Since the negation of
a contradiction is a tautology, we can define a syntactic con-
tradiction in tfl as a sentence whose negation can be derived
without any premises. The syntactic definition of a contingent
sentence is a little different. We don’t have any practical, finite
method for proving that a sentence is contingent using deriva-
tions, the way we did using truth tables. So we have to content
ourselves with defining “contingent sentence” negatively. A sen-
tence is syntactically contingent in tfl if it is not a theorem
or a contradiction.
A collection of sentences are provably inconsistent in tfl
if and only if one can derive a contradiction from them. Consis-
tency, on the other hand, is like contingency, in that we do not
have a practical finite method to test for it directly. So again,
we have to define a term negatively. A collection of sentences is
provably consistent in tfl if and only if they are not provably
inconsistent.
Finally, an argument is provably valid in tfl if and only if
there is a derivation of its conclusion from its premises. All of
these definitions are given in Table 20.1.
All of our concepts have now been defined both semantically
and syntactically. How can we prove that these definitions always
work the same way? A full proof here goes well beyond the scope
of this book. However, we can sketch what it would be like. We
Concept Truth table (semantic) definition Proof-theoretic (syntactic) definition
A sentence whose truth table only has Ts A sentence that can be derived without
Tautology
under the main connective any premises.
A sentence whose truth table only has Fs A sentence whose negation can be
Contradiction derived without any premises
under the main connective
Contingent sentence A sentence whose truth table contains A sentence that is not a theorem or
both Ts and Fs under the main connective contradiction
Equivalent sentences The columns under the main connectives The sentences can be derived from each
are identical. other
Unsatisfiable/ Sentences which do not have a single line Sentences from which one can derive a
inconsistent in their truth table where they are all true. contradiction
sentences
Satisfiable/ Sentences which have at least one line in Sentences from which one cannot derive
Consistent sentences their truth table where they are all true. a contradiction
An argument whose truth table has no
lines where there are all Ts under main An argument where one can derive the
CHAPTER 20. SOUNDNESS AND COMPLETENESS
Valid argument connectives for the premises and an F conclusion from the premises
under the main connective for the
conclusion.
Logical
To prove it present To prove it absent
property
Table 20.2: When to provide a truth table and when to provide a proof.
Practice exercises
A. Use either a derivation or a truth table for each of the follow-
ing.
10. Show that the sentences ¬(A ∨ B), ¬B, B → A are jointly
consistent.
First-order
logic
184
CHAPTER 21
Building
blocks of FOL
21.1 The need to decompose sentences
Consider the following argument, which is obviously valid in En-
glish:
L: Willard is a logician.
A: All logicians wear funny hats.
F : Willard wears a funny hat.
L, A .̇. F
185
CHAPTER 21. BUILDING BLOCKS OF FOL 186
give in TFL. The problem lies with TFL itself. ‘All logicians wear
funny hats’ is about both logicians and hat-wearing. By not re-
taining this structure in our symbolization, we lose the connec-
tion between Willard’s being a logician and Willard’s wearing a
hat.
The basic units of TFL are sentence letters, and TFL cannot
decompose these. To symbolize arguments like the preceding
one, we will have to develop a new logical language which will
allow us to split the atom. We will call this language first-order logic,
or FOL.
The details of FOL will be explained throughout this chapter,
but here is the basic idea for splitting the atom.
First, we have names. In FOL, we indicate these with lowercase
italic letters. For instance, we might let ‘b’ stand for Bertie, or let
‘i ’ stand for Willard.
Second, we have predicates. English predicates are expres-
sions like ‘ is a dog’ or ‘ is a logician’. These are not
complete sentences by themselves. In order to make a complete
sentence, we need to fill in the gap. We need to say something
like ‘Bertie is a dog’ or ‘Willard is a logician’. In FOL, we in-
dicate predicates with uppercase italic letters. For instance, we
might let the FOL predicate ‘D’ symbolize the English predicate
‘ is a dog’. Then the expression ‘D(b)’ will be a sentence
in FOL, which symbolizes the English sentence ‘Bertie is a dog’.
Equally, we might let the FOL predicate ‘L’ symbolize the En-
glish predicate ‘ is a logician’. Then the expression ‘L(i )’
will symbolize the English sentence ‘Willard is a logician’.
Third, we have quantifiers. For instance, ‘∃’ will roughly con-
vey ‘There is at least one . . . ’. So we might symbolize the English
sentence ‘there is a dog’ with the FOL sentence ‘∃x D(x)’, which
we would naturally read out-loud as ‘there is at least one thing,
x, such that x is a dog’.
That is the general idea, but FOL is significantly more subtle
than TFL, so we will come at it slowly.
CHAPTER 21. BUILDING BLOCKS OF FOL 187
21.2 Names
In English, a singular term is a word or phrase that refers to a
specific person, place, or thing. The word ‘dog’ is not a singular
term, because there are a great many dogs. The phrase ‘Bertie’
is a singular term, because it refers to a specific terrier. Likewise,
the phrase ‘Philip’s dog Bertie’ is a singular term, because it refers
to a specific little terrier.
Proper names are a particularly important kind of singular
term. These are expressions that pick out individuals without
describing them. The name ‘Emerson’ is a proper name, and
the name alone does not tell you anything about Emerson. Of
course, some names are traditionally given to boys and other are
traditionally given to girls. If ‘Hilary’ is used as a singular term,
you might guess that it refers to a woman. You might, though, be
guessing wrongly. Indeed, the name does not necessarily mean
that the person referred to is even a person: Hilary might be a
giraffe, for all you could tell just from the name.
In FOL, our names are lower-case letters ‘a’ through to ‘r ’.
We can add subscripts if we want to use some letter more than
once. So here are some singular terms in FOL:
e : Elsa
CHAPTER 21. BUILDING BLOCKS OF FOL 188
g : Gregor
m: Marybeth
21.3 Predicates
The simplest predicates are properties of individuals. They are
things you can say about an object. Here are some examples of
English predicates:
is a dog
is a member of Monty Python
A piano fell on
A(x): x is angry
H (x): x is happy
1. Elsa is angry.
CHAPTER 21. BUILDING BLOCKS OF FOL 189
21.4 Quantifiers
We are now ready to introduce quantifiers. Consider these sen-
tences:
4. Everyone is happy.
5. Someone is angry.
It might be tempting to symbolize sentence 4 as ‘H (e ) ∧ H (g ) ∧
H (m)’. Yet this would only say that Elsa, Gregor, and Marybeth
are happy. We want to say that everyone is happy, even those with
no names. In order to do this, we introduce the ‘∀’ symbol. This
is called the universal quantifier.
A quantifier must always be followed by a variable. In FOL,
variables are italic lowercase letters ‘s ’ through ‘z ’, with or with-
out subscripts. So we might symbolize sentence 4 as ‘∀x H (x)’.
The variable ‘x’ is serving as a kind of placeholder. The ex-
pression ‘∀x’ intuitively means that you can pick anyone and put
them in as ‘x’. The subsequent ‘H (x)’ indicates, of that thing you
picked out, that it is happy.
It should be pointed out that there is no special reason to
use ‘x’ rather than some other variable. The sentences ‘∀x H (x)’,
‘∀y H (y)’, ‘∀z H (z )’, and ‘∀x 5H (x 5 )’ use different variables, but
they will all be logically equivalent.
CHAPTER 21. BUILDING BLOCKS OF FOL 190
6. No one is angry.
7. There is someone who is not happy.
8. Not everyone is happy.
Sentence 6 can be paraphrased as, ‘It is not the case that some-
one is angry’. We can then symbolize it using negation and
an existential quantifier: ‘¬∃x A(x)’. Yet sentence 6 could also
be paraphrased as, ‘Everyone is not angry’. With this in mind,
it can be symbolized using negation and a universal quantifier:
‘∀x ¬A(x)’. Both of these are acceptable symbolizations. Indeed,
it will transpire that, in general, ∀x ¬A is logically equivalent to
¬∃x A. (Notice that we have here returned to the practice of us-
ing ‘A’ as a metavariable, from §7.) Symbolizing a sentence one
way, rather than the other, might seem more ‘natural’ in some
contexts, but it is not much more than a matter of taste.
Sentence 7 is most naturally paraphrased as, ‘There is some x,
such that x is not happy’. This then becomes ‘∃x ¬H (x)’. Of
course, we could equally have written ‘¬∀x H (x)’, which we would
naturally read as ‘it is not the case that everyone is happy’. That
too would be a perfectly adequate symbolization of sentence 8.
21.5 Domains
Given the symbolization key we have been using, ‘∀x H (x)’ sym-
bolizes ‘Everyone is happy’. Who is included in this everyone?
CHAPTER 21. BUILDING BLOCKS OF FOL 191
The quantifiers range over the domain. Given this domain, ‘∀x’ is
to be read roughly as ‘Every person in Chicago is such that. . . ’
and ‘∃x’ is to be read roughly as ‘Some person in Chicago is such
that. . . ’.
In FOL, the domain must always include at least one thing.
Moreover, in English we can infer ‘something is angry’ from ‘Gre-
gor is angry’. In FOL, then, we will want to be able to infer
‘∃x A(x)’ from ‘A(g )’. So we will insist that each name must pick
out exactly one thing in the domain. If we want to name people
in places beside Chicago, then we need to include those people
in the domain.
Even allowing for a domain with just one member can pro-
duce some strange results. Suppose we have this as a symboliza-
tion key:
Non-referring terms
In FOL, each name must pick out exactly one member of the
domain. A name cannot refer to more than one thing—it is a
singular term. Each name must still pick out something. This is
connected to a classic philosophical problem: the so-called prob-
lem of non-referring terms.
Medieval philosophers typically used sentences about the
chimera to exemplify this problem. Chimera is a mythological
creature; it does not really exist. Consider these two sentences:
9. Chimera is angry.
10. Chimera is not angry.
It is tempting just to define a name to mean ‘chimera.’ The sym-
bolization key would look like this:
domain: creatures on Earth
A(x): x is angry.
c : chimera
We could then symbolize sentence 9 as A(c ) and sentence 10 as
¬A(c ).
Problems will arise when we ask whether these sentences are
true or false.
One option is to say that sentence 9 is not true, because there
is no chimera. If sentence 9 is false because it talks about a non-
existent thing, then sentence 10 is false for the same reason. Yet
this would mean that A(c ) and ¬A(c ) would both be false. Given
the truth conditions for negation, this cannot be the case.
Since we cannot say that they are both false, what should
we do? Another option is to say that sentence 9 is meaningless
CHAPTER 21. BUILDING BLOCKS OF FOL 193
Sentences with
one quantifier
We now have all of the pieces of FOL. Symbolizing more compli-
cated sentences will only be a matter of knowing the right way to
combine predicates, names, quantifiers, and connectives. There
is a knack to this, and there is no substitute for practice.
194
CHAPTER 22. SENTENCES WITH ONE QUANTIFIER 195
domain: animals
M (x): x is a monkey.
S (x): x knows sign language.
R(x): x is a refrigerator
Our domain must now include both all the roses (so that we can
symbolize sentence 7) and all the cowboys (so that we can sym-
bolize sentence 8). So we might offer the following symbolization
key:
domain: people
B(x): x is a bassist.
R(x): x is a rock star.
k : Kim Deal
l : Lars
Ambiguous predicates
Suppose we just want to symbolize this sentence:
domain: people
G (x): x is greedy.
H (x): The hospital will hire x.
R(x): x is a surgeon.
K (x): x is skilled.
b: Billy
(R(c ) ∧ K (c )) ∧ T (c )
.̇. T (c ) ∧ K (c )
(R(c ) ∧ K1 (c )) ∧ T (c )
.̇. T (c ) ∧ K2 (c )
Practice exercises
A. Here are the syllogistic figures identified by Aristotle and his
successors, along with their medieval names:
domain: people
K (x): x knows the combination to the safe
S (x): x is a spy
V (x): x is a vegetarian
h: Hofthor
i : Ingmar
Multiple
generality
So far, we have only considered sentences that require one-place
predicates and one quantifier. The full power of FOL really comes
out when we start to use many-place predicates and multiple
quantifiers. For this insight, we largely have Gottlob Frege (1879)
to thank, but also C.S. Peirce.
loves
is to the left of
is in debt to
207
CHAPTER 23. MULTIPLE GENERALITY 208
borrowed from
domain: people
i : Imre
k : Karl
L(x, y): x loves y
The moral is: take great care with the order of quantification.
something like:
[︁ ]︁
∀x F (x, g ) → ∃z (D(z ) ∧ O (x, z ))
Note that we have used the same letter, ‘z ’, in both the antecedent
and the consequent of the conditional, but that these are gov-
erned by two different quantifiers. This is ok: there is no clash
here, because it is clear which quantifier that variable falls under.
We might graphically represent the scope of the quantifiers thus:
scope of ‘∀x’
⏟ˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉ⏞⏞ˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉ⏟
scope of ‘∃y’
⏟ˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉ⏞⏞ˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉ⏟
scope of 1st ‘∃z ’ scope of 2nd ‘∃z ’
[︁⏟ˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉ⏞⏞ˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉ⏟ ⏟ˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉ⏞⏞ˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉ⏟ ]︁
∀x ∃z (D(z ) ∧ O (x, z )) → ∃y(∃z (D(z ) ∧ O (y, z )) ∧F (x, y))
Practice exercises
A. Using this symbolization key:
domain: candies
C (x): x has chocolate in it.
M (x): x has marzipan in it.
S (x): x has sugar in it.
T (x): Boris has tried x.
B(x, y): x is better than y.
domain: people
D(x): x dances ballet.
F (x): x is female.
M (x): x is male.
C (x, y): x is a child of y.
S (x, y): x is a sibling of y.
e: Elmer
j: Jane
p: Patrick
Identity
Consider this sentence:
we can symbolize sentence 1 by ‘∀x O (p, x)’. But this has a (per-
haps) odd consequence. It requires that Pavel owes money to ev-
ery member of the domain (whatever the domain may be). The
domain certainly includes Pavel. So this entails that Pavel owes
money to himself.
Perhaps we meant to say:
but we do not know how to deal with the italicised words yet.
The solution is to add another symbol to FOL.
221
CHAPTER 24. IDENTITY 222
x = y: x is identical to y
This does not mean merely that the objects in question are in-
distinguishable, or that all of the same things are true of them.
Rather, it means that the objects in question are the very same
object.
Now suppose we want to symbolize this sentence:
c : Mister Checkov
A(x): x is an apple
Sentence 11 can be paraphrased as, ‘It is not the case that there
are at least two apples’. This is just the negation of sentence 9:
¬∃x∃y[(A(x) ∧ A(y)) ∧ ¬x = y]
∃x∃y((A(x) ∧ A(y)) ∧ ¬x = y) ∧
∀x∀y∀z ((A(x) ∧ A(y)) ∧ A(z )) → ((x = y ∨ x = z ) ∨ y = z )
[︁ ]︁
Practice exercises
A. Explain why:
Definite
descriptions
Consider sentences like:
1. Nick is the traitor.
2. The traitor went to Cambridge.
3. The traitor is the deputy
These are definite descriptions: they are meant to pick out a
unique object. They should be contrasted with indefinite descrip-
tions, such as ‘Nick is a traitor’. They should equally be con-
trasted with generics, such as ‘The whale is a mammal’ (it’s in-
appropriate to ask which whale). The question we face is: how
should we deal with definite descriptions in FOL?
227
CHAPTER 25. DEFINITE DESCRIPTIONS 228
∃x∃y T (x) ∧ ∀z (T (z ) → x = z ) ∧
(︁ [︁ ]︁
D(y) ∧ ∀z (D(z ) → y = z ) ∧ x = y
[︁ ]︁ )︁
Note that we have made sure that the formula ‘x = y’ falls within
the scope of both quantifiers!
CHAPTER 25. DEFINITE DESCRIPTIONS 230
a: Alex
K (x): x is a present king of France
D(x, y): x is dating y
call this outer negation, since the negation governs the entire sen-
tence. Note that it will be true if there is no present King of
France.
Sentence 6 can be symbolized by ‘∃x((K (x) ∧ ∀y(K (y) → x =
y)) ∧ ¬D(a, x))’. We might call this inner negation, since the nega-
tion occurs within the scope of the definite description. Note that
its truth requires that there is a present King of France, albeit one
who is not dating Alex.
identity.4 Two men stand in the corner: a very tall man drinking
what looks like a gin martini; and a very short man drinking what
looks like a pint of water. Seeing them, Malika says:
7′. There is exactly one gin-drinker [in the corner], and who-
ever is a gin-drinker [in the corner] is very tall.
Now suppose that the very tall man is actually drinking water
from a martini glass; whereas the very short man is drinking a
pint of (neat) gin. By Russell’s analysis, Malika has said some-
thing false, but don’t we want to say that Malika has said some-
thing true?
Again, one might wonder how clear our intuitions are on this
case. We can all agree that Malika intended to pick out a partic-
ular man, and say something true of him (that he was tall). On
Russell’s analysis, she actually picked out a different man (the
short one), and consequently said something false of him. But
maybe advocates of Russell’s analysis only need to explain why
Malika’s intentions were frustrated, and so why she said some-
thing false. This is easy enough to do: Malika said something
false because she had false beliefs about the men’s drinks; if Ma-
lika’s beliefs about the drinks had been true, then she would have
said something true.5
To say much more here would lead us into deep philosophical
waters. That would be no bad thing, but for now it would distract
us from the immediate purpose of learning formal logic. So, for
now, we will stick with Russell’s analysis of definite descriptions,
when it comes to putting things into FOL. It is certainly the best
4 Keith Donnellan, ‘Reference and Definite Descriptions’, 1966, Philosophi-
cal Review 77, pp. 281–304.
5 Interested parties should read Saul Kripke, ‘Speaker Reference and Se-
mantic Reference’, 1977, in French et al (eds.), Contemporary Perspectives in the
Philosophy of Language, Minneapolis: University of Minnesota Press, pp. 6-27.
CHAPTER 25. DEFINITE DESCRIPTIONS 233
Practice exercises
A. Using the following symbolization key:
domain: people
K (x): x knows the combination to the safe.
S (x): x is a spy.
V (x): x is a vegetarian.
T (x, y): x trusts y.
h: Hofthor
i : Ingmar
W (x): x is wild.
Sentences of
FOL
We know how to represent English sentences in FOL. The time
has finally come to define the notion of a sentence of FOL.
26.1 Expressions
There are six kinds of symbols in FOL:
Connectives ¬, ∧, ∨, →, ↔
Brackets ( , )
Quantifiers ∀, ∃
236
CHAPTER 26. SENTENCES OF FOL 237
a, b, x, x 1 x 2, y, y 254, z
D F (a)
x =a G (x, a, y)
a =b G (a, a, a)
F (x) S (x 1, x 2, a, b, y, x 1 )
F (x)
G (a, y, z )
S (y, z, y, a, y, x)
(G (a, y, z ) → S (y, z, y, a, y, x))
∀z (G (a, y, z ) → S (y, z, y, a, y, x))
F (x) ∧ ∀z (G (a, y, z ) → S (y, z, y, a, y, x))
∃y(F (x) ∧ ∀z (G (a, y, z ) → S (y, z, y, a, y, x)))
∀x∃y(F (x) ∧ ∀z (G (a, y, z ) → S (y, z, y, a, y, x)))
26.3 Sentences
Recall that we are largely concerned in logic with assertoric sen-
tences: sentences that can be either true or false. Many formulas
are not sentences. Consider the following symbolization key:
domain: people
L(x, y): x loves y
b: Boris
Consider the atomic formula ‘L(z, z )’. All atomic formula are
formulas, so ‘L(z, z )’ is a formula, but can it be true or false? You
might think that it will be true just in case the person named by
‘z ’ loves themself, in the same way that ‘L(b, b)’ is true just in case
Boris (the person named by ‘b’) loves himself. However, ‘z ’ is a
variable, and does not name anyone or any thing.
Of course, if we put an existential quantifier out front, obtain-
ing ‘∃z L(z, z )’, then this would be true iff someone loves themself.
Equally, if we wrote ‘∀z L(z, z )’, this would be true iff everyone
loves themself. The point is that we need a quantifier to tell us
how to deal with a variable.
Let’s make this idea precise.
Practice exercises
A. Identify which variables are bound and which are free.
1. ∃x L(x, y) ∧ ∀y L(y, x)
2. ∀x A(x) ∧ B(x)
3. ∀x(A(x) ∧ B(x)) ∧ ∀y(C (x) ∧ D(y))
4. ∀x∃y[R(x, y) → ( J (z ) ∧ K (x))] ∨ R(y, x)
5. ∀x 1 (M (x 2 ) ↔ L(x 2, x 1 )) ∧ ∃x 2 L(x 3, x 2 )
PART VI
Interpretations
242
CHAPTER 27
Extensionality
Recall that TFL is a truth-functional language. Its connectives
are all truth-functional, and all that we can do with TFL is key
sentences to particular truth values. We can do this directly. For
example, we might stipulate that the TFL sentence ‘P ’ is to be
true. Alternatively, we can do this indirectly, offering a symbol-
ization key, e.g.:
243
CHAPTER 27. EXTENSIONALITY 244
So, in particular:
Justin Trudeau
the number π
every top-F key on every piano ever made
j : Justin Trudeau
a: Angela Merkel
p: the number π
So, in particular:
⟨Lenin, Marx⟩
⟨de Beauvoir, Sartre⟩
⟨Sartre, de Beauvoir⟩
l: Lenin
m: Marx
b: de Beauvoir
r: Sartre
Then ‘B(l, m)’ will be true, since ⟨Lenin, Marx⟩ was in our ex-
plicit list, but ‘B(m, l )’ will be false, since ⟨Marx, Lenin⟩ was not
in our list. However, both ‘B(b, r )’ and ‘B(r, b)’ will be true, since
both ⟨de Beauvoir, Sartre⟩ and ⟨Sartre, de Beauvoir⟩ are in our
explicit list.
To make these ideas more precise, we would need to develop
some set theory. That would give us some precise tools for dealing
CHAPTER 27. EXTENSIONALITY 247
with extensions and with ordered pairs (and ordered triples, etc.).
However, set theory is not covered in this book, so we will leave
these ideas at an imprecise level. Nevertheless, the general idea
should be clear.
A(a) ↔ A(b)
B(a) ↔ B(b)
R(a, a) ↔ R(b, b)
R(a, a) ↔ R(a, b)
R(c, a) ↔ R(c, b)
∀x R(x, a) ↔ ∀x R(x, b)
27.5 Interpretations
We defined a valuation in TFL as any assignment of truth and
falsity to sentence letters. In FOL, we are going to define an
interpretation as consisting of four things:
1 2
4 3
1 2
4 3
Truth in FOL
We know what interpretations are. Since, among other things,
they tell us which predicates are true of which objects, they will
provide us with an account of the truth of atomic sentences. How-
ever, we must also present a detailed account of what it is for an
arbitrary FOL sentence to be true or false in an interpretation.
We know from §26 that there are three kinds of sentence in
FOL:
• atomic sentences
• sentences whose main logical operator is a sentential con-
nective
• sentences whose main logical operator is a quantifier
250
CHAPTER 28. TRUTH IN FOL 251
are exactly the same as they were when we considered TFL. Here
they are:
• ‘a = a ∧ P (a)’ is true
• ‘R(a, b) ∧ P (b)’ is false because, although ‘R(a, b)’ is true,
‘P (b)’ is false
• ‘a = b ∨ P (a)’ is true
• ‘¬a = b’ is true
• ‘P (a) ∧ ¬(a = b ∧ R(a, b))’ is true, because ‘P (a)’ is true and
‘a = b’ is false
A(. . . c . . . c . . .)
∃x(R(e, x) ↔ F (x))
is a substitution instance of
∀y∃x(R(y, x) ↔ F (x))
For atomic formulas, the objects, pairs of objects, etc., that sat-
isfy them are exactly the extension of the predicate given in the
interpretation. But the notion of satisfaction also applies to non-
CHAPTER 28. TRUTH IN FOL 257
Practice exercises
A. Consider the following interpretation:
1. B(c )
2. A(c ) ↔ ¬N (c )
3. N (c ) → (A(c ) ∨ B(c ))
4. ∀x A(x)
5. ∀x¬B(x)
6. ∃x(A(x) ∧ B(x))
7. ∃x(A(x) → N (x))
8. ∀x(N (x) ∨ ¬N (x))
9. ∃x B(x) → ∀x A(x)
• ‘e ’ is to refer to Eddy
1. H (c )
2. H (e )
3. M (c ) ∨ M (e )
4. G (c ) ∨ ¬G (c )
5. M (c ) → G (c )
6. ∃x H (x)
7. ∀x H (x)
8. ∃x ¬M (x)
9. ∃x(H (x) ∧ G (x))
10. ∃x(M (x) ∧ G (x))
11. ∀x(H (x) ∨ M (x))
12. ∃x H (x) ∧ ∃x M (x)
13. ∀x(H (x) ↔ ¬M (x))
14. ∃x G (x) ∧ ∃x¬G (x)
15. ∀x∃y(G (x) ∧ H (y))
1 2
3 4 5
1. ∃x R(x, x)
2. ∀x R(x, x)
3. ∃x∀y R(x, y)
4. ∃x∀y R(y, x)
CHAPTER 28. TRUTH IN FOL 259
Semantic
concepts
Offering a precise definition of truth in FOL was more than a lit-
tle fiddly, but now that we are done, we can define various central
logical notions. These will look very similar to the definitions we
offered for TFL. However, remember that they concern interpre-
tations, rather than valuations.
We will use the symbol ‘⊨’ for FOL much as we did for TFL.
So:
A1, A2, . . . , An ⊨ C
means that there is no interpretation in which all of A1 , A2 , . . . ,
An are true and in which C is false. Derivatively,
⊨A
means that A is true in every interpretation.
The other logical notions also have corresponding definitions
in FOL:
260
CHAPTER 29. SEMANTIC CONCEPTS 261
Using
interpretations
30.1 Validities and contradictions
Suppose we want to show that ‘∃x A(x, x) → B(d )’ is not a valid-
ity. This requires showing that the sentence is not true in every
interpretation; i.e., that it is false in some interpretation. If we
can provide just one interpretation in which the sentence is false,
then we will have shown that the sentence is not a validity.
In order for ‘∃x A(x, x) → B(d )’ to be false, the antecedent
(‘∃x A(x, x)’) must be true, and the consequent (‘B(d )’) must be
false. To construct such an interpretation, we start by specifying
a domain. Keeping the domain small makes it easier to specify
what the predicates will be true of, so we will start with a domain
that has just one member. For concreteness, let’s say it is the city
of Paris.
domain: Paris
d : Paris
262
CHAPTER 30. USING INTERPRETATIONS 263
Recall that we want ‘∃x A(x, x)’ to be true, so we want all members
of the domain to be paired with themselves in the extension of
‘A’. We can just offer:
A(x, y): x is identical with y
Now ‘A(d, d )’ is true, so it is surely true that ‘∃x A(x, x)’. Next,
we want ‘B(d )’ to be false, so the referent of ‘d ’ must not be in
the extension of ‘B’. We might simply offer:
B(x): x is in Germany
Now we have an interpretation where ‘∃x A(x, x)’ is true, but
where ‘B(d )’ is false. So there is an interpretation where
‘∃x A(x, x) → B(d )’ is false. So ‘∃x A(x, x) → B(d )’ is not a valid-
ity.
We can just as easily show that ‘∃xA(x, x) → B(d )’ is not a
contradiction. We need only specify an interpretation in which
‘∃xA(x, x) → B(d )’ is true; i.e., an interpretation in which either
‘∃x A(x, x)’ is false or ‘B(d )’ is true. Here is one:
domain: Paris
d : Paris
A(x, y): x is identical with y
B(x): x is in France
This shows that there is an interpretation where ‘∃xA(x, x) →
B(d )’ is true. So ‘∃x A(x, x) → B(d )’ is not a contradiction.
which the two sentences have different truth values; we want one
of them to be true and the other to be false. We start by specifying
a domain. Again, we make the domain small so that we can
specify extensions easily. In this case, we will need at least two
objects. (If we chose a domain with only one member, the two
sentences would end up with the same truth value. In order to
see why, try constructing some partial interpretations with one-
member domains.) For concreteness, let’s take:
To show that this is invalid, we must make the premise true and
the conclusion false. The conclusion is a conditional, so to make
it false, the antecedent must be true and the consequent must be
false. Clearly, our domain must contain two objects. Let’s try:
1 2
Practice exercises
A. Show that each of the following is neither a validity nor a
contradiction:
1. D(a) ∧ D(b)
2. ∃x T (x, h)
3. P (m) ∧ ¬∀x P (x)
4. ∀z J (z ) ↔ ∃y J (y)
5. ∀x(W (x, m, n) ∨ ∃yL(x, y))
6. ∃x(G (x) → ∀y M (y))
7. ∃x(x = h ∧ x = i )
1. J (a), K (a)
CHAPTER 30. USING INTERPRETATIONS 268
2. ∃x J (x), J (m)
3. ∀x R(x, x), ∃x R(x, x)
4. ∃x P (x) → Q (c ), ∃x(P (x) → Q (c ))
5. ∀x(P (x) → ¬Q (x)), ∃x(P (x) ∧ ¬Q (x))
6. ∃x(P (x) ∧ Q (x)), ∃x(P (x) → Q (x))
7. ∀x(P (x) → Q (x)), ∀x(P (x) ∧ Q (x))
8. ∀x∃y R(x, y), ∃x∀y R(x, y)
9. ∀x∃y R(x, y), ∀x∃y R(y, x)
C. Show that the following sentences are jointly satisfiable:
1. M (a), ¬N (a), P (a), ¬Q (a)
2. L(e, e ), L(e, g ), ¬L(g , e ), ¬L(g , g )
3. ¬(M (a) ∧ ∃x A(x)), M (a) ∨ F (a), ∀x(F (x) → A(x))
4. M (a) ∨ M (b), M (a) → ∀x¬M (x)
5. ∀y G (y), ∀x(G (x) → H (x)), ∃y¬I [︁ (y)
6.
]︁
∃x(B(x) ∨ A(x)), ∀x¬C (x), ∀x (A(x) ∧ B(x)) → C (x)
7. ∃x X (x), ∃x Y (x), ∀x(X (x) ↔ ¬Y (x))
8. ∀x(P (x) ∨ Q (x)), ∃x¬(Q (x) ∧ P (x))
9. ∃z (N (z ) ∧ O (z, z )), ∀x∀y(O (x, y) → O (y, x))
10. ¬∃x∀y R(x, y), ∀x∃y R(x, y)
11. ¬R(a, a), ∀x(x = a ∨ R(x, a))
12. ∀x∀y∀z [(x = y ∨ y = z ) ∨ x = z ], ∃x∃y ¬x = y
13. ∃x∃y((Z (x) ∧ Z (y)) ∧ x = y), ¬Z (d ), d = e
D. Show that the following arguments are invalid:
1. ∀x(A(x) → B(x)) .̇. ∃x B(x)
2. ∀x(R(x) → D(x)), ∀x(R(x) → F (x)) .̇. ∃x(D(x) ∧ F (x))
3. ∃x(P (x) → Q (x)) .̇. ∃x P (x)
4. N (a) ∧ N (b) ∧ N (c ) .̇. ∀x N (x)
5. R(d )e, ∃x R(x, d ) .̇. R(e, d )
6. ∃x(E(x) ∧ F (x)), ∃x F (x) → ∃x G (x) .̇. ∃x(E(x) ∧ G (x))
7. ∀x O (x, c ), ∀x O (c, x) .̇. ∀x O (x, x)
8. ∃x( J (x) ∧ K (x)), ∃x¬K (x), ∃x¬ J (x) .̇. ∃x(¬ J (x) ∧ ¬K (x))
9. L(a)b → ∀x L(x, b), ∃x L(x, b) .̇. L(b, b)
10. ∀x(D(x) → ∃y T (y, x)) .̇. ∃y∃z ¬y = z
CHAPTER 31
Reasoning
about all
interpretations
31.1 Validities and contradictions
We can show that a sentence is not a validity just by providing
one carefully specified interpretation: an interpretation in which
the sentence is false. To show that something is a validity, on the
other hand, it would not be enough to construct ten, one hundred,
or even a thousand interpretations in which the sentence is true.
A sentence is only a validity if it is true in every interpretation,
and there are infinitely many interpretations. We need to reason
about all of them, and we cannot do this by dealing with them
one by one!
Sometimes, we can reason about all interpretations fairly eas-
ily. For example, we can offer a relatively simple argument that
‘R(a, a) ∨ ¬R(a, a)’ is a validity:
269
CHAPTER 31. REASONING ABOUT INTERPRETATIONS 270
The problem is that, with the tools available to you so far, rea-
soning about all interpretations is a serious challenge! Let’s take
just one more example. Here is an argument which is obviously
valid:
∀x(H (x) ∧ J (x)) .̇. ∀x H (x)
After all, if everything is both H and J , then everything is H .
But we can only show that the argument is valid by considering
CHAPTER 31. REASONING ABOUT INTERPRETATIONS 272
Even for a simple argument like this one, the reasoning is some-
what complicated. For longer arguments, the reasoning can be
extremely torturous.
The following table summarises whether a single interpreta-
tion or counter-interpretation suffices, or whether we must reason
about all interpretations.
Yes No
validity? all interpretations one counter-interpretation
contradiction? all interpretations one counter-interpretation
equivalent? all interpretations one counter-interpretation
satisfiable? one interpretation all interpretations
valid? all interpretations one counter-interpretation
entailment? all interpretations one counter-interpretation
Natural
deduction for
FOL
274
CHAPTER 32
1 ∀x R(x, x, d )
2 R(a, a, d ) ∀E 1
275
CHAPTER 32. BASIC RULES FOR FOL 276
1 ∀x R(x, x, d )
2 R(d, d, d ) ∀E 1
m ∀x A(. . . x . . . x . . .)
A(. . . c . . . c . . .) ∀E m
1 ∀x B(x) → B(k )
2 B(b) → B(k ) naughy attempt to invoke ∀E 1
1 R(a, a, d )
2 ∃x R(a, a, x) ∃I 1
CHAPTER 32. BASIC RULES FOR FOL 277
Here, we have replaced the name ‘d ’ with a variable ‘x’, and then
existentially quantified over it. Equally, we would have allowed:
1 R(a, a, d )
2 ∃x R(x, x, d ) ∃I 1
1 R(a, a, d )
2 ∃x R(x, a, d ) ∃I 1
Here we have replaced one instance of the name ‘a’ with a vari-
able, and then existentially generalised. These observations mo-
tivate our introduction rule, although to explain it, we will need
to introduce some new notation.
Where A is a sentence containing the name c, we can
emphasize this by writing ‘A(. . . c . . . c . . .)’. We will write
‘A(. . . x . . . c . . .)’ to indicate any formula obtained by replacing
some or all of the instances of the name c with the variable x.
Armed with this, our introduction rule is:
m A(. . . c . . . c . . .)
∃x A(. . . x . . . c . . .) ∃I m
1 R(a, a, d )
2 ∃x R(x, a, d ) ∃I 1
3 ∃y∃x R(x, y, d ) ∃I 2
1 R(a, a, d )
2 ∃x R(x, a, d ) ∃I 1
3 ∃x ∃x R(x, x, d ) naughty attempt to invoke ∃I 2
1 ∀x F (x)
2 F (a) ∀E 1
3 ∃x F (x) ∃I 2
1 ∀x F (x)
2 F (a) ∀E 1
1 ∀x F (x)
2 F (a) ∀E 1
3 ∀y F (y) ∀I 2
The crucial thought here is that ‘a’ was just some arbitrary name.
There was nothing special about it—we might have chosen any
CHAPTER 32. BASIC RULES FOR FOL 281
other name—and still the proof would be fine. And this crucial
thought motivates the universal introduction rule (∀I):
m A(. . . c . . . c . . .)
∀x A(. . . x . . . x . . .) ∀I m
1 ∀x L(x, k )
2 L(k, k ) ∀E 1
3 ∀x L(x, x) naughty attempt to invoke ∀I 2
1 G (d )
2 G (d ) R1
3 G (d ) → G (d ) →I 1–2
4 ∀z (G (z ) → G (z )) ∀I 3
1 ∀x O (x, x)
2 O (d, d ) ∀E 1
3 ∀x O (x, d ) naughty attempt to invoke ∀I 2
1 ∃x F (x)
2 ∀x(F (x) → G (x))
3 F (b)
4 F (b) → G (b) ∀E 2
5 G (b) →E 4, 3
6 ∃x G (x) ∃I 5
7 ∃x G (x) ∃E 1, 3–6
m ∃x A(. . . x . . . x . . .)
i A(. . . c . . . c . . .)
j B
B ∃E m, i – j
1 L(b)
2 ∃x ¬L(x)
3 ¬L(b)
4 L(b) ∧ ¬L(b) ∧I 1, 3
5 L(b) ∧ ¬L(b) naughty attempt
to invoke ∃E 2, 3–4
The last line of the proof is not allowed. The name that we used
in our substitution instance for ‘∃x ¬L(x)’ on line 3, namely ‘b’,
occurs in line 4. The this would be no better:
1 L(b)
2 ∃x ¬L(x)
3 ¬L(b)
4 L(b) ∧ ¬L(b) ∧I 1, 3
5 ∃x(L(x) ∧ ¬L(x)) ∃I 4
6 ∃x(L(x) ∧ ¬L(x)) naughty attempt
to invoke ∃E 2, 3–5
The last line is still not allowed. For the name that we used in
our substitution instance for ‘∃x ¬L(x)’, namely ‘b’, occurs in an
undischarged assumption, namely line 1.
The moral of the story is this. If you want to squeeze information
out of an existential quantifier, choose a new name for your substitu-
tion instance. That way, you can guarantee that you meet all the
constraints on the rule for ∃E.
CHAPTER 32. BASIC RULES FOR FOL 286
Practice exercises
A. Explain why these two ‘proofs’ are incorrect. Also, provide
interpretations which would invalidate the fallacious argument
forms the ‘proofs’ enshrine:
1 ∀x R(x, x) 1 ∀x ∃y R(x, y)
2 R(a, a) ∀E 1 2 ∃y R(a, y) ∀E 1
3 ∀y R(a, y) ∀I 2 3 R(a, a)
4 ∀x ∀y R(x, y) ∀I 3 4 ∃x R(x, x) ∃I 3
5 ∃x R(x, x) ∃E 2, 3–4
B. The following three proofs are missing their citations (rule and
line numbers). Add them, to turn them into bona fide proofs.
Proofs with
quantifiers
In §16 we discussed strategies for constructing proofs using the
basic rules of natural deduction for TFL. The same principles
apply to the rules for the quantifiers. If we want to prove a quan-
tifier sentence ∀x A(x) or ∃x A(x). We can work backward by
justifying the sentence we want by ∀I or ∃I and trying to find a
proof of the corresponding premise of that rule. And to work
forward from a quantified sentence, we apply ∀E or ∃E, as the
case may be.
Specifically, suppose you want to prove ∀x A(x). To do so
using ∀I, we would need a proof of A(c) for some name c which
does not occur in any undischarged assumption. To apply the
corresponding strategy, i.e., to construct a proof of ∀x A(x) by
working backward, is thus to write A(c) above it and then to
continue to try to find a proof of that sentence.
..
.
n A(c)
n+1 ∀x A(x) ∀I n
291
CHAPTER 33. PROOFS WITH QUANTIFIERS 292
..
.
m ∃x A(x)
..
.
n A(c)
..
.
k B
k +1 B ∃E m, n–k
You’ll then continue with the goal of proving B, but now inside a
subproof in which you have an additional sentence to work with,
namely A(c).
Lastly, working forward from ∀x A(x) means that you can al-
ways write down A(c) and justify it using ∀E, for any name c.
Of course, you wouldn’t want to do that willy-nilly. Only certain
names c will help in your task of proving whatever goal sentence
you are working on. So, like working backward from ∃x A(x),
you should work forward from ∀x A(x) only after all other strate-
gies have been applied.
Let’s consider as an example the argument ∀x(A(x) → B) .̇.
∃x A(x) → B. To start constructing a proof, we write the premise
at the top and the conclusion at the bottom.
1 ∀x(A(x) → B)
..
.
n ∃x A(x) → B
The strategies for connectives of TFL still apply, and you should
apply them in the same order: first work backward from condi-
tionals, negated sentences, conjunctions, and now also universal
quantifiers, then forward from disjunctions and now existential
quantifiers, and only then try to apply →E, ¬E, ∨I, ∀E, or ∃I. In
our case, that means, working backward from the conclusion:
CHAPTER 33. PROOFS WITH QUANTIFIERS 294
1 ∀x(A(x) → B)
2 ∃x A(x)
..
.
n−1 B
n ∃x A(x) → B →I 2–(n − 1)
1 ∀x(A(x) → B)
2 ∃x A(x)
3 A(d )
..
.
n−2 B
n−1 B ∃E 2, 3–(n − 2)
n ∃x A(x) → B →I 2–(n − 1)
1 ∀x(A(x) → B)
2 ∃x A(x)
3 A(d )
4 A(d ) → B ∀E 1
5 B →E 4, 3
6 B ∃E 2, 3–5
7 ∃x A(x) → B →I 2–6
1 ∃x A(x) → B
..
.
n ∀x(A(x) → B)
1 ∃x A(x) → B
..
.
n−1 A(d ) → B
n ∀x(A(x) → B) ∀I n − 1
1 ∃x A(x) → B
2 A(d )
..
.
n−2 B
n−1 A(d ) → B →I 2–(n − 2)
n ∀x(A(x) → B) ∀I n − 1
1 ∃x A(x) → B
2 A(d )
3 ∃x A(x) ∃I 2
4 B →E 1, 3
5 A(d ) → B →I 2–4
6 ∀x(A(x) → B) ∀I 5
Practice exercises
A. Use the strategies to find proofs for each of the following ar-
guments and theorems:
Use only the basic rules of TFL in addition to the basic quantifier
rules.
B. Use the strategies to find proofs for each of the following ar-
guments and theorems:
C. Use the strategies to find proofs for each of the following ar-
guments and theorems:
These require the use of IP. Use only the basic rules of TFL in
addition to the basic quantifier rules.
CHAPTER 34
Conversion of
quantifiers
In this section, we will add some additional rules to the basic
rules of the previous section. These govern the interaction of
quantifiers and negation.
In §21, we noted that ¬∃x A is logically equivalent to ∀x ¬A.
We will add some rules to our proof system that govern this. In
particular, we add:
m ∀x ¬A
¬∃x A CQ m
and
m ¬∃x A
∀x ¬A CQ m
Equally, we add:
298
CHAPTER 34. CONVERSION OF QUANTIFIERS 299
m ∃x ¬A
¬∀x A CQ m
and
m ¬∀x A
∃x ¬A CQ m
Practice exercises
A. Show in each case that the sentences are provably inconsis-
tent:
NB: the variable ‘x’ does not occur in ‘G (a)’. When all the quan-
tifiers occur at the beginning of a sentence, that sentence is said
to be in prenex normal form. These equivalences are sometimes
called prenexing rules, since they give us a means for putting any
sentence into prenex normal form.
CHAPTER 35
Rules for
identity
In §27, we mentioned the philosophically contentious thesis of
the identity of indiscernibles. This is the claim that objects which
are indiscernible in every way are, in fact, identical to each other.
It was also mentioned that we will not subscribe to this thesis. It
follows that, no matter how much you learn about two objects,
we cannot prove that they are identical. That is unless, of course,
you learn that the two objects are, in fact, identical, but then the
proof will hardly be very illuminating.
The general point, though, is that no sentences which do not
already contain the identity predicate could justify an inference
to ‘a = b’. So our identity introduction rule cannot allow us to
infer to an identity claim containing two different names.
However, every object is identical to itself. No premises, then,
are required in order to conclude that something is identical to
itself. So this will be the identity introduction rule:
c= c =I
Notice that this rule does not require referring to any prior
301
CHAPTER 35. RULES FOR IDENTITY 302
lines of the proof. For any name c, you can write c = c on any
point, with only the =I rule as justification.
Our elimination rule is more fun. If you have established
‘a = b’, then anything that is true of the object named by ‘a’
must also be true of the object named by ‘b’. For any sentence
with ‘a’ in it, you can replace some or all of the occurrences of
‘a’ with ‘b’ and produce an equivalent sentence. For example,
from ‘R(a, a)’ and ‘a = b’, you are justified in inferring ‘R(a, b)’,
‘R(b, a)’ or ‘R(b, b)’. More generally:
m a= b
n A(. . . a . . . a . . .)
A(. . . b . . . a . . .) =E m, n
m a= b
n A(. . . b . . . b . . .)
A(. . . a . . . b . . .) =E m, n
1 a =b
2 a=a =I
3 b =a =E 1, 2
4 a =b →b =a →I 1–3
5 ∀y(a = y → y = a) ∀I 4
6 ∀x ∀y(x = y → y = x) ∀I 5
1 a =b ∧b = c
2 a =b ∧E 1
3 b =c ∧E 1
4 a =c =E 2, 3
5 (a = b ∧ b = c ) → a = c →I 1–4
6 ∀z ((a = b ∧ b = z ) → a = z ) ∀I 5
7 ∀y ∀z ((a = y ∧ y = z ) → a = z ) ∀I 6
8 ∀x ∀y∀z ((x = y ∧ y = z ) → x = z ) ∀I 7
Practice exercises
A. Provide a proof of each claim.
3. ∀x x = m, R(m, a) ⊢ ∃x R(x, x)
4. ∀x ∀y(R(x, y) → x = y) ⊢ R(a, b) → R(b, a)
5. ¬∃x¬x = m ⊢ ∀x ∀y(P (x) → P (y))
6. ∃x J (x), ∃x ¬ J (x) ⊢ ∃x ∃y ¬x = y
7. ∀x(x = n ↔ M (x)), ∀x(O (x) ∨ ¬M (x)) ⊢ O (n)
8. ∃x [︁D(x), ∀x(x = p ↔ D(x)) ⊢ D(p)
9. ∃x (K (x) ∧ ∀y(K (y) → x = y)) ∧ B(x) , K d ⊢ B(d )
]︁
And hence that both have a decent claim to symbolize the En-
glish sentence ‘Nick is the F ’.
Show that they are all provably equivalent. (Hint: to show that
three claims are provably equivalent, it suffices to show that the
first proves the second, the second proves the third and the third
proves the first; think about why.)
Derived rules
As in the case of TFL, we first introduced some rules for FOL as
basic (in §32), and then added some further rules for conversion
of quantifiers (in §34). In fact, the CQ rules should be regarded
as derived rules, for they can be derived from the basic rules of
§32. (The point here is as in §19.) Here is a justification for the
first CQ rule:
1 ∀x ¬A(x)
2 ∃x A(x)
3 A(c )
4 ¬A(c ) ∀E 1
5 ⊥ ¬E 4, 3
6 ⊥ ∃E 2, 3–5
7 ¬∃x A(x) ¬I 2–6
305
CHAPTER 36. DERIVED RULES 306
1 ∃x ¬A(x)
2 ∀x A(x)
3 ¬A(c )
4 A(c ) ∀E 2
5 ⊥ ¬E 3, 4
6 ⊥ ∃E 1, 3–5
7 ¬∀x A(x) ¬I 2–6
Practice exercises
A. Offer proofs which justify the addition of the second and
fourth CQ rules as derived rules.
CHAPTER 37
Proofs and
semantics
We have used two different turnstiles in this book. This:
A1, A2, . . . , An ⊢ C
A1, A2, . . . , An ⊨ C
307
CHAPTER 37. PROOFS AND SEMANTICS 308
For this reason, you can pick and choose when to think in terms
of proofs and when to think in terms of valuations/interpretations,
doing whichever is easier for a given task. The table on the next
page summarises which is (usually) easier.
It is intuitive that provability and semantic entailment should
agree. But—let us repeat this—do not be fooled by the similarity
of the symbols ‘⊨’ and ‘⊢’. These two symbols have very differ-
ent meanings. The fact that provability and semantic entailment
agree is not an easy result to come by.
In fact, demonstrating that provability and semantic entail-
ment agree is, very decisively, the point at which introductory
logic becomes intermediate logic.
Yes No
Are A and B equivalent? give two proofs, one for A ⊢ B and give an interpretation in which A and
one for B ⊢ A B have different truth values
Are A1, A2, . . . , An jointly give an interpretation in which all of prove a contradiction from assump-
CHAPTER 37. PROOFS AND SEMANTICS
Is A1, A2, . . . , An .̇. C valid? give a proof with assumptions give an interpretation in which each
A1, A2, . . . , An and concluding with of A1, A2, . . . , An is true and C is false
C
310
PART VIII
Modal logic
311
CHAPTER 38
Introducing
Modal Logic
Modal logic (ML) is the logic of modalities, ways in which a state-
ment can be true. Necessity and possibility are two such modalities:
a statement can be true, but it can also be necessarily true (true
no matter how the world might have been). For instance, logical
truths are not just true because of some accidental feature of the
world, but true come what may. A possible statement may not
actually be true, but it might have been true. We use □ to express
necessity, and ◇ to express possibility. So you can read □A as It
is necessarily the case that A, and ◇A as It is possibly the case that A.
There are lots of different kinds of necessity. It is humanly
impossible for me to run at 100mph. Given the sorts of creatures
that we are, no human can do that. But still, it isn’t physically
impossible for me to run that fast. We haven’t got the technology to
do it yet, but it is surely physically possible to swap my biological
legs for robotic ones which could run at 100mph. By contrast,
it is physically impossible for me to run faster than the speed of
light. The laws of physics forbid any object from accelerating up
to that speed. But even that isn’t logically impossible. It isn’t a
contradiction to imagine that the laws of physics might have been
different, and that they might have allowed objects to move faster
312
CHAPTER 38. INTRODUCING MODAL LOGIC 313
than light.
Which kind of modality does ML deal with? All of them! ML
is a very flexible tool. We start with a basic set of rules that
govern □ and ◇, and then add more rules to fit whatever kind
of modality we are interested in. In fact, ML is so flexible that
we do not even have to think of □ and ◇ as expressing necessity
and possibility. We might instead read □ as expressing provability,
so that □A means It is provable that A, and ◇A means It is not
refutable that A. Similarly, we can interpret □ to mean S knows
that A or S believes that A. Or we might read □ as expressing
moral obligation, so that □A means It is morally obligatory that A,
and ◇A means It is morally permissible that A. All we would need
to do is cook up the right rules for these different readings of □
and ◇.
A modal formula is one that includes modal operators such
as □ and ◇. Depending on the interpretation we assign to □
and ◇, different modal formulas will be provable or valid. For
instance, □A → □A might say that “if A is necessary, it is true,”
if □ is interpreted as necessity. It might express “if A is known,
then it is true,” if □ expresses known truth. Under both these
interpretations, □A → A is valid: All necessary propositions are
true come what may, so are true in the actual world. And if a
proposition is known to be true, it must be true (one can’t know
something that’s false). However, when □ is interpreted as “it is
believed that” or “it ought to be the case that,” □A → A is not
valid: We can believe false propositions. Not every proposition
that ought to be true is in fact true, e.g., “Every murderer will be
brought to justice.” This ought to be true, but it isn’t.
We will consider different kinds of systems of ML. They differ
in the rules of proof allowed, and in the semantics we use to de-
fine our logical notions. The different systems we’ll consider are
called K, T, S4, and S5. K is the basic system; everything that is
valid or provable in K is also provable in the others. But there are
some things that K does not prove, such as the formula □A → A.
So K is not an appropriate modal logic for necessity and pos-
sibility (where □A → A should be provable). This is provable
CHAPTER 38. INTRODUCING MODAL LOGIC 314
Natural
Deduction for
ML
Now that we know how to make sentences in ML, we can look at
how to prove things in ML. We will use ⊢ to express provabil-
ity. So A1, A2, . . . An ⊢ C means that C can be proven from
A1, A2, . . . An . However, we will be looking at a number of dif-
ferent systems of ML, and so it will be useful to add a subscript
to indicate which system we are working with. So for example,
if we want to say that we can prove C from A1, A2, . . . An in sys-
tem K, we will write: A1, A2, . . . An ⊢K C.
39.1 System K
We start with a particularly simple system called K, in honour of
the philosopher and logician Saul Kripke. K includes all of the
natural deduction rules from TFL, including the derived rules as
well as the basic ones. K then adds a special kind of subproof,
plus two new basic rules for □.
316
CHAPTER 39. NATURAL DEDUCTION FOR ML 317
1 A
2 A R1
3 A→A →I 1–2
But to apply □I, we need to have proven the formula inside a strict
subproof. Since our proof of A → A makes use of no assumptions
at all, this is possible.
1 □
2 A
3 A R2
4 A→A →I 2–3
5 □(A → A) □I 1–4
CHAPTER 39. NATURAL DEDUCTION FOR ML 318
m □
n A
□A □I m–n
m □A
□
n A □E m
1 □A
2 □B
3 □
4 A □E 1
5 B □E 2
6 A∧B ∧I 4, 5
7 □(A ∧ B) □I 3–7
1 □(A → B)
2 □A
3 □
4 A □E m
5 A→B □E 1
6 B →E 4, 5
7 □B
8 □A → □B →I 2–7
39.2 Possibility
In the last subsection, we looked at all of the basic rules for K.
But you might have noticed that all of these rules were about
necessity, □, and none of them were about possibility, ◇. That’s
because we can define possibility in terms of necessity:
◇A =df ¬□¬A
m ¬□¬A
◇A Def◇ m
m ◇A
¬□¬A Def◇ m
m ¬□A
◇¬A MC m
m ◇¬A
¬□A MC m
m ¬◇A
□¬A MC m
m □¬A
¬◇A MC m
39.3 System T
So far we have focussed on K, which is a very simple modal
system. K is so weak that it will not even let you prove A from
□A. But if we are thinking of □ as expressing necessity, then we
will want to be able to make this inference: if A is necessarily true,
then it must surely be true!
CHAPTER 39. NATURAL DEDUCTION FOR ML 323
m □A
n A RT m
39.4 System S4
T allows you to strip away the necessity boxes: from □A, you
may infer A. But what if we wanted to add extra boxes? That is,
what if we wanted to go from □A to □□A? Well, that would be no
problem, if we had proved □A by applying □I to a strict subproof
of A which itself does not use □E. In that case, A is a tautology,
and by nesting the strict subproof inside another strict subproof
and applying □I again, we can prove □□A. For example, we could
CHAPTER 39. NATURAL DEDUCTION FOR ML 324
1 □
2 □
3 P
4 P R3
5 P →P →I 3–4
6 □(P → P ) □I 2–5
7 □□(P → P ) □I 1–6
m □A
□
n □A R4 m
1 □A
2 □
3 □A R4 1
4 □□A □I 2–3
5 □A → □□A →I 1–6
39.5 System S5
In S4, we can always add a box in front of another box. But S4
does not automatically let us add a box in front of a diamond.
CHAPTER 39. NATURAL DEDUCTION FOR ML 326
m ¬□A
□
n ¬□A R5 m
This rule allows us to show, for instance, that ◇□A ⊢S5 □A:
1 ◇□A
2 ¬□¬□A Def◇ 1
3 ¬□A
4 □
5 ¬□A R5 3
6 □¬□A □I 4–5
7 ⊥ ¬E 2, 6
8 □A IP 3–7
1 □A
2 □¬□A
3 ¬□A RT 2
4 ⊥ ¬E 1, 3
5 ¬□¬□A ¬I 2–4
6 □
7 ¬□A
8 □
9 ¬□A R5 7
10 □¬□A □I 8–9
11 ¬□¬□A R5 5
12 ⊥ ¬E 10, 11
13 □A IP 7–12
14 □□A □I 6–13
S5 is strictly stronger than S4: there are things which can be proved
in S5, but not in S4 (e.g., ◇□A → □A).
The important point about S5 can be put like this: if you have
a long string of boxes and diamonds, in any combination what-
soever, you can delete all but the last of them. So for example,
◇□◇◇□□◇□A can be simplified down to just □A.
CHAPTER 39. NATURAL DEDUCTION FOR ML 328
Practice exercises
A. Provide proofs for the following:
1. □(A ∧ B) ⊢K □A ∧ □B
2. □A ∧ □B ⊢K □(A ∧ B)
3. □A ∨ □B ⊢K □(A ∨ B)
4. □(A ↔ B) ⊢K □A ↔ □B
B. Provide proofs for the following (without using Modal Con-
version!):
1. ¬□A ⊢K ◇¬A
2. ◇¬A ⊢K ¬□A
3. ¬◇A ⊢K □¬A
4. □¬A ⊢K ¬◇A
C. Provide proofs of the following (and now feel free to use Modal
Conversion!):
1. □(A → B), ◇A ⊢K ◇B
2. □A ⊢K ¬◇¬A
3. ¬◇¬A ⊢K □A
D. Provide proofs for the following:
1. P ⊢T ◇P
2. ⊢T (A ∧ B) ∨ (¬□A ∨ ¬□B)
E. Provide proofs for the following:
1. □(□A → B), □(□B → C ), □A ⊢S4 □□C
2. □A ⊢S4 □(□A ∨ B)
3. ◇◇A ⊢S4 ◇A
F. Provide proofs in S5 for the following:
1. ¬□¬A, ◇B ⊢S5 □(◇A ∧ ◇B)
2. A ⊢S5 □◇A
3. ◇◇A ⊢S5 ◇A
CHAPTER 40
Semantics for
ML
So far, we have focussed on laying out various systems of Natural
Deduction for ML. Now we will look at the semantics for ML. A
semantics for a language is a method for assigning truth-values
to the sentences in that language. So a semantics for ML is a
method for assigning truth-values to the sentences of ML.
40.1 Interpretations of ML
The big idea behind the semantics for ML is this. In ML, sen-
tences are not just true or false, full stop. A sentence is true or
false at a given possible world, and a single sentence may well be
true at some worlds and false at others. We then say that □A is
true iff A is true at every world, and ◇A is true iff A is true at
some world.
That’s the big idea, but we need to refine it and make it more
precise. To do this, we need to introduce the idea of an interpre-
tation of ML. The first thing you need to include in an interpreta-
tion is a collection of possible worlds. Now, at this point you might
well want to ask: What exactly is a possible world? The intuitive
idea is that a possible world is another way that this world could
329
CHAPTER 40. SEMANTICS FOR ML 330
have been. But what exactly does that mean? This is an excellent
philosophical question, and we will look at it in a lot of detail
later. But we do not need to worry too much about it right now.
As far as the formal logic goes, possible worlds can be anything
you like. All that matters is that you supply each interpretation
with a non-empty collection of things labelled possible worlds.
Once you have chosen your collection of possible worlds, you
need to find some way of determining which sentences of ML
are true at which possible worlds. To do that, we need to intro-
duce the notion of a valuation function. Those of you who have
studied some maths will already be familiar with the general idea
of a function. But for those of you who haven’t, a function is a
mathematical entity which maps arguments to values. That might
sound a little bit abstract, but some familiar examples will help.
Take the function x + 1. This is a function which takes in a num-
ber as argument, and then spits out the next number as value. So
if you feed in the number 1 as an argument, the function x +1 will
spit out the number 2 as a value; if you feed in 2, it will spit out 3;
if you feed in 3, it will spit out 4 . . . Or here is another example:
the function x + y. This time, you have to feed two arguments
into this function if you want it to return a value: if you feed in
2 and 3 as your arguments, it spits out 5; if you feed in 1003 and
2005, it spits out 3008; and so on.
A valuation function for ML takes in a sentence and a world
as its arguments, and then returns a truth-value as its value. So
if ν is a valuation function and w is a possible world, νw (A) is
whatever truth-value ν maps A and w to: if νw (A) = F , then A is
false at world w on valuation ν; if νw (A) = T , then A is true at
world w on valuation ν.
These valuation functions are allowed to map any atomic sen-
tence to any truth-value at any world. But there are rules about
which truth-values more complex sentences get assigned at a
world. Here are the rules for the connectives from TFL:
(1) νw (¬A) = T iff: νw (A) = F
(2) νw (A∧ B) = T iff: νw (A) = T and νw (B) = T
CHAPTER 40. SEMANTICS FOR ML 331
So far, these rules should all look very familiar. Essentially, they
all work exactly like the truth-tables for TFL. The only difference
is that these truth-table rules have to be applied over and over
again, to one world at a time.
But what are the rules for the new modal operators, □ and ◇?
The most obvious idea would be to give rules like these:
This is just the fancy formal way of writing out the idea that □A
is true at w just in case A is true at every world, and ◇A is true
at w just in case A is true at some world.
However, while these rules are nice and simple, they turn out
not to be quite as useful as we would like. As we mentioned, ML
is meant to be a very flexible tool. It is meant to be a general
framework for dealing with lots of different kinds of necessity.
As a result, we want our semantic rules for □ and ◇ to be a
bit less rigid. We can do this by introducing another new idea:
accessibility relations.
An accessibility relation, R, is a relation between possible
worlds. Roughly, to say that Rw 1w 2 (in English: world w 1 accesses
world w 2 ) is to say that w 2 is possible relative to w 1 . In other
words, by introducing accessibility relations, we open up the idea
that a given world might be possible relative to some worlds but
not others. This turns out to be a very fruitful idea when studying
modal systems. We can now give the following semantic rules for
□ and ◇:
1 2
A ¬A
¬B B
W : 1, 2
¬A ⊨K ¬◇A
1 2
¬A A
▷ ∀wRww
m □A
A RT m
□A ⊨T A
m □A
□
□A R4 m
□A ⊨S4 □□A
▷ ∀w 1∀w 2 (Rw 1w 2 → Rw 2w 1 )
m ¬□A
□
¬□A R5 m
The rule says that if A is not necessary, i.e., false in some ac-
cessible world, it is also not necessary in any accessible prossible
world, i.e., we have ¬□A ⊢S5 □¬□A.
To see this, just imagine trying to cook up a counter-
interpretation to this claim:
▷ ∀w 1∀w 2Rw 1w 2
If we defined ⊨S5 like this, we would still get the same sound-
ness and completeness results for S5. What does this tell us?
Well, it means that if we are dealing with a notion of necessity
according to which every world is possible relative to every world,
then we should use S5. What is more, most philosophers assume
that the notions of necessity that they are most concerned with,
like logical necessity and metaphysical necessity, are of exactly this
kind. So S5 is the modal system that most philosophers use most
of the time.
CHAPTER 40. SEMANTICS FOR ML 341
Practice exercises
A. Present counter-interpretations to the following false claims:
1. ¬P ⊨K ¬◇P
2. □(P ∨ Q ) ⊨K □P ∨ □Q
3. ⊨K ¬□(A ∧ ¬A)
4. □A ⊨K A
1. ◇A ⊨S4 □◇A
2. ◇A, □(◇A → B) ⊨S4 □B
1. □(M → O ), ◇M ⊨T O
2. □A ⊨T □□A
Further reading
Modal logic is a large subfield of logic. We have only scratched
the surface. If you want to learn more about modal logic, here
are some textbooks you might consult.
Metatheory
342
CHAPTER 41
Normal forms
and expressive
completeness
41.1 Disjunctive Normal Form
Sometimes it is useful to consider sentences of a particularly sim-
ple form. For instance, we might consider sentences in which
¬ only attaches to atomic sentences, or those which are combi-
nations of atomic sentences and negated atomic sentences us-
ing only ∧. A relatively general but still simple form is that
where a sentence is a disjunction of conjunctions of atomic or
negated atomic sentences. When such a sentence is constructed,
we start with atomic sentences, then (perhaps) attach negations,
then (perhaps) combine using ∧, and finally (perhaps) combine
using ∨.
Let’s say that a sentence is in disjunctive normal form iff
it meets all of the following conditions:
343
CHAPTER 41. NORMAL FORMS 344
A
(A ∧ ¬B ∧ C )
(A ∧ B) ∨ (A ∧ ¬B)
(A ∧ B) ∨ (A ∧ B ∧ C ∧ ¬D ∧ ¬E)
A ∨ (C ∧ ¬P 234 ∧ P 233 ∧ Q ) ∨ ¬B
Note that we have here broken one of the maxims of this book and
temporarily allowed ourselves to employ the relaxed bracketing-
conventions that allow conjunctions and disjunctions to be of ar-
bitrary length. These conventions make it easier to see when a
sentence is in disjunctive normal form. We will continue to help
ourselves to these relaxed conventions, without further comment.
To further illustrate the idea of disjunctive normal form, we
will introduce some more notation. We write ‘±A’ to indicate
that A is an atomic sentence which may or may not be prefaced
with an occurrence of negation. Then a sentence in disjunctive
normal form has the following shape:
A B C S
T T T T
T T F F
T F T T
T F F F
F T T F
F T F F
F F T T
F F F T
As it happens, S is true on four lines of its truth table, namely
lines 1, 3, 7 and 8. Corresponding to each of those lines, we will
write down four sentences, whose only connectives are negations
and conjunctions, where every negation has minimal scope:
(A ∧ B ∧ C ) ∨ (A ∧ ¬B ∧ C ) ∨ (¬A ∧ ¬B ∧ C ) ∨ (¬A ∧ ¬B ∧ ¬C )
2. S is true on at least one line of its truth table. For each line i
of the truth table, let Bi be a conjunction of the form
(±A1 ∧ . . . ∧ ±An )
These two cases are exhaustive and, either way, we have a sen-
tence in DNF that is logically equivalent to S.
So we have proved the DNF Theorem. Before we say any
more, though, we should immediately flag that we are hereby
returning to the austere definition of a (TFL) sentence, according
to which we can assume that any conjunction has exactly two
conjuncts, and any disjunction has exactly two disjuncts.
Practice exercises
A. Consider the following sentences:
1. (A → ¬B)
2. ¬(A ↔ B)
3. (¬A ∨ ¬(A ∧ B))
4. (¬(A → B) ∧ (A → C ))
5. (¬(A ∨ B) ↔ ((¬C ∧ ¬A) → ¬B))
6. ((¬(A ∧ ¬B) → C ) ∧ ¬(A ∧ D))
A B C ♥(A, B,C )
T T T F
T T F T
T F T T
T F F F
F T T F
F T F T
F F T F
F F F F
Probably this new connective would not correspond with any nat-
ural English expression (at least not in the way that ‘∧’ corre-
sponds with ‘and’). But a question arises: if we wanted to employ
a connective with this characteristic truth table, must we add a
new connective to TFL? Or can we get by with the connectives
we already have?
Let us make this question more precise. Say that some con-
nectives are jointly expressively adequate iff, for any possible
truth table, there is a sentence containing only those connectives
with that truth table.
The general point is, when we are armed with some jointly
expressively adequate connectives, no characteristic truth table
lies beyond our grasp. And in fact, we are in luck.
Given any truth table, we can use the method of proving the
DNF Theorem (or the CNF Theorem) via truth tables, to write
down a scheme which has the same truth table. For example,
employing the truth table method for proving the DNF Theorem,
CHAPTER 41. NORMAL FORMS 350
(A ∧ B ∧ ¬C ) ∨ (A ∧ ¬B ∧ C ) ∨ (¬A ∧ B ∧ ¬C )
A B A↑ B
T T F
T F T
F T T
F F T
This is often called ‘the Sheffer stroke’, after Henry Sheffer, who
used it to show how to reduce the number of logical connectives in
Russell and Whitehead’s Principia Mathematica.1 (In fact, Charles
Sanders Peirce had anticipated Sheffer by about 30 years, but
never published his results.)2 It is quite common, as well, to call
it ‘nand’, since its characteristic truth table is the negation of the
truth table for ‘∧’.
¬A and (A ↑ A)
(A∨ B) and ((A ↑ A) ↑ (B ↑ B))
A B A↓ B
T T F
T F F
F T F
F F T
This is sometimes called the ‘Peirce arrow’ (Peirce himself called
it ‘ampheck’). More often, though, it is called ‘nor’, since its
characteristic truth table is the negation of ‘∨’, that is, of ‘neither
. . . nor . . . ’.
¬A and (A ↓ A)
(A∧ B) and ((A ↓ A) ↓ (B ↓ B))
A ¬A
T F
F T
The intuitive reason, why this should be so, is simple: the top
line of the desired truth table needs to have the value False; but
the top line of any truth table for a scheme which only contains
∨ will always be True. The same is true for ∧, →, and ↔.
Soundness
In this chapter we relate TFL’s semantics to its natural deduction
proof system (as defined in Part IV). We will prove that the formal
proof system is safe: you can only prove sentences from premises
from which they actually follow. Intuitively, a formal proof system
is sound iff it does not allow you to prove any invalid arguments.
This is obviously a highly desirable property. It tells us that our
proof system will never lead us astray. Indeed, if our proof system
were not sound, then we would not be able to trust our proofs.
The aim of this chapter is to prove that our proof system is sound.
Let’s make the idea more precise. We’ll abbreviate a list of
sentences using the greek letter Γ (‘gamma’). A formal proof sys-
tem is sound (relative to a given semantics) iff, whenever there
is a formal proof of C from assumptions among Γ, then Γ gen-
uinely entails C (given that semantics). Otherwise put, to prove
that TFL’s proof system is sound, we need to prove the following
354
CHAPTER 42. SOUNDNESS 355
1 F → (G ∧ H )
2 F
3 G ∧H →E 1, 2
4 G ∧E 3
5 F →G →I 2–4
Then we will know that we have never gone astray, on any line
of a proof. Indeed, given the Shininess Lemma, it will be easy to
prove the Soundness Theorem:
Proof. Suppose Γ ⊢ C. Then there is a TFL-proof, with C
appearing on its last line, whose only undischarged assumptions
are among Γ. The Shininess Lemma tells us that every line on
every TFL-proof is shiny. So this last line is shiny, i.e. Γ ⊨ C.
QED
It remains to prove the Shininess Lemma.
To do this, we observe that every line of any TFL-proof is
obtained by applying some rule. So what we want to show is that
no application of a rule of TFL’s proof system will lead us astray.
1 The word ‘shiny’ is not standard among logicians.
CHAPTER 42. SOUNDNESS 356
∧I is rule-sound.
i A
j B
n A∧ B ∧I i , j
∧E is rule-sound.
i A∧ B
n A ∧E i
∨I is rule-sound.
∨E is rule-sound.
m A∨ B
i A
j C
k B
l C
n C ∨E m, i – j , k –l
Let v be any valuation that makes all of ∆n true. Note that all of
∆m are among ∆n . By hypothesis, line m is shiny. So any valuation
that makes ∆n true makes A ∨ B true. So in particular, v makes
A∨ B true, and hence either v makes A true, or v makes B true.
We now reason through these two cases:
¬E is rule-sound.
i A
j ¬A
n ⊥ ¬E i , j
X is rule-sound.
¬I is rule-sound.
i A
j ⊥
n ¬A ¬I i – j
Let v be any valuation that makes all of ∆n true. Note that all
of ∆n are among ∆i , with the possible exception of A itself. By
hypothesis, line j is shiny. But no valuation can make ‘⊥’ true,
so no valuation can make all of ∆ j true. Since the sentences ∆i
are just the sentences ∆ j , no valuation can make all of ∆i true.
CHAPTER 42. SOUNDNESS 360
Practice exercises
A. Complete the Lemmas left as exercises in this chapter. That
is, show that the following are rule-sound:
1. ∨I. (Hint: this is similar to the case of ∧E.)
CHAPTER 42. SOUNDNESS 361
362
APPENDIX A
Symbolic
notation
1.1 Alternative nomenclature
Truth-functional logic. TFL goes by other names. Sometimes
it is called sentential logic, because it deals fundamentally with
sentences. Sometimes it is called propositional logic, on the idea
that it deals fundamentally with propositions. We have stuck with
truth-functional logic, to emphasize the fact that it deals only with
assignments of truth and falsity to sentences, and that its connec-
tives are all truth-functional.
363
APPENDIX A. SYMBOLIC NOTATION 364
Names. In FOL, we have used ‘a’, ‘b’, ‘c ’, for names. Some texts
call these ‘constants’. Other texts do not mark any difference
between names and variables in the syntax. Those texts focus
simply on whether the symbol occurs bound or unbound.
Negation. Two commonly used symbols are the hoe, ‘¬’, and
the swung dash or tilda, ‘∼.’ In some more advanced formal sys-
tems it is necessary to distinguish between two kinds of negation;
the distinction is sometimes represented by using both ‘¬’ and
APPENDIX A. SYMBOLIC NOTATION 365
the formula that it binds. For example, they might write ‘(x)P x’
where we would write ‘∀x P x’.
negation ¬, ∼
conjunction ∧, &, •
disjunction ∨
conditional →, ⊃
biconditional ↔, ≡
universal quantifier ∀x, (x)
APPENDIX B
Alternative
proof systems
In formulating our natural deduction system, we treated certain
rules of natural deduction as basic, and others as derived. How-
ever, we could equally well have taken various different rules as
basic or derived. We will illustrate this point by considering some
alternative treatments of disjunction, negation, and the quanti-
fiers. We will also explain why we have made the choices that we
have.
367
APPENDIX B. ALTERNATIVE PROOF SYSTEMS 368
m A∨ B
i A
j C
k B
l C
n A→ C →I i – j
n+1 B→ C →I k –l
n+2 ¬C
n+3 A
n+4 C →E n + 3, n
n+5 ⊥ ¬E n + 2, n + 4
n+6 ¬A ¬I n + 3–n + 5
n+7 B DS m, n + 6
n+8 C →E n + 7, n + 1
n+9 ⊥ ¬E n + 2, n + 8
n + 10 C IP n + 2–n + 9
m A
n−1 B
n ¬B
¬A ¬I* m–n
m ¬A
n−1 B
n ¬B
A ¬E* m–n
Using these two rules, we could we could have avoided all use of
the symbol ‘⊥’ altogether.2 The resulting system would have had
fewer rules than ours.
Another way to deal with negation is to use either LEM or
DNE as a basic rule and introduce IP as a derived rule. Typically,
in such a system the rules are given different names, too. E.g.,
sometimes what we call ¬E is called ⊥I, and what we call X is
called ⊥E.3
So why did we chose our rules for negation and contradiction?
Our first reason is that adding the symbol ‘⊥’ to our natural
deduction system makes proofs considerably easier to work with.
For instance, in our system it’s always clear what the conclusion
of a subproof is: the sentence on the last line, e.g. ⊥ in IP or
¬I. In ¬I* and ¬E*, subproofs have two conclusions, so you can’t
check at one glance if an application of them is correct.
2 Again,
P.D. Magnus’s original version of this book went the other way.
3 The
version of this book due to Tim Button goes this route and replaces
IP with LEM, which he calls TND, for “tertium non datur.”
APPENDIX B. ALTERNATIVE PROOF SYSTEMS 370
m A(. . . c . . . c . . .)
k ∃xA(. . . x . . . c . . .)
m A(. . . c . . . c . . .)
m+1 ¬∃xA(. . . x . . . c . . .)
m+2 ∀x¬A(. . . x . . . c . . .) CQ m + 1
m+3 ¬A(. . . c . . . c . . .) ∀E m + 2
m+4 ⊥ ¬E m + 3, m
m+5 ∃xA(. . . x . . . c . . .) IP m + 1–m + 4
m ∃xA(. . . x . . . x . . .)
i A(. . . c . . . c . . .)
j B
k B
m ∃xA(. . . x . . . x . . .)
i A(. . . c . . . c . . .)
j B
k A(. . . c . . . c . . .) → B →I i – j
k +1 ¬B
k +2 ¬A(. . . c . . . c . . .) MT k , k + 1
k +3 ∀x¬A(. . . x . . . x . . .) ∀I k + 2
k +4 ¬∃xA(. . . x . . . x . . .) CQ k + 3
k +5 ⊥ ¬E k + 4, m
k +6 B IP k + 1–k + 5
Quick
reference
3.1 Characteristic truth tables
A ¬A A B A∧ B A∨ B A→ B A↔ B
T F T T T T T T
F T T F F T F F
F T F T T F
F F F F T T
374
APPENDIX C. QUICK REFERENCE 375
3.2 Symbolization
Sentential Connectives
Predicates
Identity
two ∃x 1 ∃x 2 F (x 1 ) (︁∧ F (x 2 ) ∧
¬x 1 = x 2 ∧ [︁∀y F (y) → (y = x 1 ∨ y = x 2 )
)︁]︁
three ∃x 1 ∃x 2 ∃x 3 F (x 1 ) ∧ F (x 2 ) ∧ F (x 3 ) ∧
¬x(︁1 = x 2 ∧ ¬x 1 = x 3 ∧ ¬x 2 = x 3 ∧ )︁]︁
∀y F (y) → [︁(y = x 1 ∨ y = x 2 ∨ y = x 3 )
n ∃x 1 . . . ∃x n F (x 1 ) ∧ . . . ∧ F (x n ) ∧
¬x(︁1 = x 2 ∧ . . . ∧ ¬x n−1 = x n ∧
∀y F (y) → (y = x 1 ∨ . . . ∨ y = x n )
)︁]︁
APPENDIX C. QUICK REFERENCE 378
Reiteration Negation
m A
i A
A Rm
j ⊥
¬A ¬I i – j
Conjunction
m ¬A
m A
n A
n B
⊥ ¬E m, n
A∧ B ∧I m, n
m A∧ B
A ∧E m
Indirect proof
m A∧ B
B ∧E m i ¬A
j ⊥
A IP i – j
Conditional
i A
j B
A→ B →I i – j Explosion
m A→ B
n A m ⊥
B →E m, n A Xm
APPENDIX C. QUICK REFERENCE 379
Disjunction Biconditional
i A
m A j B
A∨ B ∨I m k B
l A
m A
A↔ B ↔I i – j , k –l
B∨ A ∨I m
m A↔ B
m A∨ B
n A
i A
B ↔E m, n
j C
k B m A↔ B
l C n B
C ∨E m, i – j , k –l A ↔E m, n
APPENDIX C. QUICK REFERENCE 380
m A∨ B i A
n ¬A j B
B DS m, n k ¬A
l B
m A∨ B B LEM i – j , k –l
n ¬B
A DS m, n De Morgan Rules
m ¬(A∨ B)
Modus Tollens ¬A∧ ¬B DeM m
m A→ B
m ¬A∧ ¬B
n ¬B
¬(A∨ B) DeM m
¬A MT m, n
m ¬(A∧ B)
Double-negation ¬A∨ ¬B DeM m
elimination
m ¬¬A m ¬A∨ ¬B
A DNE m ¬(A∧ B) DeM m
APPENDIX C. QUICK REFERENCE 381
Identity introduction
c= c =I
Identity elimination
m a= b m a= b
n A(. . . a . . . a . . .) n A(. . . b . . . b . . .)
A(. . . b . . . a . . .) =E m, n A(. . . a . . . b . . .) =E m, n
APPENDIX C. QUICK REFERENCE 382
m ∀x¬A m ∃x¬A
¬∃xA CQ m ¬∀xA CQ m
m ¬∃xA m ¬∀xA
∀x¬A CQ m ∃x¬A CQ m
APPENDIX C. QUICK REFERENCE 383
Glossary
antecedent The sentence on the left side of a conditional.
argument a connected series of sentences, divided into premises
and conclusion.
atomic sentence An expression used to represent a basic sen-
tence; a sentence letter in TFL, or a predicate symbol
followed by names in FOL.
complete truth table A table that gives all the possible truth
values for a sentence (of TFL) or sentences in TFL, with
a line for every possible valuation of all sentence letters.
completeness A property held by logical systems if and only if
⊨ implies ⊢.
conclusion the last sentence in an argument.
conclusion indicator a word or phrase such as “therefore” used
to indicate that what follows is the conclusion of an ar-
gument.
conditional The symbol →, used to represent words and phrases
that function like the English phrase “if . . . then . . . ”; a
sentence formed by using this symbol.
384
GLOSSARY 385
main connective The last connective that you add when you
assemble a sentence using the recursive definition.
metalanguage The language logicians use to talk about the ob-
ject language. In this textbook, the metalanguage is En-
glish, supplemented by certain symbols like metavari-
ables and technical terms like “valid”.
metavariables A variable in the metalanguage that can represent
any sentence in the object language.