Necessary and sufficient conditions for the existence of solution of generalized fuzzy relation equations A double left right arrow X = B

Necessary and Sufficient Conditions for the Existence of Solution of Generalized Fuzzy Relation Equations A ⇔X=B Esko Turunen Tampere University, Finland P.O. Box 1001 FI-33014 Tampere University Abstract In 2013 Li and Jin studied a particular type of fuzzy relational equations on finite sets, where the introduced min–bi–implication composition is based on Lukasiewicz equivalence. In this paper such fuzzy relation equations are studied on a more general level, namely complete residuated lattice valued fuzzy relation equations of type Vy∈Y(A(x, y)↔X(y) = B(x) are analyzed, and the existence of solutions Sis studied. First a necessary condition for the existence of solution is established, then conditions for lower and upper limits of solutions are given, and finally sufficient conditions for the existence of the smallest and largest solutions, respectively, are characterized. If such general or global solutions do not exist, there might still be partial or point wise solutions; this is a novel way to study fuzzy relation equations. Such point wise solutions are studied on Lukasiewicz, Product and G¨odel t-norm based residuated lattices on the real unit interval. Key words Residuated lattice, t–norm, Fuzzy Relation Equation. 1 Introduction Since Sanchez’ paper [18] in 1976, solving various types of fuzzy relation equations has been one of the constant topics in research and applications of fuzzy set theory; indeed, search engine in internet produces almost 700,000 results by the headword Fuzzy Relation Equation. For some older but still relevant papers, see e.g. [1, 3, 5, 10, 15, 6, 17], and the project has not been finalized, see e.g. recent papers [7] or [23]. Sanchez studied complete Brouwerian valued fuzzy relation equations of type R◦S=T, where ‘◦’ is sub–∧ composition, and proved the conditions under which the equation R◦X=Thas a solution. In 1987 (see [20]) the present author generalized these results on complete residuated lattice valued fuzzy relation equations R◦S=T, where ‘◦’ is sup-composition and showed that R◦X=Thas a solution if, and only if R⇒T is a solution, where ‘⇒’ is the inf-→composition. Moreover, if a solution exists, then R⇒Tis the largest solution. Since for all complete residuated lattice valued fuzzy relation equations holds R◦S≤Tif, and only if S≤R⇒T, the existence of solutions of a fuzzy relation equation R=X⇒Tis closely related to the equation R◦X=T. Equations R=X⇒T, too, have been studied extensively. The decades lasting research on fuzzy relation equations has focused on finding minimal solutions, all possible solutions, solutions on a particular algebraic structure and solutions related to some real life problems. In 2013 Li and Jin [11] studied fuzzy relational equations with min-bi–implication composition on finite sets, where the min–bi–implication composition of x, y is based on Lukasiewicz equivance x↔y= 1− | x−y|. These type of fuzzy relation equations were mentioned already in [6], see also [2]; the underlying intuitive idea is to find the weakest link between given Aand B. One of the main results in [11] is that solving these fuzzy relation equations is an NP–complete problem. According to [11], applications of these fuzzy relations are e.g. in approximate reasoning and fuzzy control (cf. [6, 9, 16]) and machine learning (cf. [13, 14]). However, the solvability of this kind of fuzzy relation equations has been studied very little. Because these fuzzy relation equations have important applications, we investigate the existence of solutions at the most general level. First we generalize the focus on complete residuated lattice Lvalued fuzzy relations and then study the solvability of an equation Vy∈Y(A(x, y)↔X(y)) = B(x), where Ais an L–fuzzy relation on X×Y,Bis an L–fuzzy set on Yand Xis the unknown L–fuzzy set on Y;X, Y and are any non–void sets. If there is an L–fuzzy set Son Ysuch that Vy∈Y(A(x, y)↔S(y)) = B(x), then the equation is solvable and Sis a solution. 1 This is the accepted manuscript of the article, which has been published in Information Sciences, 2020, 536, 351-357. https://doi.org/10.1016/j.ins.2020.05.015 As is our paper [20], one of the key ideas in finding solution is based on the residual structure of the set of fuzzy relations; we first consider a general setting and prove some theorems on necessary conditions for the existence of solution, and then we characterize upper and lower limits of solutions. If there are no general solutions, there might still be some partial solutions, we call them point wise solutions. We study these point wise solutions on finite sets in some particular cases. This paper is organized as follows. In Section 2 we recall some mathematical results we need in the proofs of new theorems. In Section 3 we first prove, in the most general setting, that a necessary condition for the existence of solution is that A◦B≤B⇒A. Then we introduce a sufficient condition under which A◦B is the smallest solution, and similarly, a sufficient condition under which B⇒Ais the largest solution. In Section 4 we introduce point wise solutions and focus on particular cases, where X, Y are finite sets and Lis the unit real interval equipped with Lukasiewicz, G¨odel or Product t-norm. 2 Mathematical Preliminaries Despite of many other (equivalent) definitions, and for the sake of simplicity, the term complete residuated lattice refers in this paper to an algebraic structure L={L, ≤,,→,0,1}such that (i) (L, ≤) is a complete lattice with bottom and top elements 0,1, respectively, (ii)(L, ,1) is a commutaive monoid and (iii) for all a, b, c ∈Lholds ab≤ciff a≤b→c. The condition (iii) is called isotone residuation. Residuated lattices were introduced in 1938 in [8, 22]. A comprehensive analysis of residuated lattices is presented in [4]. Residuated lattices are common in algebraic logic framework; Boolean algebras, Heyting algebras BL–algebras and MV–algebras are exambles of residuated lattices related to classical logic, intuitionistic logic, H´ajek’s BL-logic and Lukasiewicz many–valued logic, respectively. Also continuous t–norms and left continuous t–norms are related to residuated lattices via the Galois connection. Next we list those properties of complete residuated lattices that we will use in this paper; we will not mention them always when they are used; consult [21] for detailed proofs. Proposition 1Let Lbe a complete residuated lattice and a, b, c elements of Land ∅ 6=K⊆L. Then the 2 following holds a_ K b=_ K (ab),(1) a→^ K b=^ K (a→b),(2) _ K b→a=^ K (b→a),(3) 1→a= 1 a=a, (4) a→1 = 1 (5) ab≤a, b, (6) a≤biff a→b= 1,(7) if a≤b, then c→a≤c→b, (8) if a≤b, then b→c≤a→c, (9) a→(b→c) = b→(a→c),(10) a≤b→ciff b≤a→c, (11) a↔b= (a→b)∧(b→a),(12) a↔1 = a, (13) a∗=a→0,(14) a≤a∗∗.(15) A residuated lattice Lis involutive if a=a∗∗ holds for all elements a∈L. MV–algebras are examples of involutive residuated lattice; there are also many involutive residuated lattices other than MV–algebras. Well–known and widely applied examples of complete residuated lattices are continuous t-norms defined on the real unit interval [0,1]; the lattice operations are obtained by the natural order of real numbers. Since in any residuated lattice holds a→b= 1 iff a≤b, the t–norm based residuum operations →differ from each other only in the case a>b. Similarly, for all residuated lattices holds a↔b= 1 iff a=b, so the interesting cases are those where a6=b. The operations ,→and ↔constitute the following residuated structures: 1◦G¨odel t-norm; ab=a∧b,a→b=bif b<a, and a↔b=a∧bif a6=b. 2◦Product t-norm; ab=ab,a→b=b aif b < a, and a↔b=a b∧b aif a6=b. 3◦ Lukasiewicz t-norm; ab= max{a+b−1,0},a→b= 1−a+bif b<a;a↔b= (1−a+b)∧(1−b+a) = 1− |a−b|if a6=b. 3 On the Solvability of Fuzzy Relation Equations A ⇔X=B Assume X, Y are non–void sets of any cardinality and Lis a complete residuated lattice. A mapping A: X×YyLis identified to an L–fuzzy relation on X×Yand B:XyLcan be seen as an L–fuzzy set on Xand Xis a mapping X:YyL. Our aim is to study the solvability of a fuzzy relation equation A⇔X(x) = ^ y∈Y (A(x, y)↔X(y)) = B(x) for all x∈X, (16) where A, B are given and Xis the unknown. If there exists an X=Ssuch that (16) holds, then Sis the solution of (16). We recall the following two L–fuzzy sets (see e.g. [20]). 3 Definition 2Given Aand B,A◦Bis an L–fuzzy set on Ysuch that, for all y∈Y, A◦B(y) = _ x∈X [A(x, y)B(x)],(17) and B⇒Ais an L–fuzzy set on Ysuch that, for all y∈Y, (B⇒A)(y) = ^ x∈X [B(x)→A(x, y)].(18) The following result generalizes Lemma 2.2 in [11]. Theorem 3A necessary condition for the existence of solution for (16) is that A◦B≤B⇒A; indeed, if (16) has a solution S, then A◦B≤S≤B⇒A. Proof. If (16) has a solution S, then for all x∈X, y ∈Yholds B(x)≤A(x, y)↔S(y)≤A(x, y)→S(y), or equivalently, for all x∈X, y ∈Yholds B(x)A(x, y)≤S(y), or equivalently, for all y∈Yholds _ x∈X [A(x, y)B(x)] ≤S(y), and therefore A◦B≤S. The existence of a solution Salso implies that for all x∈X, y ∈Yholds B(x)≤S(y)→A(x, y), which is equivalent to S(y)≤B(x)→A(x, y) for all x∈X, y ∈Y. Therefore S(y)≤^ x∈X [B(x)→A(x, y)] for all y∈Y. Hence S≤B⇒A. Now we study the conditions under which A◦Band B⇒Aare solutions of (16). We first define two L–fuzzy sets on Xby setting, for all x∈X, A=⇒C(x) = ^ y∈Y (A(x, y)→C(y)), C=⇒A(x) = ^ y∈Y (C(y)→A(x, y)) where Ais an L–fuzzy relation on X×Yand Cis an L–fuzzy set on Y. Then it is easy to see that, for all x∈X,A⇔C(x)≤A=⇒C(x) and A⇔C(x)≤C=⇒A(x), and therefore also A⇔C(x)≤[A=⇒C](x)∧[C=⇒A](x) = M. 4 Moreover, for all y∈Y,M≤(A(x, y)→C(y)) ∧(C(y)→A(x, y)) = A(x, y)↔C(y). Thus, for all x∈X, M≤A⇔C(x). Therefore, for all x∈X,A⇔C(x)=[A=⇒C](x)∧[C=⇒A](x). We have proved Proposition 4A⇔C= (A=⇒C)∧(C=⇒A)for all L–fuzzy relations Aon X×Yand L–fuzzy sets Con Y. We have an isotone Galois connection between the operations ‘◦’ and ‘=⇒’, indeed Proposition 5For all L–fuzzy relations Aon X×Y,L–fuzzy sets Bon Xand L–fuzzy sets Con Yholds A◦B≤Ciff B≤A=⇒C,(19) in particular, B≤A=⇒A◦B. Proof. A◦B≤Ciff for all y∈Y, A◦B(y)≤C(y) iff for all y∈Y, Wx∈X(A(x, y)B(x)) ≤C(y) iff for all y∈Y, x ∈X:A(x, y)B(x)≤C(y) iff for all y∈Y, x ∈X:B(x)≤A(x, y)→C(y) iff for all x∈X:B(x)≤^ y∈Y (A(x, y)→C(y)) = A=⇒C(x) iff B≤A→C.  Now we are able to prove Theorem 6For all L–fuzzy relations Aon X×Y,L–fuzzy sets Bon X, if B=A◦B=⇒A, the A◦Bis the smallest solution of (16). Proof. If B=A◦B=⇒A, we reason, by Proposition 4 and Proposition 5 A⇔A◦B= (A=⇒A◦B)∧(A◦B=⇒A)=(A=⇒A◦B)∧B=B, so A◦Bis a solution of (16). By Theorem 3, it is also the smallest one.  Then we have Proposition 7For all L–fuzzy relations Aon X×Yand L–fuzzy sets Bon Xholds Proof. B≤(B⇒A) =⇒Aiff for all x∈Xholds B(x)≤Vy∈Y[(B⇒A)(y)→A(x, y)] iff for all x∈X, y ∈Y:B(x)≤(B⇒A)(y)→A(x, y) iff for all x∈X, y ∈Y: (B⇒A)(y)≤B(x)→A(x, y) iff for all y∈Y: (B⇒A)(y)≤^ x∈X B(x)→A(x, y) iff for all y∈Y: (B⇒A)(y)≤(B⇒A)(y) and the last (in-)equality trivially holds.  We have 5 Theorem 8For all L–fuzzy relations Aon X×Y,L–fuzzy sets Bon X, if B=A=⇒(B⇒A), then B⇒Ais the largest solution of (16). Proof. If B=A=⇒(B⇒A), we reason, by Proposition 4 and Proposition 7, A⇔(B⇒A)=(A=⇒(B⇒A)) ∧((B⇒A) =⇒A) = B∧((B⇒A) =⇒A) = B, so B⇒Ais a solution of (16). By Theorem 3, it is also the largest one.  Remark 9Theorem 6 and Theorem 8 give sufficient conditions for the existence of the smallest solution and the largest solution, respectively, for the fuzzy relation equation (16). However, they are not necessary conditions. Indeed, let A≡1,B≡b6= 1. Then S=A◦B≡bis the unique solution of (16), thus simultaneously the smallest and largest solution However, B6=A◦B=⇒A. Similarly, let A=B≡a6= 1. Then B⇒A≡1is the largest solution of (16). However, B6=A=⇒(B⇒A)≡1. 4 Point Wise Solutions The solutions studied in the previous section are general; they hold for all x∈X; we call such solutions global; however, such solutions are case sensitive. The existence of one such y∈Ysuch that Theorem 3 does not hold implies the non–existence of global solutions. Indeed, if (16) has a solution S, then for all x1, x2∈X, y ∈Y holds B(x1)A(x1, y)≤S(y)≤B(x2)→A(x2, y). Thus, assume there are x1, x2∈X, y ∈Ysuch that B(x1) = B(x2) = A(x1, y) = 1 and A(x2, y) = 0, then B(x1)A(x1, y) = 1 while B(x2)→A(x2, y) = 0. Therefore (16) does not have a global solution. However, it makes sense to investigate conditions under which a solution for a given x∈Xexists, even if there is no global solution. This leads to the analysis of point wise solutions. To our knowledge, this is a completely new perspective to study the solvability of fuzzy relation equations. From now on, we assume that X, Y are non–void finite sets and the residuated lattice Lis linear. Then the general problem (16) reduces to the solvability of fuzzy relation equations min y∈Y{A(x, y)↔S(y)}=B(x) for all x∈X, (20) Let x0∈X, then if min y∈Y{A(x0, y)↔S(y)}=B(x0) (21) has a solution S(y), then this solution is obtained by some (maybe several) y0∈Y, that is A(x0, y0)↔S(y0) = B(x0).(22) Obviously, the existence of a solution Sat the point y0depends only on the values of A(x0, y0) and B(x0). We immediately observe Proposition 10 Let X, Y be non–void finite sets and the residuated lattice Lis linear. If 1◦B(x0)=1, then the unique solution of (22) is S(y0) = A(x0, y0). 2◦A(x0, y0)=1, then the unique solution of (22) is S(y0) = B(x0). 3◦A(x0, y0)=0, then the solution of (22) satisfies [S(y0)]∗=B(x0). 6 The other cases B(x0) = 0 and 0 <B(x0),A(x0, y0)<1 depend on the special structure of the residuated lattice. As an example we study the cases when Lis the unit real interval [0,1] endowed by the (i) Lukasiewicz, (ii) G¨odel and (iii) Product t-norm, respectively. For simplicity we abbreviate (22) to a↔s=b,(23) which has a solution sif, and only if a→s=bor s→a=b(24) has a solution s. By Proposition 10, 1◦we may assume b<1. However, for the sake of completeness and comprehensibility, the following theorems contain also the case b= 1. Theorem 11 Let X, Y be non–void finite sets and Lthe real unit interval equipped with the Lukasiewicz structure. Then we have the following cases 1. If b= 1 then s=ais the unique solution of (24). 2. If a= 1 then s=bis the unique solution of (24). 3. If a= 0 then s=b∗is the unique solution of (24). 4. If b= 0 then s= 0 is the unique solution of (24) iff a= 1, and s=1is the unique solution of (24) iff a= 0. There are no other solutions. 5. If 0<b,a<1then a solution of (24) exists iff ab>0or a+b= 1. Then the solution is s=ab>0 and s= 0 if a+b= 1. Moreover, if b<athe solution is unique. If b=athen also s= 1 is a solution, and if a<bthen also s=b→ais a solution. There are no other solutions. Proof. The cases 1. and 2. hold by Proposition 10, 1◦, 2◦, respectively, and by 3◦,s∗=b.Therefore s=s∗∗ =b∗.In Lukasiewicz structure the condition (24) is 1−a+s=bor 1 −s+a=b,where b<1.(25) Case 4. 1−a+s= 0 has a solution iff a= 1, and in that case the unique solution is s= 0. Moreover 1−s+a= 0 has a solution iff a= 0, and in that case the unique solution is s= 1. Case 5,b<a. Then no s∈[0,1] satisfies 1 −s+a=b, so the solution must satisfy 1 −a+s=b, if it exists. This happens iff s=a+b−1 iff s=ab>0 or a+b= 1 and in that case s= 0. The solution is obviously unique. Case 5,b=a. Clearly 1 −s+a=biff s= 1. Also 1 −a+s=biff s=ab>0 or a+b= 1 and in that case s= 0. Case 5,a<b. First realize that 1 −s+a=biff 1 −b+a=siff s=b→a<1. In the same way as in the two previous cases, we verify 1 −a+s=biff s=ab>0 or a+b= 1 and in that case s= 0.  Theorem 12 Let X, Y be non–void finite sets and Lthe real unit interval equipped with the G¨odel structure. Then we have the following cases 1. If b= 1 then s=ais the unique solution of (24). 2. If a= 1 then s=bis the unique solution of (24). 3. If a= 0 then all s∈(0,1] are solution of (24) iff b= 0. There are no other solutions. 7 4. If b= 0 then the solution exists for all a. If a= 0 then all s∈(0,1] are solutions of (24). If a>0then s= 0 is the unique solution of (24). 5. If 0<b<a<1then s=bis the unique solution of (24). 6. If 0<b=a<1then all s∈(a,1] are solutions of (24). 7. If 0<a<b<1then no solution exists. Proof. The cases 1. and 2. hold by Proposition 10, 1◦, 2◦, respectively. Case 3. In G¨odel structure (0 →s)∧(s→0) = biff b= 0 and s>0. Case 4. In G¨odel structure (a→s)∧(s→a) = 0 iff a= 0 and then s>0 or a>0 and then s= 0. Case 5. Let b<aand recall the condition (24). Since s→a∈ {a,1},s→a=bhas no solutions. Thus, if a solution exist, it must satisfy a→s=b; this holds iff s=b. Case 6. Since a→s=sfor all s<a=b<1 and a→s= 1 elsewhere, a→s=bhas no solution. On the other hand s→a=b=afor all s∈(a,1]. Case 7. Clearly s=ais not a solution. Since a→s=sfor all s<a<b<1 and s→a=a<bfor all a<s, (24) has no solution.  Theorem 13 Let X, Y be non–void finite sets and Lthe real unit interval equipped with the Product structure. Then we have the following cases 1. If b= 1 then s=ais the unique solution of (24). 2. If b= 0 then the solution of (24) exists for all a∈[0,1];s= 0 iff a>0and s>0iff a= 0. 3. If 0<b<1and a= 0 then no solution of (24) exists. 4. If 0<b<1and a= 1 then s=bis the unique solution of (24). 5. If 0<b,a<1then the solution of (24) is s=ab. Moreover, if b<athe solution is unique. If b=athen also s= 1 is a solution, and if a<bthen also s=b→ais a solution. There are no other solutions. Proof. The cases 1. and 4. hold by Proposition 10, 1◦, 2◦, respectively. Case 2.a→s=s a= 0 iff a>0 and s= 0, and s→a=a s= 0 iff s>0 and a= 0. Case 3. In Product structure (0 →s)∧(s→0) ∈ {0,1}, so the equation (0 →s)∧(s→0) = bhas no solution. Case 5,b<a; no s∈[0,1] satisfies b=s→a=a s. On the other hand b=a→s=s awhich holds iff s=ab. Clearly, this is the unique solution of (24). Case 5,b=a.b=s→a=a siff s= 1. Again b=a→s=s aiff s=ab. Case 5,a<b.b=s→a=a siff s=a b=b→a. Also in this case b=a→s=s aiff s=ab. We summarize by writing the following Theorem 14 Let X, Y be non–void finite sets and the real unit interval is equipped with either the Lukasiewicz, G¨odel or Product structure. Then the fuzzy relation equation (16) has a solution iff for all x0∈X, the equation (24) has a solution. Remark 15 The method described above produces all the existing solution of the equation (16). However, it requires that the corresponding element y0∈Yin equation (22) is known; y0is obtained by minimizing sover y∈Ysuch that s→A(x0,y) = B(x0)or A(x0,y)→s=B(x0). This, in turn, leads to similar calculations than in Theorem 11, Theorem 12 and Theorem 13. In all, as proved by [11], solving the problem in general is NP–complete. 8 5 Conclusion and Future Work We have generalized Li’s and Jin’s work [11] on fuzzy relational equations with min–bi–implication to generalized residuated lattice valued fuzzy inf–bi–implication fuzzy relations and, after analyzing the general structure of these fuzzy relations and conditions for the existence of solutions, solved three subtypes of the related fuzzy relation equations by introducing point wise solutions method. Based on our three theorems, it is not difficult to construct a software that, given a finite fuzzy relation Aand a finite fuzzy set Bas inputs, produces all solutions S(y0) of the fuzzy relation equation Vy∈Y(A(x, y)↔S(y)) = B(x), whenever they exist. For infinite Aand Band general residuated lattice Lthe problem is so far open and challenging. Ethical Standards The author declares that they have no conflict of interest. This article does not contain any studies with human participants or animals performed by any of the authors. References [1] De Baets, B.: Analytical solution methods for fuzzy relational equations. In Dubois, D. and Prade, H., (Eds.) Fundamentals of Fuzzy Sets, The Handbooks of Fuzzy Sets Series, Vol. 1, Kluwer, Dordrecht (2000) 291-340. [2] Belohlavek, R.; Fuzzy Relational Systems, Kluwer (2002) DOI 10.1007/978-1-4615-0633-1. [3] Bour, L., Hirsch, G., and Lamotte, M.: Operateur de minimalisation pour la resolution d’ equations de relation floue avec la composition inf-conorme, BUSEFAL, 28 (1986) 68-77. [4] Galatos, N., Jipsen, P., Kowalski, T., and Ono, H.L Residuated Lattices. An Algebraic Glimpse at Substructural Logics, Elsevier, 2007. [5] Gottwald, S.: Approximately solving fuzzy relation equations: Some mathematical results and some heuristic proposals, Fuzzy Sets and Systems, 66 (1994) 175-193. [6] Di Nola, A., Sessa, S. Pedrycz, W. and Sanchez. E.: Fuzzy Relation Equations and Their Applications to Knowledge Engineering. Springer (1989), 280 pages. DOI 10.1007/978-94-017-1650-5. [7] Diaz-Moreno, J.C., Medina, J. and Turunen, E.: Minimal solutions of general fuzzy relation equations on linear carriers. An algebraic characterization. Fuzzy Sets and Systems, 311 (2017), 112–123. [8] Dilworth, R.P.: Abstract residuation over lattices. Bull. Amer Math. Soc. 44 (1938), 335-354. [9] Klawonn, F. and Kruse, R.: Equality relations as a basis for fuzzy control. Fuzzy Sets and Systems. 54(1993), 147–156. [10] Luo, Y. and Li, Y.: Decomposition and resolution of min-implication fuzzy relation equations based on S-implication, Fuzzy Sets and Systems, 148 (2004) 305-317. [11] Li, P., and Jin, Q.: A Note on Fuzzy Relational Equations With Min-Implication Composition. Fuzzy Optimization and Decision Making 11(2)(2013) DOI: 10.1007/s10700-012-9122-0. [12] Markovskii A.V.: On the relation between equations with max-product composition and the covering problem. Fuzzy Sets and Systems 153 (2005), 261-273. [13] Moser, B.: On the T-transitivity of kernels. Fuzzy Sets and Systems, 157 (2006), 1787–1796. 9