Dependence, Independence, and Incomplete Information
Erich Grädel, Jouko Väänánen · RWTH Publications (RWTH Aachen) · 2012
Dependence logic, introduced by Väänänen, is the extension of first-order logic by atomic statements about (functional) dependencies of variables. An important feature of this logic is a model-theoretic semantics that, contrary to Tarski semantics, is not based on single assignments (mapping variables to elements of a structure) but on sets of assignments. Sets of assignments are called teams and the semantics is called team semantics. By focussing on independence rather than depencence, we have proposed a new logic, called independence logic, based on atomic formulae x ⊥z y which intuitively say that the variables x are independent from the variables y whenever the variables z are kept constant. We show that x ⊥z y gives rise to a natural logic capable of formalizing basic intuitions about independence and dependence. We contrast this with dependence logic and show that independence logic has strictly more expressive power. Further, we will discuss game-theoretic semantics, expressive power, and complexity of dependence and independence logic. 1.