Reasoning about Priorities in Default Logic

Gerhard BrewkaAAAI 1994

Abstract

In nonmonotonic reasoning, conflicts between default rules are typically resolved through external priority rankings or implicit specificity. This paper proposes a framework within Default Logic where priorities are treated as first-class citizens of the logical language. By representing priorities as internal predicates, the system can reason about the rules of preference themselves, enabling the resolution of complex conflicts found in domains like legal reasoning where factors such as authority and recency override simple specificity.

Introduction

Nonmonotonic reasoning allows for "defaults"—rules that are assumed true in the absence of evidence to the contrary. A classic example is the assumption that birds fly; however, this assumption must be retracted if the bird is known to be a penguin. Standard approaches, such as Reiter’s Default Logic (DL), often produce multiple "extensions" (sets of plausible beliefs) when defaults conflict, leaving the reasoner without a clear conclusion.

To resolve these conflicts, researchers have traditionally relied on two methods: explicit manual ranking of rules or implicit specificity (where more specific information, like "penguin," automatically overrides general information, like "bird"). This paper argues that these methods are insufficient for complex domains. In legal reasoning, for instance, a newer law might override an older one (Lex Posterior), or a federal law might override a state law (Lex Superior). These priorities are not merely metadata; they are facts about the world that a system should be able to reason about dynamically.

Internalizing Priorities

The proposed framework builds upon Prioritized Default Logic (PDL) but moves the priority ordering from the meta-level into the object language. This transformation involves three core components:

  1. Naming Defaults: Each default rule is assigned a unique name (e.g., $d_1, d_2$).
  2. Priority Predicate: A special symbol ($\prec$) is introduced. The formula $d_1 \prec d_2$ signifies that $d_1$ has priority over $d_2$.
  3. The Filtering Mechanism: The system generates standard Reiter extensions and then applies a "consistency filter." An extension is considered a valid "priority extension" only if it can be reconstructed using a rule-application order that is compatible with the priority information contained within that extension.

This creates a reflective system where the conclusions reached by the logic must justify the order in which those conclusions were derived. If an extension claims $d_1$ is superior to $d_2$, but the reasoning process applied $d_2$ first, that extension is discarded as inconsistent.

The utility of this approach is demonstrated through a legal scenario involving the Uniform Commercial Code (UCC) and the Ship Mortgage Act (SMA). This case presents a conflict between two principles:

  • Lex Posterior: Newer laws override older ones.
  • Lex Superior: Higher-authority laws (federal) override lower-authority laws (state).

In this scenario, the UCC is newer, but the SMA is a federal act. By representing these principles as defaults themselves, the system can reason about which principle takes precedence. The logic correctly identifies that while Lex Posterior might suggest the UCC wins, the principle of Lex Superior is assigned higher priority in the knowledge base, leading the system to correctly conclude that the SMA prevails.

Key Insights and Results

By treating priorities as facts, the system allows for "priorities about priorities." This multi-layered reasoning is essential for resolving conflicts between different preference criteria (e.g., deciding whether recency or authority is more important in a specific context). Furthermore, the logic remains robust against irrelevant information; adding unrelated facts (e.g., "the bird is green") does not interfere with the core conflict resolution process.

Limitations and Future Work

The primary trade-off for this increased expressiveness is computational complexity. Generating and filtering extensions in this framework is NP-hard, posing challenges for real-time applications. The current work focuses on the semantics of the logic; future research is required to develop efficient proof procedures, potentially by focusing on restricted fragments of the logic such as Horn theories. Additionally, further comparison with contemporary nonmonotonic frameworks is needed as the field continues to evolve.

Summary updated

BibTeX
@inproceedings{brewka1994reasoning,
  author = {Gerhard Brewka},
  title = {{Reasoning about Priorities in Default Logic}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure