Boolean dependence logic and partially-ordered connectives

摘要

We introduce a new variant of dependence logic (D) called Boolean dependence logic (BD). In BD dependence atoms are of the type =(x1,…,xn,α), where α is a Boolean variable. Intuitively, with Boolean dependence atoms one can express quantification of relations, while standard dependence atoms express quantification over functions. We compare the expressive powers of BD to D and first-order logic enriched by partially-ordered connectives, FO(POC). We show that the expressive power of BD and D coincide. We define natural syntactic fragments of BD and show that they coincide with the corresponding fragments of FO(POC) with respect to expressive power. We then show that the fragments form a strict hierarchy. We also gain a new characterization for SNP.