Extending Fuzzy Linguistic Logic Programming with Negation ^†

Abstract

Fuzzy linguistic logic programming (FLLP) is a framework for representation and reasoning with linguistically expressed human knowledge. In this paper, we extend FLLP by allowing negative literals to appear in rule bodies, resulting in normal logic programs. We study the stable model semantics and well-founded semantics of such programs and their relation. The two kinds of semantics are adapted from those of classical ones based on the Gelfond–Lifschitz transformation and van Gelder’s alternating fixpoint approach, respectively. To our knowledge, until now, there has been no work on the well-founded semantics of normal programs in any fuzzy logic programming (FLP) framework based on Vojtáš’s FLP. Moreover, the relation between the two kinds of semantics is usually studied using a bilattice setting of the truth domain. However, our truth domains do not possess a complete knowledge-ordering lattice and, thus, do not have a bilattice structure. The two kinds of semantics possess properties similar to those of the classical case. Every stable model contains the well-founded (partial) model, and the well-founded total model coincides with the unique stable model, but not vice versa. Since the well-founded semantics is closely related to the stable model semantics, it can help compute stable models more efficiently.

1. Introduction

In the real world, there are situations where information might not be stated in a quantitative form, but rather in a qualitative one, e.g., by linguistic terms. This may arise for different reasons [1]. In some cases, due to its nature, the information may be unquantifiable and thus can be given only in linguistic terms; for instance, when accessing the “comfort” or “design” of a car, we might be led to use linguistic terms such as “good”, “medium”, and “bad” [2]. In other cases, precise quantitative information may not be given since either it is unavailable or the cost of computation is too high, so a linguistic “approximate value” might be acceptable; for example, when the rotation speed of an electric motor is accessed, linguistic terms, e.g., “very large”, “large”, and “medium”, might be utilized instead of numerical values [3]. Furthermore, since humans primarily use words to describe phenomena and things, to reason, and to make decisions, human knowledge is usually expressed linguistically and employs fuzzy concepts and hedges. Hence, it is essential to have a knowledge representation framework that can directly work with linguistic terms and hedges to give answers to queries. Such a framework can provide a computational approach to human reasoning and can be a foundation for applications dealing with linguistic information.

FLLP is introduced in [4] as a logic programming (LP) framework without negation for representation and reasoning with linguistically expressed human knowledge, where the truth of vague sentences is stated linguistically and various linguistic hedges can be used simultaneously to express different levels of emphasis. To our knowledge, FLLP is the only FLP framework that can directly compute with linguistic terms and hedges in query answering and allow hedge connectives to appear in rule bodies to modify fuzzy predicates. Note that linguistic hedges play a very important twofold role in Zadeh’s fuzzy logic, namely in the modification of fuzzy concepts and in the generation of linguistic values of linguistic variables [5].

In FLLP, each fact or rule is evaluated by some linguistic truth value, and linguistic hedges can operate as unary connectives in rule bodies. For example, the evaluation “(A student is good if he/she is rather smart and studies very hard) is highly true” can be represented by the rule:

$$good\left(X\right)\leftarrow \wedge \left(Rsmart\right(X),Vhard\_working(X\left)\right).HT$$

where R, V, H, and T stand for rather, very, highly, and true, respectively.

FLLP has a counterpart for most of the notions and results of classical definite LP [4,6], e.g., declarative semantics, procedural semantics, and fixpoint semantics. In particular, the procedural semantics and fixpoint semantics [4] can give answers to queries by directly computing with linguistic terms. However, the latter is exhaustive and not goal-oriented, and the former is goal-oriented but may lead to an infinite loop. Therefore, in [7,8], two tabulation proof procedures for query answering, which are goal-oriented, sound, complete, and terminated, are provided. Of the procedures, the deterministic is more efficient than the non-deterministic and computes all and only the most general answers for a query.

It can be observed that permitting the representation and manipulation of negation is a key feature for real-world applications. In classical LP, Horn programs are extended to normal logic programs by allowing negative literals to occur in rule bodies for expressing explicit negative information. For example, in the real world, we usually do “jumping to conclusions” when the available information is incomplete [9]. For instance, if we know that Tweety is a bird, we jump to the conclusion that it can fly. This default assumption, i.e., that birds can fly, can be represented by the following rule:

$$fly\left(X\right)\leftarrow bird\left(X\right)$$

Later, if we have more information, it might turn out that the conclusion is no longer true and must be withdrawn. For instance, if we afterwards know that Tweety is a penguin, the conclusion is withdrawn. This use of logic is called belief revision. One method of belief revision in LP is using abnormality relations and negation. For the case of the penguin Tweety, we can change the rule to the one below [9]:

$$fly\left(X\right)\leftarrow bird\left(X\right)\wedge \neg abnorma{l}_{fly,bird}\left(X\right)$$

(1)

and add the following rule to the program:

$$abnorma{l}_{fly,bird}\left(X\right)\leftarrow penguin\left(X\right)$$

(2)

Thus, the complete, revised program consists of rules (1), (2) and the following facts:

$$\begin{array}{ccc}\hfill bird\left(tweety\right)& \leftarrow & \\ \hfill penguin\left(tweety\right)& \leftarrow \end{array}$$

The well-founded semantics [10] and the stable model semantics [11] are probably the most widely studied kinds of semantics for classical normal logic programs. The motivation behind the former is to extend the least model semantics of Horn programs to normal logic programs, i.e., keeping the property of the uniqueness of an intended/canonical model. Generally, this means moving beyond the setting of two-valued interpretations. In contrast, the objective behind the latter is to keep intended models two-valued. However, this means the existence and uniqueness properties of intended models could no longer be ensured. More precisely, all normal programs have a well-founded partial model, which can be interpreted as a three-valued model in Fitting’s sense [12], whereas a normal program can have multiple/one/no stable (total) models. Moreover, the well-founded model can be seen as an approximation of all stable models (if they exist) [13]. Every stable model contains the well-founded (partial) model. Consequently, a well-founded total model coincides with the unique stable model, but not vice versa.

In the literature of FLP, which is an extension of classical LP with many-valued logic (MVL)/fuzzy logic in the narrow sense (FLn)/mathematical fuzzy logic (MFL) for handling vagueness, there are few works addressing the issue of non-monotonic negation. Cornejo et al. [14] study the stable model semantics of multi-adjoint normal logic programs and its properties. These results are extensions of those of normal residuated logic programs in [15]. Loyer and Straccia [16] define the well-founded semantics (therein called the compromise semantics) for normal logic programs in a parametric implication-based framework. Nevertheless, to our knowledge, there is no work studying both kinds of semantics and their relation within an FLP framework.

Another approach to defining the semantics of normal logic programs is based on the notion of bilattice [17,18]. A bilattice is a structure $〈\mathcal{B},{⪯}_t,{⪯}_k〉$, where ${⪯}_t$ and ${⪯}_k$ are the truth order and knowledge order on $\mathcal{B}$, respectively. The extension of the stable model semantics and the well-founded semantics of classical normal logic programs to the context of bilattices is due to Fitting [19,20]. In this approach, Loyer and Straccia [21], Loyer and Straccia [22] propose the approximate well-founded semantics for normal logic programs in an FLP framework based on the notion of an approximate interpretation, which assigns to an atom A a logical (interval) value [a; b], meaning that the exact truth value of A is between a and b.

In this paper, we extend FLLP by permitting negative literals to appear in rule bodies, resulting in normal logic programs. We study both the stable model semantics and the well-founded semantics of such programs and their relation in terms of fixpoints of several operators. It is shown that the two kinds of semantics possess properties similar to those of the classical case. Therefore, the study conducted in this work makes the following contributions: (1) enriching the theory of FLLP with negation to extend its applicability in real-world applications; (2) studying the two most widely studied kinds of semantics of normal programs, namely the stable model semantics and the well-founded semantics (note that this is the first time the well-founded semantics is proposed for an FLP framework among those based on Vojtáš’s FLP [23]); and (3) studying the relation between the two kinds of semantics, which can help compute stable models more efficiently.

The remainder of the paper is organized as follows: Section 2 provides a literature review, while Section 3 gives an overview of FLLP without negation. Section 4 presents FLLP with negation, the stable model semantics and the well-founded semantics of normal logic programs, and their relation. Section 5 concludes the paper and gives several directions for future work.

2. Literature Review

2.1. Managing Vagueness in Logic Programming

In order to handle vagueness, classical LP is often extended with MVL/FLn/MFL. There have been many frameworks (see, for instance, [24]) proposed in this approach. In the implication-based (IB) approach [25], a truth value, which can be called the degree of confidence or the weight, is attached to each rule. The underlying logic is often truth-functional; that is, the truth value of a compound formula is computed using truth functions of connectives in the formula. Most of the works deal with logic programs without negation. More precisely, a rule is of the form:

$$A\leftarrow @(B_1,\dots ,B_n).q$$

(3)

where $A,B_1,\dots ,B_n$, $n\ge 0$, are atoms, @ is an operator aggregating atoms, and q is the truth degree of the rule. Given a fuzzy interpretation I of $B_i$s by truth values in a truth domain, the truth value of A is computed by evaluating the truth value of the rule body using the truth function ${@}^{•}$ and then somehow “propagating” it to the rule head.

One of the most well-known frameworks in the IB approach is Vojtáš’s FLP [23]. The truth domain is the unit interval [0, 1] with its usual ordering. A fuzzy logic program is a finite set of fuzzy rules of the form (3) and facts, which are graded atoms of the form $(A.a)$. In a rule, @ is an aggregation connective whose truth function is an aggregation operator. The aggregation operators can cover all kinds of fuzzy conjunctions and disjunctions. Rules can use different implication connectives ${\leftarrow }_i$. The truth function of an implication connective is an implicator which is residual to a conjunctor; i.e., they satisfy the residuation property (9). A conjunctor has the same properties as a t-norm except that commutativity and associativity are not assumed [26].

Monotonic logic programming (MLP) and residuated logic programming (RLP) [27] differ from Vojtáš’s FLP in the following ways: (a) they extend the truth space to either a complete upper semilattice $\mathcal{L}=\langle \mathcal{T},⪯\rangle$, where the carrier set $\mathcal{T}$ is not necessary to be the unit interval [0,1], for the case of MLP, or a complete residuated lattice, in which there is a pair of binary operations $(\leftarrow ,\otimes )$ forming an adjoint (residual) pair, for the case of RLP; (b) they follow an algebraic approach to both syntax and semantics of logic programs [28]. That is, monotonic logic programs (resp., residuated logic programs) are constructed from the abstract syntax induced by an implication algebra, defined with an R-implication ← on $\mathcal{L}$, (resp., by an residuated algebra, defined with a residual pair $(\leftarrow ,\otimes )$) and a set of propositional symbols; (c) the aggregation operator @ is only required to be monotonic; (d) the languages are propositional ones; and (e) there is only one implication connective used in logic programs.

Multi-adjoint logic programming (MALP) [29] is an extension of RLP in the sense that: (i) it is possible to use a number of different implication connectives in rules as in Vojtáš’s FLP; (ii) the algebraic requirements on residuated lattices are weaker (more precisely, the condition that $(\mathcal{T},\otimes ,\top )$ is a commutative monoid in a residuated lattice is replaced by a weaker condition $\top \otimes q=q\otimes \top =q$, where ⊤ is the top element of $\mathcal{L}$, in a multi-adjoint lattice); and (iii) some sufficient conditions for the continuity of the immediate consequence operator $T_P$ are established. In fact, if all operators @ in rule bodies are continuous in all arguments, and all adjoint conjunctors ⊗ are continuous in the rule body argument, then $T_P$ is continuous. MALP is extended to a first-order language in [30]. In this setting, MALP is an extension of Vojtáš’s FLP in terms of the truth space and becomes one of the most general FLP frameworks.

FLLP extends or modifies Vojtáš’s FLP on the following aspects [4]: (a) utilizing linguistic truth domains instead of the unit interval [0,1]; (b) allowing rule bodies to use hedge connectives to modify fuzzy predicates; (c) adding an admissible rule to deal with hedge connectives in procedural semantics; (d) giving detailed proofs of the mgu lemma, the lifting lemma, and the completeness theorem for the case of general (i.e., non-ground) queries; (e) allowing rule bodies to use linguistic aggregation operators [6,31]; (f) proving counterparts of the results of classical definite LP, e.g., the model intersection property and the characterization of the least Herbrand model of a logic program by the infimum of the set of all its Herbrand models [6]; (g) proving a Pavelka-style completeness [32] for ground atoms [6]; (h) providing a sound and complete terminating goal-oriented deterministic query-answering procedure, which computes all and only the most general answers to a query [7]; and (i) in this work, extending logic programs with negation. It can be seen that the purely linguistic property and hedge connective usage are unique features of FLLP among FLP frameworks. In particular, hedge connectives have no counterpart in the other FLP frameworks. Therefore, FLLP is not a special case of any FLP framework even though our LTD is just a chain.

The frameworks in [33,34,35], among others, can also be classified into the IB approach.

2.2. Normal Logic Programs for Handling Vagueness

In the literature of LP dealing with vagueness, there are few works addressing the issue of non-monotonic negation.

Cornejo et al. [14] study the stable model semantics of multi-adjoint normal logic programs (MANLP) and prove the existence of stable models for MANLPs whose truth domain is a convex compact set of a Euclidean space and the operators in rule bodies are continuous. Moreover, they show that the uniqueness of stable models is ensured for a special kind of MANLPs on the subinterval lattice $\left(\mathcal{C}\right([0,1]),\le )$. These results extend those of normal residuated logic programs (NRLP) [15]. The stable model semantics of NRLPs is also developed based on the Gelfond–Lifschitz transformation [11]. However, the well-founded semantics is not discussed in these works.

Loyer and Straccia [16], inspired by van Gelder’s alternating fixpoint approach [36], define the well-founded semantics (therein called compromise semantics) for normal logic programs in a parametric IB framework. For classical Datalog programs with negation, the proposed semantics is identical to the well-founded semantics [10].

Another approach to defining the semantics of normal logic programs is based on the notion of a bilattice [17,18]. A bilattice is a structure $〈\mathcal{B},{⪯}_t,{⪯}_k〉$, where $\mathcal{B}$ is a non-empty truth set, ${⪯}_t$ and ${⪯}_k$ are the truth order and knowledge order, respectively. If $x{⪯}_{k}y$ and $x{⪯}_{t}y$, then y represents “more information” and “more truth”, respectively, than x. Each bilattice has a negation ¬, which reverses the ${⪯}_t$ ordering, leaves unchanged the ${⪯}_k$, and verifies $\neg \neg x=x$. The simplest non-trivial bilattice, called $\mathcal{FOUR}$, is due to Belnap, Jr. [37], who introduced a logic intended to handle incomplete and/or inconsistent information. $\mathcal{FOUR}$ illustrates many basic properties of bilattices. In essence, $\mathcal{FOUR}$ expands the classical truth set $\{f,t\}$ to $\{f,t,\perp ,\top \}$, where ⊥ and ⊤ stand for unknown and inconsistent, respectively.

The extension of the notions of a stable model and a well-founded model to the context of bilattices is due to Fitting [19], Fitting [20]. Fitting proposes a binary immediate consequence operator ${\mathrm{\Psi }}_P(I,J)$, which has two input interpretations I and J over a bilattice; the former and the latter are used to assign meaning to positive literals and negative literals, respectively. It is shown that ${\mathrm{\Psi }}_P$ is monotone and, if the de Morgan laws hold, continuous in both arguments under ${⪯}_k$; ${\mathrm{\Psi }}_P$ is monotone and, if the de Morgan laws hold, continuous in the first argument and anti-monotone in the second argument under ${⪯}_t$. After that, fitting follows the idea of the Gelfond–Lifschitz transformation, i.e., fixing the interpretation for negative literals and then computing the least model under ${⪯}_t$ of the resulting positive program. To this end, Fitting further defines the operator ${\mathrm{\Psi }}_P^{\prime }$ which can be computed by iterating ${\mathrm{\Psi }}_P(x,J)$ from the least interpretation under ${⪯}_t$. It is shown that ${\mathrm{\Psi }}_P^{\prime }$ is monotone and, if the de Morgan laws hold, continuous under ${⪯}_k$ and anti-monotone under ${⪯}_t$. Every fixpoint of ${\mathrm{\Psi }}_P^{\prime }$ is a stable model of P. The set of fixpoints of ${\mathrm{\Psi }}_P^{\prime }$ is a complete lattice under ${⪯}_k$. Thus, ${\mathrm{\Psi }}_P^{\prime }$ has a least fixpoint under ${⪯}_k$, which is the well-founded model of P. The well-founded model can be obtained by iterating ${\mathrm{\Psi }}_P^{\prime }$ from the least interpretation under ${⪯}_k$. In this approach, Loyer and Straccia [21,22], within a framework extending parametric deductive databases with uncertainty [25] with negation, propose the approximate well-founded semantics for normal logic programs based on the notion of an approximate interpretation, assigning to an atom A a logical (interval) value [a; b.

Answer set programming (ASP) [38,39,40] is a form of declarative programming oriented towards hard search problems. In addition to rules and facts, ASP programs can have constraints, which are rules with no atom in the head. ASP transforms the stable model semantics into a practical computational methodology and is a formalism for modeling and solving combinatorial optimization problems. Computing stable models is a fundamental automated reasoning task of answer-set solvers [41]. Fuzzy answer set programming (FASP) [42,43] is an expansion of ASP with MVL/FLn/MFL for modeling continuous optimization problems. The truth values associated with atoms and rules are also called their weights. In FASP, which is called core FASP in [44], the weight of each rule is 1. In aggregated FASP [44,45], rules can have a weight other than 1. Cornejo et al. [46] provides a bidirectional translation between core FASP programs and MANLP programs preserving their semantics. This translation allows the expressiveness of MANLP to be combined with the compactness and simplicity of core FASP. Therefore, the existence of stable models of MANLP programs implies that of answer sets of corresponding core FASP programs. Extended MALP (EMALP) [47] is an extension of MANLP where constraints can be included in logic programs. A procedure converting EMALP programs to constraint-free EMALP ones, i.e., MANLP programs, preserving the stable model semantics is also proposed.

In LP and ASP, there is a well-known method to compute the stable model semantics of normal logic programs, called “guess-and-check” [9,48,49]. It consists of two steps: (1) guessing a candidate for a stable model/answer set of a normal logic program and (2) checking whether the candidate is actually a stable model/answer set of the program.

To our knowledge, there is no work on the well-founded semantics of normal logic programs of any FLP framework based on Vojtáš’s FLP, although it is one of the most widely studied kinds of semantics in the literature. Therefore, in this work, we study the well-founded semantics of normal logic programs of FLLP, and it may be adapted for other FLP frameworks. We also adapt the stable model semantics of classical LP to FLLP based on the usual Gelfond–Lifschitz transformation. We then study the relation between the two kinds of semantics. In fact, in the literature, this relation is usually studied using a bilattice setting of the truth domain. However, our truth domains do not possess a complete-knowledge ordering lattice and, thus, do not have a bilattice structure. Hence, we cannot utilize that method. Since the well-founded semantics is closely related to the stable model semantics, the well-founded semantics may help reduce the number of candidates in Step (1) of the above guess-and-check method. That is, the well-founded semantics might help compute stable models more efficiently.

3. Preliminaries

3.1. Linguistic Truth Domains

In hedge algebra (HA) theory [50,51], values of the linguistic variable Truth, for instance, Very True and Very Rather False, can be considered as being generated from a set of atomic terms $\mathcal{G}=\{False,True\}$ using elements from a set of linguistic hedges $\mathcal{H}=\{Very,Rather,\dots \}$ as unary operators. There exists a natural ordering among those values, for example, True <Very True, where $x\le y$ says that x is less than or equal to y in terms of truth. Thus, a value set $\mathcal{X}$ of Truth is a partially ordered set and can be characterized by an HA $\underline{X}=(\mathcal{X},\mathcal{G},\mathcal{H},\le )$.

Hedges either increase or decrease the meaning of terms, and hence they can be regarded as order operators; i.e., for all $x\in \mathcal{X}$ and for all $h\in \mathcal{H}$, we have either $hx\ge x$ or $hx\le x$. It is denoted by $h\le k$ if h modifies terms less than or equal to k; i.e., for all $x\in \mathcal{X}$, either $kx\le hx\le x$ or $x\le hx\le kx$. Since the sets $\mathcal{H}$ and $\mathcal{X}$ are disjoint, we may use the same notation ≤ for different order relations on $\mathcal{H}$ and $\mathcal{X}$. Let V, R, H, S, A, M, $c^{+}$, and $c^{-}$ stand for Very, Rather, Highly, Slightly, Approximately, More or less, True, and False, respectively. We denote $h<k$ if $h\le k$ and $h\ne k$. We have $R<S$ since, e.g., $S{c}^{+}<R{c}^{+}<c^{+}$ and $c^{-}<R{c}^{-}<S{c}^{-}$, and $H<V$ since, e.g., $c^{+}<H{c}^{+}<V{c}^{+}$ and $V{c}^{-}<H{c}^{-}<c^{-}$.

$\mathcal{H}$ can be divided into two disjoint subsets: A set of stressing/intensifying hedges ${\mathcal{H}}^{+}=\{h\mid h{c}^{+}>c^{+}\}=\{h\mid h{c}^{-}<c^{-}\}$ and a set of depressing/weakening hedges ${\mathcal{H}}^{-}=\{h\mid h{c}^{+}<c^{+}\}=\{h\mid h{c}^{-}>c^{-}\}$. For example, the set $\mathcal{H}=\{V,H,A,M,R,S\}$ is split into ${\mathcal{H}}^{+}=\{V,H\}$ and ${\mathcal{H}}^{-}=\{A,M,R,S\}$ since, e.g., $V{c}^{+}>H{c}^{+}>c^{+}$, $c^{+}<A{c}^{+}$ and $c^{+}<M{c}^{+}$. Hedges in each of the sets ${\mathcal{H}}^{+}$ and ${\mathcal{H}}^{-}$ can be either comparable, for example, V and H, or incomparable, for instance, A and M. An HA $\underline{X}=(\mathcal{X},\mathcal{G},\mathcal{H},\le )$ is said to be a linear HA if both sets ${\mathcal{H}}^{+}$ and ${\mathcal{H}}^{-}$ are linearly ordered. For example, the HA $\underline{X}=(\mathcal{X},\mathcal{G},\{V,H,R,S\},\le )$ is a linear HA since in ${\mathcal{H}}^{+}=\{V,H\}$, we have $V>H$, and in ${\mathcal{H}}^{-}=\{R,S\}$, we have $S>R$. For a linear HA $\underline{X}=(\mathcal{X},\mathcal{G},\mathcal{H},\le )$, the truth value set $\mathcal{X}$ is linearly ordered [4]. As shown in [4], in order to adequately define the truth functions of hedge connectives, we restrict ourselves to linear linguistic truth domains.

A linguistic truth domain (LTD) $\overline{X}$ generated from a linear HA $\underline{X}=(\mathcal{X},\mathcal{G},\mathcal{H},\le )$ is the linearly ordered set $\overline{X}=\mathcal{X}\cup \{0,W,1\}$, where 0, W, and 1, respectively, represent Absolutely False, the middle truth value, and Absolutely True. They are the least, the neutral and the greatest elements of $\overline{X}$, respectively, and for all $x\in \{0,W,1\}$ and for all $h\in \mathcal{H}$, we have $hx=x$ [4,7].

In order to adequately define ukasiewicz operations [32], we only consider finite truth domains. An l-limit HA, where l is a positive integer, is a linear HA whose all values have a length of at most $l+1$, i.e., at most, l hedges can be applied to the atomic term. An LTD generated from an l-limit HA is finite [4,7].

Example 1.

The LTD $\overline{X}=\{v_0=0,v_1=V{c}^{-},v_2=H{c}^{-},v_3=c^{-},v_4=R{c}^{-},v_5=S{c}^{-},v_6=W,v_7=S{c}^{+},v_8=R{c}^{+},v_9=c^{+},v_{10}=H{c}^{+},v_{11}=V{c}^{+},v_{12}=1\}$ is generated from the 1-limit HA $\underline{X}=(\mathcal{X},\{c^{-},c^{+}\},\{V,H,R,S\},\le )$, where truth values are listed in ascending order.

3.2. Truth Functions of Hedge Connectives

Let the identity hedge $I\notin \mathcal{H}$ be defined by for all $x\in \mathcal{X}$, $Ix=x$. It can be seen that I is the least element in both sets ${\mathcal{H}}^{+}\cup \left\{I\right\}$ and ${\mathcal{H}}^{-}\cup \left\{I\right\}$ [4,7].

An extended order relation ${\le }_e$ on $\mathcal{H}\cup \left\{I\right\}$ is defined as follows: for all $h,k\in \mathcal{H}\cup \left\{I\right\}$, $h{\le }_{e}k$ if one of the following conditions holds:

(i) $h\in {\mathcal{H}}^{-},k\in {\mathcal{H}}^{+}$;

(ii) $h,k\in {\mathcal{H}}^{+}\cup \left\{I\right\}$ and $h\le k$;

(iii) $h,k\in {\mathcal{H}}^{-}\cup \left\{I\right\}$ and $h\ge k$.

It is denoted by $h{<}_{e}k$ if $h{\le }_{e}k$ and $h\ne k$.

Let $\underline{X}=(\mathcal{X},\{c^{+},c^{-}\},\mathcal{H},\le )$ be a linear HA. For every hedge $h\in \mathcal{H}\cup \left\{I\right\}$, its truth function, a mapping from $\overline{X}$ to $\overline{X}$, is denoted by $h^{•}$. For all $h,k\in \mathcal{H}\cup \left\{I\right\}$, their truth functions satisfy the following conditions [7,52,53]:

$$\begin{array}{c}\hfill \forall x,y\in \overline{X},if x\ge y,h^{•}\left(x\right)\ge h^{•}\left(y\right)\end{array}$$

(4)

$$\begin{array}{c}\hfill \forall x\in \overline{X},ifh{\le }_{e}k,h^{•}\left(x\right)\ge k^{•}\left(x\right)\end{array}$$

(5)

$$\begin{array}{c}\hfill \forall x\in \{0,W,1\},h^{•}\left(x\right)=x\end{array}$$

(6)

$$\begin{array}{c}\hfill \forall x\in \overline{X},I^{•}\left(x\right)=x\end{array}$$

(7)

$$\begin{array}{c}\hfill h^{•}\left(h{c}^{+}\right)=c^{+}\end{array}$$

(8)

Every truth function of a hedge is non-decreasing and preserves 0 and 1. Furthermore, a truth function of a stressing hedge $h\in {\mathcal{H}}^{+}$ is subdiagonal (i.e., $h^{•}\left(x\right)\le x$), and that of a depressing hedge $h\in {\mathcal{H}}^{-}$ is superdiagonal (i.e., $h^{•}\left(x\right)\ge x$) [52]. According to Condition (8), if the truth value of “Lucia is young” is very true, that of “Lucia is very young” is true [54,55,56]. In [4], it is shown that truth functions of hedges always exist.

Example 2.

Consider the 1-limit HA in Example 1 and its LTD. An example of truth functions of hedges on the LTD is given in

Table 1. Truth functions of hedge connectives.

	${\mathit{V}}^{•}$	${\mathit{H}}^{•}$	${\mathit{R}}^{•}$	${\mathit{S}}^{•}$
0	0	0	0	0
$V{c}^{-}$	$V{c}^{-}$	$V{c}^{-}$	$H{c}^{-}$	$c^{-}$
$H{c}^{-}$	$V{c}^{-}$	$H{c}^{-}$	$c^{-}$	$R{c}^{-}$
$c^{-}$	$V{c}^{-}$	$H{c}^{-}$	$R{c}^{-}$	$S{c}^{-}$
$R{c}^{-}$	$H{c}^{-}$	$c^{-}$	$R{c}^{-}$	$S{c}^{-}$
$S{c}^{-}$	$c^{-}$	$R{c}^{-}$	$S{c}^{-}$	$S{c}^{-}$
W	W	W	W	W
$S{c}^{+}$	$S{c}^{+}$	$S{c}^{+}$	$R{c}^{+}$	$c^{+}$
$R{c}^{+}$	$S{c}^{+}$	$R{c}^{+}$	$c^{+}$	$H{c}^{+}$
$c^{+}$	$S{c}^{+}$	$R{c}^{+}$	$H{c}^{+}$	$V{c}^{+}$
$H{c}^{+}$	$R{c}^{+}$	$c^{+}$	$H{c}^{+}$	$V{c}^{+}$
$V{c}^{+}$	$c^{+}$	$H{c}^{+}$	$V{c}^{+}$	$V{c}^{+}$
1	1	1	1	1

, where the value of a truth function $h^{•}$, occurring in the first row, of a value x, occurring in the first column, is in the corresponding cell. For instance, $H^{•}\left(V{c}^{+}\right)=H{c}^{+}$ and $R^{•}\left(V{c}^{-}\right)=H{c}^{-}$. Below, we utilize the LTD, and these truth functions of hedges for our examples.

3.3. Operations on Linguistic Truth Domains

In MVL/FLn/MFL [32,57,58], there are three prominent sets of connectives called Łukasiewicz, Gödel, and product logic ones. Each of the sets has a pair of a continuous t-norm and its residuum. Since our truth values are linguistic, we cannot use the product logic connectives.

On an LTD $\overline{X}=\{v_0,\dots ,v_n\}$ with $v_0\le v_1\le \dots \le v_n$, Gödel t-norm, its residuum, and t-conorm can be, respectively, defined as follows [4,7]:

$$\begin{array}{ccc}\hfill {\mathcal{C}}_G(v_i,v_j)& =& min(v_i,v_j),\hfill \\ \hfill {\leftarrow }_G^{•}(v_j,v_i)& =& \left\{\begin{array}{cc}{v}_n\hfill & \mathrm{if}i\le j\hfill \\ v_j\hfill & \mathrm{otherwise},\hfill \end{array}\right.\hfill \\ \hfill {\vee }_G^{•}(v_i,v_j)& =& max(v_i,v_j).\hfill \end{array}$$

Łukasiewicz t-norm, its residuum, and t-conorm can be, respectively, defined by [4,7]:

$$\begin{array}{ccc}\hfill {\mathcal{C}}_L(v_i,v_j)& =& \left\{\begin{array}{cc}{v}_{i+j-n}\hfill & \mathrm{if} i+j-n>0\hfill \\ v_0\hfill & \mathrm{otherwise},\hfill \end{array}\right.\hfill \\ \hfill {\leftarrow }_L^{•}(v_j,v_i)& =& \left\{\begin{array}{cc}{v}_n\hfill & \mathrm{if} i\le j\hfill \\ v_{n+j-i}\hfill & \mathrm{otherwise},\hfill \end{array}\right.\hfill \\ \hfill {\vee }_L^{•}(v_i,v_j)& =& \left\{\begin{array}{cc}{v}_{i+j}\hfill & \mathrm{if} i+j<n\hfill \\ v_n\hfill & \mathrm{otherwise}.\hfill \end{array}\right.\hfill \end{array}$$

The residua are non-decreasing in the first argument, but non-increasing in the second. The other operations are non-decreasing in all arguments.

Every pair of a t-norm $\mathcal{C}$ and its residuum ${\leftarrow }^{•}$ satisfy the following properties [32], for truth values $b,r$, and h (standing for body, rule and head, respectively):

$$\begin{array}{c}\hfill \mathcal{C}(b,r)\le h \mathrm{iff} r\le {\leftarrow }^{•}(h,b)\end{array}$$

(9)

$$\begin{array}{c}\hfill (\forall b)(\forall h)\mathcal{C}(b,{\leftarrow }^{•}(h,b))\le h\end{array}$$

(10)

$$\begin{array}{c}\hfill (\forall b)(\forall r){\leftarrow }^{•}(\mathcal{C}(b,r),b)\ge r\end{array}$$

(11)

The negation of a truth value x, denoted by $-x$, is defined as follows: if $x=\sigma c$, where $\sigma$ is a string of hedges (including the empty one) and $c\in \{c^{+},c^{-}\}$, then $-x=\sigma c^{\prime }$ where $\{c,c^{\prime }\}$ = $\{c^{+},c^{-}\}$; and $-1=0$, $-0=1$, and $-W=W$. For instance, $-V{c}^{-}=V{c}^{+}$ and $-V{c}^{+}=V{c}^{-}$. The negation is decreasing and satisfies $--x=x$.

In [6], it is shown that the LOWA (Linguistic Ordered Weighted Averaging) operator [59], one of the most well-known linguistic aggregation operators that can directly compute with linguistic labels, can be used in body formulas of FLLP. Aggregation operators are very useful since they let us describe increased fulfillment of user requirements. A conjunction is one extreme case in which one desires that all the criteria be satisfied, and a disjunction is the other extreme in which the satisfaction of any of the criteria is all one needs. The LOWA operator is developed based on the ordered weighted averaging (OWA) operator [60] and the convex combination of linguistic labels [61].

Definition 1

(LOWA operator, [59]). Let $S=\{s_1,\dots ,s_m\}$ be a set of linguistic terms to be aggregated, the LOWA operator ${@}^{•}(s_1,\dots ,s_m)=C^m\{w_k,t_k,k=1\dots m\}$ is defined inductively as follows.

For $m=2$,

$$C^2\{\{w_1,1-w_1\},\{t_1,t_2\}\}=(w_1\odot v_j)\oplus ((1-w_1)\odot v_i)=v_k$$

where $t_1=v_j,t_2=v_i\in \overline{X},j\ge i$, and $k=min\{n,i+round(w_1.(j-i))\}$, in which $n+1$ is the cardinality of $\overline{X}$ and round(.) is the usual round operation.

For $m>2$,

$$C^m\{w_k,t_k,k=1\dots m\}=C^2\{\{w_1,1-w_1\},\{t_1,C^{m-1}\{{\eta }_h,t_h,h=2\dots m\}\}\}$$

where $W=[w_1,\dots ,w_m]$ is a weighting vector associated with S such that (i) $w_i\in [0,1]$, and (ii) ${\sum }_{i=1}^m{w}_i=1$; $T=[t_1,\dots ,t_m]$ is a vector such that $t_i$ is the ith largest element in the collection $s_1,\dots ,s_m$; ${\eta }_h=w_h/{\sum }_2^m{w}_k,h=2,\dots ,m$.

It can be seen that the LOWA operator is not well defined for the case $m>2$ and ${\sum }_{k=k_0}^m{w}_k=0$, for $k_0\le m-1$.

A natural question arising is how to acquire the associated weighting vector. An interesting method to compute the weights of the OWA operator using linguistic quantifiers is proposed by Yager [60]. More concretely, if Q is a relative or proportional quantifier such as “Most”, Q can be represented by a fuzzy subset of $[0,1]$ such that for each $r\in [0,1]$, $Q\left(r\right)$ states the degree to which r portion of objects satisfies the concept denoted by Q. Then, the weights can be computed by:

$$w_i=Q(i/n)-Q((i-1)/n),i=1,\dots ,n$$

The membership function of such a quantifier Q can be:

$$Q\left(r\right)=\left\{\begin{array}{cc}0\hfill & \mathrm{if} 0\le r<a\hfill \\ \frac{r-a}{b-a}\hfill & \mathrm{if} a\le r\le b\hfill \\ 1\hfill & \mathrm{if} 1\ge r>b\hfill \end{array}\right.$$

where $0\le a\le b\le 1$.

Due to the non-decreasing nature of Q, it follows that $w_i\ge 0$. Moreover, since $Q\left(1\right)=1$ and $Q\left(0\right)=0$, we have ${\sum }_{i=1}^n{w}_i=1$. The use of those quantifiers to compute the weighting vector of the LOWA operator essentially implies that the more criteria are satisfied, the better the solution is.

The LOWA operator has the following properties [59]: (i) it is commutative, i.e., ${@}^{•}(s_1,\dots ,s_m)={@}^{•}(\pi \left(s_1\right),\dots ,\pi \left(s_m\right))$, where $\pi$ is a permutation over the set of arguments; (ii) it is non-decreasing in all arguments, i.e., given $S=[s_1,\dots ,s_m]$ and $T=[t_1,\dots ,t_m]$ being two vectors such that for all $i,s_i\ge t_i$, we have ${@}^{•}\left(S\right)\ge {@}^{•}\left(T\right)$; and (iii) it is an or–and operator, i.e., $min\left(s_i\right)\le {@}^{•}(s_1,\dots ,s_m)\le max\left(s_i\right)$.

Since in all the proofs of the results in [4], we only require that truth functions of connectives in body formulas (other than negation) be non-decreasing in all arguments, allowing body formulas to be built using a LOWA operator does not affect any results.

Example 3.

If the quantifier “Most” with a = 0.3 and b = 0.8 is used to generate weighting vectors for the LOWA operator, the weighting vector of dimension 3 is $[w_1=1/15,w_2=2/3,w_3=4/15]$. We have the following:

$$\begin{array}{ccc}\hfill {@}^{•}(R{c}^{+},S{c}^{+},H{c}^{+})& =& {@}^{•}(v_8,v_7,v_{10})=v_8=R{c}^{+}\hfill \end{array}$$

3.4. Fuzzy Linguistic Logic Programming without Negation

The language is a many-sorted (or typed) predicate language without function symbols. Clauses are without negation. With no function symbols, Herbrand universes of all sorts of variables of a finite logic program are finite, and so is its Herbrand base. Together with a finite LTD, this allows us to obtain the least Herbrand model of logic programs by finitely iterating the immediate consequence operator from the least Herbrand interpretation [4]. Also, the least Herbrand model of a logic program can be obtained using finitely terminating tabulation proof procedures [7]. The underlying language of a program is assumed to be defined by constants and predicate symbols occurring in it (if no constants exist, some constant a is added to form ground terms).

Connectives are composed of the following: ${\wedge }_G,{\vee }_G,{\leftarrow }_G$ (Gödel conjunction, disjunction, and implication); ${\wedge }_L,{\vee }_L,{\leftarrow }_L$ (Łukasiewicz conjunction, disjunction, and implication); ${@}_i$ (aggregations whose truth functions are the LOWA operator with a specific weighting vector, and thus, we can have many distinct aggregation operators with different weighting vectors); and hedges as unary connectives. The truth function of a connective c is denoted by $c^{•}$.

A term is either a constant or a variable. An atom is of the form $p(t_1,...,t_n)$, where p is an n-ary predicate symbol, and $t_1,...,t_n$ are terms. A fact is a graded atom ($A.a$), where the atom A and the truth value a (different from 0) are the logical part and the truth value of the fact, respectively. A body formula is defined inductively as follows: (i) an atom is a body formula; (ii) if c is a connective with arity n other than the implications, and $B_i,i=\overline{1,n}$, are body formulas, so is $c(B_1,B_2,\dots ,B_n)$. A rule is a graded implication $(A\leftarrow B.r)$, where the atom A is called a rule head, the body formula B is called a rule body, r is the truth value (different from 0), and $(A\leftarrow B)$ is called the logical part of the rule. In every graded formula $(\phi .t)$, the truth value t is understood as a lower bound to the exact truth value of $\phi$.

A fuzzy linguistic logic program (also called a positive program) is a finite set of rules and facts, and there are no two rules (facts) with the same logical part but different truth values. Hence, a program P can be represented as a partial mapping:

$$P:Formulas\to \overline{X}\backslash \left\{0\right\},$$

where the domain of P, denoted $dom\left(P\right)$, is finite and consists only of logical parts of facts and rules. For any rule or fact $(\phi .t)\in P$, $P\left(\phi \right)=t$. A fuzzy linguistic Herbrand interpretation (interpretation, for short) f of P is a mapping from the Herbrand base $B_P$ to $\overline{X}$, assigning to every ground atom a truth value.

The ordering ≤ in $\overline{X}$ is expanded to interpretations as follows: for all interpretations $f_1$ and $f_2$ of a program P, $f_1⊑f_2$ if for all $A\in B_P$, $f_1\left(A\right)\le f_2\left(A\right)$. The meet (infimum, greatest lower bound) and join (supremum, least upper bound) operators of interpretations are denoted by ⊗ and ⊕, respectively; for all interpretations $f_1,f_2$ and atoms A, we have: (i) $(f_1\otimes f_2)\left(A\right)=f_1\left(A\right)\otimes f_2\left(A\right)$, and (ii) $(f_1\oplus f_2)\left(A\right)=f_1\left(A\right)\oplus f_2\left(A\right)$ [6].

An interpretation f is extended to all ground formulas, denoted by $\overline{f}$, as follows: (i) $\overline{f}\left(A\right)=f\left(A\right)$, if A is a ground atom; (ii) $\overline{f}\left(c(B_1,B_2,\dots ,B_n)\right)=c^{•}(\overline{f}\left(B_1\right),\overline{f}\left(B_2\right),\dots ,\overline{f}\left(B_n\right))$, where $B_i,i=\overline{1,n}$, are ground formulas, and c is a connective with arity n. For non-ground formulas, since all variables in formulas are assumed to be universally quantified, $\overline{f}\left(\phi \right)=\overline{f}(\forall \phi )=\otimes \{\overline{f}\left(\phi \vartheta \right)\mid \phi \vartheta isagroundinstanceof\phi \}$, where $\forall \phi$ denotes the universal closure of $\phi$, which is obtained from $\phi$ by adding a universal quantifier for every variable with a free occurrence in $\phi$.

Let P be a program. An interpretation f is a Herbrand model (model, for short) of a rule/fact $(\phi .t)\in P$ if $\overline{f}\left(\phi \right)\ge P\left(\phi \right)=t$; and f is a model of P if f is a model of all formulas $(\phi .t)\in P$.

Theorem 1

([6]). Let P be a positive program.

(i) Let ${\mathcal{F}}_P$ be the set of all interpretations of P. Then ${\mathcal{F}}_P$ is non-empty, and $〈{\mathcal{F}}_P,\otimes ,\oplus 〉$ is a complete lattice.

(ii) Let F be a non-empty set of models of P. Then $\otimes F$ is a model of P.

(iii) $M_P=\otimes \{f\mid f$ is a model of $P\}$ is the least model of P.

Definition 2

(Immediate consequence operator). Let P be a positive program. The operator $T_P$, mapping from interpretations to interpretations, is defined as follows: for an interpretation f and a ground atom $A\in B_P$.

$T_P\left(f\right)\left(A\right)=max\{\oplus \{{\mathcal{C}}_i(\overline{f}\left(B\right),r)\mid (A{\leftarrow }_{i}B.r)$ is a ground instance of a rule in $P\}$, $\oplus \{a\mid (A.a)$ is a ground instance of a fact in $P\left\}\right\}$.

Since the Herbrand base $B_P$ is finite, for each $A\in B_P$, there are a finite number of ground instances of logical parts of facts and rule heads that match A. Hence, both ⊕ operators in the definition of $T_P$ are, in fact, maxima.

Theorem 2

([4]). Let P be a positive program. Then $T_P$ is non-decreasing and continuous.

A model of a positive program P is a pre-fixpoint of $T_P$ [62] and vice versa.

Theorem 3

([4]). An interpretation f is a model of a positive program P iff $T_P\left(f\right)⊑f$.

The bottom-up iteration of $T_P$ is defined as:

$$T_P^k(\perp )=\left\{\begin{array}{cc}\perp \hfill & \mathrm{if} k=0\hfill \\ T_P\left(T_P^{k-1}(\perp )\right)\hfill & \mathrm{if} k \mathrm{is} \mathrm{a} \mathrm{successor} \mathrm{ordinal}\hfill \\ \oplus \{T_P^n(\perp )\mid n<k\}\hfill & \mathrm{if} k \mathrm{is} \mathrm{a} \mathrm{limit} \mathrm{ordinal},\hfill \end{array}\right.$$

where ⊥ denotes the least interpretation mapping each ground atom to 0. The bottom-up iteration of $T_P$ is denoted by $T_P^{\infty }(\perp )$. The top-down iteration of $T_P$ is defined similarly and denoted by $T_P^{\infty }(\top )$, where ⊤ is the greatest interpretation mapping each ground atom to 1.

The least model $M_P$ is exactly the least fixpoint of $T_P$, denoted $lfp\left(T_P\right)$, and can be obtained by finitely bottom-up iterating $T_P$ as follows.

Theorem 4

([4]). Let P be a positive program. Then there exists a finite number α such that $n\ge \alpha$ implies $T_P^n(\perp )=lfp\left(T_P\right)=M_P=T_P^{\infty }(\perp )$.

Analogously, the top-down iteration of $T_P$, $T_P^{\infty }(\top )$, can also be finitely obtained.

Example 4.

Assume the following piece of knowledge:

(a) (A car is good if it is rather reliable and consumes very little fuel) is very true;

(b) (A car is good if it is expensive) is rather true;

(c) (A car is safe if it is reliable) is very true;

(d) (A car is reliable if it is safe) is highly true;

(e) (A Toyota Corolla is safe) is rather true;

(f) (A Toyota Corolla is reliable) is true;

(g) (A Toyota Corolla consumes little fuel) is very true;

(h) (A Toyota Corolla is expensive) is slightly true.

The knowledge piece can be represented by the program below:

$$\begin{array}{cc}\hfill (\mathit{gd}\left(X\right){\leftarrow }_G{\wedge }_G(R\mathit{rl}\left(X\right),V\mathit{lf}\left(X\right)).V{c}^{+})& \left(r1\right)\\ \hfill (\mathit{gd}\left(X\right){\leftarrow }_L\mathit{ep}\left(X\right).R{c}^{+})& \left(r2\right)\\ \hfill (\mathit{sf}\left(X\right){\leftarrow }_G\mathit{rl}\left(X\right).V{c}^{+})& \left(r3\right)\\ \hfill (\mathit{rl}\left(X\right){\leftarrow }_G\mathit{sf}\left(X\right).H{c}^{+})& \left(r4\right)\\ \hfill (\mathit{sf}\left(cor\right).R{c}^{+})& \left(f1\right)\\ \hfill (\mathit{rl}\left(cor\right).c^{+})& \left(f2\right)\\ \hfill (\mathit{lf}\left(cor\right).V{c}^{+})& \left(f3\right)\\ \hfill (\mathit{ep}\left(cor\right).S{c}^{+})& \left(f4\right)\end{array}$$

where gd, rl, lf, ep, sf, and cor stand for good, reliable, little fuel, expensive, safe, and Toyota Corolla, respectively. Note that the program is recursive.

The bottom-up iteration of $T_P$ is as follows:

$$\begin{array}{c}\hfill T_P(\perp )=\{(\mathit{gd}\left(cor\right),0),(\mathit{sf}\left(cor\right),R{c}^{+}),(\mathit{rl}\left(cor\right),c^{+}),(\mathit{lf}\left(cor\right),V{c}^{+}),(\mathit{ep}\left(cor\right),S{c}^{+})\}\\ \hfill T_P^2(\perp )=\{(\mathit{gd}\left(cor\right),c^{+}),(\mathit{sf}\left(cor\right),c^{+}),(\mathit{rl}\left(cor\right),c^{+}),(\mathit{lf}\left(cor\right),V{c}^{+}),(\mathit{ep}\left(cor\right),S{c}^{+})\}\\ \hfill T_P^3(\perp )=\{(\mathit{gd}\left(cor\right),c^{+}),(\mathit{sf}\left(cor\right),c^{+}),(\mathit{rl}\left(cor\right),c^{+}),(\mathit{lf}\left(cor\right),V{c}^{+}),(\mathit{ep}\left(cor\right),S{c}^{+})\}\end{array}$$

Since $T_P^2(\perp )$ coincides with $T_P^3(\perp )$, it is also the least model of P.

4. Normal Fuzzy Linguistic Logic Programs and Their Semantics

FLLP is extended by permitting negative literals to appear in rule bodies, resulting in normal fuzzy linguistic logic programs (also called normal programs). An extended positive program is a positive program where elements of the truth domain can occur in the places of atoms in rule bodies, and the value of such an element in all interpretations is itself.

The notions of an interpretation, a model, and the immediate consequence operator $T_P$ of an extended positive/normal program P are defined the same as those of a positive program.

4.1. The Stable Model Semantics of Normal Programs

Results in this subsection are presented in our preliminary paper [63]. We refer the reader to that paper for detailed proofs of the theorems in this subsection.

The stable model semantics of normal programs is generalized from that of classical normal logic programs based on the usual Gelfond–Lifschitz transformation [11]. Let P be a normal program, and $P^{*}$ denote the program consisting of all ground instances of rules and facts in P. Given an interpretation J of P, the reduct P^J of P w.r.t. J is the extended positive program obtained by substituting in $P^{*}$ all negative literals with their values w.r.t. J, computed as $\overline{J}(\neg A)=-J\left(A\right)$ for all ground atoms A.

Definition 3

(Stable model). Let P be a normal program and I an interpretation of P. Then I is a stable model of P if $I=I^{\prime }$, where $I^{\prime }$ is the least model of the reduct $P^I$.

The stable model semantics of a normal program is a whole family of its stable models.

Theorem 5

([63]). A stable model of a normal program is its model.

A normal program may have more than one stable model.

Example 5.

Given the LTD in Example 1, consider a program P composed of the rules below:

$$\begin{array}{ccc}\hfill \left(good\right(X)& {\leftarrow }_G& \neg bad\left(X\right).V{c}^{+})\hfill \\ \hfill \left(bad\right(X)& {\leftarrow }_G& \neg good\left(X\right).V{c}^{+})\hfill \end{array}$$

We determine its stable models. Given an interpretation $I=\left\{\right(good\left(a\right),x),(bad\left(a\right),y\left)\right\}$ of P, in which the constant a is added to form ground terms, the reduct $P^I$ is composed of the rules below:

$$\begin{array}{ccc}\hfill \left(good\right(a)& {\leftarrow }_G& -y.V{c}^{+})\hfill \\ \hfill \left(bad\right(a)& {\leftarrow }_G& -x.V{c}^{+})\hfill \end{array}$$

The least model of $P^I$ is $M_{P^I}=\{(good\left(a\right),{\mathcal{C}}_G(-y,V{c}^{+})),(bad\left(a\right),{\mathcal{C}}_G(-x,V{c}^{+}))\}$. Hence, I is a stable model of P if $x={\mathcal{C}}_G(-y,V{c}^{+})=min(-y,V{c}^{+})$ and $y={\mathcal{C}}_G(-x,V{c}^{+})=min(-x,V{c}^{+})$. It can easily be seen that all $V{c}^{-}\le x=-y\le V{c}^{+}$ (so $V{c}^{-}\le y=-x\le V{c}^{+}$) satisfy the equations. Thus, there are 11 stable models $\left\{\right(good\left(a\right),x),(bad\left(a\right),-x\left)\right\}$ where $v_1=V{c}^{-}\le x\le V{c}^{+}=v_{11}$. These stable models are minimal models, and the program does not have a least stable model.

Theorem 6

([63]). A stable model of a normal program is its minimal model.

Theorem 3 also holds for normal programs.

Theorem 7

([63]). An interpretation f is a model of a normal program P iff $T_P\left(f\right)⊑f$.

Example 6.

Consider a normal program P composed of the rule:

$$(good\left(X\right){\leftarrow }_G\neg bad\left(X\right).1)$$

Given an interpretation $I=\left\{\right(good\left(a\right),x),(bad\left(a\right),y\left)\right\}$ with x and y being truth values, $T_P\left(I\right)=\{(good\left(a\right),-y),(bad\left(a\right),0)\}$. Obviously, $T_P\left(I\right)$ is not non-decreasing.

Since for a normal program P, $T_P$ may not be non-decreasing, $T_P$ does not necessarily have a least fixpoint.

Theorem 8

([63]). A stable model of a normal program P is a minimal fixpoint of $T_P$.

For a normal program P, $T_P$ may have many minimal fixpoints, and a minimal fixpoint of $T_P$ might not be a stable model of P.

Example 7.

Consider a normal program P composed of the rules below:

$$\begin{array}{ccc}\hfill \left(good\right(X)& {\leftarrow }_G& good\left(X\right).1)\hfill \\ \hfill \left(bad\right(X)& {\leftarrow }_G& \neg good\left(X\right).1)\hfill \end{array}$$

First, we determine its stable models. Given an interpretation $I=\left\{\right(good\left(a\right),x),(bad\left(a\right),y\left)\right\}$ of P, the reduct $P^I$ is the following:

$$\begin{array}{ccc}\hfill \left(good\right(a)& {\leftarrow }_G& good\left(a\right).1)\hfill \\ \hfill \left(bad\right(a)& {\leftarrow }_G& -x.1)\hfill \end{array}$$

The least model of $P^I$ is $M_{P^I}=\{(good\left(a\right),0),(bad\left(a\right),-x)\}$. Hence, I is a stable model of P if $I=M_{P^I}$, i.e., $I=\left\{\right(good\left(a\right),0),(bad\left(a\right),1\left)\right\}$.

Second, we determine fixpoints of $T_P$. Given an interpretation

$$\begin{array}{c}\hfill I=\left\{\right(good\left(a\right),x),(bad\left(a\right),y\left)\right\},\end{array}$$

we have $T_P\left(I\right)=\{(good\left(a\right),x),(bad\left(a\right),-x)\}$. Thus, I is a fixpoint of $T_P$ if for any truth value x, $I=\left\{\right(good\left(a\right),x),(bad\left(a\right),-x\left)\right\}$. It can be observed that all these fixpoints are minimal, but only $\left\{\right(good\left(a\right),0),(bad\left(a\right),1\left)\right\}$ is a stable model.

Moreover, for a normal program P, the bottom–up iteration of $T_P$ might not reach any of its stable models.

Example 8.

Consider the program P in Example 5:

$$\begin{array}{ccc}\hfill \left(good\right(X)& {\leftarrow }_G& \neg bad\left(X\right).V{c}^{+})\hfill \\ \hfill \left(bad\right(X)& {\leftarrow }_G& \neg good\left(X\right).V{c}^{+})\hfill \end{array}$$

It has 11 stable models $I=\left\{\right(good\left(a\right),x),(bad\left(a\right),-x\left)\right\}$, where $v_1=V{c}^{-}\le x\le V{c}^{+}=v_{11}$, but the bottom-up iteration of $T_P$ does not converge to a fixpoint as follows.

$$\begin{array}{ccc}\hfill T_P(\perp )& =& \{(good\left(a\right),V{c}^{+}),(bad\left(a\right),V{c}^{+})\}\hfill \\ \hfill T_P^2(\perp )& =& \{(good\left(a\right),V{c}^{-}),(bad\left(a\right),V{c}^{-})\}\hfill \\ \hfill T_P^3(\perp )& =& \{(good\left(a\right),V{c}^{+}),(bad\left(a\right),V{c}^{+})\}\hfill \\ \hfill \dots \end{array}$$

Therefore, the operator $T_P$ might not help compute any stable model.

4.2. The Well-Founded Semantics of Normal Programs

In this subsection, we define the well-founded semantics of a normal program based on the ideas in [16,36].

To ease the presentation below, we first define a binary immediate consequence operator $T_P(I,J)$ for a normal program P as an extension of the unary one, in which the interpretations I and J are utilized to assign truth values to positive literals and negative literals, respectively. Since the original $T_P(.)$ and the binary $T_P(.,.)$ are different in arity, by providing all the arguments, we can use the same notation $T_P$ for both of them without confusion.

Definition 4

(Binary immediate consequence operator). Let P be a normal program and ${\mathcal{F}}_P$ the set of all interpretations of P. The operator $T_P(.,.)$ mapping from ${\mathcal{F}}_P\times {\mathcal{F}}_P$ to ${\mathcal{F}}_P$ is defined as follows: for every pair of interpretations $(I,J)$ and each ground atom $A\in B_P$, $T_P(I,J)\left(A\right)=T_{P^J}\left(I\right)\left(A\right)$.

Note that if both a positive literal A and the negative one $\neg A$ simultaneously occur in the program, I and J independently assign truth values to them.

Theorem 9.

The binary $T_P$ is

(i) non-decreasing in the first argument and

(ii) non-increasing in the second.

Proof. 

(i) If we fix an interpretation J for negative literals in P, then by definition, the reduct $P^J$ is an extended positive program. By Theorem 2, $T_{P^J}\left(I\right)$ is non-decreasing, and so is $T_P(I,J)$.

(ii) Given an interpretation I for positive literals and two interpretations $J_1$ and $J_2$ for negative literals in P such that $J_1⊑J_2$, we will prove that $T_P(I,J_2)⊑T_P(I,J_1)$.

Let $(A\leftarrow B[B_1,\dots ,B_m,\neg B_{m+1},\dots ,\neg B_n].r)$ be any rule in P. For each of its ground instances $(A\vartheta \leftarrow B[B_1\vartheta ,\dots ,B_m\vartheta ,\neg B_{m+1}\vartheta ,\dots ,\neg B_n\vartheta ].r)$ in $P^{*}$, the counterpart rules in $P^{J_1}$ and $P^{J_2}$ are, respectively:

$$(A\vartheta \leftarrow B[B_1\vartheta ,\dots ,B_m\vartheta ,-J_1\left(B_{m+1}\vartheta \right),\dots ,-J_1\left(B_n\vartheta \right)].r)$$

and

$$(A\vartheta \leftarrow B[B_1\vartheta ,\dots ,B_m\vartheta ,-J_2\left(B_{m+1}\vartheta \right),\dots ,-J_2\left(B_n\vartheta \right)].r).$$

Since $J_1⊑J_2$, for all $m+1\le i\le n$, $-J_1\left(B_i\vartheta \right)\ge -J_2\left(B_i\vartheta \right)$. Hence, we have:

$$\begin{array}{ccc}& & \mathcal{C}(\overline{I}\left(B[B_1\vartheta ,\dots ,B_m\vartheta ,-J_1\left(B_{m+1}\vartheta \right),\dots ,-J_1\left(B_n\vartheta \right)]\right),r)\hfill \\ & =& \mathcal{C}(\mathcal{B}(I\left(B_1\vartheta \right),\dots ,B_m\vartheta ,-J_1\left(B_{m+1}\vartheta \right),\dots ,-J_1\left(B_n\vartheta \right)),r)\hfill \\ & \ge & \mathcal{C}(\mathcal{B}(I\left(B_1\vartheta \right),\dots ,B_m\vartheta ,-J_2\left(B_{m+1}\vartheta \right),\dots ,-J_2\left(B_n\vartheta \right)),r)\hfill \\ & =& \mathcal{C}(\overline{I}\left(B[B_1\vartheta ,\dots ,B_m\vartheta ,-J_2\left(B_{m+1}\vartheta \right),\dots ,-J_2\left(B_n\vartheta \right)]\right),r)\hfill \end{array}$$

By taking suprema for all the rules, we have:

$$\begin{array}{ccc}& & \oplus \left\{\mathcal{C}(\overline{I}\left(B[B_1\vartheta ,\dots ,B_m\vartheta ,-J_1\left(B_{m+1}\vartheta \right),\dots ,-J_1\left(B_n\vartheta \right)]\right),r)\right\}\hfill \\ & \ge & \oplus \left\{\mathcal{C}(\overline{I}\left(B[B_1\vartheta ,\dots ,B_m\vartheta ,-J_2\left(B_{m+1}\vartheta \right),\dots ,-J_2\left(B_n\vartheta \right)]\right),r)\right\}\hfill \end{array}$$

Moreover, since the fact parts of $P^{J_1}$ and $P^{J_2}$ are the same, by definition, we have

$$\begin{array}{ccc}& & T_P(I,J_1)\left(A\right)\hfill \\ & =& T_{P^{J_1}}\left(I\right)\left(A\right)\hfill \\ & \ge & T_{P^{J_2}}\left(I\right)\left(A\right)\hfill \\ & =& T_P(I,J_2)\left(A\right).\hfill \end{array}$$

Since the rule in P is arbitrary, $T_P(I,J_2)⊑T_P(I,J_1)$. □

Definition 5.

Let P be a normal program. The operator $S_P$ mapping from ${\mathcal{F}}_P$ to ${\mathcal{F}}_P$ is defined as $S_P\left(J\right)=T_{P^J}^{\infty }(\perp )=lfp\left(T_{P^J}\right)$, i.e., $S_P\left(J\right)$ computes the least model of $P^J$.

By definition, a stable model of P is a fixpoint of $S_P$. In addition to using the bottom–up iteration of $T_{P^J}$, $S_P\left(J\right)$ can be computed using tabulation proof procedures in [7], which are finitely terminating.

Theorem 10.

Let P be a normal program. The $S_P$ operator is non-increasing.

Proof. 

Recall that $S_P\left(J\right)=T_{P^J}^{\infty }(\perp )$. Given two interpretations $J_1$ and $J_2$ for negative literals in P such that $J_1⊑J_2$, we will prove by induction on $k\ge 0$ that $T_{P^{J_2}}^k(\perp )⊑T_{P^{J_1}}^k(\perp )$. The base case $k=0$ trivially holds. Suppose $T_{P^{J_2}}^k(\perp )⊑T_{P^{J_1}}^k(\perp )$; we will show that $T_{P^{J_2}}^{k+1}(\perp )⊑T_{P^{J_1}}^{k+1}(\perp )$. We have the following:

$$\begin{array}{ccc}& & T_{P^{J_2}}^{k+1}(\perp )\hfill \\ & =& T_{P^{J_2}}\left(T_{P^{J_2}}^k(\perp )\right)\hfill \\ & ⊑& T_{P^{J_2}}\left(T_{P^{J_1}}^k(\perp )\right),byTheorem\hfill \\ & =& T_P(T_{P^{J_1}}^k(\perp ),J_2),byDefinition\hfill \\ & ⊑& T_P(T_{P^{J_1}}^k(\perp ),J_1),byTheorem\hfill \\ & =& T_{P^{J_1}}\left(T_{P^{J_1}}^k(\perp )\right),byDefinition\hfill \\ & =& T_{P^{J_1}}^{k+1}(\perp )\hfill \end{array}$$

□

The following immediately follows.

Proposition 1.

$S_P\circ S_P$ ($S_P$ composed with $S_P$) is non-decreasing.

Clearly, Item (i) of Theorem 1 also holds for normal programs, as stated in the following proposition.

Proposition 2.

Let P be a normal program and ${\mathcal{F}}_P$ the set of all interpretations of P. Then ${\mathcal{F}}_P$ is non-empty and $〈{\mathcal{F}}_P,⊑〉$ is a complete lattice.

The following results can be derived from the Knaster–Tarski theorem [64].

Proposition 3

([19,65]). Let f be a non-increasing function on a complete lattice with the ordering ≤. Then f has a unique pair of extreme oscillation points, a and b. More precisely, we have the following:

(i) a and b are the least fixpoint and the greatest fixpoint of $f\circ f$, respectively, and $a\le b$;

(ii) $f\left(a\right)=b$ and $f\left(b\right)=a$;

(iii) If $f\left(x\right)=y$ and $f\left(y\right)=x$ then both x and y are between a and b in the lattice ordering.

The following proposition follows immediately from Proposition 3.

Proposition 4.

Let P be a normal program. Then we have:

(i) ${(S_P\circ S_P)}^{\infty }(\perp )$, denoted by $S_P^{\perp }$, is the least fixpoint of $(S_P\circ S_P)$; ${(S_P\circ S_P)}^{\infty }(\top )$, denoted by $S_P^{\top }$, is the greatest fixpoint of $(S_P\circ S_P)$. Thus, $S_P^{\perp }⊑S_P^{\top }$.

(ii) $S_P^{\perp }$ and $S_P^{\top }$ are two extreme oscillation points of $S_P$, i.e., $S_P\left(S_P^{\perp }\right)=S_P^{\top }$ and $S_P\left(S_P^{\top }\right)=S_P^{\perp }$, and for all interpretations $I,J$ such that $I=S_P\left(J\right)$ and $J=S_P\left(I\right)$, we have $S_P^{\perp }⊑I,J⊑S_P^{\top }$.

(iii) If an interpretation I is a stable model of P, i.e., $I=S_P\left(I\right)$, then $S_P^{\perp }⊑I⊑S_P^{\top }$. In particular, if $S_P^{\perp }=S_P^{\top }$, $S_P^{\perp }$ is the only stable model of P.

Therefore, $S_P^{\perp }$ and $S_P^{\top }$ can be seen as a lower-bound approximation and an upper-bound approximation of stable models of P, respectively.

Since given any interpretation J, $S_P\left(J\right)$ can be computed finitely, both $S_P^{\perp }$ and $S_P^{\top }$ can be computed finitely as well.

Example 9.

Given the program P in Example 5, composed of the rules below:

$$\begin{array}{ccc}\hfill \left(good\right(X)& {\leftarrow }_G& \neg bad\left(X\right).V{c}^{+})\hfill \\ \hfill \left(bad\right(X)& {\leftarrow }_G& \neg good\left(X\right).V{c}^{+}),\hfill \end{array}$$

and the interpretation $\perp =\left\{\right(good\left(a\right),0),(bad\left(a\right),0\left)\right\}$, the reduct $P^{\perp }$ is as follows:

$$\begin{array}{ccc}\hfill \left(good\right(a)& {\leftarrow }_G& 1.V{c}^{+})\hfill \\ \hfill \left(bad\right(a)& {\leftarrow }_G& 1.V{c}^{+})\hfill \end{array}$$

The least model of $P^{\perp }$ is $S_P(\perp )=\{(good\left(a\right),V{c}^{+}),(bad\left(a\right),V{c}^{+})\}$. Then the reduct $P^{S_P(\perp )}$ is the following:

$$\begin{array}{ccc}\hfill \left(good\right(a)& {\leftarrow }_G& V{c}^{-}.V{c}^{+})\hfill \\ \hfill \left(bad\right(a)& {\leftarrow }_G& V{c}^{-}.V{c}^{+})\hfill \end{array}$$

The least model of $P^{S_P(\perp )}$ is

$$(S_P\circ S_P)(\perp )=S_P\left(S_P(\perp )\right)=\{(good\left(a\right),V{c}^{-}),(bad\left(a\right),V{c}^{-})\}.$$

Then ${(S_P\circ S_P)}^2(\perp )=\{(good\left(a\right),V{c}^{-}),(bad\left(a\right),V{c}^{-})\}$.

Hence, $S_P^{\perp }={(S_P\circ S_P)}^{\infty }(\perp )=\{(good\left(a\right),V{c}^{-}),(bad\left(a\right),V{c}^{-})\}$, denoted by μ.

Similarly, $S_P^{\top }={(S_P\circ S_P)}^{\infty }(\top )=\{(good\left(a\right),V{c}^{+}),(bad\left(a\right),V{c}^{+})\}$, denoted by ν.

It can be observed that $S_P\left(\mu \right)=\nu$ and $S_P\left(\nu \right)=\mu$.

As shown in Example 5, P has 11 stable models $I=\left\{\right(good\left(a\right),x),(bad\left(a\right),-x\left)\right\}$, where $v_1=V{c}^{-}\le x\le V{c}^{+}=v_{11}$. Obviously, all the stable models lie between μ and ν.

In order to define the well-founded semantics, we first define the notion of a partial interpretation.

Definition 6

(Partial interpretation). Let P be a normal program. A partial interpretation I of P is a partial mapping from $B_P$ to the truth domain.

Note that an interpretation is a partial interpretation. The ground atoms that are assigned a truth value by a partial interpretation I are said to be I-defined, and the other atoms in $B_P$ are I-undefined. If an atom is I-defined, so is its negative literal. Also, if an atom is I-undefined, so is its negative literal. A formula (rule or fact) in P is said to be I-defined if all the literals appearing in it are I-defined. Otherwise, the formula is I-undefined.

Definition 7

(Partial model). Let P be a normal program and I a partial interpretation of P. We say that I is a partial model of a formula $(\varphi .t)\in P^{*}$ if any of the following holds:

(i) ϕ is I-defined and $\overline{I}\left(\varphi \right)\ge t$;

(ii) ϕ is I-undefined.

Moreover, it is said that I is a partial model of P as well as $P^{*}$ if I is a partial model of all formulas in $P^{*}$.

Note that a model is a partial model.

The notion of reduct program can be extended for the case of partial interpretations as follows. Given a partial interpretation J of a normal program P, the partial reduct$P_p^J$ of P w.r.t. J is the extended program obtained by substituting in $P^{*}$ all J-defined negative literals with their values w.r.t. J, and the other literals remain.

Given the partial reduct program $P_p^J$ of a normal program P w.r.t. a partial interpretation J, we denote by $P_I^J$, where I is another partial interpretation of P, the program consisting of all the I-defined rules and facts in $P_p^J$.

Proposition 5.

Let P be a normal program and I a partial interpretation of P. Then I is a partial model of P if I is a model of $P_I^I$.

Proof. 

First, it can be seen that I is a (total) interpretation of $P_I^I$, and thus, $P_I^I$ is an extended positive program. Then, the result follows from the fact that all I-defined formulas $(\varphi .t)\in P^{*}$ have a corresponding formula $({\varphi }^{\prime }.t)\in P_I^I$, where ${\varphi }^{\prime }$ is obtained from $\varphi$ by replacing all negative literals with their values under I, and vice versa, and obviously, $\overline{I}\left(\varphi \right)=\overline{I}\left({\varphi }^{\prime }\right)$. □

As in the alternating fixpoint approach [16,36], $S_P^{\perp }$ and $S_P^{\top }$ in Proposition 4 are an under-estimation and an over-estimation of the semantics of P, respectively. If we consider a (partial) interpretation as a set in which each element consists of a ground atom and its truth value, the well-founded semantics of normal programs can be defined as follows.

Definition 8

(Well-founded semantics). Let P be a normal program. The set $S_P^{\perp }\cap S_P^{\top }$ is denoted by $W_P$. Then $W_P$ is called the well-founded (partial) model of P.

Clearly, all normal programs have a unique well-founded model. Since $S_P^{\perp }$ and $S_P^{\top }$ can be computed finitely, the well-founded model $W_P$ can also be computed finitely.

Theorem 11.

Let P be a normal program. The well-founded model $W_P$ is a partial model of P.

Proof. 

We will show that $W_P$ is a model of the extended positive program $P_{W_P}^{W_P}$. Then by Proposition 5, we obtain the result.

By Definition 5, $S_P\left(S_P^{\perp }\right)$ computes the least model of $P^{S_P^{\perp }}$. On the other hand, by Item (ii) of Proposition 4, we have $S_P\left(S_P^{\perp }\right)=S_P^{\top }$. Therefore, $S_P^{\top }$ is the least model of $P^{S_P^{\perp }}$.

It can be seen that since $W_P$ is a part of the (total) interpretation $S_P^{\perp }$, the program $P_{W_P}^{W_P}$ is a part of the program $P^{S_P^{\perp }}$, which is obtained from $P^{S_P^{\perp }}$ by removing all $W_P$-undefined rules and facts. Since $S_P^{\top }$ is the least model of $P^{S_P^{\perp }}$, $S_P^{\top }$ is also a model of $P_{W_P}^{W_P}$. Since $W_P$ is the projection of $S_P^{\top }$ on the Herbrand base of $P_{W_P}^{W_P}$, $W_P$ is a model of $P_{W_P}^{W_P}$. □

4.3. The Relation between the Stable Semantics and the Well-Founded Semantics

We denote the domain of $W_P$ by $dom\left(W_P\right)$, which is the Herbrand base of $P_{W_P}^{W_P}$.

Theorem 12.

Every stable model of a normal program P contains its well-founded model $W_P$.

Proof. 

Let I be a stable model of P. By Item (iii) of Proposition 4, we have $S_P^{\perp }⊑I⊑S_P^{\top }$. Thus, for every ground atom $A\in dom\left(W_P\right)$, we have $S_P^{\perp }\left(A\right)\le I\left(A\right)\le S_P^{\top }\left(A\right)$. On the other hand, for all $A\in dom\left(W_P\right)$, we have $W_P\left(A\right)=S_P^{\perp }\left(A\right)=S_P^{\top }\left(A\right)$, so $I\left(A\right)=W_P\left(A\right)$. □

Corollary 1.

If the well-founded model of a normal program is total, then it is its unique stable model.

Proof. 

Given a normal program P, since $W_P$ is a total model, we have $S_P^{\perp }=S_P^{\top }$. By Proposition 4, $W_P$ is the only stable model of P. □

Example 10.

Given the LTD in Example 1, consider the normal program P composed of the rules and fact below:

$$\begin{array}{ccc}\hfill \left(good\right(X)& {\leftarrow }_G& good\left(X\right).W)\hfill \\ \hfill \left(bad\right(X)& {\leftarrow }_G& \neg good\left(X\right).W)\hfill \\ & \left(good\right(a).W)\end{array}$$

First, we determine stable models of P. Given an interpretation $I=\left\{\right(good\left(a\right),x),(bad\left(a\right),y\left)\right\}$, the reduct $P^I$ is the following:

$$\begin{array}{ccc}\hfill \left(good\right(a)& {\leftarrow }_G& good\left(a\right).W)\hfill \\ \hfill \left(bad\right(a)& {\leftarrow }_G& -x.W)\hfill \\ & \left(good\right(a).W)\end{array}$$

The least model of $P^I$ is $M_{P^I}=\{(good\left(a\right),W),(bad\left(a\right),min(-x,W))\}$. Hence, I is a stable model of P if $I=M_{P^I}$, i.e., $I=\left\{\right(good\left(a\right),W),(bad\left(a\right),W\left)\right\}$ (note that $-W=W$).

Given $\perp =\left\{\right(good\left(a\right),0),(bad\left(a\right),0\left)\right\}$, $P^{\perp }$ is:

$$\begin{array}{ccc}\hfill \left(good\right(a)& {\leftarrow }_G& good\left(a\right).W)\hfill \\ \hfill \left(bad\right(a)& {\leftarrow }_G& 1.W)\hfill \\ & \left(good\right(a).W)\end{array}$$

It is easy to see that for $n\ge 1$, $S_P^n(\perp )=\{(good\left(a\right),W),(bad\left(a\right),W)\}$. That is,

$$S_P^{\perp }=\{(good\left(a\right),W),(bad\left(a\right),W)\}.$$

Similarly, given $\top =\left\{\right(good\left(a\right),1),(bad\left(a\right),1\left)\right\}$, $P^{\top }$ is the following:

$$\begin{array}{ccc}\hfill \left(good\right(a)& {\leftarrow }_G& good\left(a\right).W)\hfill \\ \hfill \left(bad\right(a)& {\leftarrow }_G& 0.W)\hfill \\ & \left(good\right(a).W)\end{array}$$

and $S_P(\top )=\{(good\left(a\right),W),(bad\left(a\right),0)\}$.

For $n\ge 2$, $S_P^n(\top )=\{(good\left(a\right),W),(bad\left(a\right),W)\}$. That is,

$$S_P^{\top }=\{(good\left(a\right),W),(bad\left(a\right),W)\}.$$

Therefore, $S_P^{\perp }=S_P^{\top }$ and $W_P=\{(good\left(a\right),W),(bad\left(a\right),W)\}$ is the only stable model of P.

However, the converse is not true.

Example 11.

Consider a program P having only the rule:

$$(good\left(a\right){\leftarrow }_G\neg good\left(a\right).1)$$

Given an interpretation $I=\left\{\right(good\left(a\right),x\left)\right\}$, the reduct $P^I$ is

$$(good\left(a\right){\leftarrow }_G-x.1),$$

which has the least model $M_{P^I}=\left\{(good\left(a\right),-x)\right\}$. Thus, I is a stable model if $I=M_{P^I}$, i.e., $x=-x=W$. Therefore, the program has a unique stable model $\left\{\right(good\left(a\right),W\left)\right\}$. On the other hand, it is not difficult to see that $S_P^{\perp }=\left\{(good\left(a\right),0)\right\}$ and $S_P^{\top }=\left\{(good\left(a\right),1)\right\}$, so the well-founded model is $W_P=\varnothing$, and it does not coincide with the unique stable model.

In LP and ASP, there is a well-known method to compute stable models/answer sets of normal programs, called “guess-and-check” [9,48,49]. It consists of two steps: (1) guessing a candidate for a stable model/answer set of a normal logic program, and (2) checking whether the candidate is, in fact, a stable model/answer set of the program. Given a normal program P, since $S_P^{\perp }$ and $S_P^{\top }$ are, respectively, a lower bound and an upper bound of stable models of P, they can be used to reduce the number of candidates for Step (1). Note that for FLLP, both $S_P^{\perp }$ and $S_P^{\top }$ can be computed finitely.

Example 12.

Given the LTD in Example 1, consider a program P composed of the rules below:

$$\begin{array}{ccc}\hfill \left(good\right(X)& {\leftarrow }_G& \neg bad\left(X\right).S{c}^{+})\hfill \\ \hfill \left(bad\right(X)& {\leftarrow }_G& \neg good\left(X\right).S{c}^{+})\hfill \end{array}$$

Similar to the computation in Example 9, we have $S_P^{\perp }=\{(good\left(a\right),S{c}^{-}),(bad\left(a\right),S{c}^{-})\}$ and $S_P^{\top }=\{(good\left(a\right),S{c}^{+}),(bad\left(a\right),S{c}^{+})\}$. Thus, in order to compute stable models of the program, we only need to check six candidates $\left\{\right(good\left(a\right),x),(bad\left(a\right),y\left)\right\}$, where $v_5=S{c}^{-}\le x,y\le S{c}^{+}=v_7$, instead of checking all 26 possible candidates $\left\{\right(good\left(a\right),x),(bad\left(a\right),y\left)\right\}$, where $v_0=0\le x,y\le v_{12}=1$. In fact, the program has three stable models $\left\{\right(good\left(a\right),x),(bad\left(a\right),-x\left)\right\}$, where $v_5=S{c}^{-}\le x\le S{c}^{+}=v_7$.

5. Conclusions and Future Work

In this paper, we extend FLLP by allowing negative literals to appear in rule bodies, resulting in normal logic programs. We study both the stable model semantics and the well-founded semantics of such programs and their relation in terms of fixpoints of several operators. More concretely, we first adapt the stable model semantics of classical LP to FLLP based on the usual Gelfond–Lifschitz transformation. In fact, according to the literature, this seems to be the only way to study the stable model semantics of normal logic programs. Since our hedge connectives have no counterpart in any FLP framework, our FLLP [4] is not a special case of any of the FLP frameworks based on the well-known Vojtáš’s FLP, especially MALP, which appears to be the most expressive one among those. Therefore, our stable model semantics is not a special case of that of any of the frameworks. Furthermore, we are the first ones studying the well-founded semantics in an FLP framework among those based on Vojtáš’s FLP. The well-founded semantics is characterized by two operators $S_P^{\perp }$ and $S_P^{\top }$, which can be computed finitely. It can be seen that our well-founded semantics can be adapted for other FLP frameworks. We then study the relation between the two kinds of semantics. In fact, in the literature, this relation is usually studied using a bilattice setting of the truth domain. However, our truth domains do not possess a complete knowledge-ordering lattice and, thus, do not have a bilattice structure. Interestingly, in FLLP, the two kinds of semantics possess properties similar to those of the classical case. More precisely, every stable model contains the well-founded (partial) model, and the well-founded total model coincides with the unique stable model, but not vice versa. Moreover, in LP and ASP, there is a well-known method to compute stable models/answer sets of normal logic programs, called “guess-and-check” [9,48,49]. It is composed of two steps: (1) guessing a candidate for a stable model/answer set of a normal logic program, and (2) checking whether the candidate is, in fact, a stable model/answer set of the program. Since for a normal program P, $S_P^{\perp }$ and $S_P^{\top }$ are, respectively, a lower bound and an upper bound of stable models, they can be used to reduce the number of candidates for Step (1). That is, the well-founded semantics can make the computation of stable models more efficiently.

For future work, we will study other well-known kinds of semantics of normal logic programs such as perfect model semantics, stationary semantics [9], and their relations with the two kinds of semantics studied in this work as well as with each other.