The logic of informational independence and finite models
Gabriel Sandu · Logic Journal of IGPL · 1997
In this paper we relax the assumption that the logical constants of ordinary first-order logic be linearly ordered. As a consequence, we shall have formulas involving not only partially ordered quantifiers, but also partially ordered connectives. The resulting language, called the language of informational independence (II-language, for short) will be given an interpretation in terms of games of imperfect information. The II-logic will be seen to have some interesting properties: (I) It is very natural to define in this logic two negations, weak negation as failure to verify a sentence, and strong negation as the existence of a falsifying strategy: (ii) One can express in this logic complete problems of finite structures, like the non-connectedness and 3-colorability of finite graphs, the satisfiability problem for Boolean circuits built up from NAND-gates, etc.