Information Technology Reference
In-Depth Information
A Modal Logic for Non-deterministic
Information Systems
Md. Aquil Khan
Discipline of Mathematics,
Indian Institute of Technology Indore,
Indore 452017, India
aquilk@iiti.ac.in
Abstract.
In this article, we propose a modal logic for non-deterministic
information systems. A deductive system for the logic is presented and
corresponding soundness and completeness theorems are proved. The
logic is also shown to be decidable.
1
Introduction
Rough set theory, introduced by Pawlak in the early 1980s [17] offers an ap-
proach to deal with uncertainty inherent in real-life problems, more specifically
that stemming from inconsistency or vagueness in data. The notion of an ap-
proximation space, viz. a tuple (
U,R
), where
U
is a non-empty set and
R
an
equivalence relation, plays a crucial role in Pawlak's rough set theory. A useful
natural generalization is where the relation
R
is not necessarily an equivalence
(cf. e.g. [20,23,12]). Any concept represented as a subset (say)
X
of the domain
U
is approximated from within and outside, by its lower and upper approximations,
denoted as
X
R
and
X
R
respectively, and are defined as follows:
X
R
:=
{
x
∈
U
:
R
(
x
)
ↆ
X
}
, X
R
:=
{
x
∈
U
:
R
(
x
)
∩
X
=
∅}
,
where
R
(
x
):=
{y ∈ U
:(
x, y
)
∈ R}
.
A practical realization of approximation space is a
non-deterministic infor-
mation system
[16], formally defined as follows.
:= (
U,A,
a∈A
V
a
,F
)
,
written in brief as NIS, comprises a non-empty set U of objects, a non-empty
finite set A of attributes, a non-empty finite set
Definition 1.
A
non-deterministic information system
S
V
a
of attribute-values for each
2
a∈A
V
a
such that F
(
x, a
)
a
ↆV
a
.
In the special case when
F
(
x, a
) is singleton for each (
x, a
)
∈
A,andF
:
U
×A→
∈
U
×A
,
S
is called
a
deterministic information system
.
One may attach different interpretations with '
F
(
x, a
)=
V
'. For instance, as
exemplified in [4,5], if
a
is the attribute “speaking a language”, then
F
(
x, a
)=
{
can be interpreted as (i)
x
speaks German and English and
no other languages, (ii)
x
speaks German and English and possibly other lan-
guages, (iii)
x
speaks German or English but not both, or (iv)
x
speaks German
German, English
}
