150
Mathematical Aspects of Logic Programming Semantics
T P (J), we must have a ground instance A ← L 1 , . . . , L m of a clause in P
with J |= L 1 ∧ · · · ∧ L m . If I |= L 1 ∧ · · · ∧ L m , then l(L k ) < l(A) ≤ α for
all k, and since J and K agree on all atoms of level less than α, we obtain
K |= L 1 ∧· · ·∧L m , and hence A ∈ T P (K). If there is some L k such that I |= L k ,
then without loss of generality l(L k ) < l(A) ≤ α by Definition 5.1.12. Now,
if the predicate symbol of L k belongs to Neg
∗ , then, since d 1 (J, I) ≤ 2
−α ,
P
we obtain from J |= L k that I |= L k , which is a contradiction. Also, if the
predicate symbol of L k does not belong to Neg
∗ , then L k is an atom, and
P
since f (J) ≤ 2
−α , we obtain I |= L k , again a contradiction. This establishes
(c) and completes the proof.
•
5.1.4 Φ-Accessible Programs
Definition 5.1.12 of Φ
∗ -accessibility is obviously related to the level mapping characterization of the Fitting semantics given in Section 2.4. In the
present section, we will carry over the approach from Section 5.1.3 to programs
with a total Fitting model, and we refer the reader to [Hitzler and Seda, 2003]
for further details. The relationships between the different classes of programs
studied so far in this chapter will be further clarified in Section 5.2.
5.1.15 Definition A program is called Φ-accessible if it has a total Fitting
model.
By Corollary 2.4.10, a program P is Φ-accessible if and only if there is a
(two-valued) model I and a (total) level mapping l for P such that P satisfies
(F) with respect to I ∪ ¬(B P \ I) and l. The restriction of I to Neg
∗ is
P
then a supported model for P
− , and it follows easily that every Φ
∗ -accessible
program is Φ-accessible. However, the development of Section 5.1.3 does not
generalize without modifications, as the following example shows.
5.1.16 Program Let P be the following program.
A
b
p s
2 (x) ← p(x)
p(0) ←
A
b
A
b
p s
4 (0) ← p s
5 (0)
A
b
A
b
p s
2 (0) ← p s
3 (0)
The program P is Φ-accessible (and even definite) with respect to the model
B P = {p(s
n (0)) | n ∈ N} and the level mapping l : B P → N defined by
l(p(s
n (0))) = n. Using the dislocated generalized ultrametric � from Section
5.1.3, we obtain for K = {p(s
5 (0))} and J = {p(s
3 (0))} that �(K, J) = 2
−3
and �(T P (K), T
2
P (J)) = 2
− ; thus, T P is not a contraction relative to �.
We will modify the methods used in Section 5.1.3 by means of Proposition
4.8.23.
Mathematical Aspects of Logic Programming Semantics
T P (J), we must have a ground instance A ← L 1 , . . . , L m of a clause in P
with J |= L 1 ∧ · · · ∧ L m . If I |= L 1 ∧ · · · ∧ L m , then l(L k ) < l(A) ≤ α for
all k, and since J and K agree on all atoms of level less than α, we obtain
K |= L 1 ∧· · ·∧L m , and hence A ∈ T P (K). If there is some L k such that I |= L k ,
then without loss of generality l(L k ) < l(A) ≤ α by Definition 5.1.12. Now,
if the predicate symbol of L k belongs to Neg
∗ , then, since d 1 (J, I) ≤ 2
−α ,
P
we obtain from J |= L k that I |= L k , which is a contradiction. Also, if the
predicate symbol of L k does not belong to Neg
∗ , then L k is an atom, and
P
since f (J) ≤ 2
−α , we obtain I |= L k , again a contradiction. This establishes
(c) and completes the proof.
•
5.1.4 Φ-Accessible Programs
Definition 5.1.12 of Φ
∗ -accessibility is obviously related to the level mapping characterization of the Fitting semantics given in Section 2.4. In the
present section, we will carry over the approach from Section 5.1.3 to programs
with a total Fitting model, and we refer the reader to [Hitzler and Seda, 2003]
for further details. The relationships between the different classes of programs
studied so far in this chapter will be further clarified in Section 5.2.
5.1.15 Definition A program is called Φ-accessible if it has a total Fitting
model.
By Corollary 2.4.10, a program P is Φ-accessible if and only if there is a
(two-valued) model I and a (total) level mapping l for P such that P satisfies
(F) with respect to I ∪ ¬(B P \ I) and l. The restriction of I to Neg
∗ is
P
then a supported model for P
− , and it follows easily that every Φ
∗ -accessible
program is Φ-accessible. However, the development of Section 5.1.3 does not
generalize without modifications, as the following example shows.
5.1.16 Program Let P be the following program.
A
b
p s
2 (x) ← p(x)
p(0) ←
A
b
A
b
p s
4 (0) ← p s
5 (0)
A
b
A
b
p s
2 (0) ← p s
3 (0)
The program P is Φ-accessible (and even definite) with respect to the model
B P = {p(s
n (0)) | n ∈ N} and the level mapping l : B P → N defined by
l(p(s
n (0))) = n. Using the dislocated generalized ultrametric � from Section
5.1.3, we obtain for K = {p(s
5 (0))} and J = {p(s
3 (0))} that �(K, J) = 2
−3
and �(T P (K), T
2
P (J)) = 2
− ; thus, T P is not a contraction relative to �.
We will modify the methods used in Section 5.1.3 by means of Proposition
4.8.23.