Indiscernibility and Complementarity
Relations in Information Systems

Stéphane Demri

Laboratoire LEIBNIZ - C.N.R.S.
46 av.Félix Viallet
38000 Grenoble

Ewa Orlowska

Institute of Telecommunications
Szachowa 1
04-894 Warsaw

Dimiter Vakarelov

Department of Mathematical Logic with Laboratory for Applied Logic
Faculty of Mathematics and Computer Science
Sofia University
blvd James Bouchier 5
1126 Sofia


We present logical systems for an analysis of data that have the form of descriptions of some objects of an application domain in terms of their attributes. We analyse two types of relationships among objects referred to as indiscernibility and complementarity. We present a modal logic LIC for reasoning about indiscernibility, complementarity and relationships between them. We define a Kripke-style semantics for LIC as well as semantics determined by information systems. We present a sound and complete deduction system for LIC. We also investigate the complexity of the satisfiability problem for LIC.

Bibtex Entry