Definability in Logic and Rough Set Theory

Abstract

Rough set theory is an effective tool for data mining. According to the theory, a concept is definable if it can be written as a Boolean combination of equivalence classes induced from classification attributes. On the other hand, definability in logic has been explicated by Beth's theorem. In this paper, we propose two data representation formalisms, called first-order data logic (FODL) and attribute value-sorted logic (AVSL), respectively. Based on these logics, we explore the relationship between logical definability and rough set definability.