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.