Information Technology Reference
In-Depth Information
g
(
w
)
≤
f
(
w
)
for all
w
∈{
0
,
1
}
q
, and
g
<
f
means that
g
≤
f
and
g
=
f
.A
w
implies
f
w
)
≤
(
)
≤
(
Boolean function
f
is positive or monotone, if
w
w
f
for
q
.
Boolean variables
x
1
,
w
∈{
all
w
,
0
,
1
}
are called litera
ls
.
A clause (resp., term) is a disjunction (resp., conjunction) of at most one of
x
i
and
x
i
for each variable. The empty disjunction (resp., conjunction) is denoted by
x
2
,...
and the complements
x
1
,
x
2
,...
↥
(resp.,
). A clause
c
(resp., term
t
) is an implicate (resp., implicant) of a function
f
,if
f
). Moreover, it is prime if there is no implicate
c
<
f
≤
c
(resp.
t
≤
c
(resp.,
no implicant
t
t
)of
f
. A conjunction normal form (CNF) (resp., disjunction
normal form (DNF)) of a function
f
is a Boolean formula of
f
which is expressed
by a conjunction of implicates (resp. disjunction of implicants) of the function, and
it is prime if all its members are prime. The complete CNF (resp. DNF) of
f
is the
conjunction of all prime implicates (resp. disjunction of all prime implicants) of
f
.
When
f
is positive, there is the unique CNF (resp. DNF) of
f
which is the complete
CNF (resp. DNF) of
f
.
First, we associate conditions (
L
)(or(
P
)) and (
U
)(or(
B
)) with the conditions
of the generalized decision function. As mentioned in the previous section, condi-
tion (
U
) is equivalent to (
G
).
>
Lemma 1
([
23
,
50
])
Let A be a subset of C . We have the following statements.
•
Condition
(
L
)
is equivalent to:
∂
A
(
)
=
∂
C
(
)
∈
|
∂
C
(
)
|=
.
u
u
for all u
U
such that
u
1
(LG)
•
Condition
(
U
)
is equivalent to
(
G
)
, i.e.,
∂
A
(
u
)
=
∂
C
(
u
)
for all u
∈
U
.
(G)
The next lemma is the heart of the Boolean reasoning, which connects two notions:
“preserving” and “discerning”.
Lemma 2
Fo r u
∈
U , the following assertions are equivalent.
•
∂
A
(
u
)
=
∂
C
(
u
)
.
u
∈
u
)
=
∂
C
(
u
,
•∀
}
)
Hence, to preserve the generalized decision of an object
u
, we should discern
u
from other objects
u
having different generalized decisions from that of
u
.
Using Lemmas
1
and
2
, we define two Boolean formulas, called discernibility
functions. First, we define a discernibility matrix by
M
U
,(∂
C
(
u
)
⃒∃
a
∈
A
,(
u
)
∈
R
{
a
m
ij
)
i
,
j
=
1
,
2
,...,
n
, where
ij
-entry
m
ij
is a set of condition attributes which discern objects
u
i
and
u
j
,
=
(
m
ij
={
c
∈
C
|
c
(
u
i
)
=
c
(
u
j
)
}
.
Then, we define discernibility functions.
Search WWH ::
Custom Search