Logic Programming and fuzzy logic are active areas of research,and their scopes in terms of applications are growing fast. Fuzzy logic is a branch of many-valued logic based on the paradigm of inference under vagueness. In this work we recall some of the interplay between three 3-valued logics that are relevant in these areas: The Lukasiewicz logic, the intermediate logic G3 and the paraconsistent logic G′3, and we present a contribution to the area of answer sets that consists in extending a de nition of stable model based on proof theory in logic G3, to a more general de nition that can be based on any of the more expressive logics G′3 or Lukasiewicz.
The stable semantics allows us to handle problems with default knowledge and
produce non-monotonic reasoning using the concept of negation as failure. The
p-stable semantics is an alternative semantics, except that in some cases offers
models where the stable semantics has none. There are two popular software
implementations to compute the stable models: dlv3 and smodels4. The efficiency
of such programs has increased the list of practical applications in the areas
of planning, logical agents and arti cial intelligence. On the other hand, there
exist different approaches for knowledge representation based on the p-stable
semantics, such as, updates [
The term fuzzy logic emerged in the development of the theory of fuzzy sets
by Lot A. Zadeh (1965) [
Attribution 4.0 International (CC BY 4.0)
seminal paper by Lot A. Zadeh in 1965 [
We can distinguish two main directions in fuzzy logic [
In particular, Lukasiewicz and Post gave the rst published systematic
descriptions of many-valued logical systems in the modern era [
Our paper is structured as follows. In section 2, we summarize some de nitions, logics and semantics necessary to understand this work. In section 3, we show how to express the stable and the p-stable semantics of normal programs in terms of Lukasiewicz logic. We present a de nition of stable model for more general programs in terms of the intermediate logic G3, and then we extend such de nition, in a conservative way, in terms of the paraconsistent logic G′3. Finally, in section 4, we present some conclusions. 2
In this section we summarize some basic concepts and de nitions necessary to understand this paper. 2.1
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 propositional 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.
A normal clause is a clause of the form a
b1 ^ : : : ^ bn ^ :bn+1 ^ : : : ^ :bn+m where a and each of the bi are atoms for 1 i n + m. We de ne a normal program P , as a nite set of normal clauses.
The body of a normal clause could be empty, in which case the clause is known as a fact and can be denoted just by: a .
We write LP , to denote the set of atoms that appear in the clauses of P . Given a set of atoms M and a signature L, we de ne :Mf = f:a j a 2 LnM g.
Since we shall restrict our discussion to propositional programs, we take for granted that programs with predicate symbols are only an abbreviation of the ground program. 2.2
We review some logics that are relevant in this paper to characterize different semantics of normal and more general programs.
We present de nitions in terms of true values as well as Hilbert style de nitions for most of these logics. The logics considered here have the modus ponens as a unique inference rule. Lukasiewicz's 3-valued logic The polish logician and philosopher Jan Lukasiewicz began to create systems of multivalued logics in 1920. He developed, in particular, a system with a third value to denote \possible" that could be used to express the modalities \it is necessary that" and \it is possible that". To construct this logic, denoted by L3, we rst have to modify the syntax of our formulas to allow, as primitive connectives, only: the 0-place connective ? (failure) and the 2-place connective ! (implication). These connectives operate over a domain D = f0; 1; 2g, with 2 as the unique designated value, and are de ned as follows: { ? = 0, { x ! y = min(2; 2
x + y).
Other connectives in L3 are introduced in terms of ? and ! as follows: :A := A ! ? A _ B := (A ! B) ! B
A := :(A ! :A)
⊤ := :?
A ^ B := :(:A _ :B)
♢A := :A ! A
The truth tables of most connectives are shown in Table 1, the conjunction and
disjunction connectives (not shown) coincide with the min and max functions
respectively. A syntactic characterization of the modal content of L3 is studied in
[
Lukasiewicz generalized his three-valued logic to n values and also to an
in nite-valued system [
G3 logic Godel de ned, in fact, a family of many-valued logics Gi with truth values over the domain D = f0; 1; : : : ; i 1g and with i 1 as the unique designated value. Logic connectives are de ned as: { ? = 0, x ^ y = min(x; y), x _ y = max(x; y), and { x ! y = i 1 if x y and y otherwise.
The only difference between the true tables of G3 and G′3 is the negation of the value 1 that is 0 in G3.
A Hilbert style version of this logic G3 is obtained from intuitionistic logic
[
From now on we will denote by : the negation of G′3 and by the negation of G3.
Classical logic Classical logic, C, is obtained from intuitionistic logic [
From now on, we assume that the reader is familiar with the notion of classical
minimal model [
We present the characterization of the stable semantics for normal programs in terms of the G3 logic. A similar characterization exists for p-stable semantics in terms of logic G′3.
We use the notation X P to indicate that formula P is a theorem or a
tautology in logic X depending on logic X. For a nite family of formulas Q =
q1; q2; :::; qn and a set of atoms M , the expression Q X M will mean that M is
a classical model of Q and that X q1 ! (q2 ! (:::(qn ! m):::) for each m in
M
Stable semantics From now on, we assume that the reader is familiar with
the notion of classical minimal model [
The characterization of the stable semantics for normal programs in terms of logic G3 is given in the following de nition.
De nition 1. [
Example 1. Let P be the following normal program: fa b; b ag and let M1 = fag and M2 = fbg, according to the de nition of stable semantics, since P [ f bg G3 fag and P [ f ag G3 fbg, then M1 and M2 are stable models of P as the reader can easily check. One of our motivations to study Lukasiewicz's L3 logic is the fact that it is able to express the semantics of other logics such as Godel's G3 and G′3.
This subsection presents some results from [
Let us denote the new X or operator by the symbol ⊖. We can characterize this operator by the following three properties in order to obtain the values we need. Observe that the last equation re ects the encoding-decoding property and also that the commutativity of the operator follows from the equations shown below.
x ⊖ 0 = x x ⊖ x = 0 (x ⊖ y) ⊖ y = x
According to these properties we have from (1 ⊖1)⊖1 = 1 and (2⊖2)⊖2 = 2, that 0 ⊖ x = x, furthermore from (1 ⊖ 2) ⊖ 2 = 1 it follows that 1 ⊖ 2 = 1. A similar argument shows that 2 ⊖ 1 = 2.
Therefore we get the Table 5 for the X or operator in three truth values.
What we want next is to express this truth table as a function of two variables,
however this is not possible in logic G3, since as it is well known, any function f
of two variables de ned in this logic has the property that f (2; 2) = 2 whenever
f (1; 2) = 1 [
Let us remember that the symbol : is the G′3-negation, the symbol is the G3-negation, and that x = x ! (:x ^ ::x), then in G′3 the X or operator is expressed by the following formula: (x _ y) ^ (:x _ :y) ^ (x_ x) ^ ((::x_ x) _ (::y_ y))
Expressing p-stable and stable semantics based on L3 Here, we show how to express stable semantics via L3 logic. This is possible due to two facts: L3 logic is able to express the semantics of G3 logic, and the stable semantics is de ned in terms of this logic.
We rst de ne a function that obtains the clause that results when we substitute the G3 connectives by the L3 connectives from a given clause.
Given a clause r expressed in terms of the G3 connectives, we de ne T radG3toL3 (r) as the clause that results when we substitute the G3 connectives for the L3 connectives according to Table 3. Given a normal program P , we de ne T radG3toL3 (P ) as the set fT radG3toL3 (r) j r 2 P g.
Example 2. Let us consider the program P1 = P [ f of Example 1, namely the program bg where P is the program a b b: b: a: We can see that L1 = T radG3toL3 (P1) is the following program: ( :b ! a) ^ ( :a ! b) ^ :b: : :( : : :b ! a): : :( : : :a ! b):
Now we present the de nition of the stable semantics based on the de nition of G3 via L3. Similar results are obtained for the p-stable semantics and logic G′3.
Theorem 1. [
Example 3. Let us consider the program P of Example 1. Let M1 = fag and M2 = fbg. Then we have that T radG3toL3 (P [f bg) L3 fag and T radG3toL3 (P [ f ag) L3 fbg where T radG3toL3 (P [ f bg) corresponds to the program L1 of Example 2. Hence, M1 and M2 are stable models of P as we obtained in Example 1.
Next we take advantage of the fact that logic G3 can be expressed in terms
of paraconsistent logic G′3 to provide a de nition, by way of paraconsistency,
that extends the concept of stable model to general programs. In order to do
this, we state a general de nition of stable model in terms of G3 logic, which in
turn generalizes the de nition we have for normal programs. It is important to
observe that in the following formula we can use intuitionistic logic instead of
G3 logic.
De nition 2. [
LP is
As expected, this de nition is a generalization of de nition 1 for normal programs; it uses the fact that the double negation of the atoms in the set M are added as premises in the equation.
As it is well known, it is desirable that replacing equivalent formulas as parts of programs would leave the same stable models as in the original program. This property does not hold if we start with two programs that have the same stable models. For example, take the two programs P1 = fa bg and P2 = fag with the same stable models, and now consider the two programs Q1 = fa b; bg and Q2 = fa; bg originated from the previous two programs after adding the same atom to both of them, these two programs are no longer equivalent according to the next de nition.
De nition 3. Two programs P1 and P2 are equivalent if they have the same stable models.
In [
De nition 4. Two programs P1 and P2 are strongly equivalent if for every program P , P1 [ P and P2 [ P have the same stable models.
In order to present the generalization of the stable semantics in terms of paraconsistency, we remind the reader that the symbol that appears in the next de nition is the negation of G3 and the program P is expressed in terms of logic G′3.
Mf[ De nition 5. Let P be a program de ned in the language of G′3 and M be a set of atoms. We say that M is an L-stable model of P if T radG3toL3 (P [ M ) L3 M LP
We observe that this de nition is a conservative extension of De nition 2 since the language of logic G3 is fully expressed in terms of the paraconsistent logic G′3 as previously noted. Also observe that the G′3-negation appears only in the program P .
As a consequence of this de nition we have the following result for L-stable models of programs expressed in the G′3-language.
Theorem 2. Let P and Q programs expressed in the language of logic G′3. If P G′3 Q, then they are strongly equivalent in the context of L-stable models.
Mf[ and T radG3toL3 (Q[ Proof. The result follows from De nition 5 since T radG3toL3 (P [
M ) are equivalent in L3.
Mf[
M ) As a natural consequence that follows from our de nitions we have: Theorem 3. Let P be a program expressed in the original language of the stable semantics, then De nitions 2 and 5 provide the same sets as stable and L-stable models respectively.
Proof. We only need to observe that a program in the original language of the answer set semantics can be interpreted as written in terms of the G3 language, then the conclusion follows from the relation that exists between G3 and L3.
Finally, as an example let us compute the L-stable models of the program given by the formula x ⊖ y. This program is expressed below in terms of its clauses x _ y :x _ :y x_ x (::x_ x) _ (::y_ y)
The language of the program is fx; yg. According to De nition 5, a set of atoms M is a L-stable model of P if T radG3toL3 (P [ Mf[ M ) L3 M . We work with logic G′3 whose language is more natural. Note also that the expression Q X M as de ned in the background, is equivalent to (q1 ^ q2 ^ :::qn) ! m for each m in M when X is G′3 or L3.
Let us propose M = fxg, then Mf = y and M = x
The left hand side of this implication is a conjunction of the four rules that express x ⊖ y plus the two rules or facts: y and x
Let us assume that for certain valuation x takes the value 1, then the third rule of the antecedent takes the value 1 and therefore the antecedent cannot take the value 2. Now if we assume that the atom x takes the value 0, then the last rule of the antecedent takes the value 0 and so does the antecedent. We conclude that the implication is a tautology in G′3 and the set M = fxg is a L-stable model.
Now, if we try M = fyg, then the last two rules of the implication we are working with, become: x and y.
Let us assume that for certain valuation y takes the value 1, then the rst and fth rules of the antecedent cannot be 2 at the same time. In the case the atom y takes the value 0 the last rule of the antecedent is 0 too. Therefore the implication is a tautology and the set fyg is a L-stable model too.
In a similar way we can see that the valuation x = 2; y = 1 shows that the set M = fx; yg is not a L-stable model. 4
We show that Lukasiewicz logic can be used for knowledge representation based on logic programming. We review how two useful semantics to represent knowledge, stable and p-stable, are characterized via L3 logic. In particular we take advantage of the fact that Lukasiewicz's logic L3 is able to express G3 and G′3 logics, which characterize those two semantics for normal programs respectively. We also present the de nition of stable model for general programs in terms of logic G3 and extend it for programs in the languages of G′3 and L3. Finally we present the concept of strong equivalence in the new context of paraconsistency.