Datalog with negation 2026-10-31
Datalog with negative body premises. Its meaning depends on the specified semantics, such as stable model semantics or evaluation of a stratified Datalog program.
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.
The remaining classification rule isThe positive premise restricts the rule to years. Its negation as failure premise is evaluated by stable model semantics; it does not assert a separately stored negative fact. This gives a stratified Datalog program: divisibility and year facts are inputs, leap status is computed next, and common status last.
Skeptical entailment 2026-10-31
A consequence holds skeptically if it is true in every admitted model, in particular every stable model when using stable model semantics. Exhibiting one supporting stable model establishes only existence of support, not skeptical entailment.