Logics for Sizes with Union or Intersection
Abstract
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.
Cite
Text
Kisby et al. "Logics for Sizes with Union or Intersection." AAAI Conference on Artificial Intelligence, 2020. doi:10.1609/AAAI.V34I03.5677Markdown
[Kisby et al. "Logics for Sizes with Union or Intersection." AAAI Conference on Artificial Intelligence, 2020.](https://mlanthology.org/aaai/2020/kisby2020aaai-logics/) doi:10.1609/AAAI.V34I03.5677BibTeX
@inproceedings{kisby2020aaai-logics,
title = {{Logics for Sizes with Union or Intersection}},
author = {Kisby, Caleb and Blanco, Saúl A. and Kruckman, Alex and Moss, Lawrence S.},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2020},
pages = {2870-2876},
doi = {10.1609/AAAI.V34I03.5677},
url = {https://mlanthology.org/aaai/2020/kisby2020aaai-logics/}
}