Int. J. Fuzzy Log. Intell. Syst. 2017; 17(3): 137-144
Published online September 30, 2017
https://doi.org/10.5391/IJFIS.2017.17.3.137
© The Korean Institute of Intelligent Systems
Przemyslaw Grzegorzewski
^{1}Systems Research Institute, Polish Academy of Sciences, Warsaw, Poland, ^{2}Faculty of Mathematics and Information Science, Warsaw University of Technology, Warsaw, Poland
Correspondence to :
Przemyslaw Grzegorzewski (pgrzeg@ibspan.waw.pl)
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/3.0/) which permits unrestricted noncommercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
The problem of separability verification of fuzzy binary relations is considered. A necessary and sufficient condition for separability is given and an efficient algorithm for checking separability that can be easily applied in practice is suggested. The paper is supplemented by a simple test that sometimes might be helpful in detecting non-separability just at one glance.
Keywords: Fuzzy relation, Noninteractive fuzzy relation, Separable fuzzy relation, Connected/disconnected variables
Fuzzy relation generalize the concept of the classical relation by admitting a partial association between elements of universes of discourse [1, 2]. Hence fuzzy relations can be used for modeling more or less vague relationships between objects. They can formally be treated like fuzzy sets. The notion of fuzzy relation seems to be very natural and useful in various applications. In many cases fuzzy relations describe the actual situation more adequately than the classical ones. For instance, an association between different diseases and possible symptoms, documents and keywords, expected gain and possible states of nature, etc., are rarely of binary nature. Hence, by admitting there different intensity of association we obtain much more adequate mathematical model of the discussed problem (see, e.g., [3–5]).
Some types of relations are of special importance like fuzzy equivalence relations, fuzzy ordering relations, similarity relations, etc. (for the review and basic mathematical properties see, e.g., [10]). Separable (noninteractive) fuzzy relations are of interest in the case that one looks at a fuzzy relation
Requirements to be met for concluding that a given fuzzy binary relation is separable are not complicated. However, checking all necessary conditions might be tedious, especially if the corresponding relation matrix is large enough. Therefore, an efficient algorithm that simplifies the separability verification would be desirable. Such algorithm is suggested in this contribution.
The paper is organized as follows. In Section 2 we introduce basic notation and concepts connected with fuzzy relations. Section 3 is devoted to separable fuzzy binary relations. A simple sufficient condition showing that variables under study are connected is given in Section 4. By this result in some situations one glance might be enough to detect non-separability. Unfortunately, since this separability test is based on the sufficient condition, it cannot be conclusive generally. Therefore, in Section 5, we prove a necessary and sufficient condition for separability which gives a strong basis for the decisive criterion. The theorem is supplemented by the desired efficient algorithm for checking separability that can be easily applied in practice. The aforementioned considerations and results are illustrated by numerical examples.
A fuzzy binary relation
From now on we make the assumption that both sets
The
Thus the height is the largest intensity of the relation obtained by any pair (
We say that fuzzy binary relations
The intersection
where
where
A Cartesian product of two fuzzy sets
where
Given a fuzzy binary relation
while its
It is easily seen that dom
The domain and codomain are also called the first projection Proj
An operation, which is in some sense an inverse to the projection, is called a cylindric extension. The cylindric extension of dom
while the cylindric extension of cod
Obviously,
Moreover, it can be shown that the cylindric extensions produce the largest fuzzy relation (in the sense of inclusion) with given projection.
As it is seen from (
However, in the special case, we can uniquely reconstruct a fuzzy binary relation from its projections. It happens so if the relation is separable (see [15, 16]), noninteractive [3, 4] or orthogonal [5].
The proof of the following lemma is obvious.
i)
ii)
iii)
Separable fuzzy relations are of special interest in the case that one looks at fuzzy relation as a relationship between two variables, attributes or decision rules and with
If variables and are disconnected then the choice of the particular value
To prove that a given fuzzy binary relation
If
If
The interpretation of Lemma 4 and 5 is also straightforward since if there is no association between two variables or if all their outcomes are fully related, an information about a particular outcome of one of these variables bring no new information on the other variable.
Unfortunately, in all other cases, except of these two trivial situations, we need some time to check all necessary conditions. Therefore, an algorithm which enables to reduce the number of conditions to be checked to solve the problem of possible separability would be desirable. In next section we propose a very simple sufficient condition showing that variables under study are connected which may be used to conclude the lack of separability without any calculations, just at a glance. Then, in Section 5 we prove the necessary and sufficient condition for separability which gives us an efficient algorithm for checking separability of fuzzy binary decisions.
Let us recall that the support of a fuzzy set
Suppose, sets
Thus, the significant part of a fuzzy binary relation
In the example given above the significant part of a fuzzy relation under study is equivalent to the support of that relation but it is not a rule. For every binary fuzzy relation
Below we state a theorem that provides an easy condition to show that given a fuzzy binary relation is not separable and therefore two variables under study are connected.
Suppose the relation
i.e. there exist (
Hence dom
Theorem 7 provides a quick test for the lack of separability. Below we give its equivalent version expressed in a more useful matrix representation.
The criterion given in Corollary 8 works, of course, in one direction only: if there are no zeros in the matrix [
Although Theorem 7 specifies only the sufficient condition for separability of fuzzy binary relations, Corollary 8 could be helpful in some situations in concluding that some variables are connected. In the next section we prove the necessary and sufficient condition for separability requires more operations but solves the problem of separability definitely.
Let us start from recalling that the
It is clear that the support is simply zero
Firstly, let’s note that for any two nonempty fuzzy sets
Let us also recall the well-known fact that any two fuzzy sets
Now suppose that a fuzzy binary relation
Now, substituting dom
and combining (
Conversely, if (
One can easily notice that Theorem 7 implies from the above Theorem 9. Actually, if
Below we propose a practical and efficient algorithm for checking whether a given fuzzy binary relation is separable, based on Theorem 9. We begin from generalizing the notion of the significant part of a fuzzy relation given in Definition 6.
It is clear that zero
Now, combining Theorem 9 and the notion of the
In practice there is no need to check all
Although it is not necessary for performing the algorithm given above, it is advisable to order values in
We present the way in which our algorithm works in two examples.
for which we have domR_{2} = 0.4/x_{1}+0.7/x_{2}+1/x_{3}+0.1/x_{4} and codR_{2} = 0.3/y_{1} +1/y_{2} +0.5/y_{3} +0/y_{4} +0.9/y_{5}. Thus, the potential values to be checked are only those that appear in the domain or codomain and are smaller than 1, i.e. W = {0, 0.1, 0.3, 0.4, 0.5, 07, 0.9}. So our criteria reduces to check whether [
Sine there is no element smaller or equal to 0.1 in [
In various problems of approximate reasoning and broadly perceived decision making the information whether variables (attributes) under study are connected/noninteractive and whether the corresponding fuzzy relations are separable is of importance. Therefore, a simple test for separability of fuzzy relations is desirable. In this contribution we have suggested an efficient algorithm for checking separability based on the necessary and sufficient condition. We have also indicated a simple test for detecting interactivity based on the sufficient condition. The suggested methods could be easily applied in practice.
However, some problems in the field remain open. Firstly, in the paper we have restricted our attention to fuzzy binary relations. Therefore, a generalization of the proposed methods for more dimensions would be interesting. Secondly, in this contribution we have adopted the common assumption that the Cartesian product of fuzzy sets is defined with respect to the classical t-norm (i.e. minimum) and, consequently, the minimum operator appears in the definition of separability. However, one may consider there some other t-norms and hence discuss the notion of t-separability.
No potential conflict of interest relevant to this article was reported.
Int. J. Fuzzy Log. Intell. Syst. 2017; 17(3): 137-144
Published online September 30, 2017 https://doi.org/10.5391/IJFIS.2017.17.3.137
Copyright © The Korean Institute of Intelligent Systems.
Przemyslaw Grzegorzewski
^{1}Systems Research Institute, Polish Academy of Sciences, Warsaw, Poland, ^{2}Faculty of Mathematics and Information Science, Warsaw University of Technology, Warsaw, Poland
Correspondence to:Przemyslaw Grzegorzewski (pgrzeg@ibspan.waw.pl)
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/3.0/) which permits unrestricted noncommercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
The problem of separability verification of fuzzy binary relations is considered. A necessary and sufficient condition for separability is given and an efficient algorithm for checking separability that can be easily applied in practice is suggested. The paper is supplemented by a simple test that sometimes might be helpful in detecting non-separability just at one glance.
Keywords: Fuzzy relation, Noninteractive fuzzy relation, Separable fuzzy relation, Connected/disconnected variables
Fuzzy relation generalize the concept of the classical relation by admitting a partial association between elements of universes of discourse [1, 2]. Hence fuzzy relations can be used for modeling more or less vague relationships between objects. They can formally be treated like fuzzy sets. The notion of fuzzy relation seems to be very natural and useful in various applications. In many cases fuzzy relations describe the actual situation more adequately than the classical ones. For instance, an association between different diseases and possible symptoms, documents and keywords, expected gain and possible states of nature, etc., are rarely of binary nature. Hence, by admitting there different intensity of association we obtain much more adequate mathematical model of the discussed problem (see, e.g., [3–5]).
Some types of relations are of special importance like fuzzy equivalence relations, fuzzy ordering relations, similarity relations, etc. (for the review and basic mathematical properties see, e.g., [10]). Separable (noninteractive) fuzzy relations are of interest in the case that one looks at a fuzzy relation
Requirements to be met for concluding that a given fuzzy binary relation is separable are not complicated. However, checking all necessary conditions might be tedious, especially if the corresponding relation matrix is large enough. Therefore, an efficient algorithm that simplifies the separability verification would be desirable. Such algorithm is suggested in this contribution.
The paper is organized as follows. In Section 2 we introduce basic notation and concepts connected with fuzzy relations. Section 3 is devoted to separable fuzzy binary relations. A simple sufficient condition showing that variables under study are connected is given in Section 4. By this result in some situations one glance might be enough to detect non-separability. Unfortunately, since this separability test is based on the sufficient condition, it cannot be conclusive generally. Therefore, in Section 5, we prove a necessary and sufficient condition for separability which gives a strong basis for the decisive criterion. The theorem is supplemented by the desired efficient algorithm for checking separability that can be easily applied in practice. The aforementioned considerations and results are illustrated by numerical examples.
A fuzzy binary relation
From now on we make the assumption that both sets
The
Thus the height is the largest intensity of the relation obtained by any pair (
We say that fuzzy binary relations
The intersection
where
where
A Cartesian product of two fuzzy sets
where
Given a fuzzy binary relation
while its
It is easily seen that dom
The domain and codomain are also called the first projection Proj
An operation, which is in some sense an inverse to the projection, is called a cylindric extension. The cylindric extension of dom
while the cylindric extension of cod
Obviously,
Moreover, it can be shown that the cylindric extensions produce the largest fuzzy relation (in the sense of inclusion) with given projection.
As it is seen from (
However, in the special case, we can uniquely reconstruct a fuzzy binary relation from its projections. It happens so if the relation is separable (see [15, 16]), noninteractive [3, 4] or orthogonal [5].
The proof of the following lemma is obvious.
i)
ii)
iii)
Separable fuzzy relations are of special interest in the case that one looks at fuzzy relation as a relationship between two variables, attributes or decision rules and with
If variables and are disconnected then the choice of the particular value
To prove that a given fuzzy binary relation
If
If
The interpretation of Lemma 4 and 5 is also straightforward since if there is no association between two variables or if all their outcomes are fully related, an information about a particular outcome of one of these variables bring no new information on the other variable.
Unfortunately, in all other cases, except of these two trivial situations, we need some time to check all necessary conditions. Therefore, an algorithm which enables to reduce the number of conditions to be checked to solve the problem of possible separability would be desirable. In next section we propose a very simple sufficient condition showing that variables under study are connected which may be used to conclude the lack of separability without any calculations, just at a glance. Then, in Section 5 we prove the necessary and sufficient condition for separability which gives us an efficient algorithm for checking separability of fuzzy binary decisions.
Let us recall that the support of a fuzzy set
Suppose, sets
Thus, the significant part of a fuzzy binary relation
In the example given above the significant part of a fuzzy relation under study is equivalent to the support of that relation but it is not a rule. For every binary fuzzy relation
Below we state a theorem that provides an easy condition to show that given a fuzzy binary relation is not separable and therefore two variables under study are connected.
Suppose the relation
i.e. there exist (
Hence dom
Theorem 7 provides a quick test for the lack of separability. Below we give its equivalent version expressed in a more useful matrix representation.
The criterion given in Corollary 8 works, of course, in one direction only: if there are no zeros in the matrix [
Although Theorem 7 specifies only the sufficient condition for separability of fuzzy binary relations, Corollary 8 could be helpful in some situations in concluding that some variables are connected. In the next section we prove the necessary and sufficient condition for separability requires more operations but solves the problem of separability definitely.
Let us start from recalling that the
It is clear that the support is simply zero
Firstly, let’s note that for any two nonempty fuzzy sets
Let us also recall the well-known fact that any two fuzzy sets
Now suppose that a fuzzy binary relation
Now, substituting dom
and combining (
Conversely, if (
One can easily notice that Theorem 7 implies from the above Theorem 9. Actually, if
Below we propose a practical and efficient algorithm for checking whether a given fuzzy binary relation is separable, based on Theorem 9. We begin from generalizing the notion of the significant part of a fuzzy relation given in Definition 6.
It is clear that zero
Now, combining Theorem 9 and the notion of the
In practice there is no need to check all
Although it is not necessary for performing the algorithm given above, it is advisable to order values in
We present the way in which our algorithm works in two examples.
for which we have domR_{2} = 0.4/x_{1}+0.7/x_{2}+1/x_{3}+0.1/x_{4} and codR_{2} = 0.3/y_{1} +1/y_{2} +0.5/y_{3} +0/y_{4} +0.9/y_{5}. Thus, the potential values to be checked are only those that appear in the domain or codomain and are smaller than 1, i.e. W = {0, 0.1, 0.3, 0.4, 0.5, 07, 0.9}. So our criteria reduces to check whether [
Sine there is no element smaller or equal to 0.1 in [
In various problems of approximate reasoning and broadly perceived decision making the information whether variables (attributes) under study are connected/noninteractive and whether the corresponding fuzzy relations are separable is of importance. Therefore, a simple test for separability of fuzzy relations is desirable. In this contribution we have suggested an efficient algorithm for checking separability based on the necessary and sufficient condition. We have also indicated a simple test for detecting interactivity based on the sufficient condition. The suggested methods could be easily applied in practice.
However, some problems in the field remain open. Firstly, in the paper we have restricted our attention to fuzzy binary relations. Therefore, a generalization of the proposed methods for more dimensions would be interesting. Secondly, in this contribution we have adopted the common assumption that the Cartesian product of fuzzy sets is defined with respect to the classical t-norm (i.e. minimum) and, consequently, the minimum operator appears in the definition of separability. However, one may consider there some other t-norms and hence discuss the notion of t-separability.
Arif Reza Anwary,Yong-il Lee,Hee Jung,Yong-Gi Kim
Int. J. Fuzzy Log. Intell. Syst. 2008; 8(1): 82-86