Logics for Sizes with Union or Intersection

Caleb Kisby, Saúl A. Blanco, Alex Kruckman, Lawrence S. MossAAAI 2020 · DOI

Abstract

In the intersection of artificial intelligence and cognitive science, the ability to reason about set sizes and relationships is fundamental. However, existing formal frameworks that handle these operations, such as Boolean Algebra with Presburger Arithmetic (BAPA), are often NP-complete, making them computationally expensive. This paper introduces two new "natural logics," $A^\cup(card)$ and $A^\cap(card)$, which focus on unions and intersections respectively. By identifying a specific fragment of set-theoretic reasoning, the authors demonstrate that it is possible to achieve mathematical completeness and polynomial-time decidability, providing a more cognitively plausible model for human-like inference.

Introduction

Human reasoning frequently involves intuitive judgments about the sizes of groups and their overlaps. For instance, if we know that all cats are mammals that purr, and that there are at least as many cats as there are purring things, we can logically conclude that all purring things must be cats. While this type of inference feels instantaneous to humans, formalizing it in a way that a computer can execute efficiently is a significant challenge.

Traditional frameworks like BAPA or CardCompLogic are highly expressive, allowing for complex combinations of negation, disjunction, and exact numerical counts. However, this power comes at the cost of being NP-complete. This paper seeks to find a "sweet spot"—a logic that is expressive enough to handle basic set operations like unions ("animals or plants") and intersections ("mammals with paws") alongside size comparisons, yet remains "computationally light" enough for real-time applications and cognitive modeling.

The Framework: $A^\cup(card)$ and $A^\cap(card)$

The researchers define two primary logical systems:

  1. $A^\cup(card)$: This logic handles subset relations (All x y) and size comparisons (AtLeast x y), where terms can be formed using unions.
  2. $A^\cap(card)$: This system mirrors the first but utilizes intersections instead of unions.

By intentionally omitting full negation (the ability to say "not x") and general disjunction (the ability to say "Sentence A OR Sentence B"), the authors collapse the computational complexity from NP-complete down to polynomial time. Despite these restrictions, the logic remains surprisingly expressive; the authors show that any complex nested union (e.g., $a \cup b \cup c$) can be represented by introducing fresh variables, maintaining the system's efficiency.

Methodology and Theoretical Innovations

To establish the validity of these logics, the authors employed several rigorous mathematical techniques:

Axiomatization and Completeness

The authors developed a set of "natural deduction" rules specifically for these fragments. These rules are reminiscent of classic syllogisms (like Barbara) but are adapted for set sizes and operations. A core contribution is the Representation Lemma, which proves that if a set of relations is consistent with these rules, a physical model (a collection of finite sets) can always be constructed to satisfy them.

The "Clamp" Operation

A novel technical contribution is the Clamp operation. This iterative method allows for the construction of models by adding elements to sets to adjust their sizes without violating existing subset relationships. This operation is crucial for proving that the logic is not just a theoretical construct but can be mapped to actual finite sets.

Complexity Analysis

Using a variant of McAllester’s Tractability Lemma, the researchers proved that determining whether a conclusion follows from a set of premises in these logics can be done in polynomial time. This makes the systems suitable for integration into larger AI architectures or SMT (Satisfiability Modulo Theories) solvers.

Key Insights

  • Duality of Operations: The authors demonstrated that reasoning about intersections is mathematically dual to reasoning about unions. By utilizing set complements, they showed that a proof of completeness for one logic automatically extends to the other.
  • Natural Logic Alignment: This work contributes to the "Natural Logic" program, which aims to model natural language inference using simple, decidable systems rather than translating language into the often-unwieldy complexity of first-order logic.
  • Extension to Strict Inequality: The system was successfully extended to include "More x y" ($|x| > |y|$) while maintaining completeness, though the specific polynomial-time bounds for this extension are still being refined.

Conclusion and Future Work

The research successfully identifies a fragment of set-theoretic logic that balances expressivity with computational efficiency. However, the authors note that the "road ends" at the inclusion of full complements; combining unions, intersections, and set complements inevitably returns the system to NP-completeness.

Future research will focus on the "pesky rule"—the difficulty of integrating both union and intersection into a single polynomial-time logic. Additionally, while $M^\cup(card)$ (the logic including "More") is complete, confirming its polynomial-time decidability remains a priority, potentially through the application of a new rule termed (DIAMOND) to bypass current limitations in proof structures.

Summary updated

BibTeX
@inproceedings{kisby2020logics,
  author = {Caleb Kisby and Saúl A. Blanco and Alex Kruckman and Lawrence S. Moss},
  title = {{Logics for Sizes with Union or Intersection}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i03.5677},
}
Figure