<<

. 3
( 11 .)



>>


Truth tables are often used even when the formula in question is
not broken down all the way into atomic formulas. For example, if ±
and β are any formulas and we know that ± is true but β is false, then
the truth of (± ’ (¬β)) can be determined by means of the following
table:
± β (¬β) (± ’ (¬β))
TF T T
Definition 2.2. If v is a truth assignment and • is a formula, we
will often say that v satis¬es • if v(•) = T . Similarly, if Σ is a set
of formulas, we will often say that v satis¬es Σ if v(σ) = T for every
σ ∈ Σ. We will say that • (respectively, Σ) is satis¬able if there is
some truth assignment which satis¬es it.
Definition 2.3. A formula • is a tautology if it is satis¬ed by
every truth assignment. A formula ψ is a contradiction if there is no
truth assignment which satis¬es it.
For example, (A4 ’ A4) is a tautology while (¬(A4 ’ A4)) is a
contradiction, and A4 is a formula which is neither. One can check
whether a given formula is a tautology, contradiction, or neither, by
grinding out a complete truth table for it, with a separate line for each
possible assignment of truth values to the atomic subformulas of the
formula. For A3 ’ (A4 ’ A3 ) this gives
A3 A4 A4 ’ A3 A3 ’ (A4 ’ A3)
TT T T
TF T T
FT F T
FF T T
so A3 ’ (A4 ’ A3) is a tautology. Note that, by Proposition 2.2, we
need only consider the possible truth values of the atomic sentences
which actually occur in a given formula.
One can often use truth tables to determine whether a given formula
is a tautology or a contradiction even when it is not broken down all
the way into atomic formulas. For example, if ± is any formula, then
the table
± (± ’ ±) (¬(± ’ ±))
T T F
F T F
demonstrates that (¬(± ’ ±)) is a contradiction, no matter which
formula of LP ± actually is.
14 2. TRUTH ASSIGNMENTS

Proposition 2.5. If ± is any formula, then ((¬±) ∨ ±) is a tau-
tology and ((¬±) § ±) is a contradiction.
Proposition 2.6. A formula β is a tautology if and only if ¬β is
a contradiction.
After all this warmup, we are ¬nally in a position to de¬ne what it
means for one formula to follow logically from other formulas.
Definition 2.4. A set of formulas Σ implies a formula •, written
as Σ |= •, if every truth assignment v which satis¬es Σ also satis¬es •.
We will often write Σ • if it is not the case that Σ |= •. In the case
where Σ is empty, we will usually write |= • instead of … |= •.
Similarly, if ∆ and “ are sets of formulas, then ∆ implies “, written
as ∆ |= “, if every truth assignment v which satis¬es ∆ also satis¬es
“.
For example, { A3, (A3 ’ ¬A7) } |= ¬A7 , but { A8 , (A5 ’ A8) }
A5. (There is a truth assignment which makes A8 and A5 ’ A8 true,
but A5 false.) Note that a formula • is a tautology if and only if |= •,
and a contradiction if and only if |= (¥).
Proposition 2.7. If “ and Σ are sets of formulas such that “ ⊆ Σ,
then Σ |= “.
Problem 2.8. How can one check whether or not Σ |= • for a
formula • and a ¬nite set of formulas Σ?
Proposition 2.9. Suppose Σ is a set of formulas and ψ and ρ are
formulas. Then Σ ∪ {ψ} |= ρ if and only if Σ |= ψ ’ ρ.
Proposition 2.10. A set of formulas Σ is satis¬able if and only
if there is no contradiction χ such that Σ |= χ.
CHAPTER 3


Deductions

In this chapter we develop a way of de¬ning logical implication
that does not rely on any notion of truth, but only on manipulating
sequences of formulas, namely formal proofs or deductions. (Of course,
any way of de¬ning logical implication had better be compatible with
that given in Chapter 2.) To de¬ne these, we ¬rst specify a suitable
set of formulas which we can use freely as premisses in deductions.
Definition 3.1. The three axiom schema of LP are:
A1: (± ’ (β ’ ±))
A2: ((± ’ (β ’ γ)) ’ ((± ’ β) ’ (± ’ γ)))
A3: (((¬β) ’ (¬±)) ’ (((¬β) ’ ±) ’ β)).
Replacing ±, β, and γ by particular formulas of LP in any one of the
schemas A1, A2, or A3 gives an axiom of LP .
For example, (A1 ’ (A4 ’ A1 )) is an axiom, being an instance of
axiom schema A1, but (A9 ’ (¬A0 )) is not an axiom as it is not the
instance of any of the schema. As had better be the case, every axiom
is always true:
Proposition 3.1. Every axiom of LP is a tautology.
Second, we specify our one (and only!) rule of inference.1
Definition 3.2 (Modus Ponens). Given the formulas • and (• ’
ψ), one may infer ψ.
We will usually refer to Modus Ponens by its initials, MP. Like any
rule of inference worth its salt, MP preserves truth.
Proposition 3.2. Suppose • and ψ are formulas. Then { •, (• ’
ψ) } |= ψ.
With axioms and a rule of inference in hand, we can execute formal
proofs in LP .
1
Natural deductive systems, which are usually more convenient to actually
execute deductions in than the system being developed here, compensate for having
few or no axioms by having many rules of inference.
15
16 3. DEDUCTIONS

Definition 3.3. Let Σ be a set of formulas. A deduction or proof
from Σ in LP is a ¬nite sequence •1•2 . . . •n of formulas such that for
each k ¤ n,
1. •k is an axiom, or
2. •k ∈ Σ, or
3. there are i, j < k such that •k follows from •i and •j by MP.
A formula of Σ appearing in the deduction is called a premiss. Σ proves
a formula ±, written as Σ ±, if ± is the last formula of a deduction
from Σ. We™ll usually write ± for … ±, and take Σ ∆ to mean
that Σ δ for every formula δ ∈ ∆.
In order to make it easier to verify that an alleged deduction really
is one, we will number the formulas in a deduction, write them out in
order on separate lines, and give a justi¬cation for each formula. Like
the additional connectives and conventions for dropping parentheses in
Chapter 1, this is not o¬cially a part of the de¬nition of a deduction.
Example 3.1. Let us show that • ’ •.
1. (• ’ ((• ’ •) ’ •)) ’ ((• ’ (• ’ •)) ’ (• ’ •)) A2
2. • ’ ((• ’ •) ’ •) A1
3. (• ’ (• ’ •)) ’ (• ’ •) 1,2 MP
4. • ’ (• ’ •) A1
5. • ’ • 3,4 MP
Hence • ’ •, as desired. Note that indication of the formulas from
which formulas 3 and 5 beside the mentions of MP.
Example 3.2. Let us show that { ± ’ β, β ’ γ } ± ’ γ.
1. (β ’ γ) ’ (± ’ (β ’ γ)) A1
2. β ’ γ Premiss
3. ± ’ (β ’ γ) 1,2 MP
4. (± ’ (β ’ γ)) ’ ((± ’ β) ’ (± ’ γ)) A2
5. (± ’ β) ’ (± ’ γ) 4,3 MP
6. ± ’ β Premiss
7. ± ’ γ 5,6 MP
Hence { ± ’ β, β ’ γ } ± ’ γ, as desired.
It is frequently convenient to save time and e¬ort by simply referring
to a deduction one has already done instead of writing it again as part
of another deduction. If you do so, please make sure you appeal only
to deductions that have already been carried out.
Example 3.3. Let us show that (¬± ’ ±) ’ ±.
1. (¬± ’ ¬±) ’ ((¬± ’ ±) ’ ±) A3
3. DEDUCTIONS 17

2. ¬± ’ ¬± Example 3.1
3. (¬± ’ ±) ’ ± 1,2 MP
Hence (¬± ’ ±) ’ ±, as desired. To be completely formal, one
would have to insert the deduction given in Example 3.1 (with • re-
placed by ± throughout) in place of line 2 above and renumber the
old line 3.
Problem 3.3. Show that if ±, β, and γ are formulas, then
1. { ± ’ (β ’ γ), β } ± ’ γ
2. ± ∨ ¬±
Example 3.4. Let us show that ¬¬β ’ β.
1. (¬β ’ ¬¬β) ’ ((¬β ’ ¬β) ’ β) A3
2. ¬¬β ’ (¬β ’ ¬¬β) A1
3. ¬¬β ’ ((¬β ’ ¬β) ’ β) 1,2 Example 3.2
4. ¬β ’ ¬β Example 3.1
5. ¬¬β ’ β 3,4 Problem 3.3.1
Hence ¬¬β ’ β, as desired.
Certain general facts are sometimes handy:
Proposition 3.4. If •1•2 . . . •n is a deduction of LP , then •1 . . . •
is also a deduction of LP for any such that 1 ¤ ¤ n.
δ ’ β, then “
Proposition 3.5. If “ δ and “ β.
Proposition 3.6. If “ ⊆ ∆ and “ ±, then ∆ ±.
Proposition 3.7. If “ ∆ and ∆ σ, then “ σ.
The following theorem often lets one take substantial shortcuts
when trying to show that certain deductions exist in LP , even though
it doesn™t give us the deductions explicitly.
Theorem 3.8 (Deduction Theorem). If Σ is any set of formulas
and ± and β are any formulas, then Σ ± ’ β if and only if Σ∪{±}
β.
• ’ •. By the Deduction
Example 3.5. Let us show that
Theorem it is enough to show that {•} •, which is trivial:
1. • Premiss
Compare this to the deduction in Example 3.1.
Problem 3.9. Appealing to previous deductions and the Deduction
Theorem if you wish, show that:
1. {δ, ¬δ} γ
18 3. DEDUCTIONS

2. • ’ ¬¬•
3. (¬β ’ ¬±) ’ (± ’ β)
4. (± ’ β) ’ (¬β ’ ¬±)
5. (β ’ ¬±) ’ (± ’ ¬β)
6. (¬β ’ ±) ’ (¬± ’ β)
7. σ ’ (σ ∨ „ )
8. {± § β} β
9. {± § β} ±
CHAPTER 4


Soundness and Completeness

How are deduction and implication related, given that they were
de¬ned in completely di¬erent ways? We have some evidence that they
behave alike; compare, for example, Proposition 2.9 and the Deduction
Theorem. It had better be the case that if there is a deduction of a
formula • from a set of premisses Σ, then • is implied by Σ. (Otherwise,
what™s the point of de¬ning deductions?) It would also be nice for the
converse to hold: whenever • is implied by Σ, there is a deduction of
• from Σ. (So anything which is true can be proved.) The Soundness
and Completeness Theorems say that both ways do hold, so Σ • if
and only if Σ |= •, i.e. and |= are equivalent for propositional logic.
One direction is relatively straightforward to prove . . .
Theorem 4.1 (Soundness Theorem). If ∆ is a set of formulas and
± is a formula such that ∆ ±, then ∆ |= ±.
. . . but for the other direction we need some additional concepts.
Definition 4.1. A set of formulas “ is inconsistent if “ ¬(± ’
±) for some formula ±, and consistent if it is not inconsistent.
For example, {A41} is consistent by Proposition 4.2, but it follows
from Problem 3.9 that {A13, ¬A13} is inconsistent.
Proposition 4.2. If a set of formulas is satis¬able, then it is con-
sistent.
Proposition 4.3. Suppose ∆ is an inconsistent set of formulas.
Then ∆ ψ for any formula ψ.
Proposition 4.4. Suppose Σ is an inconsistent set of formulas.
Then there is a ¬nite subset ∆ of Σ such that ∆ is inconsistent.
Corollary 4.5. A set of formulas “ is consistent if and only if
every ¬nite subset of “ is consistent.
To obtain the Completeness Theorem requires one more de¬nition.
Definition 4.2. A set of formulas Σ is maximally consistent if Σ
is consistent but Σ ∪ {•} is inconsistent for any • ∈ Σ.
/
19
20 4. SOUNDNESS AND COMPLETENESS

That is, a set of formulas is maximally consistent if it is consistent,
but there is no way to add any other formula to it and keep it consistent.
Problem 4.6. Suppose v is a truth assignment. Show that Σ =
{ • | v(•) = T } is maximally consistent.
We will need some facts concerning maximally consistent theories.
Proposition 4.7. If Σ is a maximally consistent set of formulas,
• is a formula, and Σ •, then • ∈ Σ.
Proposition 4.8. Suppose Σ is a maximally consistent set of for-
mulas and • is a formula. Then ¬• ∈ Σ if and only if • ∈ Σ.
/
Proposition 4.9. Suppose Σ is a maximally consistent set of for-
mulas and • and ψ are formulas. Then • ’ ψ ∈ Σ if and only if
• ∈ Σ or ψ ∈ Σ.
/
It is important to know that any consistent set of formulas can be
expanded to a maximally consistent set.
Theorem 4.10. Suppose “ is a consistent set of formulas. Then
there is a maximally consistent set of formulas Σ such that “ ⊆ Σ.
Now for the main event!
Theorem 4.11. A set of formulas is consistent if and only if it is
satis¬able.
and |= in slightly
Theorem 4.11 gives the equivalence between
disguised form.
Theorem 4.12 (Completeness Theorem). If ∆ is a set of formulas
and ± is a formula such that ∆ |= ±, then ∆ ±.
It follows that anything provable from a given set of premisses must
be true if the premisses are, and vice versa. The fact that and |= are
actually equivalent can be very convenient in situations where one is
easier to use than the other. For example, most parts of Problems 3.3
and 3.9 are much easier to do with truth tables instead of deductions,
even if one makes use of the Deduction Theorem.
Finally, one more consequence of Theorem 4.11.
Theorem 4.13 (Compactness Theorem). A set of formulas “ is
satis¬able if and only if every ¬nite subset of “ is satis¬able.
We will not look at any uses of the Compactness Theorem now,
but we will consider a few applications of its counterpart for ¬rst-order
logic in Chapter 9.
First-Order Logic
CHAPTER 5

<<

. 3
( 11 .)



>>