Think about how you decide if someone's home. You don't see their car in the driveway, their lights are off, and there's no response when you knock — you conclude they must be out. You didn't directly verify their absence; you reasoned based on what you didn't observe.This kind of "absence of evidence" reasoning is deeply intuitive to humans but traditionally challenging for computers. ASP's default negation operator (not) elegantly captures this natural way of thinking.
Default Negation
Default negation is indicated by the "not" operator is read as "... is not and will never be included in the answer set". The rule
p ← not q .
is read as "if q is not and will never be in the answer set then p is in the answer set" and results in
{p}
since there is no q. An alternate reading of this rule is "if there is no evidence of q then p".If q is added as a fact
q .
then the result is
{q}
since the body of (1) now evaluates to false (⊥) which causes the rule to be struck out and removed.Default negation in ASP is about "absence of evidence" rather than explicit false values. For developers coming from languages like JavaScript, default negation is similar to checking for undefined values:
// JavaScript: do something when there's no evidence of person
if (typeof person === 'undefined') { … }
Default negation is commonly referred to as "negation by failure" and is one of the most powerful concepts in ASP that differentiates it from other Logic Programming languages such as Prolog. It follows from the closed world assumption that was introduced earlier: "what is not currently known to be true, is false".
Evaluating Answer Sets
As has been demonstrated, programs that consist of only positive terms (i.e. terms without negation) can be rationalized by expanding and substitution. Some programs that contain negative terms can be evaluated in the same way.
p ← not q .
q ← not r .
The first rule depends on q which is found in the second rule therefore the second rule must be evaluated first. Since there are no rules that have r in the head, the second rule emits q. In an answer set with q, the first rule cannot hold therefore the answer set will not contain p. The result of (4) is
{q}
as expected.
p ← not q .
q ← not p .
Because the rules of (5) are cyclic, we need to follow a technique similar that in "Circular Dependencies > Cycles in Rules" where we looked at each possible answer set in turn and determined if it violated any rule and is therefore disqualified as a candidate.
{ } The empty set contains neither p nor q. The first rule states that if there is no q in the answer set then pmust exist in the answer set. The answer set does not contain p therefore the rule is violated; this is not a valid answer set.
{ p } The second rule states that if there is no p in the answer set then there must be a q. There is a p in the answer set therefore this rule is removed. The first rule states that if there is no q in the answer set then pmust exist in the answer set. This is exactly this case therefore no rules are violated and this is a valid answer set.
{ q } This answer set follows the same logic as { p } but with p and q transposed therefore it too is a valid answer set.
{ p q } The first rule states that if q is not in the answer set then p must be in the answer set; this rule is violated. Similarly, the second rule states that if p is in the answer set then q must not be in the answer set; this too is violated. This is not a valid answer set.
The result of this program is
{q}{p}
. (Similar to the Circular Dependencies example, once either { p } or { q } was determined to be in the answer sets then there was was no need to check { p q } since it is a superset of an existing answer and therefore not a candidate.)
Example: Relations
Let's encode some information about the relationship domain:
single(X) ← man(X), not husband(X) .
husband(X) ← man(X), not single(X) .
By itself this program results in the empty set (
{}
) but if a man/1 predicate were introduced
man(pete) .
the result is
{husband(pete)man(pete)}{man(pete)single(pete)}
— pete is either single or a husband (married).If we also state that pete is single
single(pete) .
then the result is limited to a single answer set
{man(pete)single(pete)}
. In some ways, this is wholly uninteresting since (7) and (8)by themselves results in
{man(pete)single(pete)}
since the answer sets always includes any facts that are given. What's important to note is that our encoding of the domain in (6) combined with these facts did not result in any unintentional atoms.
Elaboration Tolerance
This can be expanded to include women as well:
single(X) ← woman(X), not wife(X) .
wife(X) ← woman(X), not single(X) .
If a woman/1 predicate is added
woman(zuzu) .
then the result is all combinations
{wife(zuzu)woman(zuzu)}{single(zuzu)woman(zuzu)}
.Notice that it was straightforward to add additional rules as the requirements changed. It wasn't necessary to change the existing program to add new information. This shows that ASP exhibits good elaboration tolerance — a small change to the domain should result in a small change to the encoding of that domain.
Refactoring
In order to make the program easier to maintain going forward, we may reorganize (refactor) the rules to be more generic and we'll introduce two new predicates person/1 and married/1.
You might be asking: why does the definition of married/1 and single/1 need to include person/1? Specifically, following the example of (5), why isn't the following a valid encoding?
married(X) ← not single(X) .
single(X) ← not married(X) .
Evaluating this program results in an error:
<Error>
. This program is unsafe because X could be any value — there's no bound on what X could be, leading to an infinite set of possible groundings. A variable must occur in at least one positive body literal (i.e. not negated) in order to be considered 'safe'. In other words, there must be some (positive) term that bounds the set of values that the variable may take on. In (11)person(X) serves this role. This is not needed in (5) since there is no variable for which a set of values needs to be determined.
Leverage Relations
ASP allows one to use rules in ways that might not have originally intended since the program simply states what relates and what holds. Leveraging all of the possible relations does require some forethought when encoding the domain.Rather than specifying a woman/1 predicate, let's specify a married/1 predicate
married(zuzu) .
This results in
{married(zuzu)}
. Why isn't it { married(zuzu) person(zuzu) woman(zuzu) }? Simply because the encoding doesn't contain a rule that derives woman (i.e. no rule has a head that includes woman/1). If we also specify that zuzu is a woman (10) then the desired result is seen:
{married(zuzu)person(zuzu)wife(zuzu)woman(zuzu)}
What if we were only to specify that zuzu is a person in general rather than specifically a woman?
, it does not contain husband/1 or wife/1 for the same reason.So how might we enhance this encoding to allow for zuzu as a person to be either a man or a woman? We have two choices:Disjunction of the two genders
Notice that adding this additional rule does not change the existing semantics of our program.We can still specify zuzu as a woman and get the expected results:
(Remember that the solver will always return the minimum answer sets.) We can further qualify zuzu as married
{married(zuzu)person(zuzu)wife(zuzu)woman(zuzu)}
. Notice that this isn't as boring of a result as was seen in the previous encoding since we introduced the additional person/1 and married/1 predicates.
Using Default Negation for Exceptions
Default negation is particularly powerful for handling exceptions or "unless" cases. Consider this common pattern:
person(alice ; bob ; charlie) .
has_meeting(alice) .
on_vacation(bob) .
% charlie has no constraints
the results are
{
available/1
charlie
busy/1
alice
bob
has_meeting/1
alice
on_vacation/1
bob
person/1
alice
bob
charlie
}
This naturally expresses "a person is available unless they're busy" where "busy" can have multiple definitions. This pattern is common in real-world reasoning where we often think in terms of general rules with exceptions. The use of default negation makes it easy to add new exceptions without modifying the original rule — another example of elaboration tolerance.
Complete Encoding
For reference, the (one of many possible) full encoding:
Default negation in ASP is more than just a programming feature — it's a bridge between how humans naturally reason and how we can encode that reasoning in logic. Key insights include:
Natural Reasoning: Default negation mirrors how we think in everyday life. Just as you assume a store is closed when you don't see any "Open" signs, ASP lets you reason about absence of evidence naturally.
Elaboration Tolerance: The ability to add new rules and exceptions without modifying existing code makes ASP programs highly maintainable and extensible.
Safe Variables: Understanding that variables must be "grounded" in positive literals ensures our programs remain computationally tractable.
Relationship Modeling: Default negation excels at expressing real-world relationships where categories are often mutually exclusive (such as being either single or married) or where exceptions modify general rules.
Common Sense Rules: The combination of default negation with ASP's declarative nature lets us write programs that capture "common sense" reasoning in a way that traditional imperative programming cannot.
The power of default negation lies not just in what it lets us express technically, but in how naturally it maps to human intuition about the world. By allowing us to reason about what's not true just as easily as what is true, ASP with default negation becomes an incredibly powerful tool for modeling real-world domains where absence of evidence is often evidence of absence.
ASP's #count directive enables working with quantities and cardinality constraints. The directive provides a natural way to reason about counting in the real world.13 January 2025
ASP's classical negation operator (-) enables explicit representation of falsity, complementing default negation's ability to reason about unknown information. This powerful combination allows ASP to distinguish between 'known to be false' and 'not known to be true'.15 January 2025
