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.