47
The Semantics of Logic Programs
2.5.5 Example Consider the program Tweety4, as follows; it is a modification of Tweety2 (Program 2.3.9), where the last clause has been changed.
penguin(tweety) ←
bird(bob) ←
bird(X) ← penguin(X)
flies(X) ← bird(X), ¬penguin(X)
penguin(bob) ← penguin(bob), ¬flies(bob)
This program has the weakly perfect model
{bird(bob), bird(tweety), penguin(tweety), ¬flies(tweety)},
and we show here how this model is calculated. We begin by setting P = P 0 =
ground(Tweety4), as follows.
penguin(tweety) ←
bird(bob) ←
bird(tweety) ← penguin(tweety)
bird(bob) ← penguin(bob)
flies(tweety) ← bird(tweety), ¬penguin(tweety)
flies(bob) ← bird(bob), ¬penguin(bob)
penguin(bob) ← penguin(bob), ¬flies(bob)
Next, we set M 0 = ∅ and carry out reduction of P 0 with respect to M 0
to obtain P 1 = P 0 /M 0 , which turns out to be equal to P 0 with the fourth
clause removed. The dependency graph G P1 of P 1 is shown in Figure 2.1,
where we use the obvious abbreviations for the ground atoms in P 1 such
as p(t) for penguin(tweety) and so on. Using G P1 , it is simple to check that
the components of P 1 are {bird(bob)}, {bird(tweety)}, {penguin(tweety)},
{flies(tweety)}, and {flies(bob), penguin(bob)} and that the minimal
components are the first three of these. Therefore, the bottom stratum
S 1 = S(P 1 ) of P 1 is {penguin(tweety), bird(bob), bird(tweety)}. Hence,
the bottom layer L 1 = L(P 1 ) of P 1 is the definite program
penguin(tweety) ←
bird(bob) ←
bird(tweety) ← penguin(tweety)
whose least two-valued model is clearly equal to S 1 . Note that N 1 =
δ<1 M δ = M 0 = ∅. Reduction of P 0 with respect to M 0 removed one clause,
but did not eliminate any atoms from P ; hence, R 1 = ∅. Since L 1 is definite,
we put M 1 = H ∪¬R 1 , where H is the total three-valued model corresponding
to S 1 ; thus, M 1 = S 1 , and the process continues.