## Abstract

We study properties of rough sets, that is, approximations to sets of records in a database or, more formally, to subsets of the universe of an information system. A rough set is a pair 〈L, U〉 such that L, U are definable in the information system and L ⊆ U. In the paper, we introduce a language, called the language of inclusion-exclusion, to describe incomplete specifications of (unknown) sets. We use rough sets in order to define a semantics for theories in the inclusion-exclusion language. We argue that our concept of a rough set is closely related to that introduced by Pawlak. We show that rough sets can be ordered by the knowledge ordering (denoted ≤_{kn}). We prove that Pawlak's rough sets are characterized as ≤_{kn}-greatest approximations. We show that for any consistent (that is, satisfiable) theory T in the language of inclusion-exclusion there exists a ≤_{kn}-greatest rough set approximating all sets X that satisfy T. For some classes of theories in the language of inclusion-exclusion, we provide algorithmic ways to find this best approximation. We also state a number of miscellaneous results and discuss some open problems.

Original language | English |
---|---|

Pages (from-to) | 389-409 |

Number of pages | 21 |

Journal | Fundamenta Informaticae |

Volume | 39 |

Issue number | 4 |

DOIs | |

State | Published - Sep 1999 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- Algebra and Number Theory
- Information Systems
- Computational Theory and Mathematics