Information Technology Reference
In-Depth Information
Definition 7
Discernibility functions
F
U
and
F
L
are defined as follows:
F
U
(
˜
c
1
,...,
˜
c
m
)
=
m
ij
˜
c
,
c
∈
i
,
j
|
∂
(
u
j
)
=
∂
(
u
i
)
C
C
F
L
(
˜
c
1
,...,
˜
c
m
)
=
m
ij
˜
,
c
c
∈
i
||
∂
C
(
u
i
)
|=
1
j
|
∂
C
(
u
j
)
=
∂
C
(
u
i
)
where
c
i
is a Boolean variable corresponding to
i
th condition attribute
c
i
.
˜
c
A
c
1
,...,
˜
c
m
)
For
A
ↆ
C
, we consider a Boolean vector
˜
=
(
˜
, where,
1f
c
i
∈
A
,
c
i
˜
=
0f
c
i
∈
A
.
Let
F
U
c
A
,
the intersection of
A
and
m
ij
should not be empty by the definition of
F
U
.By
Lemma
2
, in that case,
(
˜
)
=
1. Then, for each pair
u
i
and
u
j
such that
∂
C
(
u
i
)
=
∂
C
(
u
j
)
∂
A
(
u
)
=
∂
C
(
u
)
for each
u
holds. We have the simi-
lar consequence when
F
L
c
A
(
˜
)
=
1. Therefore, the following theorem holds. Let
ˆ
A
=
{˜
c
|
c
∈
A
}
.
Theorem 2
([
43
,
45
,
50
])
Let A be a subset of C . We have the following equivalences:
A satisfies
(
G
)
, i.e.,
(
U
)
if and only if F
U
c
A
•
(
˜
)
=
1
. Moreover, A is a U-reduct in
ˆ
A
is a prime implicant of F
U
,
RSM if and only if
A satisfies
(
LG
)
, i.e.,
(
L
)
if and only if F
L
c
A
•
(
˜
)
=
1
. Moreover, A is an L-reduct
ˆ
A
is a prime implicant of F
L
.
in RSM if and only if
Definition
7
showsCNFsof
F
U
and
F
L
. The prime CNFs of the functions can be
easily obtained. Because the functions are positive, the prime implicants of the prime
DNF of each function are all of the prime implicants of the function. Therefore, all
reducts of each type appear in the prime DNF of the corresponding function. The
problem which converts the prime CNF of a positive Boolean function to its prime
DNF is called the dualization problem [
14
]. We show an example for enumerating
reducts by solving the dualization problems of the discernibility functions.
Example 6
Remember the decision table
D =
(
U
,
C
∪{
d
}
,
{
V
a
}
)
in Table
7.1
.In
Table
7.2
, we show again the decision table
D
with the generalized decision func-
tion
∂
C
.
The discernibility matrix is obtained as below. Sign
attached to objects
u
i
means
that the generalized decision of
u
i
is a singleton, or equivalently,
u
i
is in the positive
region POS
C
(
∗
d
)
.
Search WWH ::
Custom Search