37
The Semantics of Logic Programs
2.3.10 Program (Tweety3) Consider the program Tweety3, as follows.
eagle(tweety) ← ¬penguin(tweety)
penguin(tweety) ← ¬eagle(tweety)
bird(X) ← eagle(X)
bird(X) ← penguin(X)
flies(X) ← bird(X), ¬penguin(X)
This program has the two stable models
{eagle(tweety), bird(tweety), flies(tweety)}
and
{penguin(tweety), bird(tweety)}.
2.4 Fitting Models
The stable model semantics is more satisfactory than the supported model
semantics in that each definite program has a unique stable model which
coincides with its least model. However, for normal logic programs in general,
uniqueness cannot be guaranteed, as can be seen from Program 2.1.7, which
has two stable models {p} and {q}. It is desirable to be able to associate with
each program a unique model in some natural way. One way of doing this is
by means of three-valued logic, and we discuss this next.
10
In fact, we will work with Kleene’s strong three-valued logic as discussed
in Chapter 1 and, in particular, with the knowledge ordering, ≤ k , on the truth
values. We find it convenient here to represent three-valued interpretations as
signed sets, see Section 1.3.3, so that the corresponding ordering [ k is subset
inclusion of signed sets.
'
Given a normal logic program P , we define the following operators T and
P
'
F P on I P = I P,3 = I P,J,3 . First, T (I) is the set of all A ∈ B P for which
P
there is a clause A ← body in ground(P ) with body true in I with respect
to Kleene’s strong three-valued logic. Second, F P (I) is the set of all A ∈ B P
such that for all clauses A ← body in ground(P ) we have that body is false in
I with respect to Kleene’s strong three-valued logic. Finally, we define
'
Φ P (I) = T (I) ∪ ¬F P (I)
P
for all I ∈ I P . We will call the operator Φ P the Fitting operator for P or the
Φ P -operator .
10 The resulting Kripke-Kleene semantics, herein called the Fitting semantics, is due to
Fitting [Fitting, 1985].