TY - JOUR

T1 - Equivalence and quantifier rules in logics with imperfect information

AU - Caicedo, X.

AU - Dechesne, F.

AU - Janssen, T.M.V.

PY - 2009

Y1 - 2009

N2 - In this paper, we present a prenex form theorem for a version of Independence Friendly logic, a logic with imperfect information. Lifting classical results to such logics turns out not to be straightforward, because independence conditions make the formulas sensitive to signalling phenomena. In particular, nested quantification over the same variable is shown to cause problems. For instance, renaming of bound variables may change the interpretations of a formula, there are only restricted quantifier extraction theorems, and slashed connectives cannot be so easily removed. Thus we correct some claims from Hintikka [8], Caicedo & Krynicki [3] and Hodges [11]. We refine definitions, in particular the notion of equivalence, and sharpen preconditions, allowing us to restore (restricted versions of) those claims, including the prenex form theorem of Caicedo & Krynicki [3], and, as a side result, we obtain an application to Skolem forms of classical formulas. It is a known fact that a complete calculus for IF-logic is impossible, but with our results we establish several quantifier rules that form a partial calculus of equivalence for a general version of IF-logic reflecting general properties of information flow in games.

AB - In this paper, we present a prenex form theorem for a version of Independence Friendly logic, a logic with imperfect information. Lifting classical results to such logics turns out not to be straightforward, because independence conditions make the formulas sensitive to signalling phenomena. In particular, nested quantification over the same variable is shown to cause problems. For instance, renaming of bound variables may change the interpretations of a formula, there are only restricted quantifier extraction theorems, and slashed connectives cannot be so easily removed. Thus we correct some claims from Hintikka [8], Caicedo & Krynicki [3] and Hodges [11]. We refine definitions, in particular the notion of equivalence, and sharpen preconditions, allowing us to restore (restricted versions of) those claims, including the prenex form theorem of Caicedo & Krynicki [3], and, as a side result, we obtain an application to Skolem forms of classical formulas. It is a known fact that a complete calculus for IF-logic is impossible, but with our results we establish several quantifier rules that form a partial calculus of equivalence for a general version of IF-logic reflecting general properties of information flow in games.

U2 - 10.1093/jigpal/jzn030

DO - 10.1093/jigpal/jzn030

M3 - Article

SN - 1367-0751

VL - 17

SP - 91

EP - 129

JO - Logic Journal of the IGPL

JF - Logic Journal of the IGPL

IS - 1

ER -