154
Mathematical Aspects of Logic Programming Semantics
5.2.1 Proposition Let P be a program, let I be a three-valued interpretation
for P , and let A ∈ B P . Then Φ P (I)(A) = I 1,1 (body A ), that is, the truth value
of A under Φ P (I) is exactly I 1,1 (body A ).
The logics from Table 5.1 give rise to different operators.
9
5.2.2 Definition Let P be a program. For any j = 1, 2, 3 and any k = 1, 2,
we define an operator Φ P,j,k : I P,3 → I P,3 by Φ P,j,k (I)(A) = I j,k (body A ).
We can now rephrase Proposition 5.2.1 by saying that the operators Φ P,1,1
and Φ P coincide. The following proposition lists properties of the Φ P,j,k
operators. We use the notation of three-valued interpretations as signed sets,
see Section 1.3.3, and of two-valued interpretations as subsets of B P .
5.2.3 Proposition Let P be a program, and let I, J, K ∈ I P,3 . Then the
following hold.
(a) Φ P,j,k is monotonic for j = 1, 2, 3 and k = 1, 2.
(b) Φ P,3,k (I) ⊆ Φ P,2,k (J) ⊆ Φ P,1,k (K) for k = 1, 2 if I ⊆ J ⊆ K.
(c) Φ P,j,2 (I) ⊆ Φ P,j,1 (I) for j = 1, 2, 3.
(d) Φ P,j,2 (I)
− = Φ P,j,1 (I)
− .
Proof: (a) The proof of this statement is very similar to that of Proposition
2.4.4 and is therefore omitted.
(b) From the truth tables, it follows that for all A ∈ B P and each k ∈ {1, 2}
we have I 3,k (body A ) ⊆ J 2,k (body A ) ⊆ K 1,k (body A ), and this suffices.
(c) From the truth tables, we obtain I j,2 (body A ) ⊆ I j,1 (body A ) for all
A ∈ B P .
(d) By (c), it suffices to show that Φ P,j,2 (I)
− ⊇ Φ P,j,1 (I)
− . So let A ∈ B P
be such that I j,1 (body A ) = I j,1
i Λ body i = f . Then I j,1 (body i ) = f for
∈
all i, and hence I j,2 (body i ) = f
A
for
o
all i. Consequen
b
tly, I j,2 (body A ) = f , as
required.
•
Proposition 5.2.3 shows that the operators are “nested” and that Φ P,1,1 =
Φ P is the least sceptical of them. In particular, for each ordinal α and all j
and k, the following hold.
Φ P,3,k ↑ α ⊆ Φ P,2,k ↑ α ⊆ Φ P,1,k ↑ α
Φ P,j,2 ↑ α ⊆ Φ P,j,1 ↑ α
We can also relate Φ P to the two-valued immediate consequence operator, T P ,
thereby extending Proposition 2.4.13.
9 We refer to the papers [Hitzler and Seda, 1999a, Hitzler and Seda, 2002b] for further
details concerning the results of this section.
Mathematical Aspects of Logic Programming Semantics
5.2.1 Proposition Let P be a program, let I be a three-valued interpretation
for P , and let A ∈ B P . Then Φ P (I)(A) = I 1,1 (body A ), that is, the truth value
of A under Φ P (I) is exactly I 1,1 (body A ).
The logics from Table 5.1 give rise to different operators.
9
5.2.2 Definition Let P be a program. For any j = 1, 2, 3 and any k = 1, 2,
we define an operator Φ P,j,k : I P,3 → I P,3 by Φ P,j,k (I)(A) = I j,k (body A ).
We can now rephrase Proposition 5.2.1 by saying that the operators Φ P,1,1
and Φ P coincide. The following proposition lists properties of the Φ P,j,k
operators. We use the notation of three-valued interpretations as signed sets,
see Section 1.3.3, and of two-valued interpretations as subsets of B P .
5.2.3 Proposition Let P be a program, and let I, J, K ∈ I P,3 . Then the
following hold.
(a) Φ P,j,k is monotonic for j = 1, 2, 3 and k = 1, 2.
(b) Φ P,3,k (I) ⊆ Φ P,2,k (J) ⊆ Φ P,1,k (K) for k = 1, 2 if I ⊆ J ⊆ K.
(c) Φ P,j,2 (I) ⊆ Φ P,j,1 (I) for j = 1, 2, 3.
(d) Φ P,j,2 (I)
− = Φ P,j,1 (I)
− .
Proof: (a) The proof of this statement is very similar to that of Proposition
2.4.4 and is therefore omitted.
(b) From the truth tables, it follows that for all A ∈ B P and each k ∈ {1, 2}
we have I 3,k (body A ) ⊆ J 2,k (body A ) ⊆ K 1,k (body A ), and this suffices.
(c) From the truth tables, we obtain I j,2 (body A ) ⊆ I j,1 (body A ) for all
A ∈ B P .
(d) By (c), it suffices to show that Φ P,j,2 (I)
− ⊇ Φ P,j,1 (I)
− . So let A ∈ B P
be such that I j,1 (body A ) = I j,1
i Λ body i = f . Then I j,1 (body i ) = f for
∈
all i, and hence I j,2 (body i ) = f
A
for
o
all i. Consequen
b
tly, I j,2 (body A ) = f , as
required.
•
Proposition 5.2.3 shows that the operators are “nested” and that Φ P,1,1 =
Φ P is the least sceptical of them. In particular, for each ordinal α and all j
and k, the following hold.
Φ P,3,k ↑ α ⊆ Φ P,2,k ↑ α ⊆ Φ P,1,k ↑ α
Φ P,j,2 ↑ α ⊆ Φ P,j,1 ↑ α
We can also relate Φ P to the two-valued immediate consequence operator, T P ,
thereby extending Proposition 2.4.13.
9 We refer to the papers [Hitzler and Seda, 1999a, Hitzler and Seda, 2002b] for further
details concerning the results of this section.