key: cord-0044772-7ju0sb6m
authors: Cao, Nhung; Štěpnička, Martin
title: Sufficient Solvability Conditions for Systems of Partial Fuzzy Relational Equations
date: 2020-05-18
journal: Information Processing and Management of Uncertainty in Knowledge-Based Systems
DOI: 10.1007/978-3-030-50146-4_8
sha: beb4f9fdf8fb8a98916ae1938ac9256fd22fea5e
doc_id: 44772
cord_uid: 7ju0sb6m

This paper focuses on searching sufficient conditions for the solvability of systems of partial fuzzy relational equations. In the case of solvable systems, we provide solutions of the systems. Two standard systems of fuzzy relational equations – namely the systems built on the basic composition and on the Bandler-Kohout subproduct – are considered under the assumption of partiality. Such an extension requires to employ partial algebras of operations for dealing with undefined values. In this investigation, we consider seven most-known algebras of undefined values in partial fuzzy set theory such as the Bochvar, Bochvar external, Sobociński, McCarthy, Nelson, Kleene, and the Łukasiewicz algebra. Conditions that are sufficient for the solvability of the systems are provided. The crucial role will be played by the so-called boundary condition.

Systems of fuzzy relational equations were initially studied by Sanchez in the 1970s [17] and later on, many authors have focused on this topic and it becomes an important topic in fuzzy mathematics especially in fuzzy control. The most concerned problem attracting a large number of researchers regards the solvability criterions or at least conditions sufficient for the solvability of the systems. The applications of the topic are various including in the dynamic fuzzy system [14] , solving nonlinear optimization problems and covering problem [13, 15] , and many others. It is worth mentioning that the topic is still a point of the interest in the recent research [5, 10, 12] .

Recently, investigations of the systems of fuzzy relational equations allowing the appearance of undefined values in the involved fuzzy sets were initiated [4, 7] . Partial fuzzy logic which is considered as a generalization of the threevalued logic, and the related partial fuzzy set theory has been established [1] [2] [3] 11] . Several well-known algebras were already generalized in partial fuzzy set theory such as the Bochvar algebra, the Sobociński algebra, the Kleene algebra, or Nelson algebra [2] . Lets us note that it seems there is no absolutely accepted general agreement on what types of undefined values are the particular algebras mostly appropriate for but they turned out to be useful in various areas and applications [9] .

Recently, further algebras for partial fuzzy logics motivated by dealing with missing values were designed [6, 18] . In [4] , the initial investigation on the solvability of the systems of partial fuzzy relational equations was provided. The study was restricted on the equations with fully defined (non-partial) consequents. In [7] , the problem was extended by considering the partially defined consequents, however, only the Dragonfly algebra [18] was considered and only one of the systems of equations was investigated. The article [7] provided readers with the particular shape of the solution however, under the assumption of the solvability. However, the solvability was not ensured, no criterion was provided. This article aims at paying this debt and focuses on the determination of the sufficient conditions for the solvability of both standard systems of partial fuzzy relational equations. Various kinds of algebras dealing with undefined values are considered, in particular the Bochvar, Sobociński, Kleene, McCarthy, Bochvar external, Nelson, and Lukasiewicz algebras.

In this subsection, we briefly recall the definitions of several algebras of undefined values we apply in this work. Let us consider a complete residuated lattice L = [0, 1], ∧, ∨, ⊗, → 0, 1 as the structure for the whole article and thus, all the used operations will be stemming from it. Let denotes the undefined values regardless its particular semantic sub-type of the undefinedness [9] . Then the operations dealing with undefined values are defined on the support L = [0, 1] ∪ { }, for more details we refer to [2] . Note that the operations on L applying to a, b ∈ [0, 1] are identical with the operations from the lattice L. The following brief explanation of the role of in particular algebras is based on Tables 1, 2 and 3. The value in the Bochvar (abbr. B when denoting the operations) algebra works as an annihilator and so, no matter which values a ∈ L is combined with it, the result is always . In the Sobociński (abbr. S) algebra, acts like a neutral element for the conjunction and the disjunction as well. It means that the conjunctive/disjunctive combination of any value a ∈ L with results in a. In the Kleene algebra (abbr. K), the operations combining and 0 or 1 comply the ordering 0 ≤ ≤ 1, otherwise they coincide with the Bochvar algebra operations when is combined with a / ∈ {0, 1}. The Lukasiewicz algebra (abbr. L) and the Nelson (abbr. N) algebra are identical with the Kleene algebra regarding their conjunctions and disjunctions however, the difference lies in the implication operations. In particular, in the Lukasiewicz case → L = 1 holds, and in the Nelson case the equalities → N 0 = 1 and → N = 1 hold, while in both cases, the Kleene implication results into again. The McCarthy (abbr. Mc) algebra interestingly combines the Kleene and the Bochvar behavior with the distinction between the cases whether appears in the first argument or in the second argument of the operation.

Let us recall two useful external ones [9] : ↓ is given by ↓α = 0 if α = and ↓α = α otherwise; and ↑ is given by ↑α = 1 if α = and ↑α = α otherwise. The external operations play a significant role in the so-called Bochvar external algebra (abbr. Be) as it applies operation ↓ to and lowers it to 0 in any combinations with a ∈ L . Table 3 . Implicative operations of distinct algebras (α ∈ (0, 1], β ∈ (0, 1)). 

Let us denote the set of all fuzzy sets on a universe U by F(U ). Then two standard systems of fuzzy relational equations are provided in the forms:

where A i ∈ F(X), B i ∈ F(Y ), i = 1, . . . , m for some universes X, Y . The direct product • and the Bandler-Kohout subproduct (BK-subproduct) in systems (1) and (2) are expanded as follows:

In [8] , the authors defined so-called boundary condition and shown, that it is a sufficient condition for the solvability of the direct product systems (1). In [16] , using the so-called skeleton matrix, it was shown that it serves as the sufficient condition also for the solvability of (2) and in [19] , an alternative proof not requiring the skeleton matrix was presented.

Theorem 1 [8, 16] . Let A i fulfill the boundary condition. Then systems (1)- (2) are solvable and the following models are solutions of the systems, respectively:

As we have recalled above, the standard systems of fuzzy relational equations are solvable if the antecedents fulfil the boundary condition [8] . Of course, the question whether the solvability of partial fuzzy relational equations can be ensured by the same or similar condition appears seems natural. As we will demonstrate the answer is often positive. Moreover, we investigate some specific cases of solvable systems even if the boundary condition is not preserved.

Let F (U ) stands for the set of all partially defined fuzzy sets (partial fuzzy sets) on a universe U , i.e., let

The following denotations will be used in the article assuming that the righthand side expressions hold for all u ∈ U :

Moreover, let us introduce the following denotations for particular parts of the universe U with respect to a given partial fuzzy set A ∈ F (U ):

Let us first consider the use of the Bochvar operations in the systems:

We recall that in the Bochvar algebra the behaves like an annihilator i.e., when it combines with any other values the result is always . Thus, when there is an x ∈ X such that A i (x) = the inferred output B i is a fuzzy set to which all the elements have an undefined membership degree, i.e., B i = ∅ . It immediately leads to the following theorems with necessary conditions demonstrating that the solvability of both systems falls into trivial cases as long as the partial fuzzy sets appear on the inputs.

Sketch of the proof: As there exists x ∈ X such that A i (x) = , one can check that the following holds for any R ∈ F (X × Y ):

which leads to that B i has to be equal to ∅ .

Sketch of the proof: The proof is similar to the proof of Theorem 2.

Sketch of the proof: Based on a simple demonstration that R B ∈ F (X × Y ) given by R B (x, y) = is a solution.

Theorems 2 and 3 are direct consequences of the "annihilating effect" of in the Bochvar algebra. Whenever the input is undefined, the consequents have to be even fully undefined. Now, we focus on the systems applying the McCarthy algebra:

As the McCarthy operations provide the same result as the Bochvar operations whenever appears in their first argument, we naturally come to results about solvability of (5)-(6) that are the analogous to the results about solvability of (3)-(4). (5) is that B j = ∅ for all such indexes j ∈ {1, . . . , m} for which the corresponding antecedents A j ∈ F (X) F(X).

Sketch of the proof: Analogous to Theorem 2.

Theorem 5. The necessary condition for the solvability of system (6) is that B j = ∅ for all such indexes j ∈ {1, . . . , m} for which the corresponding antecedents A j ∈ F (X) F(X).

Sketch of the proof: Analogous to Theorem 3.

Although the necessary conditions formulated in Theorems 4 and 5 are identical for McCarthy and Bochvar algebra, the sufficient condition for the McCarthy algebra has to also take into account the differences in the operations of these two otherwise very similar algebras. Sketch of the proof: As in the case of Corollary 1 the proof is based on a simple demonstration that R Mc ∈ F (X × Y ) given by R Mc (x, y) = is a solution however, the case of the empty input that would lead to the empty output has to be eliminated from the consideration. Sketch of the proof: As in the case of Corollary 2 the proof is based on a simple demonstration that R Mc ∈ F (X × Y ) given by R Mc (x, y) = is a solution however, the case of the empty input that would lead to the output constantly equal to 1, has to be eliminated from the consideration.

In this section, we present the investigation of the solvability of systems of partial fuzzy relational equations in the case of the Bochvar external algebra and in the case of Sobociński algebra. Let us start with the Bochvar external operations employed in the systems:

(A i • BeRBe )(y) = B i (y), for y ∈ Def(B i ), whereR Be (x, y) = m Be i=1 (A i (x) → Be B i (y)) .

A i (x) → Be B i (y) = , no matter the choice of x, y, and hence:

We may split the right-hand side expression running over X into two expressions, one running over A i0 ∪ A i , the other one running over A iP and show, that each of them is smaller or equal to B i :

Now, we prove the opposite inequality. Based on the assumption of the boundary condition, let us pick x i such that A i (x i ) = 1 and A j (x i ) = 0, j = i. Then we may check

which completes the sketch of the proof.

If we assume that the output fuzzy sets B i are fully defined we obtain the following corollary.

The following theorem and corollary provides us with similar results for the BK-subproduct system of partial fuzzy relational equations (8).

Sketch of the proof: Due to the external operations, A i (x) ⊗ Be B i (y) = holds independently on the choice of x and y. Jointly with the property c → Be a ≤ c → Be b that holds for a ≤ b it leads to the inequality

For y ∈ Def(B i ) we get the following inequalities Be x∈Ai0∪Ai

that jointly prove that (A i BeŘBe )(y) ≥ B i (y). In order to prove the opposite inequality, we again pick up the point x i in order to use the boundary condition.

If the consequents B i in system (8) are fully defined we obtain the following corollary.

Now let us focus on the following systems applying the Sobociński operations:

is its solution.

Sketch of the proof: The proof uses an analogous technique as the proof of Theorem 6.

is its solution.

Sketch of the proof: The proof uses an analogous technique as the proof of Theorem 7.

has been shown to be a solution of the system (10) under the assumption of its solvability [4] . And the solvability can ensured by the boundary condition, see Theorem 9.

Let us start with the focus on the systems employing the Kleene operations: Then system (11) is solvable and moreover, the following partial fuzzy relation

is one of the solutions.

Sketch of the proof: By proving thatR K is a solution we prove also the solvability of the system. Let us take arbitrary j and assume that condition (a) holds. Then, for x ∈ X such that A j (x ) = 1 we can prove that A j (x ) ⊗ KRK (x , y) = 1 and hence, the following holds

Now, let us assume that (b) holds for the given j. Then independently on the choice of x and y,R K (x, y) ∈ { , 1}, and based on the following facts

In both cases (a) and (b), the result of (A j • KRK ) was equal to the consequent B j and the proof was made for arbitrarily chosen index j. Then system (12) is solvable and moreover, the following partial fuzzy relatioň

is one of the solutions.

Sketch of the proof: Let us take an arbitrary j and assume that (a) holds. Then, for x ∈ X such that A j (x ) = 1 we can prove that A i (x ) → KŘK (x, y) = 0 and hence, the following holds

Now, let us assume that (b) holds for the given j. ThenŘ K (x, y) ∈ { , 1} independently on the choice of x and y, and based on the following facts

we may derive (A j KŘK )(y) = .

In both cases (a) and (b), the result of (A j • KRK ) was equal to the consequent B j and the proof was made for arbitrarily chosen index j.

Let for all j ∈ {1, . . . , m} the following condition holds (c) B j = 1.

Then system (12) is solvable and moreover, the following fuzzy relatioň

is one of the solutions.

Sketch of the proof: The proof is based on the following three equalities

The use of the Lukasiewicz operations and the Nelson operations give the same results and very similar to the use of the Kleene operations. Therefore, we will study the system jointly for both algebras of operations, in particular, we will consider

where γ ∈ {L, N} will stand for the the Lukasiewicz and Nelson algebra, respectively. Therefore, the following results will hold for both algebras. Then system (13) is solvable and moreover, the following partial fuzzy relation

is one of the solutions.

Sketch of the proof: The proof uses an analogous technique as the proof of Theorem 10.

Let for all j ∈ {1, . . . , m} one of the following conditions holds (a) A j is a normal fuzzy set and B i = ∅,

Then system (14) is solvable and the following partial fuzzy relatioň

is one of the solutions.

Sketch of the proof: Under the assumption that (a) holds, the proof uses the same technique as the proof of Theorem 11.

When proving the theorem under the assumption of the preservation of (b), we stem from the fact that A j (x) → γŘγ (x, y) = 1 when A j (x) = , and from the fact that A j (x) → γŘγ (x, y) = when A j (x) / ∈ {0, }, and hence, we come to the conclusion that (A j γŘγ )(y) = for any y ∈ Y .

Let us consider case (c). Using the fact that A j (x) → γŘγ (x, y) = 1 in case of A j (x) = and also for A j (x) = we come to the same conclusion, we prove that (A i γŘγ )(y) = 1 for arbitrary y ∈ Y .

All the results presented above can be summarized in Table 4 . 

A i •τ R = B i A i τ R = B i

Bochvar

A i -boundary and

A i -normal, B i = 1Rτ A i -normal, B i = ∅Řτ A i = ∅, B i = ∅ ∃x : A i (x) / ∈ {0, } and B i = ∅ B i = 1

We have attempted to find, formulate and prove sufficient conditions for the solvability of systems of partial fuzzy relational equations. Distinct well-known algebras dealing with undefined values have been considered, namely Bochvar, Bochvar external, Sobociński, Kleene, Nelson, Lukasiewicz, and McCarthy algebras. Let us recall that the choice of many algebras to apply to such a study was not random but to cover various types of undefined values and consequently, various areas of applications. We have obtained distinct sufficient conditions for distinct algebras. Some of the conditions seem to be rather flexible, e.g., for the case of Bochvar external and Sobociński, it was sufficient to consider the boundary condition met by the antecedent fuzzy sets. On the other hand, most cases showed that the solvability can be guaranteed under very restrictive conditions. Although apart from the Bochvar case, the conditions are not necessary but only sufficient, from the construction of the proofs and from the investigation of the behavior of the particular operations it is clear, that in such algebras, very mild conditions cannot be determined.

For the future work, we intend to complete the study by adding also necessary conditions and by considering also the Dragonfly and Lower estimation algebras that seem to be more promising for obtaining mild solvability conditions similarly to the case of Sobociński or Bochvar external algebra. Furthermore, there exist problems derived from the solvability modeling more practically oriented research that are not expected to be so demanding on the conditions such as the solvability itself. By this, we mean, for instance, modeling the partial inputs incorporated into the fully defined systems of fuzzy relational equations. Indeed, this models very natural situations when the knowledge (antecedents and consequents) is fully defined but the input is partly damaged by, e.g., containing missing values etc.

Finally, we plan to study the compatibility (or the sensitivity) of the used computational machinery with undefined values with respect to ranging values that can possibly replace the . This investigation should show us which algebras are the most robust ones when we know in advance that belongs to a certain range or is described using natural language such as "low values", or "big values", etc.

Towards fuzzy partial set theory

Towards fuzzy partial logic

Fuzzy relational modalities admitting truth-valueless propositions

Solvability of fuzzy relational equations employing undefined values

Fuzzy relation equations with fuzzy quantifiers

Compositions of partial fuzzy relations employing the lower estimation approach

Fuzzy relational equations employing Dragonfly operations

A new look at solving a system of fuzzy relational equations

A map of dependencies among three-valued logics

On the solvability of bipolar max-product fuzzy relation equations with the product negation

Fuzzy relations and fuzzy functions in partial fuzzy set theory

Minimal solutions of general fuzzy relation equations on linear carriers. An algebraic characterization. Fuzzy Sets Syst

An efficient genetic algorithm for solving nonlinear optimization problems defined with fuzzy relational equations and Max-Lukasiewicz composition

A fuzzy relational equation in dynamic fuzzy systems

On fuzzy relational equations and the covering problem

Finitary solvability conditions for systems of fuzzy relation equations

Resolution of composite fuzzy relation equations

Missing values and Dragonfly operations in fuzzy relational compositions

Interpolativity of at-least and at-most models of monotone fuzzy rule bases with multiple antecedent variables