Inverted Fuzzy Implications in Backward Reasoning Without Yager Implication Zbigniew Suraj1 and Agnieszka Lasek2 1 Chair of Computer Science, Faculty of Mathematics and Natural Sciences, University of Rzeszow, Prof. S. Pigonia Str. 1, 35-310 Rzeszow, Poland zbigniew.suraj@ur.edu.pl 2 Department of Electrical Engineering and Computer Science Lassonde School of Engineering, York University, 4700 Keele Street, Toronto, Canada alasek@cse.yorku.ca Abstract. One of the most popular methods of knowledge representation are the fuzzy rules. One of the ways of representation of fuzzy rules is the functional representation. From over eight decades a number of different fuzzy implica- tions have been described, e.g. [5]-[9]. This leads to the following question: how to choose the proper function among basic fuzzy implications. This paper is a continuation of study [15], where we proposed a new method for choosing impli- cations in backward reasoning. Here we presented a way of simplify the analysis by skipping Yager fuzzy implication. Key words: fuzzy logic, fuzzy implications, inverted fuzzy implications, back- ward reasoning 1 Introduction One of the most popular methods of knowledge representation are the fuzzy rules. From imprecise inputs and fuzzy rules imprecise conclusions are obtained. Reason- ing is mainly classified into two types: forward reasoning and backward reasoning. The inference mechanism of forward reasoning has a strong forecasting capability, whereas the aim of backward reasoning generally is to find the most possible causes associated with the existing reality. Backward reasoning plays an essential role in fault diagnosis, accident analysis, and defect detection. This kind of reasoning uses fuzzy logic [3] to reason about data in the inference mechanism instead of many other logics, including Boolean logic, (non-fuzzy) many-valued logics, non-monotonic logics, etc. Paper [4] discusses different representations of rules in a non-fuzzy setting and ex- tends these representations to rules with a fuzzy conclusion part. It introduces the dif- ferent types of fuzzy rules and put them in the framework of fuzzy sets and possibility theory. Fuzzy rules are often presented in the form of implications. In [3] a typology of fuzzy rules and the problem of multiple-valued implications are discussed. The paper 188 reviews the problem of representing fuzzy knowledge, and ranges from linguistic vari- ables to conditional if-then rules and qualified statements. One of the ways of representation of fuzzy rules is the functional representation (e.g.[11],[12],[17]). The definition of fuzzy implications and their mathematical prop- erties can be found e.g. in [1] and [16]. One of basic problems in building an inference system is choosing the relevant fuzzy implication. In [10] authors proposed a method allowing to choose the most suitable fuzzy implication in an inference system appli- cation. They introduced an algorithm that calculates the distance between two fuzzy implications and which is based on generalized modus ponens. In paper [13] we have presented a fuzzy forward reasoning methodology for rule- based systems using the functional representation of fuzzy rules. In [15] we extended this methodology for selecting relevant fuzzy implications for backward reasoning. The proposed methodology takes full advantage of the functional representation of fuzzy implications and the algebraic properties of the family of all fuzzy implications. It al- lows to compare two fuzzy implications. If the truth value of the conclusion and the truth value of the implication are given, we can easily optimize the truth value of the implication premise. In particular, in [15] we introduced an algorithm of finding the fuzzy implication which has the highest truth value of the antecedent when the truth value of the consequent and the truth value of the implication are given. This method- ology can be useful for the design of inference engine based on the rule knowledge for a given rule-based system. In the solution in [15] we divided the domain of fuzzy implications into areas, in which it was possible to select appropriate fuzzy implication, and to do that we had to use the Lambert W function. Lambert W function is a special function used when solving equations containing unknown to both the base and the exponent power. It is marked W (z) and defined as the inverse of f (z) = zez , where z belongs to the set of complex numbers. Thus, for each complex number z holds: z = W (z)eW (z) . The Lambert W function cannot be expressed in terms of elementary functions. In this paper we present the way of avoiding this complexity of solution presented in [15]. The rest of this paper is organized as follows. Sect. 2 contains basic information on fuzzy implications. In Sect. 3 the research problem is formulated. Sect. 4 presents the solution of the given research problem. Sect. 5 is devoted to the pseudo-code of an algorithm for determining a basic fuzzy implication which has the highest truth value of the antecedent when the truth value of the consequent and the truth value of the implication are given. Sect. 6 includes summarizing of our research and some remarks. 2 Preliminaries In this section we recall a definition of a fuzzy implication and we list a few of basic fuzzy implications known from the subject literature [1]. A function I : [0, 1]2 → [0, 1] is called a fuzzy implication if it satisfies, for all x, x1 , x2 , y, y1 , y2 ∈ [0, 1], the following conditions: – if x1 ≤ x2 , then I(x1 , y) ≥ I(x2 , y), i.e., I(., y) is decreasing; 189 Name Year Formula of basic fuzzy implication Łukasiewicz 1923, [9] ILK (x, y) = min(1,  1 − x + y) 1 if x ≤ y Gödel 1932, [4] IGD (x, y) = y if x > y Reichenbach 1935, [11] IRC (x, y) = 1 − x + xy Kleene-Dienes 1938, [8]; 1949, [2] IKD (x, y) = max(1 − x, y) 1 if x ≤ y Goguen 1969, [7] IGG (x, y) = y  x if x > y 1 if x ≤ y Rescher 1969, [12] IRS (x, y) = 0  if x > y 1 if x = 0 and y = 0 Yager 1980, [18] IY G (x, y) = x  if x > 0 or y > 0 y 1 if x < 1 Weber 1983, [17] IW B (x, y) =  y if x = 1 1 if x ≤ y Fodor 1993, [3] IF D (x, y) = max(1 − x, y) if x > y Table 1. Examples of basic fuzzy implications – if y1 ≤ y2 , then I(x, y1 ) ≤ I(x, y2 ), i.e., I(x, .) is increasing; – I(0, 0) = 1; I(1, 1) = 1; I(1, 0) = 0. There exist uncountably many fuzzy implications. The following Table 1 contains a few examples of basic fuzzy implications. One of the fuzzy implication in the table is Yager implication. As we noted in Sect. 1 we skip this implication in our analysis in this paper to avoid complexity of solution presented in [15]. Figure 1 gives us some plots of these functions. 3 Problem Statement Our goal is to design an algorithm to find a method of selecting fuzzy implication in view of the value of the implication antecedent. Assume that there is given a basic fuzzy implication z = I(x, y), where x, y belong to [0,1]. y is the truth value of the consequent and is known. z is the truth value of the implication and is also known. In order to determine the value of the truth of the implication antecedent x it is needed to compute the inverse function InvI(y, z). In other words, the inverse function InvI(y, z) has to be determined. Not every of basic implications can be inverted. The function can be inverted only when it is injective. 4 Results Table 2 lists inverse fuzzy implications and their domains and in Figure 2 there are some plots of them. 190 £ ukasiewicz implication Kleene-Dienes implication 1.0 1.0 1.0 1.0 z z 0.5 0.5 0.0 0.0 0.0 0.5 y 0.0 0.5 y 0.5 0.5 x x 0.0 0.0 1.0 1.0 (a) (b) Fig. 1. Plots of ILK and IKD fuzzy implications Formula of inverted fuzzy implication Domain of inverted fuzzy implication InvILK (y, z) = 1 − z + y y ≤ z < 1, y ∈ [0, 1) 1−z InvIRC (y, z) = 1−y y ≤ z ≤ 1, y ∈ [0, 1) InvIKD (y, z) = 1 − z y < z ≤ 1, y ∈ [0, 1) InvIGG (y, z) = yz y ≤ z < 1, y ∈ (0, 1) InvIF D (y, z) = 1 − z y < z < 1 − y, y ∈ [0, 1) Table 2. Inverted fuzzy implications Inverted Kleene-Dienes implication Inverted £ ukasiewicz implication 1.0 1.0 z z 0.5 0.5 0.0 1.0 0.0 1.0 0.5 x 0.5 x 0.0 0.0 1.0 1.0 0.5 0.5 y y 0.0 0.0 (a) (b) Fig. 2. Plots of InvILK and InvIKD fuzzy implications 191 The domains of every considered inverted fuzzy implications are included in a half of the unit square, where y ≤ z < 1 and y ∈ (0, 1). Only one inverted fuzzy implication has a domain which is smaller than this area. This is inverted Fodor implication and in the whole its domain ( y ≤ z < 1 − y, y ∈ [0, 1] ) this function is equal to inverted Kleene-Dienes implication. For y ≤ z < 1 − y there are the following inequalities: InvIF D = InvIKD < InvIRC < InvILK , InvIRC < InvILK , InvIGG < InvILK . A graphical represen- tation of the ordering of inverted basic fuzzy implications is given in Figure 3. InvILK InvIRC InvIGG InvIKD = InvIF D Fig. 3. A graphical representation of the ordering of inverted basic fuzzy implications for y ≤ z < 1 − y For 1 − y ≤ z < 1 and y ≤ z there are the same inequalities, but without inverted Fodor implication, because this function does not exist in this area. The resulting inverse functions can be compared with each other so that it is possible to order them. However, some of those functions are incomparable in the whole domain. By taking into account six inverted fuzzy implications (including inverted Yager impli- cation) and by dividing their domain into separable areas, we obtained 19 inequalities between inverted fuzzy implications for any y ≤ z < 1 and y ∈ (0, 1) described in [15]. To simplify that solution and avoid Lambert W function in this paper we skip Yager fuzzy implication in our analysis. With this assumption there is only five different area and inequalities instead of nineteen. The areas are shown in the Figure 4 and the in- equalities are given in Table 3. 192 Fig. 4. The unit square [0, 1]2 divided into five separable areas Table 3: Table of inequalities No Area and inequality Chart of area Graph of inequalities z InvILK 1.0 0.8 A InvIGG For z > 1 − y 0.6 A. InvIKD < InvIRC < InvIGG < InvILK 0.4 InvIRC 0.2 y InvIKD 0.2 0.4 0.6 0.8 1.0 z 1.0 InvILK 0.8 B For z = 1 − y 0.6 InvIRC = InvIGG B. InvIKD < InvIRC = 0.4 InvIKD InvIGG < InvILK 0.2 y 0.2 0.4 0.6 0.8 1.0 Continued on next page 193 Table 3 – Continued from previous page No Area and inequality Chart of area Graph of inequalities z InvILK 1.0 √ For (z > 1+ 21−4y or 0.8 InvIRC √ z < 1− 21−4y or 0.6 C. z ∈ (0.25, 0.5)) and z < 1 − y C 0.4 InvIKD < InvIGG < InvIGG InvIRC < InvILK 0.2 y InvIKD 0.2 0.4 0.6 0.8 1.0 z 1.0 InvILK √ 0.8 For z = 1+ 21−4y or √ D. z = 1− 21−4y 0.6 D InvIRC InvIGG = InvIKD < 0.4 InvIRC < InvILK InvIGG = InvIKD 0.2 y 0.2 0.4 0.6 0.8 1.0 z InvILK 1.0 √ 0.8 For z > 1− 21−4y and InvIRC √ E. z < 1+ 21−4y 0.6 E InvIGG < InvIKD < 0.4 InvIKD InvIRC < InvILK 0.2 y InvIGG 0.2 0.4 0.6 0.8 1.0 All inequalities given in Table 3 can be proven in a similar way. As examples, we will consider one of inequalities. Let y ∈ (0, 1) and z ∈ (y, 1). y < z, so obviously y 2 < yz. By adding and subtracting 1 − z + y to the equation we obtained 1 − z < 1−z 1 − z + y − y + yz − y 2 . And therefore, 1−y < 1 − z + y. This completes the proof of the inequality: InvIRC < InvILK in domains of these functions. 194 5 Algorithm Below we present the pseudo-code of the algorithm (DetermineImplicationGTVA) for determining a basic fuzzy implication which has the highest truth value of the an- tecedent whereas the truth value of the consequent and the truth value of the implication are given. The algorithm uses the results of our research presented in Table 3. The first step in the algorithm determines to which area (A) − (E) from Table 3 point (y, z) belongs to. Algorithm DetermineImplicationGTVA Input: W - a given subset of the basic fuzzy implications; y - the truth value of the consequent; z - the truth value of the implication Output: I ∈ W - fuzzy implication(s) which has (have) the highest truth value of the antecedent 1. a ← area(y, z) //determines the area from (A) − (E) to which a point (y, z) belongs to; 2. order the set W with respect to the graph Ga of inequalities from the area a; 3. I ← the maximal element(s) from the ordered set W ; 4. return I; 6 Concluding Remarks In the paper, we introduced an algorithm for finding the fuzzy implication which has the highest truth value of the antecedent from a given subset of the basic fuzzy implications, when the truth value of the consequent and the truth value of the implication are given. In order to simplify the solution we skipped Yager fuzzy implication in the presented analysis. We considered a set of basic implications mentioned in Table 1, because they are well known and widely used. But considering only these basic implications implied the solution which does not cover the whole unit square as in the case with the forward reasoning [13], only one of its halves. It raises the question how to find such a set of im- plications that could give a solution for a backward reasoning in the whole unit square. Our future works will focus on answering the question whether such implications could exist and how they could be defined. Acknowledgments. This work was partially supported by the Center for Innovation and Transfer of Natural Sciences and Engineering Knowledge at the University of Rzeszów. The authors are also very grateful to the anonymous reviewer for giving him precious and helpful comments. 195 References 1. Baczyński, M., Jayaram, B., Fuzzy implications. Studies in Fuzziness and Soft Computing, vol. 231, Springer, Berlin (2008). 2. Dienes, Z.P.: On an implication function in many-valued systems of logic. Journal of Symbolic Logic 14, 95-97 (1949). 3. Dubois, D., Prade, H., Fuzzy sets in approximate reasoning, Part 1: Inference with possibility distributions. Fuzzy Sets and Systems 40(1), 143-202 (1991). 4. Dubois, D., Prade, H., What are fuzzy rules and how to use them. Fuzzy Sets and Systems 84(2), 169-185 (1996). 5. Fodor, J.C., On contrapositive symmetry of implications in fuzzy logic. In: Proceedings of 1st European Congress on Fuzzy and Inteligent Technologies (EUFIT 1993), pp. 1342-1348. Verlag der Augustinus Buchhandlung, Aachen (1993). 6. Gödel, K., Zum intuitionistischen Aussagenkalkul. Auzeiger der Akademie der Wissenschaften in Wien. Mathematisch, naturwissenschaftliche Klasse 69, 65-66 (1932). 7. Goguen, J.A., The logic of inexact concepts. Synthese 19, 325-373 (1969). 8. Kleene, S.C., On a notation for ordinal numbers. Journal of Symbolic Logic 3, 150-155 (1938). 9. Łukasiewicz, J., Interpretacja liczbowa teorii zdań. Ruch Filozoficzny 7, 92-93 (1923). 10. Papadopoulos, B., Trasanides, G., Hatzimichailidis, A., Optimization Method for the Selec- tion of the Appropriate Fuzzy Implication. Journal of Optimization Theory and Applications 134(1), 135-141 (2007). 11. Reichenbach, H., Wahrscheinlichkeitslogik. Erkenntnis 5, 37-43 (1935). 12. Rescher, N., Many-valued logic, McGraw-Hill, New York (1969). 13. Suraj, Z., Lasek, A. and Lasek, P., Inverted fuzzy implications in approximate reasoning. In: Proceedings of 23th International Workshop on Concurrency, Specification and Programming (CS&P 2014), September 29 - October 1, 2014, Chemnitz, Germany, pp. 237-244, Informatik- Bericht Nr. 245, Humboldt-Universitaet, Berlin (2014). 14. Suraj, Z. and Lasek, A., Toward Optimization of Approximate Reasoning Based on Rule Knowledge. In: Proceedings of International Conference on Systems and Informatics, Novem- ber 15-17, 2014, Shanghai, China, pp. 281-285, IEEE Systems, Man & Cybernetics Society, IEEE Catalog Numbers: CFP1473R-CDR ISBN: 978-1-4799-5457-5. 15. Suraj, Z. and Lasek, A., Inverted Fuzzy Implications in Backward Reasoning. In: Proceedings of 6th International Conference on Pattern Recognition and Machine Intelligence, June 30 - July 3, 2015, Warsaw, Poland, pp. 354-364, LNCS 9124, Springer, Heidelberg, 2015. 16. Tick, J. and Fodor, J., Fuzzy implications and inference processes. Computing and Informat- ics 24, 591-602 (2005). 17. Weber, S., A general concept of fuzzy connectives, negations and implications based on t- norms and t-conorms. Fuzzy Sets and Systems 11, 115-134 (1983). 18. Yager, R.R., An approach to inference in approximate reasoning. International Journal of Man-Machine Studies 13, 323-338 (1980). 19. Zadeh, L.A., Fuzzy logic and approximate reasoning. Synthese 30(3-4), 407-428 (1975).