+
p(t)
p(b)
+
−
−
b(t)
−
b(b)
+
+
f(t)
f(b)
+
p(b)
−
−
f(b)
FIGURE 2.1: Dependency graph for P 1 .
FIGURE 2.2: Dependency graph for P 2 .
48
Mathematical Aspects of Logic Programming Semantics
1
1
1
The program P 2 = P 1 /M 1 is
flies(bob) ← ¬penguin(bob)
penguin(bob) ← penguin(bob), ¬flies(bob)
The dependency graph G P2 of P 2 , shown in Figure 2.2, has only one component {penguin(bob), flies(bob)}, which is therefore equal to the bottom stratum S 2 = S(P 2 ) of P 2 . Furthermore, N 2 = M 0 ∪ M 1 = M 1 and
R 2 = {flies(tweety)}. Since the bottom layer L 2 = L(P 2 ) is equal to P 2 ,
it is not definite. Therefore, the construction stops, and the weakly perfect
model is N 2 ∪ ¬R 2 = M 1 ∪ ¬R 2 , as claimed.
2.5.6 Proposition Let P be a program, and let M be its (partial) weakly
perfect model. Then M is a model with respect to Kleene’s strong three-valued
logic.
Proof: It is straightforward to show that Φ P (M ) = M , and we leave the
details to the reader.
•
A weakly stratified program is a program with a total weakly perfect model.
The set of all its strata is then called its weak stratification.
2.5.7 Remark We remark that our definition of weakly perfect model, as