Why withdrawal is different from adding a fact
A rule-based assistant may conclude that a device needs inspection because either a sensor reports heat or a technician reports smoke. If the sensor is later found faulty, the conclusion should remain if the smoke report is still reliable. Conversely, a conclusion supported only by the faulty sensor must be withdrawn. Deleting every conclusion reached after the sensor report is too aggressive: a conclusion can have more than one independent derivation. Keeping everything once inferred is too permissive.
We will specify a small truth-maintenance service whose answers are defined by recomputation. This gives a correctness target for more efficient incremental implementations. It uses positive rules and a finite vocabulary; it does not model negation, probabilities, or contradictory expert testimony. The facts below are toy examples, not device-safety instructions.
Grounded meaning of a rule base
Definition 17.1.1
(Rules and the consequence operator)
Let be a finite set of atoms, the currently accepted assumptions, and a finite collection of rules with finite body and head . An empty body is allowed and represents an unconditional rule. Define
Definition 17.1.2
(Closed sets and the grounded closure)
Call closed if every rule with has .
Start with and calculate . Because the operator is monotone, this sequence grows; because is finite, it eventually stabilizes. Write its stable value as for the fixed rule base . The empty start matters: rules may refer to one another, and we accept a cyclic conclusion only when some derivation is ultimately rooted in a current assumption or an unconditional rule.
Theorem 17.1.3
(Recomputation gives the least closed set)
For finite and positive rules as above, iteration stabilizes after at most strict increases. Its result contains , is closed under every rule, and is contained in every closed set containing . In particular, if , then .
Proof
Proof
(Monotone iteration and leastness)
Monotonicity means implies . Since , induction gives . Each strict increase adds at least one atom, so at most strict increases are possible. Once , applying the same operator again leaves the sequence constant, so it stabilizes at a fixed point. At the fixed point , assumptions are included and each rule with its body in has its head there.
Let contain and be closed under the rules. Then . If , : the assumptions lie in , and closure puts every applicable rule head in . Thus . Induction gives . For , the set is closed and contains , so leastness gives the final inclusion. Retraction cannot create a positive-rule conclusion in this model; this property need not hold when default negation is added.
Proof X-ray
Why a fixed point is not enough
A circular set of atoms can satisfy all the implications while having no grounding. Starting from the empty set selects the least fixed point, rather than an arbitrary self-supporting one. The monotonicity claim concerns positive rules; an absence test would change the argument.
A precise update contract
Store the rules unchanged and track accepted assumption identifiers. After removing an identifier, construct the remaining assumption set and recompute from the empty set. The atoms to retract from the previous display are exactly . If two independent observations assert the same atom, removing one identifier must not remove the atom from while the other remains. Conversely, two copied database rows from one observation should not be counted as independent evidence. The mapping from identifiers to underlying events is a data-provenance decision, separate from the closure calculation.
One can record the firing stage of each newly derived atom as a compact explanation: each rule body was already available at an earlier stage. Such a trace proves that the atom is in the closure, but a single trace does not list all alternative explanations. A practical incremental algorithm may use dependency indexes and support information, but it must produce the same answer as recomputation after every update. Merely retaining an atom because an old justification points to another retained atom does not meet this contract.
Common mistake
(Confusing event identifiers with atoms)
Two errors arise in the mapping from events to atoms. If atom is asserted by identifiers and and the system deletes when is withdrawn, it removes a conclusion that is still grounded. Conversely, if rows and are copies of one sensor report, withdrawing the report must withdraw both rows; counting them as independent evidence leaves in the assumption set through row .
Worked example: alternate routes
Worked example 17.1.4
(Alternate routes to one conclusion)
Let and let the rules be , , and . Thus and are separately accepted reports, is an intermediate conclusion, and is a candidate for inspection. Starting from empty, the successive sets are
Remove but retain . Recomputing yields , then , then , then . Only disappears: still grounds , which grounds . Remove as well and the closure becomes empty. The last operation removes from the previous display. This example explains why an update must examine alternate derivations, not just reverse the first trace that produced .
Worked example 17.1.5
(Conjunctive and alternative supports)
Let with rules , , and . The closure is . Withdraw , so . Starting from empty, the successive sets are , , , , and the last is stable. The atom disappears, because its only rule needs both and ; and survive, because still grounds . A body of several atoms thus behaves as a conjunction of supports, while several rules with the same head behave as alternatives.
Worked example 17.1.6
(Assumptions, derivable atoms and unconditional rules)
Let with rules and . Then , where arrives at the first step from the empty-body rule. Withdraw the assumption alone: and the iteration gives , , , so remains, now as a derived atom. Withdraw instead: and , so only disappears. Withdraw both: and , because an unconditional rule needs no assumption.
Concept lensStructural
Evidence, inference and action
The closure says which atoms follow from the model and currently accepted inputs. It does not establish that a report is reliable or authorize a physical action. A separate evidence policy decides which inputs to accept; a separate action policy decides what to do with the conclusions.
The cycle that defeats naive support counts
A derivation must start from something outside the conclusions themselves. An updater that only counts how many rules currently support an atom does not check this, as the next case shows.
Counterexample mode
Mutual support is not a foundation
Let with rules and . Initially . Now withdraw , so . Starting from empty derives nothing, hence . A naive updater that keeps each old atom whenever some rule for it has a currently kept body (equivalently, its count of currently satisfied supporting rules is positive) can retain both: appears supported by and by . That set is closed, but is not the least closed set. Counts alone, without a mechanism to remove ungrounded cycles, cannot certify the correct result.
This does not forbid cycles. If an independent assumption remains and is also a rule, then and are both grounded after itself is withdrawn. The question is whether a finite derivation starts at a remaining assumption or an empty-body rule, not whether a dependency graph has a cycle.
Common mistake
(Assuming that retraction only removes conclusions)
In this model, implies . The property fails as soon as a rule can test for absence, which is outside the positive model above. A rule reading " and no implies " gives but derives after is withdrawn. A retraction-only update algorithm must not be reused for such rules.
Exercises
Exercise 17.1.7
(Let and rules , , and . Find the closure, then the closure after withdrawing . Which atoms disappear?)
Foundation
Solution(3)
- 1
Closure before withdrawal
From the empty set the iteration gives , then , because already fires and fires. The initial closure is .
- 2
Closure after withdrawing p
Key step
The remaining assumption is . The rule still applies, but does not. The closure is .
Because: Only the assumption remains, and has a two-atom body.
- 3
Compare the two closures
The atoms and disappear. The alternative route preserves .
Quick check
(Let and rules , , . Withdraw . Explain why retaining by mutual support is wrong. What changes if the rule is also present?)
Solution · Answer
With no remaining assumptions or empty-body rules, iteration from empty stays empty. Thus neither nor is grounded, even though the set is closed. If is added, the first iteration derives , the next derives , and the closure is .
Quick check
(An input atom is asserted by independent event identifiers 17 and 18. A programmer deletes as soon as identifier 17 is withdrawn. Explain the error and propose a correct representation of the inputs.)
Solution · Answer
Identifier 18 still asserts , so withdrawing 17 alone does not remove from the assumption set. Maintain a set of active event identifiers for each atom and include the atom while at least one active, independently identified event asserts it. Deduplicate copied records before applying this policy.