1Propositional calculus
II Logic and Set Theory
1.1 Propositions
We’ll start by defining propositions, which are the statements we will consider
in propositional calculus.
Definition (Propositions). Let
P
be a set of primitive propositions. These are a
bunch of (meaningless) symbols (e.g.
p
,
q
,
r
), which are used as the basic building
blocks of our more interesting propositions. These are usually interpreted to
take a truth value. Usually, any symbol (composed of alphabets and subscripts)
is in the set of primitive propositions.
The set of propositions, written as L or L(P ), is defined inductively by
(i) If p ∈ P , then p ∈ L.
(ii) ⊥ ∈ L, where ⊥ is read as “false” (also a meaningless symbol).
(iii) If p, q ∈ L, then (p ⇒ q) ∈ L.
Example. If our set of primitive propositions is
P
=
{p, q, r}
, then
p ⇒ q
,
p ⇒ ⊥, ((p ⇒ q) ⇒ (p ⇒ r)) are propositions.
To define L formally, we let
L
0
= {⊥} ∪ P
L
n+1
= L
n
∪ {(p ⇒ q) : p, q ∈ L
n
}.
Then we define L = L
0
∪ L
1
∪ L
2
∪ ···.
In formal language terms,
L
is the set of finite strings of symbols from the
alphabet
⊥ ⇒
( )
p
1
p
2
···
that satisfy some formal grammar rule (e.g. brackets
have to match).
Note here that officially, the only relation we have is
⇒
. The familiar “not”,
“and” and “or” do not exist. Instead, we define them to be abbreviations of
certain expressions:
Definition (Logical symbols).
¬p (“not p”) is an abbreviation for (p ⇒ ⊥)
p ∧ q (“p and q”) is an abbreviation for ¬(p ⇒ (¬q))
p ∨ q (“p or q”) is an abbreviation for (¬p) ⇒ q
The advantage of having just one symbol
⇒
is that when we prove something
about our theories, we only have to prove it for
⇒
, instead of all
⇒, ¬, ∧
and
∨
individually.