Abductive Logic

Origin. Peirce introduced abduction (late 19th c.). Formalized in AI by Pople, Poole (1970s-80s). Inference to best explanation. Given observation and theory, find hypothesis explaining it. Foundation for diagnosis, planning, theory formation.

Models. Reasoning from effects to causes. Deduction: theory + cause → effect. Induction: observations → theory. Abduction: theory + effect → cause. "If H explains E, and E is observed, maybe H." Hypothesis selection problem.

Formalism.

Abduction problem: Given:

• Background theory T
• Observation O
• Abducible set A (what may be assumed)

Find H ⊆ A such that:

1. T ∪ H ⊨ O (H explains O)
2. T ∪ H ⊬ ⊥ (H is consistent with T)
3. H is "best" (minimal, most probable, etc.)

Logic programming abduction: T: logic program (rules) H: abducible predicates (assumable) O: goal to explain

Find: set of ground abducibles making O true.

Preference criteria:

• Subset minimality: no smaller H works
• Cardinality minimality: fewest hypotheses
• Probability: most probable H
• Simplicity: Occam's razor

Integrity constraints: IC: rules that must not be violated. Abductive solution must satisfy ICs.

Example: T: wet_grass ← rain. wet_grass ← sprinkler. O: wet_grass. H = {rain} or H = {sprinkler} — both explain O.

Symbols.

Metatheory. Deciding whether a propositional abduction problem has any solution is Σ₂ᵖ-complete (Eiter and Gottlob 1995), not NP-complete. Two quantifier alternations are unavoidable: guessing H is existential, but verifying T ∪ H ⊨ O is itself coNP-hard. The problem drops to NP-complete when T is Horn — even acyclic Horn — because deduction and consistency are then polynomial and only the guess remains. Imposing subset-minimality does not raise the complexity for classical theories, though prioritization can push problems to the third level of the polynomial hierarchy, and abduction from default theories is harder still. Minimality is the expensive requirement rather than explanation as such: Bylander, Allemang, Tanner and Josephson (1991) showed that finding a parsimonious explanation is NP-hard already for propositional set-covering problems where finding some explanation is trivial. In the logic-programming setting the relation to deduction is exact in both directions. Console, Dupré and Torasso (1991) proved that for a class of programs the abductive explanations of an observation are recoverable from the Clark completion by ordinary deduction, and Eshghi and Kowalski (1989) ran the correspondence the other way, simulating negation as failure by abduction with negative literals treated as abducibles governed by integrity constraints.

Applies to. Medical diagnosis. Fault diagnosis. Scientific discovery. Natural language understanding. Plan recognition. Legal reasoning (evidence). Debugging programs.

Limitations. The definition fixes only that T ∪ H entails O consistently, which almost always leaves many candidate hypotheses, and no logical criterion ranks them: subset-minimality, cardinality-minimality and probability disagree on the same problem, and whichever is used must be stipulated from outside the logic. The abducible set is likewise an input; nothing decides what may be hypothesised, and enlarging it changes the answers. Explanations are required to entail, not to be relevant or causal, so any observation that is itself abducible explains itself, and such degenerate solutions must be excluded by integrity constraints supplied by hand. Abduction is non-monotonic in the observation as well as the theory, so an explanation adequate for O need not survive the arrival of a further observation, and no notion of revising rather than recomputing a hypothesis is part of the framework.

© 2026 Lingenic LLC