We introduce three di®erent formats for normal programs with constraints. These forms help to simplify the search of p-stable models of the original program. In this way we further the study of the p-stable semantics. In this paper we indicate that the p-stable semantics for one of the normal forms proposed agrees with the Comp semantics.
Some approaches used to formalize non-monotonic reasoning (NMR) are based on the semantics of logic programs. In this work we are interested in furthers the study of one of the semantics useful in this formalization called p-stable.
In [
The present paper introduces three di®erent formats for normal programs with constraints: Negative normal programs, Restricted negative normal programs and Semi-Negative normal programs. These forms help to simplify the search of p-stable models of the original program. Besides, for programs in these formats the p-stable and the stable semantics coincide. This furthers the interest in developing the p-stable semantics as a tool to help to understand the NMR.
This paper is structured as follows. In section 2 we give some de¯nitions useful to understand this paper. In section 3 we give the de¯nition of the di®erent formats for normal programs with constraints: negative normal programs and restricted negative normal programs. We also show the di®erent results about the stable semantics and the p-stable semantics of programs in these formats. In this section we also introduce another format for normal programs with constraints called Semi-negative normal programs. We show how to obtain the p-stable models of a Semi-negative normal program with constraints by means of the completion of a particular restricted negative normal program with constraints. Finally in section 4 we present some conclusions. 2
In this section we summarize some basic concepts and de¯nitions used to understand this paper.
A signature L is a ¯nite set of elements that we call atoms, or propositional symbols. The language of a propositional logic has an alphabet consisting of proposition symbols : p0; p1; : : : ; connectives: ^, _, Ã, :; and auxiliary symbols : (, ). Where ^, _, Ã are 2-place connectives and : is a 1-place connective. Formulas are built up as usual in logic. A literal is either an atom a, called positive literal ; or the negation of an atom :a, called negative literal. The formula F ´ G is an abbreviation for (F Ã G) ^ (G Ã F ). A clause is a formula of the form H Ã B (also written as B ! H), where H and B, arbitrary formulas in principle, are known as the head and body of the clause respectively. The body of a clause could be empty, in which case the clause is known as a fact and can be denoted just by: H Ã. In the case when the head of a clause is empty, the clause is called a constraint and is denoted by: Ã B.
A normal clause is a clause of the form H Ã B+ [ :B¡ where H consists of one atom or can be empty, B+ is a conjunction of atoms b1 ^ b2 ^ : : : ^ bn, and :B¡ is a conjunction of negated atoms :bn+1 ^ :bn+2 ^ : : : ^ :bm. B+, and B¡ could be empty sets of atoms. A ¯nite set of normal clauses P is a normal program. A ¯nite set of normal clauses P joined with a set of constraints C is a normal program with constraints, denoted as hP; Ci. Since we shall restrict our discussion to propositional programs, then we take for granted that programs with predicate symbols are only an abbreviation of the ground program.
Finally we give two de¯nitions useful to understand the de¯nitions of stable and p-stable semantics for normal programs.
Let P be a normal program and M be a set of atoms. We de¯ne: RED(P; M ) = fH Ã B+; :(B¡ \ M ) j H Ã B+; :B¡ 2 P g.
For any program P , the positive part of P , denoted by P OS(P ) is the program consisting exclusively of those rules in P that do not have negated literals.
From now on, we assume that the reader is familiar with the notion of classical
minimal model [
Now we give the de¯nition of stable semantics for normal programs as given
in [
De¯nition 1. [
The stable semantics for normal programs with constraints is de¯ned as
follows [
De¯nition 2. [
De¯nition 3. [
The p-stable semantics for normal programs with constraints is de¯ned as
follows [
De¯nition 4. [
We are going to present some transformations for normal programs that modify a program into another, in general, shorter program; the idea is that some program transformations may help to reduce the size of a program and keep at least the same p-stable semantics. These transformations are simple, and the transformed program is p-stable equivalent to the original program. De¯nition 5. Two normal programs P1 and P2 are p-stable equivalent, if P1 and P2 have the same p-stable models. Two normal programs with constraints (P1; C1) and (P2; C2) are p-stable equivalent, if (P1; C1) and (P2; C2) have the same p-stable models.
De¯nition 6. [
Proposition 1. [
The transformation Dsuc can also be applied to normal programs with constraints.
De¯nition 7. [
De¯nition 8. [
The transformation Failure can also be applied to normal programs with constraints.
De¯nition 9. [
Proposition 4. [
Here we present a result that establishes a one-to-one correspondence between the p-stable models of a tight normal program and the classical models of its Clark's completion. This classical models can be obtained by using classical model generator systems.
De¯nition 10. [
For each symbol a, let S(a) denote the set of all clauses with a in the head.
Suppose S(a) is the set: fa à Body1; : : : ; a à Bodykg Replace this set with the
single formula, a $ Body1 _ : : : _ Bodyk If S(a) = ;, then replace it by :a.
De¯nition 11. [
In this section we give the de¯nition of two formats for normal programs with constraints: Negative normal programs and Restricted negative normal programs. One of the main results indicates that the stable semantics and the p-stable semantics of a restricted negative normal program coincide. We also show how the p-stable semantics of a negative normal program corresponds to the p-stable semantics of a particular restricted negative normal program.
We start by introducing the de¯nitions of negative normal programs and restricted negative normal programs without constraints. De¯nition 12. Let P be a normal program. We say that P is a negative normal (NN) program if it satis¯es the ¯rst of the two conditions listed below, and we say that P is a restricted negative normal (RNN) program if it satis¯es both conditions 1. every rule has its body composed of negative literals only; 2. the head of any rule does not appear in the body of the same rule.
We also introduce the de¯nitions of negative normal programs and restricted negative normal programs with constraints.
De¯nition 13. Let hP; Ci be a normal program with constraints. We say that hP; Ci is a NN program with constraints if P is a NN program. We say that hP; Ci is a RNN program with constraints if P is a RNN program.
The following lemma will be useful to show that the stable semantics and the p-stable semantics of a RNN program coincide. Given a RNN program P , this lemma gives a characterization for a set M µ LP , to be a p-stable model of P .
Let P be a RNN program, for any M µ LP , we de¯ne SM = fa j a à :b1; ^ : : : ^ :bm 2 P; fb1; : : : ; bmg \ M = ;g.
Lemma 1. Let P be a RNN program. If M is p-stable model of P then M = SM . Proof. RED(P; M ) = fa à :(B¡ \ M ) j H à :B¡ 2 P g: By part 1) of the de¯nition of p-stable model (De¯nition 3), it follows that SM ½ M . Let us assume that M n SM 6= ; and take m 2 M n SM . Let us de¯ne an interpretation: I : LP ! f0; 1g such that I(a) = 1 for each a 2 LP n fmg and I(m) = 0.
Now, using the fact that the program P has the property that the head of each rule does not appear in its body, it follows that I is a classical model for RED(P; M ) but it is not a model for M (Since I(m) = 0) this contradicts 2) in the de¯nition of a p-stable model (De¯nition 3) and the lemma is proved.
The following theorem indicates that the stable semantics and the p-stable semantics of a RNN program coincide.
Theorem 1. Let P be a RNN program, then the stable semantics of P coincides with the p-stable semantics of P .
Proof. If M is a p-stable model of P then M = SM according to the lemma 1, and from the de¯nition of P M (De¯nition of a stable model), P M = fa à j a 2 SM g then we conclude that M is a minimal model of P M and then a stable model of P .
Let us now assume that M is a stable model of P . It follows that M is a minimal model for P M = fa à j a 2 SM g. Therefore M = SM . From the fact that P M ½ RED(P; M ), it follows that RED(P; M ) j= M .
We still need to show that M is a classical model of P . Let us consider a rule a à :b1 ^ :b2 ^ : : : ^ :bs 2 P , such that a 62 M . Then there is at least an i for which bi 2 M (otherwise a 2 SM = M ), then the rule is modeled by M . Therefore M models all of the rules in P as we wanted to show.
The following corollary of theorem 1 indicates that the stable semantics and the p-stable semantics of a RNN program with constraints also coincide. Corollary 1. Let hP; Ci be a RNN program with constraints, then the stable semantics of hP; Ci coincides with the p-stable semantics of hP; Ci. Proof. Straightforward from theorem 1, de¯nition of stable semantics for normal programs with constraints (de¯nition 2), and de¯nition of p-stable semantics for normal programs with constraints (de¯nition 4).
Let us observe that, from the de¯nition, in a NN program the head of any rule could appear in the body of the same rule.
We shall show how the p-stable semantics of a NN program P corresponds to the p-stable semantics of a particular program associated to P . This new program is a RNN program and it is the result of applying the following transformation to P : For any normal program P , the transformed program, denoted by T RN (P ) is the program that results from P after deleting from the body of each rule the atom that appears as the head of the same rule. The rules that do not present this condition remain the same.
De¯nition 14. For a rule r of the form a à :a ^ :b1 ^ : : : ^ :bn 2 P , we de¯ne the transformation T RN as follows: T RN (r) = a à :b1 ^ : : : ^ :bn. For a rule r for which head(r) 62 body(r), we de¯ne T RN (r) = r. For a normal program P we de¯ne the transformation T RN as follows: T RN (P ) = fT RN (r) j r 2 P g. For a normal program with constraints hP; Ci we de¯ne the transformation T RN as follows: T RN (hP; Ci) = (T RN (P ); C).
Here we show how the p-stable semantics of a NN program P corresponds to the p-stable semantics of the RNN program T RN (P ).
Theorem 2. Let P be a NN program, then the p-stable semantics of P coincides with the p-stable semantics of the RNN program T RN (P ).
Proof. Let us assume that M is a p-stable model of P and let a à :a; :b1; ::::bn be one of the rules in P with the property that the head appears in the body. Assume that a 2= M . Since M is a classical model for the rule, then at least for one i, bi 2 M , making the rule true according to M ; but then it is clear that the corresponding rule in T RN (P ) is also modeled by M . It follows that a classical model for P is also a classical model for T RN (P ). Next, by hypothesis we have that RED(P; M ) j= M . Now, it is easy to see that for each rule r 2 P , the rule RED(r; M ) is a logical consequence (in classical logic) of the rule RED(T RN (r); M ). Therefore we conclude that RED(T RN (P ); M ) j= M .
Now, if M is a p-stable model of T RN (P ), according to lemma 1, M consists of those atoms for which there exists a rule r : a à :b1 ^ : : : ^ :bn such that bi 62 M for all i.
Let us show ¯rst that M is a classical model of P . It is enough to examine the rules in P n T RN (P ): a à :a ^ :b1 ^ : : : ^ :bn.
In the case for which a 2 M , there is nothing to prove. In the case for which a 62 M , according to the lemma 1 there must exist bi 2 M for some i, and then the rule is modeled by M . So M models P .
Now, it only remains to prove that RED(P; M ) j= M . But again, M consists of those atoms for which there is a rule, a à :b1 ^ : : : ^ :bn and bi 62 M for all i; then RED(P; M ) contains the rules a Ã, for all a 2 M . The desired conclusion follows now.
The following corollary of theorem 2 indicates that the p-stable semantics of a NN program with constraints hP; Ci corresponds to the p-stable semantics of the RNN program T RN (hP; Ci).
Corollary 2. Let hP; Ci be a NN program with constraints, then the p-stable semantics of hP; Ci coincides with the p-stable semantics of the RNN program T RN (hP; Ci).
Proof. Straightforward from theorem 2 and de¯nition of p-stable semantics for normal programs with constraints (de¯nition 4).
Now we introduce another format for normal programs called Semi-negative normal programs.
De¯nition 15. Let P be a normal program. We say that P is a semi-negative normal (semi-NN) program if for any atom that appears as a positive literal in the body of a rule, the following condition holds: It does not appear in the head of any rule unless it appears as a fact.
We also give the de¯nition of Semi-negative normal programs with constraints. We say that a positive constraint is a constraint that consists of a conjunction of positive literals in its body.
De¯nition 16. Let hP; Ci be a normal program with constraints. We say that hP; Ci is a semi-NN program with constraints if P is a semi-NN program and every constraint in C is a positive constraint.
The following proposition indicates that each semi-NN program has a p-stable equivalent NN-program.
Proposition 6. If P is a semi-NN program, then P is p-stable equivalent to an NN program. If hP; Ci is a semi-NN program, then hP; Ci is p-stable equivalent to a NN program with constraints.
Proof. After several applications (if necessary) of the program transformations Dsuc and F ailure, P and hP; Ci can be transformed into a NN program or a NN program with constraints respectively with the same p-stable semantics.
Since NN programs, RNN programs and semi-NN programs without constraints are tight (see de¯nition 11), it is possible to show that the p-stable models of a RNN program P correspond to the classical models of its completion Comp(P ). Proposition 7. Let P be a RNN program. M is a p-stable model of P if and only if M is a model (in classical logic) of Comp(P ).
Proof. Let M be a pstable model of P . By theorem 1, M is a p-stable model of P if and only M is a stable model of P . Since P is tight; by proposition 5, M is an stable model of P if and only if M is a model (in classical logic) of Comp(P ).
Moreover, we also can show that the p-stable models of a RNN program with constraints hP; Ci correspond to the classical models of its completion Comp(hP; Ci). First we need to introduce two de¯nitions: tight normal programs with constraints, and completion for a normal program with constraints.
We say that a normal program with constraints hP; Ci is tight if P is tight. Therefore NN programs, RNN programs and semi-NN programs with constraints are tight.
The de¯nition of completion for a normal program with constraints is based on the de¯nition of completion for normal programs without constraints (see de¯nition 10).
De¯nition 17. For a positive constraint c : Ã a1^a2^: : : an we de¯ne Comp(c) = :a1 _ :a2 _ : : : _ :an. If C is a set of constraints then Comp(C) = fcomp(c)jc 2 Cg. For any normal program with constraints tight hP; Ci, we de¯ne Comp(hP; Ci) = Comp(P ) [ Comp(C).
Now we are ready to show that the p-stable models of a RNN program with constraints hP; Ci correspond to the classical models of its completion Comp(hP; Ci).
Proposition 8. Let hP; Ci be a RNN program with constraints. M is a p-stable model of hP; Ci if and only if M is a model (in classical logic) of Comp(hP; Ci). Proof. In particular Comp(hP; Ci) = Comp(P ) [ Comp(C).
)) If M is a p-stable model of hP; Ci then, by corollary 1, M is a stable model of hP; Ci. If M is a stable model of hP; Ci then, by de¯nition 2, M is a stable model of P and M models C in classical logic. By proposition 5 M is a classical model of Comp(P ) and also a classical model of Comp(C) since C and Comp(C) are equivalent in classical logic. Therefore M is a classical model of Comp(hP; Ci).
() Conversely if M is a classical model of Comp(P ) [ Comp(C), then by proposition 5, M is a stable model of P . Also M is a classical model of R, since R and Comp(R) are equivalent in classical logic. Therefore M is a stable model of hP; Ci. Again by corollary 1 M is a p-stable model of hP; Ci.
As a direct consequence of proposition 8 we can see that it is possible to obtain the p-stable models of a semi-NN program with constraints by means of the completion of a particular RNN program with constraints. By proposition 6 we showed that if hP; Ci is a semi-NN program with constraints, then hP; Ci is p-stable equivalent to an NN program with constraints hP; CiNN . By corollary 2 we showed that the p-stable semantics of hP; CiNN corresponds to the p-stable semantics of the RNN program with constraints T RN (hP; CiNN ); and by corollary 1 we showed that the p-stable semantics and the stable semantics of T RN (hP; CiNN ) coincide. Finally by proposition 8 we showed that the p-stable models of T RN (hP; CiNN ) correspond to the classical models of its completion, Comp(T RN (hP; CiNN )). 4
This paper furthers the study of p-stable semantics. We introduced three different formats for normal programs with constraints. We show that the stable semantics and the p-stable semantics of a Restricted Negative Normal program coincide. We also show that the p-stable semantics for Semi-Negative Normal programs with constraints agrees with the completion of a particular Restricted Negative Normal program with constraints.