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
Hypothesis space H

Find H ⊆ H such that:

T ∪ H ⊨ O (H explains O)
T ∪ H ⊬ ⊥ (H is consistent with T)
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.

Symbol	Unicode	Name	Meaning
⊨	U+22A8	Entails	Logical consequence
←	U+2190	Rule	If body then head
H	—	Hypothesis	Explanation
O	—	Observation	Given data
T	—	Theory	Background knowledge
⊥	U+22A5	Inconsistent	Contradiction

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. Multiple solutions typical (hypothesis selection). Non-monotonic: new observations may invalidate explanations. Probabilistic abduction: Bayesian reasoning.

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

Limitations. Multiple explanations problem. Computational hardness. Preference criteria not always clear. Ignoring unlikely hypotheses. Integration with learning. Iterated abduction (revising hypotheses). Open-world assumption issues.