Negation as failure Created 2026-10-31 Updated 2026-11-05
Negation as failure interprets failure of a specified proof search as a negative result. In the Prolog operation
\+ Goal, the negative goal succeeds when trying Goal fails in finite time; it fails when Goal succeeds. A search that never finishes does not establish the negative result.[ref]For example, suppose a finite knowledge base records
penguin(opus) and has no rule capable of deriving penguin(robin). A search for penguin(robin) finitely fails, so its negation succeeds under this operational rule. That result relies on the chosen knowledge base and search semantics. Adding the missing fact changes the result; an unrecorded fact in the outside world has not been independently disproved.Stable model semantics gives a related model-based interpretation for negative rule premises through the stable model reduct. The rules and have two stable models, and : in either candidate, the surviving rule forces exactly its one member. Neither atom follows by skeptical entailment. Operational finite failure and a chosen model semantics must therefore be distinguished when interpreting a negative rule.
A Herbrand interpretation is a stable model when it is the least Herbrand model of its stable model reduct . To form the reduct, ground the rules, delete each rule with a premise for which , and remove the remaining occurrences of
not and their atoms.For , the rules concerning in the reduct aretogether with . No rule has a divisibility atom in its head, so forward chaining produces no divisibility facts and no leap fact. Ground rules for the other constants cannot fire because their year premises are absent. ThusTherefore .
For , the rule using is deleted. The common-year rule is retained without its negative premise, since is absent. Crucially, the reduct does not convert atoms already in into facts. Its least Herbrand model is again . The two divisibility atoms in have no support. Hence
Inspecting these two interpretations alone is not sufficient for skeptical entailment. That requires every stable model to contain . Here we can finish the argument: every reduct has no rule deriving divisibility atoms, so every stable model has empty divisibility relation. Its leap relation must then be empty as well. The common-year rule consequently derives , and the only year fact is . Thus is the unique stable model, andThis final uniqueness argument, rather than the examination of just two candidate interpretations, establishes the required universal claim.
Stable model semantics 2026-10-31
A semantics in which an interpretation must equal the least Herbrand model of its own stable model reduct. Some programs have no stable model, and others have several.