[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/en\/stable-model-semantics-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/en\/stable-model-semantics-wikipedia\/","headline":"Stable model semantics – Wikipedia","name":"Stable model semantics – Wikipedia","description":"before-content-x4 The concept of a stable model, or answer set, is used to define a declarative semantics for logic programs","datePublished":"2014-02-06","dateModified":"2014-02-06","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/en\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/en\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/cd810e53c1408c38cc766bc14e7ce26a?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/cd810e53c1408c38cc766bc14e7ce26a?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/ae90817589e80d41c0c2b75e3da5081afd4a15d0","url":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/ae90817589e80d41c0c2b75e3da5081afd4a15d0","height":"","width":""},"url":"https:\/\/wiki.edu.vn\/en\/stable-model-semantics-wikipedia\/","wordCount":25198,"articleBody":"     (adsbygoogle = window.adsbygoogle || []).push({});before-content-x4The concept of a stable model, or answer set, is used to define a declarative semantics for logic programs with negation as failure. This is one of several standard approaches to the meaning of negation in logic programming, along with program completion and the well-founded semantics. The stable model semantics is the basis ofanswer set programming.       (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4Table of ContentsMotivation[edit]Relation to nonmonotonic logic[edit]Stable models[edit]Definition[edit]Example[edit]Programs without a unique stable model[edit]Properties of the stable model semantics[edit]Relation to other theories of negation as failure[edit]Program completion[edit]Well-founded semantics[edit]Strong negation[edit]Representing incomplete information[edit]Coherent stable models[edit]Closed world assumption[edit]Programs with constraints[edit]Disjunctive programs[edit]Stable models of a set of propositional formulas[edit]General definition of a stable model[edit]Properties of the general stable model semantics[edit]See also[edit]References[edit]Motivation[edit]Research on the declarative semantics of negation in logic programming was motivated by the fact that the behavior of SLDNF resolution\u00a0\u2014 the generalization of SLD resolution used by Prolog in the presence of negation in the bodies of rules\u00a0\u2014 does not fully match the truth tables familiar from classical propositional logic. Consider, for instance, the program       (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4p\u00a0{displaystyle p }r\u2190p,\u00a0q{displaystyle rleftarrow p, q}s\u2190p,\u00a0not\u2061q.{displaystyle sleftarrow p, operatorname {not} q.}Given this program, the query p will succeed, because the program includes p as a fact; the query q will fail, because it does not occur in the head of any of the rules. The query r will fail also, because the only rule with r in the head contains the subgoal q in its body; as we have seen, that subgoal fails. Finally, the query s succeeds, because each of the subgoals p,        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4not\u2061q{displaystyle operatorname {not} q} succeeds. (The latter succeeds because the corresponding positive goal q fails.) To sum up, the behavior of SLDNF resolution on the given program can be represented by the following truth assignment:On the other hand, the rules of the given program can be viewed as propositional formulas if we identify the comma with conjunction \u2227{displaystyle land }, the symbol not{displaystyle operatorname {not} } with negation \u00ac{displaystyle neg }, and agree to treat F\u2190G{displaystyle Fleftarrow G} as the implication G\u2192F{displaystyle Grightarrow F} written backwards. For instance, the last rule of the given program is, from this point of view, alternative notation for the propositional formulap\u2227\u00acq\u2192s.{displaystyle pland neg qrightarrow s.}If we calculate the truth values of the rules of the program for the truth assignment shown above then we will see that each rule gets the value T. In other words, that assignment is a model of the program. But this program has also other models, for instanceThus one of the models of the given program is special in the sense that it correctly represents the behavior of SLDNF resolution. What are the mathematical properties of that model that make it special? An answer to this question is provided by the definition of a stable model.Relation to nonmonotonic logic[edit]The meaning of negation in logic programs is closely related to two theories of nonmonotonic reasoning\u00a0\u2014 autoepistemic logic and default logic. The discovery of these relationships was a key step towards the invention of the stable model semantics.The syntax of autoepistemic logic uses a modal operator that allows us to distinguish between what is true and what is believed. Michael Gelfond [1987] proposed to read not\u2061p{displaystyle operatorname {not} p} in the body of a rule as “p{displaystyle p} is not believed”, and to understand a rule with negation as the corresponding formula of autoepistemic logic. The stable model semantics, in its basic form, can be viewed as a reformulation of this idea that avoids explicit references to autoepistemic logic.In default logic, a default is similar to an inference rule, except that it includes, besides its premises and conclusion, a list of formulas called justifications. A default can be used to derive its conclusion under the assumption that its justifications are consistent with what is currently believed. Nicole Bidoit and Christine Froidevaux [1987] proposed to treat negated atoms in the bodies of rules as justifications. For instance, the rules\u2190p,\u00a0not\u2061q{displaystyle sleftarrow p, operatorname {not} q}can be understood as the default that allows us to derive s{displaystyle s} from p{displaystyle p} assuming that \u00acq{displaystyle neg q} is consistent. The stable model semantics uses the same idea, but it does not explicitly refer to default logic.Stable models[edit]The definition of a stable model below, reproduced from [Gelfond and Lifschitz, 1988], uses two conventions. First, a truth assignment is identified with the set of atoms that get the value T. For instance, the truth assignmentis identified with the set {p,s}{displaystyle {p,s}}. This convention allows us to use the set inclusion relation to compare truth assignments with each other. The smallest of all truth assignments \u2205{displaystyle emptyset } is the one that makes every atom false; the largest truth assignment makes every atom true.Second, a logic program with variables is viewed as shorthand for the set of all ground instances of its rules, that is, for the result of substituting variable-free terms for variables in the rules of the program in all possible ways. For instance, the logic programming definition of even numberseven\u2061(0)\u00a0{displaystyle operatorname {even} (0) }even\u2061(s(X))\u2190not\u2061even\u2061(X){displaystyle operatorname {even} (s(X))leftarrow operatorname {not} operatorname {even} (X)}is understood as the result of replacing X in this program by the ground terms0,\u00a0s(0),\u00a0s(s(0)),\u2026.{displaystyle 0, s(0), s(s(0)),dots .}in all possible ways. The result is the infinite ground programeven\u2061(0)\u00a0{displaystyle operatorname {even} (0) }even\u2061(s(0))\u2190not\u2061even\u2061(0){displaystyle operatorname {even} (s(0))leftarrow operatorname {not} operatorname {even} (0)}even\u2061(s(s(0)))\u2190not\u2061even\u2061(s(0)){displaystyle operatorname {even} (s(s(0)))leftarrow operatorname {not} operatorname {even} (s(0))}\u2026{displaystyle dots }Definition[edit]Let P be a set of rules of the formA\u2190B1,\u2026,Bm,not\u2061C1,\u2026,not\u2061Cn{displaystyle Aleftarrow B_{1},dots ,B_{m},operatorname {not} C_{1},dots ,operatorname {not} C_{n}}where A,B1,\u2026,Bm,C1,\u2026,Cn{displaystyle A,B_{1},dots ,B_{m},C_{1},dots ,C_{n}} are ground atoms. If P does not contain negation (n=0{displaystyle n=0} in every rule of the program) then, by definition, the only stable model of P is its model that is minimal relative to set inclusion.[1] (Any program without negation has exactly one minimal model.) To extend this definition to the case of programs with negation, we need the auxiliary concept of the reduct, defined as follows.For any set I of ground atoms, the reduct of P relative to I is the set of rules without negation obtained from P by first dropping every rule such that at least one of the atoms Ci{displaystyle C_{i}} in its bodyB1,\u2026,Bm,not\u2061C1,\u2026,not\u2061Cn{displaystyle B_{1},dots ,B_{m},operatorname {not} C_{1},dots ,operatorname {not} C_{n}}belongs to I, and then dropping the parts not\u2061C1,\u2026,not\u2061Cn{displaystyle operatorname {not} C_{1},dots ,operatorname {not} C_{n}} from the bodies of all remaining rules.We say that I is a stable model of P if I is the stable model of the reduct of P relative to I. (Since the reduct does not contain negation, its stable model has been already defined.) As the term “stable model” suggests, every stable model of P is a model of P.Example[edit]To illustrate these definitions, let us check that {p,s}{displaystyle {p,s}} is a stable model of the programp\u00a0{displaystyle p }r\u2190p,\u00a0q{displaystyle rleftarrow p, q}s\u2190p,\u00a0not\u2061q.{displaystyle sleftarrow p, operatorname {not} q.}The reduct of this program relative to {p,s}{displaystyle {p,s}} isp\u00a0{displaystyle p }r\u2190p,\u00a0q{displaystyle rleftarrow p, q}s\u2190p.{displaystyle sleftarrow p.}(Indeed, since q\u2209{p,s}{displaystyle qnot in {p,s}}, the reduct is obtained from the program by dropping the part not\u2061q.\u00a0{displaystyle operatorname {not} q. }) The stable model of the reduct is {p,s}{displaystyle {p,s}}. (Indeed, this set of atoms satisfies every rule of the reduct, and it has no proper subsets with the same property.) Thus after computing the stable model of the reduct we arrived at the same set {p,s}{displaystyle {p,s}} that we started with. Consequently, that set is a stable model.Checking in the same way the other 15 sets consisting of the atoms p,\u00a0q,\u00a0r,\u00a0s{displaystyle p, q, r, s} shows that this program has no other stable models. For instance, the reduct of the program relative to {p,q,r}{displaystyle {p,q,r}} isp\u00a0{displaystyle p }r\u2190p,\u00a0q.{displaystyle rleftarrow p, q.}The stable model of the reduct is {p}{displaystyle {p}}, which is different from the set {p,q,r}{displaystyle {p,q,r}} that we started with.Programs without a unique stable model[edit]A program with negation may have many stable models or no stable models. For instance, the programp\u2190not\u2061q{displaystyle pleftarrow operatorname {not} q}q\u2190not\u2061p{displaystyle qleftarrow operatorname {not} p}has two stable models {p}{displaystyle {p}}, {q}{displaystyle {q}}. The one-rule programp\u2190not\u2061p{displaystyle pleftarrow operatorname {not} p}has no stable models.If we think of the stable model semantics as a description of the behavior of Prolog in the presence of negation then programs without a unique stable model can be judged unsatisfactory: they do not provide an unambiguous specification for Prolog-style query answering. For instance, the two programs above are not reasonable as Prolog programs\u00a0\u2014 SLDNF resolution does not terminate on them.But the use of stable models in answer set programming provides a different perspective on such programs. In that programming paradigm, a given search problem is represented by a logic program so that the stable models of the program correspond to solutions. Then programs with many stable models correspond to problems with many solutions, and programs without stable models correspond to unsolvable problems. For instance, the eight queens puzzle has 92 solutions; to solve it using answer set programming, we encode it by a logic program with 92 stable models. From this point of view, logic programs with exactly one stable model are rather special in answer set programming, like polynomials with exactly one root in algebra.Properties of the stable model semantics[edit]In this section, as in the definition of a stable model above, by a logic program we mean a set of rules of the formA\u2190B1,\u2026,Bm,not\u2061C1,\u2026,not\u2061Cn{displaystyle Aleftarrow B_{1},dots ,B_{m},operatorname {not} C_{1},dots ,operatorname {not} C_{n}}where A,B1,\u2026,Bm,C1,\u2026,Cn{displaystyle A,B_{1},dots ,B_{m},C_{1},dots ,C_{n}} are ground atoms.Head atomsIf an atom A belongs to a stable model of a logic program P then A is the head of one of the rules of P.MinimalityAny stable model of a logic program P is minimal among the models of P relative to set inclusion.The antichain propertyIf I and J are stable models of the same logic program then I is not a proper subset of J. In other words, the set of stable models of a program is an antichain.NP-completenessTesting whether a finite ground logic program has a stable model is NP-complete.Relation to other theories of negation as failure[edit]Program completion[edit]Any stable model of a finite ground program is not only a model of the program itself, but also a model of its completion [Marek and Subrahmanian, 1989]. The converse, however, is not true. For instance, the completion of the one-rule programp\u2190p{displaystyle pleftarrow p}is the tautology p\u2194p{displaystyle pleftrightarrow p}. The model \u2205{displaystyle emptyset } of this tautology is a stable model of p\u2190p{displaystyle pleftarrow p}, but its other model {p}\u00a0{displaystyle {p} } is not. Fran\u00e7ois Fages [1994] found a syntactic condition on logic programs that eliminates such counterexamples and guarantees the stability of every model of the program’s completion. The programs that satisfy his condition are called tight.Fangzhen Lin and Yuting Zhao [2004] showed how to make the completion of a nontight program stronger so that all its nonstable models will be eliminated. The additional formulas that they add to the completion are called loop formulas.Well-founded semantics[edit]The well-founded model of a logic program partitions all ground atoms into three sets: true, false and unknown. If an atom is true in the well-founded model of P{displaystyle P} then it belongs to every stable model of P{displaystyle P}. The converse, generally, does not hold. For instance, the programp\u2190not\u2061q{displaystyle pleftarrow operatorname {not} q}q\u2190not\u2061p{displaystyle qleftarrow operatorname {not} p}r\u2190p{displaystyle rleftarrow p}r\u2190q{displaystyle rleftarrow q}has two stable models, {p,r}{displaystyle {p,r}} and {q,r}{displaystyle {q,r}}. Even though r{displaystyle r} belongs to both of them, its value in the well-founded model is unknown.Furthermore, if an atom is false in the well-founded model of a program then it does not belong to any of its stable models. Thus the well-founded model of a logic program provides a lower bound on the intersection of its stable models and an upper bound on their union.Strong negation[edit]Representing incomplete information[edit]From the perspective of knowledge representation, a set of ground atoms can be thought of as a description of a complete state of knowledge: the atoms that belong to the set are known to be true, and the atoms that do not belong to the set are known to be false. A possibly incomplete state of knowledge can be described using a consistent but possibly incomplete set of literals; if an atom p{displaystyle p} does not belong to the set and its negation does not belong to the set either then it is not known whether p{displaystyle p} is true or false.In the context of logic programming, this idea leads to the need to distinguish between two kinds of negation\u00a0\u2014 negation as failure, discussed above, and strong negation, which is denoted here by \u223c{displaystyle sim }.[2] The following example, illustrating the difference between the two kinds of negation, belongs to John McCarthy. A school bus may cross railway tracks under the condition that there is no approaching train. If we do not necessarily know whether a train is approaching then the rule using negation as failureCross\u2190not Train{displaystyle {hbox{Cross}}leftarrow {hbox{not Train}}}is not an adequate representation of this idea: it says that it’s okay to cross in the absence of information about an approaching train. The weaker rule, that uses strong negation in the body, is preferable:Cross\u2190\u223cTrain.{displaystyle {hbox{Cross}}leftarrow ,sim {hbox{Train}}.}It says that it’s okay to cross if we know that no train is approaching.Coherent stable models[edit]To incorporate strong negation in the theory of stable models, Gelfond and Lifschitz [1991] allowed each of the expressions A{displaystyle A}, Bi{displaystyle B_{i}}, Ci{displaystyle C_{i}} in a ruleA\u2190B1,\u2026,Bm,not\u2061C1,\u2026,not\u2061Cn{displaystyle Aleftarrow B_{1},dots ,B_{m},operatorname {not} C_{1},dots ,operatorname {not} C_{n}}to be either an atom or an atom prefixed with the strong negation symbol. Instead of stable models, this generalization uses answer sets, which may include both atoms and atoms prefixed with strong negation.An alternative approach [Ferraris and Lifschitz, 2005] treats strong negation as a part of an atom, and it does not require any changes in the definition of a stable model. In this theory of strong negation, we distinguish between atoms of two kinds, positive and negative, and assume that each negative atom is an expression of the form \u223cA{displaystyle sim A}, where A\u00a0{displaystyle A } is a positive atom. A set of atoms is called coherent if it does not contain “complementary” pairs of atoms \u00a0A,\u223cA{displaystyle  A,sim A}. Coherent stable models of a program are identical to its consistent answer sets in the sense of [Gelfond and Lifschitz, 1991].For instance, the programp\u2190not\u2061q{displaystyle pleftarrow operatorname {not} q}q\u2190not\u2061p{displaystyle qleftarrow operatorname {not} p}r\u00a0{displaystyle r }\u223cr\u2190not\u2061p{displaystyle sim rleftarrow operatorname {not} p}has two stable models, {p,r}\u00a0{displaystyle {p,r} } and \u00a0{q,r,\u223cr}{displaystyle  {q,r,sim r}}. The first model is coherent; the second is not, because it contains both the atom \u00a0r{displaystyle  r} and the atom \u00a0\u223cr{displaystyle  sim r}.Closed world assumption[edit]According to [Gelfond and Lifschitz, 1991], the closed world assumption for a predicate p\u00a0{displaystyle p } can be expressed by the rule\u223cp(X1,\u2026,Xn)\u2190not\u2061p(X1,\u2026,Xn){displaystyle sim p(X_{1},dots ,X_{n})leftarrow operatorname {not} p(X_{1},dots ,X_{n})}(the relation p\u00a0{displaystyle p } does not hold for a tuple X1,\u2026,Xn{displaystyle X_{1},dots ,X_{n}} if there is no evidence that it does). For instance, the stable model of the programp(a,b)\u00a0{displaystyle p(a,b) }p(c,d)\u00a0{displaystyle p(c,d) }\u223cp(X,Y)\u2190not\u2061p(X,Y){displaystyle sim p(X,Y)leftarrow operatorname {not} p(X,Y)}consists of 2 positive atomsp(a,b),\u00a0p(c,d)\u00a0{displaystyle p(a,b), p(c,d) }and 14 negative atoms\u223cp(a,a),\u00a0\u223cp(a,c),\u00a0\u2026{displaystyle sim p(a,a), sim p(a,c), dots }i.e., the strong negations of all other positive ground atoms formed from p,\u00a0a,\u00a0b,\u00a0c,\u00a0d{displaystyle p, a, b, c, d}.A logic program with strong negation can include the closed world assumption rules for some of its predicates and leave the other predicates in the realm of the open world assumption.Programs with constraints[edit]The stable model semantics has been generalized to many kinds of logic programs other than collections of “traditional” rules discussed above\u00a0\u2014 rules of the formA\u2190B1,\u2026,Bm,not\u2061C1,\u2026,not\u2061Cn{displaystyle Aleftarrow B_{1},dots ,B_{m},operatorname {not} C_{1},dots ,operatorname {not} C_{n}}where A,B1,\u2026,Bm,C1,\u2026,Cn{displaystyle A,B_{1},dots ,B_{m},C_{1},dots ,C_{n}} are atoms. One simple extension allows programs to contain constraints\u00a0\u2014 rules with the empty head:\u2190B1,\u2026,Bm,not\u2061C1,\u2026,not\u2061Cn.{displaystyle leftarrow B_{1},dots ,B_{m},operatorname {not} C_{1},dots ,operatorname {not} C_{n}.}Recall that a traditional rule can be viewed as alternative notation for a propositional formula if we identify the comma with conjunction \u2227{displaystyle land }, the symbol not{displaystyle operatorname {not} } with negation \u00ac{displaystyle neg }, and agree to treat F\u2190G{displaystyle Fleftarrow G} as the implication G\u2192F{displaystyle Grightarrow F} written backwards. To extend this convention to constraints, we identify a constraint with the negation of the formula corresponding to its body:\u00ac(B1\u2227\u22ef\u2227Bm\u2227\u00acC1\u2227\u22ef\u2227\u00acCn).{displaystyle neg (B_{1}land cdots land B_{m}land neg C_{1}land cdots land neg C_{n}).}We can now extend the definition of a stable model to programs with constraints. As in the case of traditional programs, we begin with programs that do not contain negation. Such a program may be inconsistent; then we say that it has no stable models. If such a program P{displaystyle P} is consistent then P{displaystyle P} has a unique minimal model, and that model is considered the only stable model of P{displaystyle P}.Next, stable models of arbitrary programs with constraints are defined using reducts, formed in the same way as in the case of traditional programs (see the definition of a stable model above). A set I{displaystyle I} of atoms is a stable model of a program P{displaystyle P} with constraints if the reduct of P{displaystyle P} relative to I{displaystyle I} has a stable model, and that stable model equals I{displaystyle I}.The properties of the stable model semantics stated above for traditional programs hold in the presence of constraints as well.Constraints play an important role in answer set programming because adding a constraint to a logic program P{displaystyle P} affects the collection of stable models of P{displaystyle P} in a very simple way: it eliminates the stable models that violate the constraint. In other words, for any program P{displaystyle P} with constraints and any constraint C{displaystyle C}, the stable models of P\u222a{C}{displaystyle Pcup {C}} can be characterized as the stable models of P{displaystyle P} that satisfy C{displaystyle C}.Disjunctive programs[edit]In a disjunctive rule, the head may be the disjunction of several atoms:A1;\u2026;Ak\u2190B1,\u2026,Bm,not\u2061C1,\u2026,not\u2061Cn{displaystyle A_{1};dots ;A_{k}leftarrow B_{1},dots ,B_{m},operatorname {not} C_{1},dots ,operatorname {not} C_{n}}(the semicolon is viewed as alternative notation for disjunction \u2228{displaystyle lor }). Traditional rules correspond to k=1{displaystyle k=1}, and constraints to k=0{displaystyle k=0}. To extend the stable model semantics to disjunctive programs [Gelfond and Lifschitz, 1991], we first define that in the absence of negation (n=0{displaystyle n=0} in each rule) the stable models of a program are its minimal models. The definition of the reduct for disjunctive programs remains the same as before. A set I{displaystyle I} of atoms is a stable model of P{displaystyle P} if I{displaystyle I} is a stable model of the reduct of P{displaystyle P} relative to I{displaystyle I}.For example, the set {p,r}{displaystyle {p,r}} is a stable model of the disjunctive programp;q\u00a0{displaystyle p;q }r\u2190not\u2061q{displaystyle rleftarrow operatorname {not} q}because it is one of two minimal models of the reductp;q\u00a0{displaystyle p;q }r.\u00a0{displaystyle r. }The program above has one more stable model, {q}{displaystyle {q}}.As in the case of traditional programs, each element of any stable model of a disjunctive program P{displaystyle P} is a head atom of P{displaystyle P}, in the sense that it occurs in the head of one of the rules of P{displaystyle P}. As in the traditional case, the stable models of a disjunctive program are minimal and form an antichain. Testing whether a finite disjunctive program has a stable model is \u03a32P{displaystyle Sigma _{2}^{rm {P}}}-complete [Eiter and Gottlob, 1993].Stable models of a set of propositional formulas[edit]Rules, and even disjunctive rules, have a rather special syntactic form, in comparison with arbitrary propositional formulas. Each disjunctive rule is essentially an implication such that its antecedent (the body of the rule) is a conjunction of literals, and its consequent (head) is a disjunction of atoms. David Pearce [1997] and Paolo Ferraris [2005] showed how to extend the definition of a stable model to sets of arbitrary propositional formulas. This generalization has applications to answer set programming.Pearce’s formulation looks very different from the original definition of a stable model. Instead of reducts, it refers to equilibrium logic\u00a0\u2014 a system of nonmonotonic logic based on Kripke models. Ferraris’s formulation, on the other hand, is based on reducts, although the process of constructing the reduct that it uses differs from the one described above. The two approaches to defining stable models for sets of propositional formulas are equivalent to each other.General definition of a stable model[edit]According to [Ferraris, 2005], the reduct of a propositional formula F{displaystyle F} relative to a set I{displaystyle I} of atoms is the formula obtained from F{displaystyle F} by replacing each maximal subformula that is not satisfied by I{displaystyle I} with the logical constant \u22a5{displaystyle bot } (false). The reduct of a set P{displaystyle P} of propositional formulas relative to I{displaystyle I} consists of the reducts of all formulas from P{displaystyle P} relative to I{displaystyle I}. As in the case of disjunctive programs, we say that a set I{displaystyle I} of atoms is a stable model of P{displaystyle P} if I{displaystyle I} is minimal (with respect to set inclusion) among the models of the reduct of P{displaystyle P} relative to I{displaystyle I}.For instance, the reduct of the set{p,\u00a0p\u2227q\u2192r,\u00a0p\u2227\u00acq\u2192s}{displaystyle {p, pland qrightarrow r, pland neg qrightarrow s}}relative to {p,s}{displaystyle {p,s}} is{p,\u00a0\u22a5\u2192\u22a5,\u00a0p\u2227\u00ac\u22a5\u2192s}.{displaystyle {p, bot rightarrow bot , pland neg bot rightarrow s}.}Since {p,s}{displaystyle {p,s}} is a model of the reduct, and the proper subsets of that set are not models of the reduct, {p,s}{displaystyle {p,s}} is a stable model of the given set of formulas.We have seen that {p,s}{displaystyle {p,s}} is also a stable model of the same formula, written in logic programming notation, in the sense of the original definition. This is an instance of a general fact: in application to a set of (formulas corresponding to) traditional rules, the definition of a stable model according to Ferraris is equivalent to the original definition. The same is true, more generally, for programs with constraints and for disjunctive programs.Properties of the general stable model semantics[edit]The theorem asserting that all elements of any stable model of a program P{displaystyle P} are head atoms of P{displaystyle P} can be extended to sets of propositional formulas, if we define head atoms as follows. An atom A{displaystyle A} is a head atom of a set P{displaystyle P} of propositional formulas if at least one occurrence of A{displaystyle A} in a formula from P{displaystyle P} is neither in the scope of a negation nor in the antecedent of an implication. (We assume here that equivalence is treated as an abbreviation, not a primitive connective.)The minimality and the antichain property of stable models of a traditional program do not hold in the general case. For instance, (the singleton set consisting of) the formulap\u2228\u00acp{displaystyle plor neg p}has two stable models, \u2205{displaystyle emptyset } and {p}{displaystyle {p}}. The latter is not minimal, and it is a proper superset of the former.Testing whether a finite set of propositional formulas has a stable model is \u03a32P{displaystyle Sigma _{2}^{rm {P}}}-complete, as in the case of disjunctive programs.See also[edit]References[edit]Bidoit, N.; Froidevaux, C. (1987). “Minimalism subsumes default logic and circumscription”. Proceedings: Symposium on Logic in Computer Science, Ithaca, New York, June 22-25, 1987. IEEE Computer Society Press. pp.\u00a089\u201397. ISBN\u00a0978-0-8186-0793-6. 87CH2464-6.Eiter, T.; Gottlob, G. (1993). “Complexity results for disjunctive logic programming and application to nonmonotonic logics”. ILPS ’93: Proceedings of the 1993 international symposium on Logic programming. MIT Press. pp.\u00a0266\u2013278. ISBN\u00a0978-0-262-63152-5.van Emden, M.; Kowalski, R. (1976). “The semantics of predicate logic as a programming language” (PDF). Journal of the ACM. 23 (4): 733\u2013742. CiteSeerX\u00a010.1.1.64.9246. doi:10.1145\/321978.321991. S2CID\u00a011048276.Fages, F. (1994). “Consistency of Clark’s completion and existence of stable models”. Journal of Methods of Logic in Computer Science. 1: 51\u201360. CiteSeerX\u00a010.1.1.48.2157.Ferraris, P. (2005). “Answer sets for propositional theories”. Logic Programming and Nonmonotonic Reasoning. LPNMR 2005. Lecture Notes in Computer Science. Vol.\u00a03662. Springer. pp.\u00a0119\u2013131. CiteSeerX\u00a010.1.1.129.5332. doi:10.1007\/11546207_10. ISBN\u00a0978-3-540-31827-9.Ferraris, P.; Lifschitz, V. (2005). “Mathematical foundations of answer set programming”. We Will Show Them! Essays in Honour of Dov Gabbay. King’s College Publications. pp.\u00a0615\u2013664. CiteSeerX\u00a010.1.1.79.7622.Gelfond, M. (1987). “On stratified autoepistemic theories” (PDF). AAAI’87: Proceedings of the sixth National conference on Artificial intelligence. pp.\u00a0207\u2013211. ISBN\u00a0978-0-934613-42-2.Gelfond, M.; Lifschitz, V. (1988). “The stable model semantics for logic programming”. Proceedings of the Fifth International Conference on Logic Programming (ICLP). MIT Press. pp.\u00a01070\u201380. ISBN\u00a0978-0-262-61054-4.Gelfond, M.; Lifschitz, V. (1991). “Classical negation in logic programs and disjunctive databases”. New Generation Computing. 9 (3\u20134): 365\u2013385. CiteSeerX\u00a010.1.1.49.9332. doi:10.1007\/BF03037169. S2CID\u00a013036056.Hanks, S.; McDermott, D. (1987). “Nonmonotonic logic and temporal projection”. Artificial Intelligence. 33 (3): 379\u2013412. doi:10.1016\/0004-3702(87)90043-9.Lin, F.; Zhao, Y. (2004). “ASSAT: Computing answer sets of a logic program by SAT solvers” (PDF). Artificial Intelligence. 157 (1\u20132): 115\u2013137. doi:10.1016\/j.artint.2004.04.004. S2CID\u00a0514581.Marek, V.; Subrahmanian, V.S. (1989). “The relationship between logic program semantics and non-monotonic reasoning”. Logic Programming: Proceedings of the Sixth International Conference. MIT Press. pp.\u00a0600\u2013617. ISBN\u00a0978-0-262-62065-9.Pearce, D. (1997). “A new logical characterization of stable models and answer sets” (PDF). Non-Monotonic Extensions of Logic Programming. Lecture Notes in Artificial Intelligence. Vol.\u00a01216. pp.\u00a057\u201370. doi:10.1007\/BFb0023801. ISBN\u00a0978-3-540-68702-3.Reiter, R. (1980). “A logic for default reasoning” (PDF). Artificial Intelligence. 13 (1\u20132): 81\u2013132. doi:10.1016\/0004-3702(80)90014-4.     (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4"},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/en\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/en\/stable-model-semantics-wikipedia\/#breadcrumbitem","name":"Stable model semantics – Wikipedia"}}]}]