Gödel, Escher, Bach An Eternal Golden Braid by Douglas R. Hofstadter

CHAPTER VII

The Propositional Calculus

Words and Symbols

THE PRECEDING DIALOGUE is reminiscent of the Two-Part Invention by

Lewis Carroll. In both, the Tortoise refuses to use normal, ordinary words

in the normal, ordinary way-or at least he refuses to do so when it is not to

his advantage to do so. A way to think about the Carroll paradox was given

last Chapter. In this Chapter we are going to make symbols do what

Achilles couldn't make the Tortoise do with his words. That is, we are going

to make a formal system one of whose symbols will do just what Achilles

wished the word 'and' would do, when spoken by the Tortoise, and another

of whose symbols will behave the way the word's 'if ... then .. .' ought to

behave. There are only two other words which we will attempt to deal with:

'or' and 'not'. Reasoning which depends only on correct usage of these four

words is termed propositional reasoning.

Alphabet and First Rule of the Propositional Calculus

I will present this new formal system, called the Propositional Calculus, a little

like a puzzle, not explaining everything at once, but letting you figure

things out to some extent. We begin with the list of symbols:

p

< >

Q

v

R

:::>

The first rule of this system that I will reveal is the following:

RULE OF JOINING: If x and yare theorems of the system, then so is the

string < x/\ y >.

This rule takes two theorems and combines them into one. It should

remind you of the Dialogue.

Well-Formed Strings

There will be several other rules of inference, and they will all be presented

shortly-but fi.rst, it is important to define a subset of all strings, namely the

The Propositional Calculus^181