39
The Semantics of Logic Programs
2.4.3 Program Consider the following program P .
p ← ¬q
p ← ¬r
q ← q
r ← r
Define M as follows: M (p) = f , M (q) = u, and M (r) = t. Then M is a
three-valued interpretation for P satisfying Φ P (M ) [ k M , and yet M is not
a model for P .
On the other hand, take P to be Program 2.2.4. Define M as follows:
M (p) = t, M (q) = u, and M (r) = t. Then M is a three-valued model for P ,
but it does not satisfy the inequality Φ P (M ) [ k M .
Therefore, neither implication of Proposition 2.4.2 holds in the case of the
knowledge ordering.
The following fact about Φ P is fundamental.
2.4.4 Proposition Let P be a program. Then Φ P is monotonic on I P,3 in
the knowledge ordering [ k .
Proof: Let I, K ∈ I P,3 with I ⊆ K. We show Φ P (I) ⊆ Φ P (K). Let A ∈ Φ P (I)
'
be an atom. Then A ∈ T (I). Therefore, there is a ground clause A ← body
P
such that body is true in I. From Table 1.1, each literal in body must be true
and therefore, noting the results of Section 1.3.3, must belong to I. Hence,
each literal in body belongs to K since I ⊆ K and is therefore true in K.
'
Hence, body is also true in K, and we obtain that A ∈ T (K) ⊆ Φ P (K). Now
P
let ¬A ∈ Φ P (I) be a negated atom. Then A ∈ F P (I), and so, for all ground
clauses A ← body, we have that body is false in I. So, given such a clause,
from Table 1.1 we see that at least one literal L j , say, in body, is false. Hence,
by the results of Section 1.3.3 again, we have ¬L j ∈ I. But I ⊆ K and hence
¬L j ∈ K. Therefore, L j is also false in K, and consequently body is false in
K. Thus, we obtain A ∈ F P (K), and hence ¬A ∈ Φ P (K), as required.
•
2.4.5 Example Take P to be Program 2.2.4 again. Define three-valued interpretations I and K for P as follows: I(p) = I(q) = I(r) = f , and
K(p) = K(q) = K(r) = t. Then I c t K. Yet Φ P (K) is constant with value f ,
and Φ P (I) is constant with value t. Hence, Φ(K) c t Φ(I), and so Φ P is not
monotonic relative to the truth ordering.
Since the operator Φ P is monotonic relative to the ordering [ k , it has
a least fixed point by the Knaster-Tarski theorem, Theorem 1.1.10, and this
least fixed point is an ordinal power Φ P ↑ α, as defined in Section 1.1, for
some ordinal α. The least fixed point of Φ P is called the Kripke-Kleene model
or Fitting model for P . It turns out, as we show later, that Φ P is not order
The Semantics of Logic Programs
2.4.3 Program Consider the following program P .
p ← ¬q
p ← ¬r
q ← q
r ← r
Define M as follows: M (p) = f , M (q) = u, and M (r) = t. Then M is a
three-valued interpretation for P satisfying Φ P (M ) [ k M , and yet M is not
a model for P .
On the other hand, take P to be Program 2.2.4. Define M as follows:
M (p) = t, M (q) = u, and M (r) = t. Then M is a three-valued model for P ,
but it does not satisfy the inequality Φ P (M ) [ k M .
Therefore, neither implication of Proposition 2.4.2 holds in the case of the
knowledge ordering.
The following fact about Φ P is fundamental.
2.4.4 Proposition Let P be a program. Then Φ P is monotonic on I P,3 in
the knowledge ordering [ k .
Proof: Let I, K ∈ I P,3 with I ⊆ K. We show Φ P (I) ⊆ Φ P (K). Let A ∈ Φ P (I)
'
be an atom. Then A ∈ T (I). Therefore, there is a ground clause A ← body
P
such that body is true in I. From Table 1.1, each literal in body must be true
and therefore, noting the results of Section 1.3.3, must belong to I. Hence,
each literal in body belongs to K since I ⊆ K and is therefore true in K.
'
Hence, body is also true in K, and we obtain that A ∈ T (K) ⊆ Φ P (K). Now
P
let ¬A ∈ Φ P (I) be a negated atom. Then A ∈ F P (I), and so, for all ground
clauses A ← body, we have that body is false in I. So, given such a clause,
from Table 1.1 we see that at least one literal L j , say, in body, is false. Hence,
by the results of Section 1.3.3 again, we have ¬L j ∈ I. But I ⊆ K and hence
¬L j ∈ K. Therefore, L j is also false in K, and consequently body is false in
K. Thus, we obtain A ∈ F P (K), and hence ¬A ∈ Φ P (K), as required.
•
2.4.5 Example Take P to be Program 2.2.4 again. Define three-valued interpretations I and K for P as follows: I(p) = I(q) = I(r) = f , and
K(p) = K(q) = K(r) = t. Then I c t K. Yet Φ P (K) is constant with value f ,
and Φ P (I) is constant with value t. Hence, Φ(K) c t Φ(I), and so Φ P is not
monotonic relative to the truth ordering.
Since the operator Φ P is monotonic relative to the ordering [ k , it has
a least fixed point by the Knaster-Tarski theorem, Theorem 1.1.10, and this
least fixed point is an ordinal power Φ P ↑ α, as defined in Section 1.1, for
some ordinal α. The least fixed point of Φ P is called the Kripke-Kleene model
or Fitting model for P . It turns out, as we show later, that Φ P is not order