Research Article
On Multi-valued Semantics for Logic Programs
Faculty of Computer Science, University AL.I.Cuza lasi, General Berthelot 16, lasi, 6600, Romania
The well-founded semantics has been introduced by Van Gelder et al.[1]. It is a 3-valued semantics. They use as truth values "true", "false" and ⊥ (an unknown truth value). They have shown that if a logic program P has a 2-valued well-founded model, then this model is the unique stable model of P.
The stable model semantics has been introduced by Gelfond and Lifschitz[2] and by Bidoit and Froidevaux[3].
Przymusinski[4] has introduced 3-valued stable models as a generalization of 2-valued stable models. He also found that the well-founded model of any program P coincides with the smallest 3-valued stable model of P.
Luong[5] has defined a new semantics for Datalog programs, which includes the well-founded models and all stable models.
Fitting[6] has studied the structure of the family of all stable models for a logic program using two orderings; one is called the knowledge ordering based on degree of definedness, the other is called truth ordering based on degree of truth. In the first ordering every logic program has a smallest stable model, which coincides with the well-founded model.
Przymusinski[7] has introduced the stable model semantics for disjunctive logic programs and deductive databases. For normal programs, the partial disjunctive stable semantics coincides with the well-founded semantics.
Loyer and Umberto[8] proposed a well-founded semantics for deductive databases with uncertainty frameworks.
Malfon[9] gives a new characterization of Fitting model and of the well-founded model.
Lallouet[10] has defined a semantics for normal logic programs based on the property of composition. This semantics extends well-founded semantics and Fitting semantics.
This study defines a semantics of type well-founded and a stable semantics for the case multi-valued interpretations and points out a relationship between them.
Interpretations and models: Let P be a general logic program in sense Gelder[1]. Let H be the Herbrand base associated to P. We consider a total ordered set of truth values Ln = (0, v1,...,vn-1,1), where, value 0 corresponds to false, value 1 is for true and the values vk, 1≤k≤n-1 are intermediate between false and true. For every truth value v from Ln, we used a constant proposition denoted by cv and defined by cv(A) = v for every ground atom A from H. The undefined value will be denoted by u and corresponding constant by cu, where, cu(A) = u for every A ∈ H. Let us denote 0 by v0 and 1 by v1. The constant propositions cv, as well cu may appear in the bodies of rules from P.
Definition 1: By a multi-valued Herbrand partial interpretation I we mean a partial function from H into Ln. For an interpretation I, let us denote by VI the vector of sets from H:
VI = (S0, S1,...,Sn) |
where, Sj = {A/A ∈ H and I(A) = vj}, 0≤j≤n.
We denote by Su the set of all remaining atoms from . If V = (S0, S1,...,Sn) where, Sj are disjoint sets of H, 0≤j≤n, then there is an interpretation I, such that VI = V. In the case Su is empty, then I is called total interpretation.
Assume that Ln admits a negation, denoted , which satisfies the following properties: 0 = 1, 1 = 0 and vi<vj implies vj<vi, for every i,j, 0≤i,j≤n. Moreover, we consider u = u.
For an atom A, such that A ∈ Su, we write I(A) = u and I(A) ≠ u, otherwise.
For a ground instantiated rule r of P, having the form: r ≡ A ← L1,..., Lm, let us denote by Î (body (r)) = min {Î(Li), Î(Li) ≠ u, 1≤i≤m}. We consider min ø=1, where ø is empty set.
Let MA be the set of all ground instantiated rule of P, having A as its head. Let vIj,A be the truth value from Ln defined by: vIj,A = max{Î(body(r))/ r ∈ MA}.
The interpretation I is extended to ground literals denoted Î by : Î(A) = I(A) and Î(~A) = XI(A) for every ground atom A ∈ H.
In the following we define the notion of model for P.
Definition 2: An interpretation I satisfies the ground instantiated rule of P having the form A ← L1,...,Lm if one of the following relations holds:
a. | there is j, 1≤j≤m, such that Î(Lj) = 0 or |
b. | Î(A) ≠ u and min{Î(Li), Î(Li) ≠ u, 1≤i≤m}≤Î(A) or |
c. | Î(A) = u →[(Î(body(r)) = vIj,A)→ (∃i, 1≤i≤m, such that Î(Li) = u)]. |
An interpretation I is a model for P if I satisfies every ground instantiated rule of P.
In the following we need to specify two ordering between interpretations. The first one denoted ≤F, is of type Fitting and the second one denoted ≤s is of type standard[4].
Definition 3: Let I and J be two interpretations, such that VI = (S0,..., Sn) and VJ = (T0,..., Tn). We say that I ≤FJ if Sj ⊆Tj, for every j, 0 ≤ j ≤ n.
We say that I ≤s J if T0 ⊆ S0, Sn ⊆ Tn and Sj ⊆Tj ∪... ∪ Tn-1 for every j, 1≤ j ≤ n-1.
Remark 1: In the case n = 1, the ordering ≤F is the Fitting ordering and ≤S is the standard ordering. These orderings were used by Przymusinski[4] to study the well-founded semantics and three-valued stable semantics.
Stable semantics: Study defines here multi-valued stable models. Firstly, define an operator between the set of all interpretations of the program P. This operator will be denoted by SP.
Definition 4: Let P be a logic program and I be an interpretation of P. We define the interpretation SP(I) in the following manner: if then:
i. | For a ground atom A, A ∈ T0 if for every ground instantiated rule of P, having the form A ← L1,..., Lm, there exists i, 1≤i≤m, such that Î(Li) = 0. |
ii. | For each h, 1≤h<n, a ground atom A is considered in Th if a) and b) hold: |
a. | for every ground instantiated rule of P having the form: A ← L1,..., Lm we have: min {Î(Lj), Î(Lj)≠ u, 1≤j≤m } ≤vh. |
b. | there is a ground instantiated rule of P of the form: A ← V1,..., Vm, such that: min {Î(Vj), Î(Vj)≠ u, 1≤j≤ m} = vh. |
iii. | For a ground atom A, A is considered in Tn, if there is a ground instantiated rule of P having the form A ← C1,..., Cq, such that Î(Cj) = 1 for every j, 1≤j≤q. |
Proposition 2: Let P be a positive program. The operator SP as it is defined in the definition 4 is monotonic with respect to the standard ordering ≤s.
The proof results from the definition of the operator SP and the standard ordering ≤s.
The existence of the least model with respect to ≤s for a positive program P is emphasized by the following theorem:
Theorem 1: For a positive program P, there is the least fixed point of the operator SP with respect to the ordering ≤s, denoted LP. Moreover, LP is the least model of P with respect to the ordering ≤s.
Proof: Consider ⊥ = (H, ø,..., ø) the least interpretation with respect the ordering ≤s. The model LP is obtained applying the operator SP ω times: ⊥, SP (⊥),...., SωP, (⊥) where, ω is the first ordinal.
The rest of the proof is classical, therefore it is skipped.
Now, we need to introduce an operator Γ* defined on the set of all interpretations, which extends the operator Γ defined by Przymusinski[4].
Definition 5: Let P be a general logic program and I an interpretation. We denote by P|I the positive program, which is obtained from P by replacing in every ground instantiated clause of P, all negative literals of the form ~A by cv if I(A) ≠ u and by u otherwise, where v = I(A). The program P|I is positive, hence applying the Theorem 1, it results that P|I admits a unique least model J with respect ordering ≤s. The operator Γ* is defined by: Γ*(I) = J.
Proposition 3: Let M be a fixed point of the operator Γ* from the definition 5. Then M is a minimal model of P with respect to ordering ≤s.
Proof: Let M be a fixed point of Γ*, hence M is the least model of P|M with respect to ≤s-ordering. Firstly, we show that M is a model for P. Let r be an arbitrary ground instantiated clause from P of the form:
(1) |
The corresponding clause r from P|M has the form:
(2) |
where, vj = M(Dj) if M(Dj) ≠ u and u otherwise.
It results that M(~Dj) = M(Dj) = , therefore M satisfies r iff M satisfies r.
Secondly, it must show that M is a minimal model for P with respect to ≤s-ordering. Let M1 be a model for P, such that M1 ≤s M. It is sufficient to show that M1 is also a model for P|M. Since M is the least model of P|M with respect to ≤s-ordering, we obtain that M1≤sM, hence M1 = M.
For the ground instantiated clause r having the form (1), let us denote by r" the corresponding clause to r from P|M1:
(3) |
where, wj = M1(Dj), for every j, 1≤j≤q.
As before, since M1 is a model for P, it obtains that M1 is a model for P|M1, hence M1 satisfies r".
Since M1 ≤s M and using the definition of vj and wj, the following statements are satisfied:
i. | if wj = 0 then vj = 0, for every j, 1≤j≤q. |
ii. | if vj = 1 then wj = 1, 1≤j≤q. |
iii. | if wj = 1 then we have: vj≤wj whenever vj ≠ u, 1≤j≤q. |
iv. | If 0<wj<1, then we have (vj ≠u and vj≤wj, 1≤j≤q). |
These statements imply the inequality:
(4) |
The relation (4) and the fact that M1 is a model for r" involve that M1 is a model for r, hence for P|M.
A multi-valued stable model for P is defined as a fixed point of the operator Γ*.
Definition 6: A multi-valued interpretation M for a program P is called a multi-valued stable model for P if M is a fixed point of Γ*.
Well-founded models: For definition of well-founded models we need to introduce an operator, denoted W, defined on the set of all multi-valued interpretations.
For an interpretation I, if J=W(I) and VJ= (S0, S1,..., Sn), we define the sets Sj, 0≤j≤n.
Definition 7: Let I be an interpretation. We define the sets Sj, 0≤j≤n in the following manner:
a. | for every j, 1 ≤ j ≤ n, a ground atom A is included in Sj iff |
a1. | for every ground instantiated rule r of P of the form: r ≡ A ← L1,..., Lm, we have : min {Î(Lj), Î(Lj)≠ u, 1 ≤ j ≤ m} ≤ vj and |
a2. | there exists a ground instantiated rule r1 of P with the form: r1≡ A ← Q1,..., Qh, such that: Î(Qi)≠ u, for every i, 1 ≤ i ≤ h and min {Î(Qi),1 ≤ i ≤ h } =vj. |
b. | A set of atoms V from H is called unfounded set of P with respect to I if every atom A from V satisfies the following property: for each ground instantiated rule r of P, having the form: r ≡ A ← L1,..., Lm, one of the following statements holds: |
b1. | there is i, 1 ≤ i ≤ m, such that Î(Li) = 0 or |
b2. | there is i, 1 ≤ i ≤ m, such that Li is an atom and Li∈V. |
c. | we consider S0 as the union of all unfounded sets of p with respect to I. |
Remark 2: If V1 and V2 are unfounded sets of P with respect to I, then their union V1 ∪V2 is also an unfounded set with respect to I.
Proposition 4: The operator W is monotonic with respect to Fitting ordering ≤F.
Proof. Let I and J be two interpretations, such that I≤F J. Let VI = (S0, S1,...,Sn) and VJ = (T0, T1,..., Tn).
We have Sj ⊆ Tj for every j, 0 ≤ j ≤ n. That means: if Î(Li) ≠u then Î(Li) ≠ u and Î(Li) = Î(Li), for every literal Li.
If Vw(I) = (S0, S1,...., Sn) and Vw(J) = (T0, T1,...., Tn) then it obtains that Sj⊆Tj, for every j, 1 ≤ j ≤ n. (1)
The relations S0 ⊆ T0 and Sn ⊆ Tn imply the following statement: every unfounded set of P with respect to I is an unfounded set of P with respect to J.
We obtain S0 ⊆ T0. This relation and those from (1) involve W(I) ≤F W(J).
Now, we define a sequence of interpretations using the operator W defined above.
Definition 8: Let α range over countable ordinals. We define recursively the interpretations Iα and I∞ as follows:
1. | For ordinal 0, I0 = (ø,..., ø), where ø is the empty set; |
2. | For the limit ordinal |
3. | For successor ordinal α = γ+1: Iα = W(Iγ); |
4. |
Remark 3
i. | The interpretation I∞ is the least fixed point of W with respect to the Fitting ordering ≤F. |
ii. | There exists a countable ordinal α, such that I∞ = Iα. |
Let us denote the interpretation I∞ by IP.
Theorem 2: The sequence of interpretation Iα as defined in the Definition 8 is a monotonic sequence of interpretations with respect to ≤F-ordering and moreover it is a sequence of models for P.
Proof: The monotony of the sequence of interpretations results from the Proposition 4.
By the Definition 2, I0 is a model for P. Since the operator W is monotonic with respect to ordering≤F, it results by induction on ordinals α the following statement:
for every ground literal L and γ<α, if Iγ (L) ≠ u then Iα (L) ≠ u and Iγ (L) = Iα (L) | (1) |
Assume that Iγ is a model for P. Let us show that I γ+1 is also a model for P, where γ is an arbitrary ordinal. Let r ≡ A 7 L1,..., Lm be a ground instantiated rule of P. If Iγ+1 (A) = u, then Iγ+1 satisfies r.
In the case Iγ+1 (A) ≠ u, let = (S0, S1,..., Sn). There exists j, 0 ≤ j ≤ n, such that A ∈ Sj. We have Iγ+1 (A) = vj. Using the Definition 7 and the relation (1), we obtain that Iγ+1 satisfies r.
Now, let A be a limit ordinal. Assume that Iβ for every β<α are models for P. Let us show that Iα is model.
Let r be defined as above. If Iα (A) = u, then Iα satisfies r. In the case Iα (A) ≠ u, there is h, 0≤h≤n, such that . The sequence of sets , β<α is ascending monotonic with respect to the inclusion. Let β1 be the first ordinal such that . We have Iβl(A)= vh and Iβl is a model for r. Since β1<α and using the relation (1), it results that Iα satisfies r.
Stable Semantics versus well-founded semantics: In this section we point out a relation between the stable semantics and the well-founded semantics, namely the well-founded model of P is the least stable model of P with respect to≤F-ordering.
Theorem 3: Let P be a normal logic program. Then P admits≤F-least stable model. Moreover, this model coincides with the well-founded model of P.
Proof: Let IP be the well-founded model for P and λ be the minimum ordinal such that Iλ = Iλ+1 (from the Definition 8).
Firstly, we show that IP is a stable model for P. Let P be P/IP and M1 be an arbitrary model for P, such that M1≤s IP. It must show that M1 = IP. Let be the vector (T0,..., Tn) and .
The relation M1≤s IP is equivalent with:
Assume that M1 ≠ IP. Then, we have one of the following assertions:
The sign "⊂" denotes the strict inclusion and "ø" means "not included".
In the case a) let us consider α the least ordinal such that . where is specified in the Definition 8, for every ordinal α. It results that and there exists a ground atom A, such that . By the definition of Snα+1, there is a ground instantiated rule r of P, having the form: r1 ≡ A ← B1... Bm ~ D1...~Dp,
where, Bj, 1≤j≤m and Dl, 1≤l≤p are ground atoms with the properties:
Îα(Bj) = 1 for every j, 1≤j≤m and Îα(Dl) = 0 for every l, 1≤l≤p.
Let r1 be the rule from P corresponding to r1. Then r1≡ A ← B1,...,Bm, where, vj = Îλ(Dj) for every j, 1≤j≤p. Since Sαn⊆Tn, we obtain that M1(Bj)= 1, j = Since Iα≤F Iλ, it results Iλ(Dj) = 0, j = hence vj = 1, for every j, 1≤j≤p. We have: M1 is a model for r1. This implies M1(A) = 1, hence A ∈ Tn, which is impossible. Therefore, we have Tn = Snλ.
In the case c)let α be the least ordinal, such that ∉ Th ∪...∪ Tn-1 (1)
It results: ∪...∪ Tn-1 (2)
Using the relation (1), we obtain: there is A, such that A ∈ Shα+1 and A ∉ Th ∪...∪ Tn-1 (3)
A ∈ Shα+1 implies: for every r ∈ MA, r ≡ A ← L1,..., Lm, we have Îα(body(r))≤vh (4)
and there is r1 ∈ MA, r1 ≡ A ← Z1,..., Zp, such that Îα(Zj) ≠ u, for every j, 1≤j≤p and min {Îα(Zj)}= vh. (5)
Let r1 from (5) be expressed as follows: r1 ≡ A ← B1... Bm ~ D1...~Dq
We have: Îα(Bi) ≠ u, i = and Îα(~Dj) ≠ u, i = which imply: Îα(Bi)≥vh and Îα(~Dj)≥vh i = (6)
Let r1 be the clause from P/IP corresponding to r1: r1≡ A 7B1,...,Bm, where, vj = ÎP(Dj), j = Since Iα≤F IP, we have ÎP(~Dj) = Îα(~Dj), for every j, j = hence vj≥vh for j = (7)
We have Iα(Bi)>0, i = If Iα(Bi) = 1, then Iλ(Bi) = 1 and using Tn = Snλ, it obtains that M1(Bi) = 1. If Iα(Bi)<1, then using (2) it results: Bj∈ Th ∪...∪ Tn-1, hence M1(Bi)≥vh. Since M1 satisfies r1, we have M1(A)≥vh. We show that M1(A) ≠ 1. Assume the contrary: M1(A) = 1. Using Tn = Snλ, we obtain A ∈ Snλ. (8)
From A ∈ Shα+1, it results A∈Shλ, with h<n. (9)
But Shλ ∩ Snλ=ø for h<n. The relations (8) and (9) constitute a contradiction.
From M1(A)≥vh and M1(A)<1 we obtain A ∈Th ∪...∪ Tn-1 which contradicts the relation (3).
In conclusion for the case c), we have:
Shλ⊆Th ∪...∪ Tn-1 for every .
Using (iii), it results .
In the case b), namely S0λ⊂T0, we show that T0⊆S0λ, which will be a contradiction.
Let A be from T0, hence M1(A) = 0. Let r be a ground instantiated rule from P, having the form: r ≡ A ← B1... Bm ~ D1...~Dp
The clause corresponding to r from P/IP is r:
r≡ A ← B1,...,Bm, where, vj = XÎλ(Dj), j = .
Since M1 is a model for r, it follows that there exists i, 1≤i≤m such that M1(Bi) = 0 or there is j, 1≤j≤p, such that
For every we have Îλ(~Dj) = 0. (10)
If for all j, 1≤j≤p, then there is i, 1≤i≤m, such that M1 (Bi) = 0,
hence Bi∈ T0. (11)
The assertions (10) and (11) say that T0 is an unfounded set with respect to Iλ.
But W(Iλ) = Iλ, hence we have T0 = Sλ0, which implies T0⊆Sλ0 therefore a contradiction.
Thus, we have Sλ0 = T0, hence M1 = IP and Iλ = IP is a stable model for P.
Secondly, we show that IP is≤F-least stable model for P.
Let M1 be a stable model for P. Let VM1 be defined as follows:
VM1 = (T0, T1,..., Tn). |
The model M1 is the least model of P/M1 with respect to the ordering≤s. Let Ia be the interpretations as in the Definition 8. Let .
We show by induction on α the following relations: Sα⊆Tk, for every k, 0≤k≤n. (12)
Since I0 = (ø,..., ø), we have that (12) are true for k = 0.
Assume that (12) is true for every ordinal α, α<ί.
If ß is limit ordinal, then (12) is true for ß.
Now let ß be a successor ordinal, ß = α + 1.
It must show that (13)
Let us distinguish two cases:
1) k≥1, 2) k = 0.
In case 1) let A be from Sα+1k. We have: for every r ∈ MA, having the form: r ≡ A 7 Z1... Zq, min {Îα(Zj), Îα(Zj) ≠ u}≤vk and there is r1 ≡ A 7 S1... Sp, such that Îα(Sj) ≠ u, for every j, 1≤j≤p and min {Îα(Sj), 1≤j≤p} = vk. From (12) it results:
Îα(L) = M1(L) for every ground literal L.(14)
Since M1 is also a model for P, we have M1(A) ≠ u and moreover M1(A)≥vk. Let us denote M1(A)= vh.
If we assume that vh>vk, then we define an interpretation M1 as follows:
M1 (B) = M1 (B) if B ≠ A and vk otherwise. |
It results that M1 is a model for P/M1, M1≤s M1 and M1≠ M1, which contradicts the fact M1 is the least model for P/M1 with respect to the ordering≤S. Hence, we have vh = vk, i.e. A∈Tk.
In the case 2) let A be form S0α+1.
In this case, for every r ∈ MA, of the form: r ≡ A ← L1... Lm, there is i such that Îα(Li) = 0, or there is i, such that Li is atom and Li ∈ S0α+1. (15)
Using the hypothesis of induction (12), we obtain: Îα(Li ) = 0 implies M1(Li ) =0.
Let r ∈ MA be of the form r ≡ A ← B1... Bq ~ D1...~Dp
The clause corresponding to r from P/M1 is r:
r≡ A 7B1,...,Bq, where vj = XM1(Dj),
If M1(A) ≠ u and M1(A) = 0, then A∈ T0.
If M1(A) ≠ u and M1(A) = vk, with vk>0, then we consider a model M1 defined by following:
Since S0α+1 is an unfounded set with respect to M1, we have M1 is a model for P/M1.
Moreover, since M1≤s M1 and M1 ≠ M1, it results a contradiction.
If M1(A) = u, we consider the same interpretation M1 as it was described above, which implies a contradiction. It results the statement (13). Taking in (13) α = λ, it obtains that IP≤F M1, therefore IP is the≤F-least stable model for P.
This study introduced new semantics for general logic programs considering a set of n+1-truth logic values and an undefined value. One of semantics is of type well-founded and the other is of type stable. We have studied a relationship between the two semantics. For n=1 and u=1/2, the results of Przymusinski[4] are obtained.