Boolean Extensions of Inheritance Networks

John F. Horty, Richmond H. ThomasonAAAI 1990

Abstract

Nonmonotonic inheritance networks provide a graphical formalism for default reasoning. Traditional systems, however, are limited to simple links between primitive concepts. This paper extends these networks to include complex Boolean combinations (conjunction, disjunction, and negation) of properties. We define a formal framework for defeasible inheritance over these Boolean nodes, addressing challenges in specificity and conflict resolution.

Introduction

In the late 1980s, AI researchers utilized inheritance networks to represent knowledge hierarchies where nodes denote concepts and links represent properties. While intuitive, these "austere" formalisms struggled with complex real-world relationships like "Purple mushrooms are poisonous" (conjunction) or "Members of Congress are senators or representatives" (disjunction). This work integrates Boolean operators into a unified theory of defeasible inheritance, allowing for more expressive knowledge representation while maintaining the ability to handle exceptions.

Argument Trees and Boolean Nodes

To accommodate Boolean complexity, the authors shift from linear path-based reasoning to argument trees. In this framework, properties are closed under Boolean operations ($\wedge, \vee, \neg$). Chaining these links results in tree structures rather than simple paths.

An argument tree representing the derivation of a conjunction from individual a via intermediate conclusions p and q.

Inheritability of a conclusion is determined by three core criteria:

  1. Constructibility: The argument must be derivable from existing strict and defeasible links.
  2. Conflict-freeness: The conclusion must not logically contradict other accepted information.
  3. Preemption: More specific information (e.g., "penguins don't fly") must override general defaults ("birds fly").

Reasoning with Specificity and Conflict

A significant contribution of this work is the generalization of the specificity principle to Boolean nodes. Specificity ($V < U$) is defined based on whether $V$ represents a more refined category than $U$. This ensures that detailed knowledge takes precedence over general defaults.

Graphical representation of inheritance networks with Boolean nodes, illustrating how conjunctions and negations are integrated into the graph structure.

Handling conflicts in Boolean networks is inherently more complex than in primitive networks. A set of conclusions might be individually consistent but collectively inconsistent (e.g., $\{A, B, \neg(A \wedge B)\}$). The authors employ "minimal conflict sets" to identify and resolve these indirect contradictions by tracing them back to specific defeasible links.

Results and Computational Complexity

The proposed framework successfully generalizes Touretzky’s classic inheritance definitions. It also provides a formal specification for "classifier" algorithms, which automatically place new concepts within a hierarchy even in the presence of exceptions.

However, this increased expressivity comes at a computational cost. The authors demonstrate that determining inheritability in this system is NP-complete, as it subsumes the Boolean Satisfiability Problem (SAT).

Conclusion and Future Directions

While the framework provides a rigorous proof-theoretic account of Boolean inheritance, several challenges remain. The computational intractability suggests a need for identifying "tractable fragments" of the logic. Furthermore, the current "credulous" approach—where the system picks one consistent set of beliefs—could be expanded to a "skeptical" model that only accepts conclusions true across all possible consistent interpretations. Future work will also explore model-theoretic semantics to provide a formal definition of truth for these networks.

Summary updated

BibTeX
@inproceedings{horty1990boolean,
  author = {John F. Horty and Richmond H. Thomason},
  title = {{Boolean Extensions of Inheritance Networks}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1990},
}
Figure