Boolean Dependence Logic and Partially-Ordered Connectives

2014/06/27 by Johannes Ebbing, Ebbing, Johannes, Lauri Hella +5
Computer Science · Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO) #Logic in Computer Science (cs.LO) #cs.LO #math.LO

paper · pdf · doi:10.48550/arxiv.1406.7132

41 pages

arxiv created 2014/06/27 · arxiv updated 2014/06/30

Abstract

We introduce a new variant of dependence logic called Boolean dependence logic. In Boolean dependence logic dependence atoms are of the type =(x₁,...,x_n,α), 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 power of Boolean dependence logic to dependence logic and first-order logic enriched by partially-ordered connectives. We show that the expressive power of Boolean dependence logic and dependence logic coincide. We define natural syntactic fragments of Boolean dependence logic and show that they coincide with the corresponding fragments of first-order logic enriched by partially-ordered connectives with respect to expressive power. We then show that the fragments form a strict hierarchy.

Related

• Hierarchies in Dependence Logic
• Axiomatizing first order consequences in dependence logic
• Computational Aspects of Dependence Logic
• Characterizing Quantifier Extensions of Dependence Logic
• On Dependence Logic