6. Equivalent Transformations of Fuzzy Sectioned Matrices
6.1. Finding Prime Disjunctions
The problem of finding prime disjunctions has the same significance as that
in the boolean case since once we have found prime disjunctions we can solve
many other problems. In this section we consider a method for generating
prime disjunctions which is based on the operation of fuzzy resolution.
Prime disjunctions are always defined in relation to some fuzzy distribution
which is supposed to be represented by a fuzzy CNF. In other words, a disjunction
may be prime in relation to one fuzzy distribution and it may be not prime
in relation to another fuzzy distribution. Prime disjunction is a disjunction
which is a consequence of the corresponding fuzzy distribution but is not
a consequence of any other disjunction (among those which are a consequence
of this distribution). Thus prime disjunction is in a certain sense the most
strong disjunction among those which can represent the corresponding fuzzy
distribution, i.e., those which can be added to the CNF without the distribution
change. If a prime disjunction is in a reduced form then it can be shown that
if any its component is decreased then new disjunction is already not a consequence
of the corresponding distribution, i.e., no one component of a prime disjunction
in a reduced form can be decreased..
The method of finding prime disjunctions based on the resolution operation
consists in applying the resolution to different disjunctions from the CNF
on different variables, adding the resolvents obtained to the CNF and absorbing
disjunctions which are a consequence of other disjunctions in this CNF. The process
is stopped when any new resolvent is absorbed, i.e., no new resolvent can
be generated. The main problem in this method is in which order to apply
the resolution. According to the breadth first approach the resolution
is applied to all disjunction pairs in the current CNF and new resolvents
are added to the end of this CNF but the resolution is not applied to them.
After the generation phase the process of absorption is carried out when
all disjunctions which are a consequence of any other are removed from the
CNF. After that new generation-absorption pass is started until no new
resolvents can be generated. Obviously, before generating each new resolvent
we check if two disjunctions are adjacent and if yes then after the resolvent
is built we check if it is not a consequence of some disjunction already in
the CNF. The whole process is shown in Fig. 7.
|
Fig. 7. Breadth first strategy of generating prime
disjunctions.
For example, if we have a fuzzy CNF represented by means of the sectioned
matrix (1, 2 and 3 are disjunctions)
| D = |
{0.3, 0} |
{1, 0.5, 0} |
{0, 0, 0, 0} |
1 |
| {0, 0} |
{0, 0.4, 1} |
{0, 0.2, 0.7, 1} |
2 |
| {0, 1} |
{0, 0, 0} |
{1, 0.3, 0, 0} |
3 |
then the generation of resolvents at the first pass results in the matrix
| D1 = |
{0.3, 0} |
{1, 0.5, 0} |
{0, 0, 0, 0} |
1 |
| {0, 0} |
{0, 0.4, 1} |
{0, 0.2, 0.7, 1} |
2 |
| {0, 1} |
{0, 0, 0} |
{1, 0.3, 0, 0} |
3 |
| {0.3, 0} |
{0, 0.4, 0} |
{0, 0.2, 0.7, 1} |
4=1<x2>2 |
| {0, 0} |
{1, 0.5, 0} |
{1, 0.3, 0, 0} |
5=1<x1>3 |
| {0, 1} |
{0, 0.4, 1} |
{0, 0.2, 0, 0} |
6=2<x3>3 |
No one disjunction in this matrix can be absorbed therefore it is taken as
an input of the pass 2. During the pass 2 we generate only one disjunction
7
-- other generated disjunctions are absorbed by the disjunctions which are already
in the matrix. For example, the resolvent 2<x2>5
is absorbed by the disjunction 4 and is not added to the matrix. The
disjunction 7 does not absorbs previous disjunctions 1-6
and the pass 2 is finished with the matrix
| D2 = |
{0.3, 0} |
{1, 0.5, 0} |
{0, 0, 0, 0} |
1 |
| {0, 0} |
{0, 0.4, 1} |
{0, 0.2, 0.7, 1} |
2 |
| {0, 1} |
{0, 0, 0} |
{1, 0.3, 0, 0} |
3 |
| {0.3, 0} |
{0, 0.4, 0} |
{0, 0.2, 0.7, 1} |
4=1<x2>2 |
| {0, 0} |
{1, 0.5, 0} |
{1, 0.3, 0, 0} |
5=1<x1>3 |
| {0, 1} |
{0, 0.4, 1} |
{0, 0.2, 0, 0} |
6=2<x3>3 |
| {0.3, 1} |
{0, 0.4, 0} |
{0, 0.2, 0, 0} |
7=3<x3>4 |
During the pass 3 we generate only one disjunction (the disjunction 7 has to
be transformed to the 2-nd reduced form)
| {0, 1} |
{0, 0.4, 0.3} |
{0, 0.2, 0, 0} |
8=6<x2>7 |
which absorbs its premises -- disjuncts 6 and 7. Thus we obtain
the matrix
| D3 = |
{0.3, 0} |
{1, 0.5, 0} |
{0, 0, 0, 0} |
1 |
| {0, 0} |
{0, 0.4, 1} |
{0, 0.2, 0.7, 1} |
2 |
| {0, 1} |
{0, 0, 0} |
{1, 0.3, 0, 0} |
3 |
| {0.3, 0} |
{0, 0.4, 0} |
{0, 0.2, 0.7, 1} |
4=1<x2>2 |
| {0, 0} |
{1, 0.5, 0} |
{1, 0.3, 0, 0} |
5=1<x1>3 |
| {0, 1} |
{0, 0.4, 0.3} |
{0, 0.2, 0, 0} |
8=6<x2>7 |
Each pair of disjunctions from this matrix generates a resolvent which is
absorbed by some other disjunction. So we cannot generate more disjunctions and
the process is stopped. Thus we obtained the final matrix D3
which consists of 6 prime disjunctions.
6.2. Transforming Matrix into the Dual Form
Let us consider only transformation of DNF into CNF. The back transformation
is carried out in the dual way. This problem is formulated as follows.
There is a sectioned matrix C consisting of fuzzy conjunctions and
representing a fuzzy DNF. It is necessary to transform it into the matrix
of disjunctions D interpreted as a CNF and characterized by the same
fuzzy distribution.
This procedure is based on the operation of adding the conjunction c
to the disjunction d which results in the CNF D:
(c1 AND c2 AND ... AND cn)
OR (d1 OR d2 OR ... OR dn)
= D
It can be proved that this operation results in n disjunctions:
((d1 OR c1) OR d2
OR ... OR dn) AND
(d1 OR (d2 OR c1)
OR ... OR dn) AND
--/--/--/--
(d1 OR d2 OR ... OR (dn
OR c1))
or in the sectioned matrix form
| D = |
(d1 OR c1)
|
d2
|
...
|
dn
|
|
d1
|
(d2 OR c1)
|
...
|
dn
|
|
...
|
...
|
...
|
...
|
|
d1
|
d2
|
...
|
(dn OR c1)
|
Thus to add the conjunction c to the disjunction d we have to copy
d
n times and for each i-th copy di fulfill the transformation:
dii = dii
OR ci
Note that if the disjunction d consists of only 0 (complete inconsistency)
then we obtain the procedure for transforming the DNF consisting from a
single conjunction into the CNF.
For example the conjunction
| {1, 1} |
{0, 0.5, 1} |
{1, 0.7, 0.2, 0} |
being added to the disjunction
| {1, 0} |
{0, 0.8, 0} |
{0, 0.4, 0.9, 1} |
results in the matrix
| D = |
{1, 1}
|
{0, 0.8, 0}
|
{0, 0.4, 0.9, 1}
|
|
{1, 0}
|
{0, 0.8, 1}
|
{0, 0.4, 0.9, 1}
|
|
{1, 0}
|
{0, 0.8, 0}
|
{1, 0.7, 0.9, 1}
|
Obviously the first disjunction can be removed from the matrix since it is
absolutely valid (its constant is equal to 1).
In general, before generating i-th disjunction di at
the i-th step it is natural to check if the section ci
is present (i.e., it is not equal to the constant 1) and if the disjunction
di
OR ci is not valid.
The procedure of transforming DNF into CNF is based on the operation
of adding a conjunction to a disjunction. At each step of this procedure we add
new conjunction from the DNF to all disjunctions from the CNF. At the beginning
we add the first conjunction from the DNF to the empty CNF which involves
only one disjunction consisting of all 0. The number of disjunctions in the matrix
D
grows very quickly therefore it is necessary to carry out periodically
the procedure of absorption.
For example, let us suppose that we have to transform the matrix of
DNF
| C = |
{0.3, 1} |
{1, 0.5, 0} |
{0, 1, 1, 0} |
c1 |
| {0, 1} |
{0, 0.4, 1} |
{0, 0, 0, 1} |
c2 |
| {1, 0} |
{1, 1, 0} |
{1, 0.3, 0, 0} |
c3 |
consisting of three conjunctions c1, c2
and c3 into the matrix of CNF. The whole procedure consists
of 3 steps. At each step we add to the DNF one conjunction from C.
Thus at the first step we transform the conjunction c1 into
the matrix of DNF, i.e., we add this conjunction to the initial disjunction consisting
of all 0. This results in the matrix
| D1 = |
{0.3, 1} |
{0, 0, 0} |
{0, 0, 0, 0} |
1 |
| {0, 0} |
{1, 0.5, 0} |
{0, 0, 0, 0} |
2 |
| {0, 0} |
{0, 0, 0} |
{0, 1, 1, 0} |
3 |
At the second step we have to add the conjunction c2 to
the matrix D1, i.e., this conjunction have to be added to
each disjunction from D1. First, we make 3 copies of each
of our disjunctions
| D2 = |
{0.3, 1} |
{0, 0, 0} |
{0, 0, 0, 0} |
1 |
| {0.3, 1} |
{0, 0, 0} |
{0, 0, 0, 0} |
1 |
| {0.3, 1} |
{0, 0, 0} |
{0, 0, 0, 0} |
1 |
| {0, 0} |
{1, 0.5, 0} |
{0, 0, 0, 0} |
2 |
| {0, 0} |
{1, 0.5, 0} |
{0, 0, 0, 0} |
2 |
| {0, 0} |
{1, 0.5, 0} |
{0, 0, 0, 0} |
2 |
| {0, 0} |
{0, 0, 0} |
{0, 1, 1, 0} |
3 |
| {0, 0} |
{0, 0, 0} |
{0, 1, 1, 0} |
3 |
| {0, 0} |
{0, 0, 0} |
{0, 1, 1, 0} |
3 |
Then we impose on them with the operation OR the corresponding section
of the conjunction c2
| D2 = |
{0.3, 1} OR {0, 1} |
{0, 0, 0} |
{0, 0, 0, 0} |
1.1 |
| {0.3, 1} |
{0, 0, 0} OR {0, 0.4, 1} |
{0, 0, 0, 0} |
1.2 |
| {0.3, 1} |
{0, 0, 0} |
{0, 0, 0, 0} OR {0, 0, 0, 1} |
1.3 |
| {0, 0} OR {0, 1} |
{1, 0.5, 0} |
{0, 0, 0, 0} |
2.1 |
| {0, 0} |
{1, 0.5, 0} OR {0, 0.4, 1} |
{0, 0, 0, 0} |
2.2 |
| {0, 0} |
{1, 0.5, 0} |
{0, 0, 0, 0} OR {0, 0, 0, 1} |
2.3 |
| {0, 0} OR {0, 1} |
{0, 0, 0} |
{0, 1, 1, 0} |
3.1 |
| {0, 0} |
{0, 0, 0} OR {0, 0.4, 1} |
{0, 1, 1, 0} |
3.2 |
| {0, 0} |
{0, 0, 0} |
{0, 1, 1, 0} OR {0, 0, 0, 1} |
3.3 |
and finally we obtain the matrix (disjunctions 1.2 , 1.3 are
absorbed by the dijsunct 1.1, i.e., the disjunction 1
has not changed)
| D2 = |
{0.3, 1} |
{0, 0, 0} |
{0, 0, 0, 0} |
1.1 |
| {0, 1} |
{1, 0.5, 0} |
{0, 0, 0, 0} |
2.1 |
| {0, 0} |
{1, 0.5, 1} |
{0, 0, 0, 0} |
2.2 |
| {0, 0} |
{1, 0.5, 0} |
{0, 0, 0, 1} |
2.3 |
| {0, 1} |
{0, 0, 0} |
{0, 1, 1, 0} |
3.1 |
| {0, 0} |
{0, 0.4, 1} |
{0, 1, 1, 0} |
3.2 |
| {0, 0} |
{0, 0, 0} |
{0, 1, 1, 1} |
3.3 |
After adding to the matrix D2 the third conjunction c3
we obtain the final matrix D3 which is equivalent to
the source matrix of conjunctions C:
| D3 = |
{0.3, 1} |
{1, 1, 0} |
{0, 0, 0, 0} |
1.1.2 |
| {0.3, 1} |
{0, 0, 0} |
{1, 0.3, 0, 0} |
1.1.3 |
| {0, 1} |
{1, 1, 0} |
{0, 0, 0, 0} |
2.1.2 |
| {0, 1} |
{1, 0.5, 0} |
{1, 0.3, 0, 0} |
2.1.3 |
| {1, 0} |
{1, 0.5, 1} |
{0, 0, 0, 0} |
2.2.1 |
| {0, 0} |
{1, 0.5, 1} |
{1, 0.3, 0, 0} |
2.2.3 |
| {1, 0} |
{1, 0.5, 0} |
{0, 0, 0, 1} |
2.3.1 |
| {0, 0} |
{1, 1, 0} |
{0, 0, 0, 1} |
2.3.2 |
| {0, 0} |
{1, 0.5, 0} |
{1, 0.3, 0, 1} |
2.3.3 |
| {0, 1} |
{1, 1, 0} |
{0, 1, 1, 0} |
3.1.2 |
| {0, 1} |
{0, 0, 0} |
{1, 1, 1, 0} |
3.1.3 |
| {1, 0} |
{0, 0.4, 1} |
{0, 1, 1, 0} |
3.2.1 |
| {0, 0} |
{0, 0.4, 1} |
{1, 1, 1, 0} |
3.2.3 |
| {1, 0} |
{0, 0, 0} |
{0, 1, 1, 1} |
3.3.1 |
| {0, 0} |
{1, 1, 0} |
{0, 1, 1, 1} |
3.3.2 |
This matrix can be further transformed, for example, disjunction 1.1.2
is absobed by 2.1.2 and should be removed.
© Copyright 1997, Alexandr
A. Savinov