Logic

Three tutorials at Tbilisi

Wilfrid Hodges 1.1
Queen Mary, University of London
w.hodges@qmul.ac.uk FIRST TUTORIAL
October 2003 Entailments

Revised 17 October 2003.

For copyright reasons some of the photos are not included.

1 2

1.2
1.3
Two sentences:
If p and q are sentences, the expression
(a) Noam Chomsky is very clever.
p |= q
(b) Noam Chomsky is clever.
is called a sequent.
If (a) is true then (b) must be true too. If it is true, i.e. if p does entail q,
We express this by saying that (a) entails (b), in symbols then we say it is a valid sequent,
NC is very clever. |= NC is clever. or for short an entailment.

3 4
 1.5
Typical problem
Imagine a situation with two Noam Chomskys,
1.4
Provisional definition
Logic is the study of entailments.

But it’s a bad idea to go to a definition so early.

one very clever and one very unintelligent.

5 6

1.7

1.6 Remedy

Conversation: A situation (for a set of sentences) consists of the information

needed to fix who the named people are, what the date is,
• “Noam Chomsky is very clever.” and anything else relevant to the truth of the sentences.
• “Yes, but on the other hand Noam Chomsky Then we can revise our notion of entailment:
is not clever at all.” ‘(a) entails (b)’ means
We can understand this conversation. In every situation, if (a) is true then (b) is true.
(David Lewis, ‘Scorekeeping in a language game’.)
This remedy is not waterproof,
but it will allow us to continue building up logic.

7 8
1.8
We generalise. Suppose p1 , . . . , pn and q are sentences. 1.9
The sequent
In particular
p1 , . . . , pn |= q
|= q
(‘p1 , . . . , pn entail q’) means that in any situation
expresses that q is true in every situation
where p1 , . . . , pn are all true, q is true too.
(i.e. a necessary truth).
p1 , . . . , pn are the premises of the sequent,
q is its conclusion.

9 10

1.10 1.12

Gerhard Gentzen Axiom Rule

Gerhard Gentzen made some of the most important For every sentence p,
discoveries in logic. p |= p.
In particular he discovered a mathematical theory of
entailments, For example:
which we will study for the rest of this lecture. Bush was right to invade Iraq. |= Bush was right to
He deserves to be better known. invade Iraq.

11 12
 1.14
Jean-Yves Girard (1989):
1.13 In fact, contrary to popular belief, these [structural]
Three structural rules rules are the most important of the whole calculus
...
1. If p, q |= r then q, p |= r. (A typical exchange rule)
Girard in his linear logic drops the structural rules in order to
2. If p |= r then p, q |= r. (An example of monotonicity, also
study (1) the order in which the premises are used to reach
called weakening.)
the conclusion, (2) exactly which premises are really needed,
3. If p, q, q |= r then p, q |= r. (A typical contraction rule.) and (3) how many times each premise is used.
This makes sense only when we have a notion of
‘reaching’ the conclusion from the premises.

13 14

1.15 1.16
The cut rule There remain the Logical rules.
Suppose Typical examples, the rules for ‘and’:

p1 , . . . , pn |= q, 1 (lefthand rules). If p |= r then

p1 , . . . , pn , q |= r. (p and q) |= r.

Then If q |= r then

p1 , . . . , pn |= r. (p and q) |= r.
2 (rightthand rule). If p1 , . . . , pn |= q and p1 , . . . , pn |= r
The sentence q is cut out.
then
The cut rule is the only Gentzen rule in which we ‘lose’ a
whole sentence as we generate a new entailment. p1 , . . . , pn |= (q and r).

15 16
1.17
We can justify the rules for ‘and’ by noting that
1.18
(p and q) is true exactly when p and q are both true.
Truth table of ‘and’:
Charles Peirce
p q (p and q)
T T T
1839–1914
T F F introduced truth

F T F tables
F F F

17 18

1.19
1.20
But equally we can deduce the truth table of ‘and’
from Gentzen’s rules: • Conversely, by the axiom rule, p |= p
so by weakening, p, q |= p.
• By the axiom rule, p |= p.
Similarly p, q |= q.
So by the lefthand rule for ‘and’,
But then by the righthand rule for ‘and’,
(p and q) |= p.
p, q |= (p and q).
So if (p and q) is true then so is p.
So if p and q are both true, then so is (p and q).
Similarly if (p and q) is true then so is q.

19 20
1.21
1.22
Gentzen’s rules for ‘Every’:
Comment
3 (lefthand rule):
We can’t replace
If
(For everybody x,    x + ++)
(   Noam Chomsky + ++) |= r (   everybody + ++).
by
then For example
(For everybody x,    x + ++) |= r. (VALID:) I haven’t read Noam Chomsky. |= I haven’t
read Noam Chomsky.
(We can replace ‘Noam Chomsky’ by any name of a
(INVALID:) I haven’t read everybody. |= I haven’t
person, since ‘everybody’ is a quantifier ranging
read Noam Chomsky.
over people.)

21 22

1.23
4 (righthand rule for ‘Everybody’): 1.24
If Both of Gentzen’s rules for ‘Every’ follow the language and
practice of mathematicians.
p |= (   Mr or Mrs X + ++)
Otherwise he probably wouldn’t have discovered them.
then
Mathematicians had adjusted their language so that
p |= (For everybody x,    x + ++). entailments could often be recognised from their
grammatical structure.
Idea: If a statement about Mr or Mrs X must be true
This is a feature of Frege’s ‘logically perfect languages’.
regardless of who Mr or Mrs X is,
it must be true about everybody.

23 24
 1.26
5. Gentzen’s righthand rule for ‘If . . . then’:
1.25
Suppose

Gottlob Frege p, q |= r.

1848–1925 Then

p |= (If q then r).

25 26

1.26 1.27
Again if you think in terms of ‘reaching’ the conclusion from But this is an interpretation of Gentzen’s rules,
the premises, and it lands us in problems about what it is to assume
this rule says that to show you can reach the conclusion ‘for the sake of argument’ something we know is false.
(If q then r) One view is that Gentzen’s calculus shows how
assumptions ‘for the sake of argument’ can be explained
it’s enough to start from q (i.e. assume q)
without having to consider counterfactual implications.
and then reach r.

27 28
1.28 1.29

To introduce Gentzen’s other rules, we have to extend the 6. Gentzen’s lefthand rule for ‘If . . . then’:
notions of sequents and entailments, by allowing any Suppose
number of sentences on the righthand side.
p, r |= s
We say the sequent
and
p1 , . . . , pn |= q1 , . . . , qm
p |= q, s.
is valid, and an entailment, if there is no situation in which
p1 , . . . , pn are all true and q1 , . . . , qm are all false; Then
in other words, if in every situation where p1 , . . . , pn are all
true, at least one of q1 , . . . , qm is true. p, (If q then r) |= s.

29 30

1.30 1.31
The link between Gentzen’s rules and truth tables is not so Gentzen’s rules for ‘not-p’ (i.e. ‘It is not true that p’):
clear for ‘If . . . then’ as it is with ‘and’.
7 (lefthand). If
If ‘If . . . then’ has a truth table, then the Gentzen rules force
it to be p |= q, r
p q If p then q p, not-q |= r.
then
T T T
8 (righthand). If
T F F
p, q |= r
F T T
p |= not-q, r.
F F T then

31 32
1.32 1.33
Notation: We write We can use the Gentzen rules as a mathematical calculus.
(p ∧ q) for (p and q) ; When we do this, we normally write rather than |=.
(p ∨ q) for (p or q or both) ; Example:
(p → q) for (If p then q) ; (1) p, q q, r by axiom rule.
(2) p, q, r r by axiom rule.
¬p for not-p ;
(3) p, q, (q → r) r by (1), (2), left rule for →.
∀x for (For everything x),
(4) p, (q → r) p, r by axiom rule.
∃x for (There exists something x). (5) p, (p → q), (q → r) r by (3), (4), left rule for →.
First-order logic is logic using just these symbols. (6) (p → q), (q → r) (p → r) by right rule for →.

33 34

1.34
We proved:

(p → q), (q → r) (p → r).

Gentzen noticed that although the entailment ‘cuts out’ the 2.1
sentence q, the proof never uses the cut rule. SECOND TUTORIAL
His ‘Cut elimination theorem’ showed that in his calculus, Form and matter
the cut rule is never needed.
Hence we can construct a proof of an entailment by working
backwards from the entailment.
(This is the idea behind the tableau calculus.)

35 36
 2.3
By these tests, there are two clusters of subjects,
2.2 one around entailment and the other around definability,
The definition of logic with important overlaps between them.
Are we ready to come back to this question? Related to entailment:
Two naive tests of whether something belongs to logic: Proof theory.
• Do the people who study it call themselves logicians? Logic programming.
Constructive mathematics and foundations of
• Does it involve the same skills as other things that mathematics.
belong to logic? Modal and temporal logics.
Dynamic logics and logics of processes.
etc.

37 38

2.4
Related to definability:
2.5
Set theory.
Recursion theory.
This kind of definition of logic draws a picture of an area of
Lambda calculus. research,
Model theory. but it doesn’t answer any fundamental question.
Formal semantics of artificial or natural languages. Are there more fundamental questions that could lead us to
Formal specification theory. a more precise definition of logic?
etc.
(Myself I believe not, but this is a question that quite a lot of
Category theory and relation algebras are related to logic people have strong views on.)
but not in a simple way.
People disagree about whether fuzzy logic is a part of logic.

39 40
2.6
2.7
Entailments are usually instances of general laws
It’s useful to generalise the definition of entailment to cover
Recall the sequent we proved last time:
formulas as well as sentences:
(If p then q), (If q then r) |= (If p then r). If p1 , . . . , pn and q are formulas, then
The expression
p1 , . . . , pn |= q
(If p then q)
means:
is not a sentence, because it contains variables p, q.
Whenever we replace the variables by appropriate
So we call it a formula.
expressions so as to get sentences, then the sentences
What we showed is that if we replace p and q by any sentences, got from p1 , . . . , pn entail the sentence got from q.
then the resulting sequent is a valid entailment.

41 42

2.8
Back to our two sentences:
(a) Noam Chomsky is very clever. 2.9

(b) Noam Chomsky is clever. We can generalise to a formula with variables X and Y :

Here (a) entails (b). (c) X is very Y .

Compare: (d) X is Y .
(a’) Georgia is very mountainous. In our new sense of entailment, (c) entails (d).
(b’) Georgia is mountainous.
Again (a’) entails (b’).

43 44
2.10
Some people have suggested that when we replace
2.11
sentences by formulas with variables,
we are ‘abstracting away the content’.
Immanuel Kant: Immanuel Kant
Logic contains no matter at all, only form of thought. 1724–1804
(From Dohna-Wundlacken Logic)

45 46

2.13
According to the textbook of Hilbert and Ackermann,
Grundzuege der Theoretischen Logik (1928), entailments like 2.15
this can be handled by logic if we apply ‘conceptual The mathematicians’ view:
analysis’. We can leave conceptual analysis to the philosophers and
Their example was the linguists.

There is a son. |= There is a father. This is too fast. Recall the sequent we proved earlier:

In their conceptual analysis, ‘y is a son of x’ means ‘y is male (If p then q), (If q then r) |= (If p then r).
and x is is either the male parent of y or the female parent of
y’, and ‘x is a father of y’ means ‘x is the male parent of y’.

47 48
 2.17
Analysis of Burley’s counterexample
2.16 The meaning of Burley’s r changes according to its context.
Counterexample (Walter Burley, c. 1300) It expresses ‘The statement of mine just mentioned is true’.

p I call you a donkey. We have to put another condition on the sentences used to
replace variables in entailments: Their contribution to the
q I call you an animal.
truth or falsity of the sentence as a whole depends only on their
r I state the truth. truth value in the (non-verbal) situation in question.
So to apply the sequent calculus to sentences of English,
we must be prepared to do some conceptual analysis.

49 50

2.18 2.19

Kant also believed that entailments are related to ‘thought’. Some people believe that we have a ‘deducing’ module,
which we use in all our thinking
We often ‘think’ entailments
and possibly in our use of language too.
p |= q Kant again:
in the sense that we believe p, Logical rules are not ones according to which we
and as a result we come to believe q too. think, but according to which we ought to think.

51 52
 2.22
The Wason selection task (1966)
You will be shown four cards.
2.20
Each of these cards has a number written on one side
Problem: Work of Peter Wason and others shows that and a letter on the other.
in fact our intuitive reasoning often disagrees with
You will also be shown a statement S about the cards.
logical entailments.
Then you must answer the following question:
Which card or cards must I turn over in order to
check whether the statement S is true?

53 54

2.24
2.23
The true answer is cards E and 7.
S: If a card has a vowel on one side, it has an even number
In my logic class (which was already expert with truth
on the other side.
tables):

E and 7 0%
E 50%

E K 4 7 E and 4
K and 7
other
20 %
15%
15%.
This experiment always gives similar results.

55 56
2.25 2.26

How did we evolve to be so illogical? In these circumstances it is not obvious that we ought
always to reason logically.
Probable answer: The most important things for the species
Logical reasoning is expensive in time and effort.
are
It uses up large amounts of working memory and requires
• to avoid being killed by tigers or buses, one to form abstract concepts.
• to catch, dig or buy meat or vegetables, Oaksford and Chater (1994) analysed the Wason selection
task in terms of ‘optimal data selection’, and got a prediction
• to seduce members of the opposite sex.
not far from the observed facts.

57 58

2.27 2.28
Summary Eliminating false entailments
Logicians can often explain entailments as examples of We can show that a rule is false by giving a counterexample.
general laws.
For example Aristotle seems to have believed the following
One can develop these general laws as a mathematical entailment:
theory.
In a moment we shall see that one can not only prove laws, If p then q. If not-p then q. |= Not-q.
but also refute incorrect laws of entailment. Counterexample:
But we hit serious practical and philosophical questions p Rome is beautiful.
when we apply the general laws to either (a) entailments in
q Rome is a town.
ordinary English or (b) intuitive human reasoning.

59 60
2.29
Euclid’s parallel postulate
Euclid wrote some axioms for geometry, including one 2.30
known as the Parallel Postulate. 19th century mathematicians gave the answer No,
(A modern form of the Parallel Postulate: For every infinite by treating the terms ‘point’, ‘line’, ‘passes through’ etc. as
straight line L in the plane and every point P not on L, variables, and then replacing these variables by other
there is exactly one infinite straight line in the plane that expressions so as to make the Parallel Postulate false
passes through P and has no points in common with L.) but the other axioms true.

An old question: Do Euclid’s other axioms together entail

the Parallel Postulate?

61 62

2.31
Schwarz’s tesselation
(1872) 2.32
Hence the question: If an entailment is written in the
language of Gentzen’s sequences, what is the relation
between
(a) The sequent is provable in the sequent calculus.
(b) There is a counterexample to the sequent?
The completeness theorem (essentially Goedel, 1930) says that
for first-order logic, exactly one of (a) and (b) holds.

63 64
 3.2
We saw that we can use the Gentzen sequent calculus to
prove valid sequents in first-order logic.
3.1 By the completeness theorem, we can prove all and only the
valid sequents this way.
THIRD TUTORIAL
Truth and proof There are several other proof calculi with various strong and
weak points.
For example Gentzen’s natural deduction calculus uses proofs
that (roughly) start from the premises and finish with the
conclusion.

65 66

3.4
Example

p q r (p → q) (q → r) (p → r)
3.3 T T T T T T
Propositional logic is first-order logic using only ∧, ∨, → T T F T F F
and ¬, not ∀ or ∃. T F T F T T
We can use truth tables as a kind of proof calculus for T F F F T F
propositional entailments. F T T T T T
F T F T F T
F F T T T T
F F F T T T

67 68
 3.6

3.5
Many mathematical problems can be solved by truth tables,
by translating them into propositional logic.
Truth tables are more than a proof calculus for
propositional entailments. Example. A proper colouring of a map is a colouring of the
countries in the map, so that if two countries have a border
They form a decision procedure. in common then they are coloured different colours.
This means we can use truth tables to check mechanically
whether or not any given propositional sequent is valid. In 1976 Appel and Haken used a computer to prove a very
old conjecture: Every map on the surface of a sphere has a proper
colouring using at most four colours.

69 70

3.8
3.7
Instead we number the countries,
Suppose we have a map and we want to know whether it and for each country i and each colour C we write
has a proper colouring with three colours (R, G, B).
piC
Just trying to colour it is not a good strategy.
We will almost certainly have to keep changing colours as for the statement:
we go.
Country i has colour C.

71 72
3.9
Requirements
(1) For every country i,
3.10
¬(piR ∧ piG ), ¬(piR ∧ piB ), ¬(piG ∧ piB ). Now we draw a truth table showing all possible values of
the propositional variables piC , and we look for a row in
(2) For every country i,
which all the formulas (1), (2), (3) have the value True.
((piR ∨ piG ) ∨ piB ).
This row tells us how to colour the map:
(3) For every pair of countries i and j with a common if piC is true in the row, colour country i colour C.
border,

¬(piR ∧ pjR ), ¬(piG ∧ pjG ), ¬(piB ∧ pjB ).

73 74

3.11
Problem. 3.12
Suppose our map has 100 countries. In 2000 the Clay Mathematics Institute offered a prize of a
Then there are 300 propositional variables, million dollars to anybody who can show whether there are
and the number of rows in the truth table is mechanical methods for solving truth table problems of this
kind in a reasonable time.
2300 , which is about 1090 .
This is the ‘P = NP’ problem.
The size of the calculation increases exponentially with the
number of countries.

75 76
3.13
Truth table calculations 3.14

We calculate the truth table for one of the sentences in (1) of Next we join p1R and p1G with ∧,
slide 3.9: and we write the truth values for (p1R ∧ p1G ) under ∧:

p1R p1G ¬ (p1R ∧ p1G ) p1R p1G ¬ (p1R ∧ p1G )

T T T T T T T T T
T F T F T F T F F
F T F T F T F F T
F F F F F F F F F

We write under each letter its truth value in each row.

77 78

3.15
Finally we add ¬ at the left, 3.16
and we write the truth value of the whole formula under ¬: In this calculation we calculate the truth values,
p1R p1G ¬ (p1R ∧ p1G ) starting from the sentence letters
and working up to more and more complex formulas.
T T F T T T
The value of a compound formula is determined by the
T F T T F F
values of its immediate constituents,
F T T F F T including the symbol (∧, ¬) used to combine them.
F F T F F F So the assignment of truth values is compositional.
⇑

79 80
3.17
In 1933 Alfred Tarski showed how to extend these 3.18
calculations to logic with quantifiers. Suppose that instead of the formulas of first-order logic,
On the left, instead of truth value assignments we have we consider meaningful sentences of a natural language.
structures Then in place of structures we can take ‘possible worlds’,
(in general infinitely many) and we can follow the suggestion of Carnap and Quine
and assignments of elements of these structures to the free that Tarski’s way of assigning truth values is a good
variables. substitute for assigning meanings.

The ‘value’ of a formula is the class of those structures and The result is Montague’s semantics for fragments of English.
assignments that make it true. The semantics is compositional, following Tarski’s example.
These values are still assigned compositionally.

81 82

3.19
Testing validity 3.21

For full first order logic we don’t have a way of testing

whether any given entailment is valid. G. W. Leibniz
In fact Alonzo Church showed in 1936 that there can’t be 1646–1716
such a method, either fast or slow.

83 84
3.22 3.23

Leibniz hoped to build a calculus (a ‘Universal Three questions:

Characteristic’) that would allow us to solve problems of
(1) Is this a proof?
reasoning by pure calculation.
(2) Does this have a proof?
Important point: He never claimed his calculus would
determine whether a given statement is true. (3) Is this true?
He did claim that his calculus would determine whether Apparently Leibniz foresaw that question (1) is decidable,
any proposed proof is correct or not. but he made no claim about (2) or (3).

85 86

3.24 3.25
In 1931 Kurt Goedel showed that the question whether a We consider the structure N consisting of the natural
given arithmetical statement is true is an undecidable numbers.
question.
0, 1, 2, 3, . . .
In 1970 he wrote to a student (Yossef Balas) saying that the
key to proving this was to understand the difference We write symbols S for ‘plus one’, and 0 for the number
between truth and proof. zero.

We shall sketch a proof of Church’s theorem that rests on the We write down some true statements about N, using these
same idea. symbols:

87 88
 3.27
By a diophantine sentence we mean a sentence of the form
3.26
There are numbers x1 , . . . , xn such that s = t.
If x and y are numbers with S(x) = S(y) then x = y.
There is no number x such that 0 = S(x). where s and t are arithmetical expressions using x1 , . . . , xn ,
If x = 0 then there is y such that x = S(y). 0, S, + and ..
For every number x, x + 0 = x and x.0 = 0. Example. The sentence
For all numbers x and y, x + S(y) = S(x + y) and
There are numbers x, y, z such that x2 + y 2 = 4z + 3.
x.S(y) = x.y + x.
The set of these five statements is called Q. is a diophantine sentence,
writing SSS(u) for u + 3 and SSSS(0) for 4.
This sentence happens to be false.

89 90

3.29

3.28 Goedel and Yuri Matiyasevich, developing ideas of Leibniz,

showed that if we use numbers to label the symbols in a
In 1888 Richard Dedekind showed (in effect) that for every
proof, then we can express and prove properties of proofs
diophantine sentence p, p is true if and only if Q entails p.
by using diophantine sentences.
So truth and provability agree up as far as diophantine
In particular, if we have a mechanical test for whether any given
sentences.
diophantine sentence is true, then for every number n the
Goedel’s intuition was that this agreement must break down sentence
for more complex sentences, and it’s just a matter of finding
how far we have to search for the breakdown. The diophantine sentence with number n is false.
can be written as a diophantine sentence θ(n).

91 92
3.31
Goedel showed also that if this formula θ(x) exists, then we
can find a number n such that the sentence with number n is 3.32
in fact
It follows that there is no mechanical test for whether or not
θ(n). a sequent of first-order logic is a valid entailment.

So θ(n) expresses that θ(n) is false. For if there was such a test,
But this is impossible, since θ(n) is true if and only if θ(n) is we could use it to test whether or not a given diophantine
false. sentence θ is true,
(Compare the Liar paradox: ‘This sentence is not true’.) by checking whether or not Q θ.

So there is test for whether any given diophantine sentence

is true.

93 94