46
Mathematical Aspects of Logic Programming Semantics
Let C 1 and C 2 be two components of a program P . We write C 1 � C 2 if
and only if C 1 = C 2 and for each A 1 ∈ C 1 there is A 2 ∈ C 2 with A 1 < A 2 . A
component C 1 is called minimal if there is no component C 2 with C 2 � C 1 .
Given a normal logic program P , the bottom stratum S(P ) of P is the union
of all minimal components of P . The bottom layer of P is the subprogram L(P )
of P which consists of all clauses from P with heads belonging to S(P ).
Given a three-valued interpretation I for P , thought of as a signed subset,
we define the reduct of P with respect to I to be the program P/I obtained
from P by performing the following reductions. (1) Remove from P all clauses
which contain a body literal L such that ¬L ∈ I or whose head belongs to
I. (2) Remove from all remaining clauses all body literals L with L ∈ I. (3)
Remove from the resulting program all non-unit clauses whose heads appear
also as heads of unit clauses in the program.
Note that the definition of P/I used here differs from that given in Definition 2.3.6 in the context of stable models. The new definition just given will
only be used in the present section.
2.5.4 Definition The weakly perfect model M P for a program P is defined by
transfinite induction as follows. Let P 0 = P , and let M 0 = ∅. For each (countable) ordinal α > 0 such that programs P δ and three-valued interpretations
M δ have already been defined for all δ < α, let
N α =
M δ ,
δ<α
P α = P/N α ,
R α is the set of all atoms which are undefined in N α and were eliminated from
P by reducing it with respect to N α ,
S α = S (P α ) , and
L α = L (P α ) .
The construction then proceeds with one of the following three cases. (1) If
P α is empty, then the construction stops, and M P = N α ∪ ¬R α is the (total )
weakly perfect model for P . (2) If the bottom stratum S α is empty or if the
bottom layer L α contains a negative literal, then the construction also stops,
and M P = N α ∪ ¬R α is the (partial ) weakly perfect model for P . (3) In the
remaining case, L α is a definite program, and we define M α = H ∪¬R α , where
H is the total three-valued model corresponding to the least two-valued model
for L α , and the construction continues.
For every α, the set S α ∪ R α is called the α-th stratum of P , and the
program L α is called the α-th layer of P .
We now present a detailed example of the calculation of the weakly perfect
model; see also Program 2.6.12 for further discussion of this example.
Mathematical Aspects of Logic Programming Semantics
Let C 1 and C 2 be two components of a program P . We write C 1 � C 2 if
and only if C 1 = C 2 and for each A 1 ∈ C 1 there is A 2 ∈ C 2 with A 1 < A 2 . A
component C 1 is called minimal if there is no component C 2 with C 2 � C 1 .
Given a normal logic program P , the bottom stratum S(P ) of P is the union
of all minimal components of P . The bottom layer of P is the subprogram L(P )
of P which consists of all clauses from P with heads belonging to S(P ).
Given a three-valued interpretation I for P , thought of as a signed subset,
we define the reduct of P with respect to I to be the program P/I obtained
from P by performing the following reductions. (1) Remove from P all clauses
which contain a body literal L such that ¬L ∈ I or whose head belongs to
I. (2) Remove from all remaining clauses all body literals L with L ∈ I. (3)
Remove from the resulting program all non-unit clauses whose heads appear
also as heads of unit clauses in the program.
Note that the definition of P/I used here differs from that given in Definition 2.3.6 in the context of stable models. The new definition just given will
only be used in the present section.
2.5.4 Definition The weakly perfect model M P for a program P is defined by
transfinite induction as follows. Let P 0 = P , and let M 0 = ∅. For each (countable) ordinal α > 0 such that programs P δ and three-valued interpretations
M δ have already been defined for all δ < α, let
N α =
M δ ,
δ<α
P α = P/N α ,
R α is the set of all atoms which are undefined in N α and were eliminated from
P by reducing it with respect to N α ,
S α = S (P α ) , and
L α = L (P α ) .
The construction then proceeds with one of the following three cases. (1) If
P α is empty, then the construction stops, and M P = N α ∪ ¬R α is the (total )
weakly perfect model for P . (2) If the bottom stratum S α is empty or if the
bottom layer L α contains a negative literal, then the construction also stops,
and M P = N α ∪ ¬R α is the (partial ) weakly perfect model for P . (3) In the
remaining case, L α is a definite program, and we define M α = H ∪¬R α , where
H is the total three-valued model corresponding to the least two-valued model
for L α , and the construction continues.
For every α, the set S α ∪ R α is called the α-th stratum of P , and the
program L α is called the α-th layer of P .
We now present a detailed example of the calculation of the weakly perfect
model; see also Program 2.6.12 for further discussion of this example.