Fuzzy techniques have been originally designed to describe imprecise (“fuzzy”) expert knowledge. Somewhat surprisingly, fuzzy techniques have also been successfully used in situations without expert knowledge, when all we have is data. In this paper, we explain this surprising phenomenon by showing that the need for optimal processing of data (including crisp data) naturally leads to fuzzy and neural data processing techniques. This result shows the potential of fuzzy data processing. To maximally utilize this potential, we need to provide an operational meaning of the corresponding fuzzy degrees. We show that such a meaning can be extracted from the above justification of fuzzy techniques. It turns out that, in contrast to probabilistic uncertainty, the natural operational meaning of fuzzy degrees is indirect—similarly to the operational meaning of geometry and physics in general relativity.

Often, about the same real-life system, we have both measurement-related probabilistic information expressed by a probability measure P(S) and expert-related possibilistic information expressed by a possibility measure M(S). To get the most adequate idea about the system, we must combine these two pieces of information. For this combination, R. Yager—borrowing an idea from fuzzy logic—proposed to use a t-norm f&(a,b) such as the product f&(a,b)=a· b, i.e., to consider a set function f(S)=f&(P(S),M(S)). A natural question is: can we uniquely reconstruct the two parts of knowledge from this function f(S)? In our previous paper, we showed that such a unique reconstruction is possible for the product t-norm; in this paper, we extend this result to a general class of t-norms. © 2011 Wiley Periodicals, Inc.

In 1951, K.J. Arrow proved that, under certain assumptions, it is impossible to have group decision-making rules that satisfy reasonable conditions like symmetry. This Impossibility Theorem is often cited as a proof that reasonable group decision-making is impossible. We start our article by remarking that Arrow's result covers only those situations when the only information we have about individual preferences is their binary preferences between the alternatives. If we follow the main ideas of modern decision making and game theory and also collect information about the preferences between lotteries (i.e., collect the utility values of different alternatives), then reasonable decision-making rules are possible, e.g., Nash's rule in which we select an alternative for which the product of utilities is the largest possible. We also deal with two related issues: how we can detect individual preferences if all we have is preferences of a subgroup and how we take into account the mutual attraction between participants. © 2008 Wiley Periodicals, Inc.

It has been observed that when people make crude estimates, they feel comfortable choosing between alternatives that differ by a half-order of magnitude (e.g., were there 100, 300, or 1000 people in the crowd?) and less comfortable making a choice on a more detailed scale, with finer granules, or on a coarser scale (like 100 or 1000). In this article, we describe two models of choosing granularity in commonsense estimates, and we show that for both models, in the optimal granularity, the next estimate is three to four times larger than the previous one. Thus, these two optimization results explain the commonsense granularity. © 2006 Wiley Periodicals, Inc. Int J Int Syst 21: 843–855, 2006.

In a 1944 book that started game theory (and the mathematical approach to conflict resolution), von Neumann and Morgenstern proposed the notion of a solution. When the situation changes, the old solution is often no longer a solution, so it needs to be updated. In practical applications, it is usually desirable to keep the solution change “minimal” in some reasonable sense. We show that for a seemingly straightforward formalization of this minimality, checking whether a change is minimal is NP-hard. We also show that by representing the notion of a solution as a collection of revision rules, we can produce a reasonable notion of minimality for which there exists a feasible algorithm for checking the minimality of the update. © 2005 Wiley Periodicals, Inc. Int J Int Syst 20: 939–956, 2005.

A 1990 article in the American Mathematical Monthly has shown that most combinatorial identities of the type described in Monthly problems can be solved by known identity checking algorithms. A natural question arises: are these algorithms always feasible or can the number of computational steps be so big that application of these algorithms sometimes is not physically feasible? We prove that the problem of checking identities is nondeterministic polynomial (NP) hard, and thus (unless NP = P) for every algorithm that solves it, there are cases in which this algorithm would require exponentially long running time and thus will not be feasible. This means that no matter how successful computers are in checking identities, human mathematicians will always be needed to check some of them. © 2004 Wiley Periodicals, Inc.

In fuzzy logic, every word or phrase describing uncertainty is represented by a real number from the interval [0, 1]. There are only denumerable many words and phrases and continuum many real numbers; thus, not every real number corresponds to some common sense degree of uncertainty. In this article, for several fuzzy logics, we describe which numbers are describing such degrees, i.e., in mathematical terms, which real numbers are definable in the corresponding fuzzy logic. © 2003 Wiley Periodicals, Inc.

There are two main fuzzy system methodologies for translating expert rules into a logical formula: In Mamdani's methodology, we get a DNF formula (disjunction of conjunctions), and in a methodology which uses logical implications, we get, in effect, a CNF formula (conjunction of disjunctions). For both methodologies, universal approximation results have been proven which produce, for each approximated function f(x), two different approximating relations RDNF(x, y) and RCNF(x, y). Since, in fuzzy logic, there is a known relation FCNF(x) ≤ FDNF(x) between CNF and DNF forms of a propositional formula F, it is reasonable to expect that we would be able to prove the existence of approximations for which a similar relation RCNF(x, y) ≤ RDNF(x, y) holds. Such existence is proved in our paper. © 2002 Wiley Periodicals, Inc.

Several universal approximation and universal representation results are known for non-Boolean multivalued logics such as fuzzy logics. In this paper, we show that similar results can be proven for multivalued Boolean logics as well. © 2001 John Wiley & Sons, Inc.

Chess is probably the best known example of a game which is “biased”—in the sense that whoever starts the game has an advantage. From the commonsense viewpoint, the resulting bias should be the same whether we allow the players to play as usual: 1st, 2nd, 1st, 2nd, or whether we allow each player to make two moves at the same time. However, in practice, if we allow each player to make two moves in succession, the bias increases. In this paper, we provide a theoretical explanation for this empirical phenomenon. © 2001 John Wiley & Sons, Inc.

One of the reasons why fuzzy methodology is successful is that fuzzy systems are universal approximators, i.e., we can approximate an arbitrary continuous function within any given accuracy by a fuzzy system. In some practical applications (e.g., in control), it is desirable to approximate not only the original function, but also its derivatives (so that, e.g., a fuzzy control approximating a smooth control will also be smooth). In our paper, we show that for any given accuracy, we can approximate an arbitrary smooth function by a fuzzy system so that not only the function is approximated within this accuracy, but its derivatives are approximated as well. In other words, we prove that fuzzy systems are universal approximators for smooth functions and their derivatives. ©2000 John Wiley & Sons, Inc.

Function approximation is a very important practical problem: in many practical applications, we know the exact form of the functional dependence y=f(x1,…,xn) between physical quantities, but this exact dependence is complicated, so we need a lot of computer space to store it, and a lot of time to process it, i.e., to predict y from the given xi. It is therefore necessary to find a simpler approximate expression g(x1,…,xn)≈f(x1,…,xn) for this same dependence. This problem has been analyzed in numerical mathematics for several centuries, and it is, therefore, one of the most thoroughly analyzed problems of applied mathematics. There are many results related to approximation by polynomials, trigonometric polynomials, splines of different type, etc. Since this problem has been analyzed for so long, no wonder that for many reasonable formulations of the optimality criteria, the corresponding problems of finding the optimal approximations have already been solved. Lately, however, new clustering-related techniques have been applied to solve this problem (by Yager, Filev, Chu, and others). At first glance, since for most traditional optimality criteria, optimal approximations are already known, the clustering approach can only lead to non-optimal approximations, i.e., approximations of inferior quality. We show, however, that there exist new reasonable criteria with respect to which clustering-based function approximation is indeed the optimal method of function approximation. © 2000 John Wiley & Sons, Inc.

If we view fuzzy logic as a logic, i.e., as a particular case of a multi-valued logic, then one of the most natural questions to ask is whether the corresponding propositional logic is decidable, i.e., does there exist an algorithm that, given two propositional formulas F and G, decides whether these two formulas always have the same truth value. It is known that the simplest fuzzy logic, in which &=min and ∨=max, is decidable. In this paper, we prove a more general result: that all propositional fuzzy logics with algebraic operations are decidable. We also show that this result cannot be generalized further, e.g., no deciding algorithm is possible for logics in which operations are algebraic with constructive (nonalgebraic) coefficients. ©1999 John Wiley & Sons, Inc.14: 935–947, 1999

In many practical problems, we must optimize a set function, i.e., find a set A for which f(A)→max, where f is a function defined on the class of sets. Such problems appear in design, in image processing, in game theory, etc. Most optimization problems can be solved (or at least simplified) by using the fact that small deviations from an optimal solution can only decrease the value of the objective function; as a result, some derivative must be equal to 0. This approach has been successfully used, e.g., for set functions in which the desired set A is a shape, i.e., a smooth (or piece-wise smooth) surface. In some real-life problems, in particular, in the territorial division problem, the existing methods are not directly applicable. For such problems, we design a new simple differential formalism for optimizing set functions. ©1999 John Wiley & Sons, Inc.

One of the most important parts of designing an expert system is elicitation of the expert's knowledge. This knowledge usually consists of facts and rules. Eliciting these rules and facts is relatively easy: the more complicated task is assigning weights (numerical or interval-valued degrees of belief) to different statements from the knowledge base. Experts often cannot quantify their degrees of belief, but they can order them (by suggesting which statements are more reliable). It is, therefore, reasonable to try to reconstruct the degrees of belief from such an ordering.In this paper, we analyze when such a reconstruction is possible, whether it lead to unique values of degrees of belief, and how computationally complicated the corresponding reconstruction problem can be. © 1998 John Wiley & Sons, Inc.

In fuzzy logic, there are several methods of representing implication in terms of &, ∨, and ¬; in particular, explicit representations define a class of S implications, implicit representations define a class of R implications. Some reasonable implication operations have been proposed, such as Yager's ab, that are difficult to represent as S or R implications. For such operations, a new class of representations has recently been proposed, called A implications, for which the relationship between implications and the basic operations &, ∨, and ¬ is even more complicated. A natural question is: Is this complexity really necessary? In other words, is it true that A operations cannot be described as S or R operations, or they can, but we simply have not found these representations? In this paper we show that yes, the complexity is necessary, because there are operations that cannot be represented in a simpler form. © 1998 John Wiley & Sons, Inc.

In science and engineering, there are “paradoxical” cases in which we have some arguments in favor of some statement A (so the degree to which A is known to be true is positive (nonzero)), and we have some arguments in favor of its negation ¬A, and we do not have enough information to tell which of these two statements is correct. Traditional fuzzy logic, in which “truth values” are described by numbers from the interval [0, 1], easily describes such “paradoxical” situations: the degree a to which the statement A is true and the degree 1−a to which its negation ¬A is true can both be positive. In this case, if we use traditional fuzzy &-operations (min or product), the “truth value” a&(1−a) of the statement A&¬A is positive, indicating that there is some degree of inconsistency in the initial beliefs. When we try to use fuzzy logic to formalize expert reasoning in the humanities, we encounter the problem that is humanities, in addition to the above-described paradoxical situations caused by the incompleteness of our knowledge, there are also true paradoxes, i.e., statements that are perceived as true and false at the same time. For such statements, A&¬A=“true.” The corresponding equality a&(1−a)=1 is impossible in traditional fuzzy logic (where a&(1−a) is always≤0.5), so, to formalize such true paradoxes, we must extend the set of truth values from the interval [0, 1]. In this paper we show that such an extension can be achieved if we allow truth values to be complex numbers. © 1998 John Wiley & Sons, Inc.

We humans usually think in words; to represent our opinion about, e.g., the size of an object, it is sufficient to pick one of the few (say, five) words used to describe size (“tiny,” “small,” “medium,” etc.). Indicating which of 5 words we have chosen takes 3 bits. However, in the modern computer representations of uncertainty, real numbers are used to represent this “fuzziness.” A real number takes 10 times more memory to store, and therefore, processing a real number takes 10 times longer than it should. Therefore, for the computers to reach the ability of a human brain, Zadeh proposed to represent and process uncertainty in the computer by storing and processing the very words that humans use, without translating them into real numbers (he called this idea granularity). If we try to define operations with words, we run into the following problem: e.g., if we define “tiny” + “tiny” as “tiny,” then we will have to make a counter-intuitive conclusion that the sum of any number of tiny objects is also tiny. If we define “tiny” + “tiny” as “small,” we may be overestimating the size. To overcome this problem, we suggest to use nondeterministic (probabilistic) operations with words. For example, in the above case, “tiny” + “tiny” is, with some probability, equal to “tiny,” and with some other probability, equal to “small.” We also analyze the advantages and disadvantages of this approach: The main advantage is that we now have granularity and we can thus speed up processing uncertainty. The main disadvantage is that in some cases, when defining symmetric associative operations for the set of words, we must give up either symmetry, or associativity. Luckily, this necessity is not always happening: in some cases, we can define symmetric associative operations. © 1997 John Wiley & Sons, Inc.

The formal concept of logical equivalence in fuzzy logic, while theoretically sound, seems impractical. The misinterpretation of this concept has led to some pessimistic conclusions. Motivated by practical interpretation of truth values for fuzzy propositions, we take the class (lattice) of all subintervals of the unit interval [0, 1] as the truth value space for fuzzy logic, subsuming the traditional class of numerical truth values from [0, 1]. The associated concept of logical equivalence is stronger than the traditional one. Technically, we are dealing with much smaller set of pairs of equivalent formulas, so that we are able to check equivalence algorithmically. The checking is done by showing that our strong equivalence notion coincides with the equivalence in logic programming. © 1996 John Wiley & Sons, Inc.

Fuzzy control is a methodology that translates “if”-“then” rules, Aji (x1) &…& Ajn(xn) → Bj(u), formulated in terms of a natural language, into an actual control strategy u(x). Implication of uncertain statements is much more difficult to understand than “and,” “or,” and “not.” So, the fuzzy control methodologies usually start with translating “if”-“then” rules into statements that contain only “and,” “not,” and “or.” the first such translation was proposed by Mamdani in his pioneer article on fuzzy control. According to this article, a fuzzy control is reasonable iff one of the rules is applicable, i.e., either the first rule is applicable (A11(x1) &…& A1n(xn) & B1(u)), or the second one is applicable, etc. This approach turned out to be very successful, and it is still used in the majority of fuzzy control applications. However, as R. Yager noticed, in some cases, this approach is not ideal: Namely, if for some x, we know what u(x) should be, and add this crisp rule to our rules, then the resulting fuzzy control for this x may be different from the desired value u(x). to overcome this drawback, Yager proposed to assign priorities to the rules, so that crisp rules get the highest priority, and use these priorities while translating the rules into a control strategy u(x). In this article, we show that a natural modification of Mamdani's approach can solve this problem without adding any ad hoc priorities. © 1995 John Wiley & Sons, Inc.

The notion of a transitive closure of a fuzzy relation is very useful for clustering in pattern recognition, for fuzzy databases, etc. It is based on translating the standard definition of transitivity and transitive closure into fuzzy terms. This definition works fine, but to some extent it does not fully capture our understanding of transitivity. the reason is that this definition is based on fuzzifying only the positive side of transitivity: if R(a, b) and R(b, c), then R(a, c); but transitivity also includes a negative side: if R(a, b) and not R(a, c), then not R(b, c). In classical logic, this negative statement follows from the standard “positive” definition of transitivity. In fuzzy logic, this negative part of the transitivity has to be formulated as an additional demand. In the present article, we define a strongly transitive fuzzy relation as the one that satisfies both the positive and the negative parts of the transitivity demands, prove the existence of strong transitive closure, and find the relationship between strongly transitive similarity and clustering. © 1995 John Wiley & Sons, Inc.