ASP-14 | Classical Negation
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'.Photo Credit: Rob Grzywinski
Introducing Restrictions in ASP
In the last section we covered default negation. You might ask yourself why are two forms of negation needed? What doesn't default negation cover? John McCarthy, one of the founders of artificial intelligence, used the following example to explain the problem:A bus may cross railway tracks if there is no approaching train.Using default negation, the rulecross ← not train .
is read as "if there is no evidence of a train approaching then the bus may cross". Just because the bus cannot see the train (i.e. has no evidence of the train) does not mean that it is safe to cross. There must be no train for it to be safe! Classical negation (denoted by a "-") adds the notion of "strong" negationcross ← -train .
This rule is read as "if there is no train approaching then the bus may cross".The relationship between the complements train and -train is that they cannot both hold. This can be thought of as the implicit integrity constraint⊥ ← train, -train .
"It cannot be that both train and -train hold." Using both classical and default negation allows one to distinguish between what is known to be false (-train) and what is unknown (not train).
Explicit Closed World Assumption
Using both forms of negation, it's possible to explicitly represent the closed world assumption.-q(X, Y) ← not q(X, Y), p(X), p(Y) .
This rule explicitly states -q/2 if q/2 is not known. This can be seen with the following factsp(a ; b ; c) .
q(a,b ; b,c) .
The answer set explicitly contains all combinations of a, b, and c. For those pairs that weren't defined (a,b and b,c) they are negated. Answer Sets
As stated above, -p and p are complements that cannot jointly hold. Any answer set that contains the pair are ineligible.-p .
p .
results in "unsatisfiable" () — there are no answer sets.{ p(a ; b) } .
-p(a) .
results in . Note that when limiting which predicates are shown (via the answer set "shows"), an atom and its negation are separate atoms that must be explicitly listed. See the [Usage] section below for an example. (You can use ±q/2 to show both q/2 and -q/2.)Usage
Classical negation is convenient when an encoding includes atoms that have opposite meaning.candidate(janie ; pete ; tommy ; zuzu) .
elected(janie) .
-elected(tommy ; zuzu) .
Candidate janie has won and is elected. Candidates tommy and zuzu have both lost and were not elected. The result for candidate pete is still undecided (unknown).(Note that it was required to specify both elected/1 and -elected/1 in the "shows" of the answer set (as "±elected/1".))
Examples
Initially it can be confusing to understand the difference between -p and not p. Think through the answer sets of the following program before you look at the result.{ p ; -p } .
q ← p .
r ← not p .
s ← -p .
t ← not -p .
(The answer containing p and -p must be eliminated by definition.)If you're ever lost or confused, create a simple example similar to (9) and leverage the power of choice rules to examine all possibilities.
Medical Diagnosis Example
Let's explore a medical diagnosis system that demonstrates the crucial difference between "known to be false" and "unknown". This example models how doctors must carefully distinguish between confirmed negative symptoms and those that simply haven't been tested for.- Basic Domain Facts: Define our patients and the symptoms we're tracking:
patient(alice ; bob ; charlie) .
symptom(fever ; cough ; fatigue) .
- Known Medical Test Results: Critical distinction between positive findings (
has_symptom) and confirmed negative results (-has_symptom): has_symptom(alice, fever) . % Alice tested positive for fever
-has_symptom(bob, fever) . % Bob tested negative for fever
has_symptom(charlie, cough) . % Charlie tested positive for cough
Note: All other symptom states are unknown. We haven't tested for them yet - Health Status Rules: Determine if someone is definitively healthy or unhealthy:
-healthy(P) ← patient(P), has_symptom(P,S) . % Any positive symptom means not healthy
healthy(P) ← patient(P), -has_symptom(P,S) : symptom(S) . % Only healthy if ALL symptoms confirmed negative
- Uncertainty Handler: Identify cases where we need more information:
needs_further_tests(P) ←
patient(P),
not healthy(P), % Not known to be healthy
not -healthy(P) . % Not known to be unhealthy
- Treatment Protocol: Action items based on our knowledge state:
recommend_treatment(P) ← patient(P), -healthy(P) . % Confirmed unhealthy - needs treatment
monitor_only(P) ← patient(P), healthy(P) . % Confirmed healthy - just monitor
continue_diagnosis(P) ← needs_further_tests(P) . % Uncertain - more tests needed
{| recommend_treatment/1 |
|---|
| alice |
| charlie |
} - Alice: Has a confirmed fever (
has_symptom(alice, fever)). This triggers the first rule about health status, marking her as definitely not healthy (-healthy(alice)). This in turn leads to recommend_treatment(alice). - Charlie: Similar to Alice - has a confirmed cough, so is definitely not healthy and needs treatment.
- Bob: This is where it gets interesting! We know Bob definitely doesn't have a fever (
-has_symptom(bob, fever)), but we have no information about cough or fatigue. The solver shows needs_further_tests(bob) and continue_diagnosis(bob) because: - We can't conclude he's healthy (would need confirmed negatives for all symptoms)
- We can't conclude he's unhealthy (no confirmed positive symptoms)
- This uncertainty triggers our "needs more tests" rule resulting in
continue_diagnosis
This example demonstrates why classical negation is so powerful in real-world reasoning:- Default negation (
not has_symptom(…)) means "we haven't observed this symptom" - Classical negation (
-has_symptom(…)) means "we've confirmed this symptom is absent"
In medical diagnosis, this distinction is crucial — the absence of evidence (not seeing a symptom) is very different from evidence of absence (confirming a symptom is not present).
Aside: The Power of Choice Rules for Understanding
What's truly exciting about ASP is that if you're ever confused by a complex rule, you can break it down into its simplest form and use choice rules to explore all possible cases. It's like having a logic laboratory where you can experiment!For example, take this rule from our medical diagnosis system (12)healthy(P) ← patient(P), -has_symptom(P,S) : symptom(S) .
Let's strip it down to its bare essence and explore:thing(x) .
prop(p1; p2) .
% Allow all combinations for both properties
{ has_prop(X,P) ; -has_prop(X,P) } ← thing(X), prop(P) .
% The rule we want to understand - must have ALL properties negative
good(X) ← thing(X), -has_prop(X,P) : prop(P) .
The answer sets show us every possible combination, making it crystal clear that good(x) only appears when all properties are explicitly negative. This is incredibly powerful because:- You can experiment in isolation without other rules interfering
- The choice rules generate all possible scenarios automatically
- You can see exactly when your rule fires and when it doesn't
- It's like having a microscope for your logic!
This isn't just debugging — it's a way to deeply understand how ASP rules work. You're not just fixing problems, you're building intuition. And that's what makes ASP such a powerful tool for knowledge representation. You can always lift the hood and see exactly how things work!
Classical Negation vs Constraints
While classical negation and constraints may seem similar at first, they serve different purposes. Let's explore the difference:- Using classical negation:
- Using constraints:
The results look similar, but the key difference emerges when we try to reason about b. Let's add a rule to detect when we have explicit knowledge about an atom's status:knows_status(X) ← p(X).
knows_status(X) ← -p(X).
When used with (17) the results are .Compare this with constraints (18) With classical negation, we can determine that we explicitly know b's status (it's negative). With constraints, we simply prevent b from having property p, but we can't reason about that fact directly.This distinction becomes crucial in knowledge representation where we need to:- Explicitly reason about both positive and negative facts
- Distinguish between "known to be false" and "prevented from being true"
- Build upon our knowledge of negative facts
The medical diagnosis example above demonstrates this — we need to explicitly represent negative test results (-has_symptom), not just prevent certain symptoms from appearing.
Remarks
Note that -⊤ and -⊥ are not valid atoms and using them will result in an error from the solver.q ← -⊤ .
r ← not -⊤ .
s ← -⊥ .
t ← not -⊥ .
Takeaways
Classical negation in ASP provides a crucial capability that complements default negation:- Explicit Falsity: While default negation (
not) handles "absence of evidence", classical negation (-) expresses "evidence of absence". This distinction is vital for accurate knowledge representation in real-world domains like medical diagnosis. - Knowledge Representation: Classical negation enables explicit representation of negative facts, allowing programs to reason about what is known to be false rather than just what is unknown. This maps naturally to human reasoning patterns.
- Complementary Predicates: The relationship between an atom and its classical negation is automatically enforced - they cannot both be true in any answer set. This provides a natural way to represent mutually exclusive states.
- Flexibility with Uncertainty: Using both forms of negation allows ASP programs to handle three-valued logic: true (
p), false (-p), and unknown (neither p nor -p). This matches many real-world scenarios where complete information isn't available.
The power of classical negation lies not just in what it can express, but in how naturally it maps to human reasoning about certainty and uncertainty. When combined with ASP's other features like default negation and choice rules, it enables elegant solutions to complex knowledge representation challenges.Remember McCarthy's railway crossing example: sometimes knowing something is definitely false is very different from simply not knowing if it's true. Classical negation gives ASP the power to make this critical distinction.
