Logics for Sizes with Union or Intersection


  • Caleb Kisby Indiana University
  • Saul Blanco Indiana University
  • Alex Kruckman Wesleyan University
  • Lawrence Moss Indiana University




This paper presents the most basic logics for reasoning about the sizes of sets that admit either the union of terms or the intersection of terms. That is, our logics handle assertions All x y and AtLeast x y, where x and y are built up from basic terms by either unions or intersections. We present a sound, complete, and polynomial-time decidable proof system for these logics. An immediate consequence of our work is the completeness of the logic additionally permitting More x y. The logics considered here may be viewed as efficient fragments of two logics which appear in the literature: Boolean Algebra with Presburger Arithmetic and the Logic of Comparative Cardinality.




How to Cite

Kisby, C., Blanco, S., Kruckman, A., & Moss, L. (2020). Logics for Sizes with Union or Intersection. Proceedings of the AAAI Conference on Artificial Intelligence, 34(03), 2870-2876. https://doi.org/10.1609/aaai.v34i03.5677



AAAI Technical Track: Knowledge Representation and Reasoning