1Propositional calculus
II Logic and Set Theory
1 Propositional calculus
Propositional calculus is the study of logical statements such
p ⇒ p
and
p ⇒
(
q ⇒ p
). As opposed to predicate calculus, which will be studied in Chapter 4,
the statements will not have quantifier symbols like ∀, ∃.
When we say “
p ⇒ p
is a correct”, there are two ways we can interpret this.
We can interpret this as “no matter what truth value
p
takes,
p ⇒ p
always has
the truth value of “true”.” Alternatively, we can interpret this as “there is a
proof that p ⇒ p”.
The first notion is concerned with truth, and does not care about whether we
can prove things. The second notion, on the other hand, on talks about proofs.
We do not, in any way, assert that
p ⇒ p
is “true”. One of the main objectives
of this chapter is to show that these two notions are consistent with each other.
A statement is true (in the sense that it always has the truth value of “true”) if
and only if we can prove it. It turns out that this equivalence has a few rather
striking consequences.
Before we start, it is important to understand that there is no “standard”
logical system. What we present here is just one of the many possible ways of
doing formal logic. In particular, do not expect anyone else to know exactly how
your system works without first describing it. Fortunately, no one really writes
proof with formal logic, and the important theorems we prove (completeness,
compactness etc.) do not depend much on the exact implementation details of
the systems.