Logic in Computer Science
An Introductory Course for Master Students
Wang Ji
jiwang@nudt.edu.cn
Lecture 10
Logic in Computer Science { p.1/21
Completenss
Logic in Computer Science { p.2/21
Two forms of Completeness Theorem
Let be a set of w s. The following parts are
equivalent.
If j= A then ‘ A
If is consistent, then is satis able.
Logic in Computer Science { p.3/21
Sequence of consistent sets of w s
Partially Ordered Set A relation on a set S is
called partial ordering or partial order if it is
re exive, antisymmetric and transitive. A set S
together with a partial ordering R is called a
partially ordered set, or poset.
Totally Ordered Set If < S;R > is a poset and
every two elements of S are comparable, S is
called a totally ordered set or linearly ordered
set. A totally ordered set is also called a chain.
Lemma Let S 2
L(F)
. If < S; > is a totally
ordered set, and for any 2 S, is consistent,
then
S
S is consistent.
Logic in Computer Science { p.4/21
Existence of consistent and maximal set
Theorem Let L(F) be consistent. There
exists
0
2 L(F) such that
1.
0
, and
2.
0
is consistent and maximal.
Zorn’s Lemma Let S be a nonempty set such that
for any chain Z S, the set
S
Z 2 S. Then
there is a m 2 S which is maximal in the sense
that it is not a subset of any other element of S.
Logic in Computer Science { p.5/21
Expansion
Let F
1
and F
2
be two rst order systems.
1. If L(F
1
) L(F
2
), then we say that F
2
is an
expansion of F
1
.
2. If L(F
1
) L(F
2
), then we say that F
2
is a
proper expansion of F
1
.
3. F
2
is an expansion of F
1
i every constant of F
1
is a constant F
2
.
Logic in Computer Science { p.6/21
Extension
Let F
1
and F
2
be two rst order systems.
1
L(F
1
) and
2
L(F
2
).
1. If L(F
1
) L(F
2
) and
Th(F
1
S
1
) Th(F
2
S
2
), then we say that
F
2
S
2
is an extension of F
1
S
1
.
2. If for every A 2 L(F
1
),
1
‘
F
1
A i
2
‘
F
2
A,
then we say that
F
2
S
2
is a conservative extension of F
1
S
1
.
Logic in Computer Science { p.7/21
Expansion and Extension
1. If F
2
is an expansion of F
1
, then
Th(F
1
) Th(F
2
).
2. If F
2
S
2
is a conservative extension of F
1
S
1
,
then
Th(F
1
[
1
) = Th(F
2
[
2
) \L(F
1
)
Logic in Computer Science { p.8/21
Expansion, Extension and Consistency
1. If F
2
S
2
is a conservative extension of F
1
S
1
,
then F
1
S
1
is consistent i F
2
S
2
is
consistent.
2. Let F
1
and F
2
be formulations of F, so that F
2
is an expansion of F
1
obtained by adding
additional individual constants to the set of
constants of F
1
. Let L(F
1
), Then
(a) F
2
S
is a conservative extension of F
1
S
,
and
(b) F
1
S
is consistent i F
2
S
is consistent.
Logic in Computer Science { p.9/21
Frugal Interpretation
An interpretation < D;I
0
> for F is said to be
frugal i #D #L(F).
An interpretation I is said to be a frugal model
of if it is a frugal interpretation of .
Logic in Computer Science { p.10/21
Ideas of Proof of Completeness Theorem
We begin with a consistent set . In steps 1-3 we
extend to for which
is consistent and is maximal in the sense that
for any w A either A 2 or A 2 .
For any w A and individual variable x, there is
an individual constant d such that
8xA S
x
d
A 2
Then in step 4, we form an interpretation I and
2
I
which satis es .
Logic in Computer Science { p.11/21
Step 1
Expand the language by adding countable in nite set
of new individual constants.
1. F F
+
2. F [ F
+
[
Logic in Computer Science { p.12/21
Step 2
For each A 2 L(F
+
) and each individual variable x,
add to the w
8xA S
x
d
A 2
where d is one of the new individual constant. The
resulted set [
0
of w s is still consistent.
Logic in Computer Science { p.13/21
Step 3
Extend [
0
to a consistent and maximal set .
Logic in Computer Science { p.14/21
Step 4
De ne I =< D;I
0
>, where
1. D = Term
F
+
2. I
0
(a) If d is an individual constant, then I(d) = d.
(b) If f
n
is an n-ary function constant, then
I(f
n
) = f
n
.
(c) If p is a propositional constant, then
I(p) = T i p 2 .
(d) If P
n
is an n-ary predicate constant, then
I(P
n
) = P
n
, where < t
1
; ;t
n
>2 P
n
i
P
n
(t
1
; ;t
n
) 2 .
Logic in Computer Science { p.15/21
Step 4 (continued)
2
I
is de ned as
1. If x is an individual variable, then (x) = d.
2. If f
n
is an n-ary function variable, then
(f
n
) = f
n
.
3. If p is a propositional variable, then (p) = T i
p 2 .
4. If P
n
is an n-ary predicate variable, then
(P
n
) = P
n
, where < t
1
; ;t
n
>2 P
n
i
P
n
(t
1
; ;t
n
) 2 .
Logic in Computer Science { p.16/21
I?
I(t)( ) = t
I(A)( ) = T i A 2
Logic in Computer Science { p.17/21
G
odel Completeness Theorem
1. If j= A, then ‘ A.
2. Any consistent set of w s is satis able.
Logic in Computer Science { p.18/21
Consistent vs Satis able
Let L(F). The following parts are equivalent.
is consistent.
There exists a frugal interpretation I such that
is satis able in I.
is satis able.
Logic in Computer Science { p.19/21
Let L
0
(F). The following parts are equivalent.
is consistent.
has a frugal model.
has a model.
Logic in Computer Science { p.20/21
Compactness
Let L(F).
is satis able i every nite subset of is
satis able.
is consistent i every nite subset of is
consistent.
Let L
0
(F).
has a model i every nite subset of has a
model.
Logic in Computer Science { p.21/21