Tansu KUCUKONCU , PhD
( Tansu KÜÇÜKÖNCÜ ( in Turkish alphabet ) )
FUZZY REASONING as a way of Automated Reasoning
( A SURVEY OF FUZZY LOGIC AND SET THEORIES )
OUTLINE
- INTRODUCTION
- A BRIEF OVERVIEW OF ORDINARY SET THEORY
. BASIC CONCEPTS
. HISTORY
. PROBLEMS (PARADOXES)
. RELATION BETWEEN SET THEORY AND LOGIC
- FUZZY SET AND LOGIC THEORIES
. CONCEPT OF FUZZINESS
. HISTORY
. BASIC DEFINITIONS
. MORE ON FUZZY SETS
. PROPERTIES OF FUZZY SETS
. GRAPHICAL INTERPRETATION OF FUZZY SETS
. FUZZY-VALUED LOGICS
. PARADOXES AND FUZZY LOGIC
. FUZZINESS VERSUS RANDOMNESS
. MEASURES OF FUZZINESS
. FUZZY REASONING
.. Translation Rules
.. Modifier Rules
.. Rules of Inference
. A SURVEY OF POTENTIAL APPLICATIONS
. PROBLEMS
- *** A PROPOSAL FOR ***
*** BIVALENT INTERPRETATION OF FUZZY LOGIC ***
*** AND FUZZY SET THEORIES ***
- PHILOSOPHICAL ASPECTS
- INTRODUCTION
Zadeh: "AI has not come to grips with common sense reasoning. It has not contributed significantly to the solution of real-world problems in robotics, computer vision, speech recognition, and machine translation. And AI arguably has not led to a significantly better understanding of
thought processes, concept formation, and pattern recognition."
He believes that this is because that AI restricted itself to ordinary logic. But most of the real world problems includes uncertainty and imprecision.
Zadeh:"Generally, fuzzy systems work well when we can use experience or introspection to articulate the fuzzy if-then rules".
[3, Foreword]
Fuzzy systems run subways, tune tv.s and computer disc heads, focus and stabilize cameras and camcorders, adjust air conditioners and washing machines and vacuum sweepers, defrost refrigirators, schedule elevators and traffic lights, and control automobile motors, suspensions,
and emergency breaking systems, control cruises, cement mixers, guide robot-arm manipulators, recognize charecters, select golf clubs, even arrange flowers. [3, Preface]
Fuzziness provides a fresh, and deterministic, interpretation of probability and randomness. [3,3]
Mathematically fuzziness means multivaluedness or multivalence and stems from the Heisenberg position-momentum uncertainty principle in quantum mechanics. Three-valued fuzziness corresponds to truth, falsehood, and indeterminacy, or to presence, absence, and ambiguity. Multivalued fuzziness corresponds to degrees of indeterminacy or ambiguity, partial occurance of events or relations.
Neural networks and fuzzy systems estimate input-output function. Both are trainable dynamical systems. Unlike statistical estimators, they estimate a function without a mathematical model of how outputs depend on inputs. They are model-free estimators. They "learn from experience" with numerical and, sometimes, linguistic sample data. [3, 13]
Fuzzy systems reason with parallel associative inference. When asked a question or given an input, a fuzzy system fires each rule in parallel, but to different degree, to infer a conclusion or output. Thus fuzzy systems reason with sets, fuzzy or multivalued sets, instead of bivalent
propositions.
Adaptive fuzzy systems learn to control complex processes as much as we do. [3, 18]
- A BRIEF OVERVIEW OF ORDINARY SET THEORY
. BASIC CONCEPTS
Basically, a set can be defined as a collection of objects, generally, which have similar properties or attributes.
The main concept related to sets is elementhood, or equivalently membership.
Let X be a classical set of objects, called the universe, whose generic elements are denoted x. Membership in a classical subset A of X is often viewed as a charecteristic function f.A.(x) from X to {0,1} such that
1 iff x E A,
f.A.(x) =
0 iff x !E A.
{0,1} is called a valuation set. [2, 10]
. HISTORY
The birth of the set theory can be recognized in Cantor's paper in 1874 in Crelle's Journal (in German). [6, 23]
One of the first attemps to axiomatize set theory was performed by Frege. But his system was failed by the invention of Russel's paradox.
Then a first powerful axiomatized set theory was constituted by Zermaelo, including a solution for avoiding Russel's paradox.
. PROBLEMS (PARADOXES)
Basically, a paradox is a proposition having both true and false as its truth value. It can be said that a paradoxial statement is both true and false, or neither true nor false.
The famous paradox is of Russel. It is the set of objects which is not an element of itself.
Some famous linguistic forms of Russel's paradox:
Does the liar from Crete lie when he says that all Cretans are liars ? If he lies, he tells the truth. If he tells the the truth, he lies.
Russel's barber is a man in a town whose advertises his service with the logo "I shave all, and only, those men who don't shave themselves". Who shaves the barber ? If he shaves himself, then according to the logo he does not. If he does not, then according to the logo he does.
And lastly, consider the card that says on one side "The sentence on the other side is true", and says on the other side "The sentence on the other side is false".
. RELATION BETWEEN SET THEORY AND LOGIC
Logic provides a strong link between philosophy and sciences, especially via mathematics.
There are usually considered to be three principal present-day school of mathematics: the intuituonist, formalist, and logistic schools. [6, 69]
The thesis of the logistic school is that mathematics is a branch of logic. Mathematical concepts are to be formulated in terms of logical concepts, and all the theorems of mathematics are to be developed as theorems of logic. [6, 73]
Set theory is one of the bases of mathematics. It also tries to supply ontological support to mathematics. Ontological reasons are its link to philosophy, and hence logic. Because of this relation, there is a relation between basic set theoretic operations (union and inclusion) and
basic logical operators (or connectors; "and" and "or").
- FUZZY SET AND LOGIC THEORIES
A.Einstein:"So far as the laws of mathematics refer to reality, they are not certain. And so far as they are certain, they do not refer to reality". [3, 263]
. CONCEPT OF FUZZINESS
"The class of all real numbers much greater than 1", or "the class of beautiful women", or "the class of tall men" do not constitute classes or sets in the usual mathematical sense of these terms. Such imprecisely defined "classes" play an important role in human thinking, particularly in the domains of pattern recognition, communication of information,
and abstraction [1,338].
The concept in question is that of a fuzzy set, that is class with a
continuum of grades of membership. The notion of fuzzy set provides a
convenient point of departure for the construction of conceptual framework which parallels in many respects the framework used in the case of ordinary sets, but is more general than the latter and, potentially, may prove to have a much wider scope of applicability, particularly in
the fields of pattern classification and information processing. Such a framework provides a natural way to dealing with problems in which the source of imprecision is the absence of sharply defined criteria of class membership [1,339].
. HISTORY
Fuzziness in the 20th Century. Logical paradoxes and the Heisenberg uncertainty principle led to the development of multivalued or fuzzy logic in the 1920s and 1930s. Quantum theorists allowed for indeterminacy by including a third or middle truth value in the bivalent logical framework. The next step allowed degrees of indeterminacy, viewing TRUE and
FALSE as the two limiting cases of spectrum of indeterminacy.
The Universe as a Fuzzy Set. The Heisenberg uncertinty principle, with its continuum of indeterminacy, forced multivaluedness on science, though few Western philosophers have accepted multivaluedness, Lukasiewicz, Godel, and Black did accept it and developed the first multivalued or fuzzy logic and set systems.
Fuzziness arises from the ambiguity or vagueness between a thing and its opposite !A. If we do not know A with certainty, we do not know !A with certainty either. Else by double negation we would know A with certainty. This ambiguity produces nondegenerate overlap: A | !A != O, which breaks the law of noncontardiction. Equivalently, it also produses nondegenerate underlap: A U !A != X, which breaks the law of excluded middle. Here X denotes the ground set or universe of discourse. [3, 269]
Polish logician Jan Lukasiewicz first formally developed a three-valued logical system in the early 1930s. Lukaziewicz, finally, extended the range of truth values to all numbers in [3, 1].
In the 1930s quantum philosopher Max Black applied continuous logic
componentwise to sets or lists of elements or symbols. Historically, Black
drew the first fuzzy-set membership functions. Black called the uncertainty of these structures "vagueness". Anticipating Zadeh's fuzzy-set theory, each element in Black's multivalued sets and lists behaved as a statement in a continuaus logic.
In 1965 systems scientists Lotfi Zadeh published the paper "Fuzzy Sets" that formally developed multivalued set theory, introduced the term fuzzy into the technical literature, and inaugurated a second wave of interest in multivalued mathematical structures, from systems to
topologies. [3, 6]
A Zermelo-Fraenkel-like axiomatization, formulated in ordinary first-order logic with equality, was first investigated by Netto (1968), and completely developed by Chapin (1974). [2, 16]
. BASIC DEFINITIONS
A fuzzy set (class) A in X (universe of discourse) is charecterized by a membership (charecteristic) function f.A.(x) which associates with each point in X a real number in the interval [0,1], with the value of f.A.(x) at x representing the "grade of membership" of x in A. The nearer the value of f.A.(x) to unity, the higher the grade of membership of x in A [1,339].
W x f.x.(x) = 1. [2, 10] (This contradicts with Russel's paradox; my note)
When A is an ordinary subset of X, the pair (A, !A) is a partition of X provided that A != O and A != X. When A is a fuzzy set (!=O, !=X), the pair (A, !A) is called a fuzzy partition. [2, 13]
A fuzzy set is empty iff its membership function is identically zero on X [1,339]; that's, W xEX, f.0.(x) = 0. [2, 10]
Two fuzzy sets A and B are equal, written as A = B, iff f.A.(x) = f.B.(x) for all x in X [1,339].
I will use f.A as an equivalent of f.A.(x) for notational simplicity.
The complement of a fuzzy set A is donated by !A and is defined by
f.!A = 1 - f.A [1,340]
Containment. A is contained in B (or A is a subset of B, or A is included in B, or A is smaller than B) iff f.A <= f.B . In symbols A C B <=> f.A =< d =" A" d =" f.A" d =" A" d =" f.A" a =" (" b =" (.9" b =" (.9" b =" (" a =" (" a =" (" a =" ("> f.A*B = f.A * f.B ; such that
A * B C A | B [1, 344]
and a so-called algebraic sum
A + B -> f.A+B = f.A + f.B
provided that the sum f.A + f.B is less than equal to unity. [1, 344]
and probabilistic sum again for for union:
A +- B -> f.A+-B = f.A + f.B - f.A * f.B [4, 14] [2, 16]
Absolute Difference. f.|A-B| = |f.A - f.B| . In the case of ordinary sets this reduces to the relative complement of A | B in A U B . [1, 344]
Fuzzy sets defined in a finite universe of discourse X can be represented as lists structuring information about grades of membership at individual points of X. For instance, a list composed of two-element sublists:
[ [x1, 1.0] [x2, 0.8] [x3, 0.5] [x4, 0.0] ]
denotes a fuzzy set A with these grades of membership:
A(x1) = 1.0 , A(x2) = 0.8 , A(x3) = 0.5 , A(x4) = 0.0
Then the logic operations can be defined pointwise using a PROLOG-like
notation:
AND(a,b):- min(a,b)
OR(a,b):- max(a,b)
NEG(a):- 1.0 - a
where a and b are two grades of membership. [4, 9]
. MORE ON FUZZY SETS
The support of a fuzzy set A is the ordinary subset of X:
supp A = {xEX, f.A.(x) > 0}
The elements of x such that f.A.(x) = 1/2 are the crossover points of A. [2, 10]
By the height of a fuzzy set A, hgt(A), we mean a maximal value of its membership function:
hgt(A) = sup.xEX.A(x) [4, 6]
a-cuts (alfa-cuts) (in the literature these are also called as level fuzzy sets). When we want to exhibit an element xEX that typically belongs to a fuzzy set A, we may demand its membership value to be greater than some thresh-old a E [0, 1]. The ordinary set of such elements is the
a-cut A_a of A,
A_a = {xEX, f.A.(x) >= a}.
One also defines the strong a-cut
A__a = {xEX, f.A.(x) > a}.
The essence of an a-cut operation is that it allows us to convert a fuzzy set into its Boolean counterpart. [4, 23]
Bounded Difference, |-|
W xEX, f.A|-|B.(x) = Max [0, f.A.(x) - f.B.(x)]
It is the fuzzy set of elements that belong to A more than B.
Symmetrical Difference,
W xEX, f.A/-B.(x) = |f.A.(x) - f.B.(x)| (not associative)
It is elements belong more to A than to B or conversely.
W xEX, f.A-/B.(x) =
Max [Min [f.A.(x), 1 - f.B.(x)], Min [1 - f.A.(x), f.B.(x)] (associative)
Its elements approximately belong to A and not to B, or conversely to B and not to A. [2, 18]
m.th power of a fuzzy set. A**m is defined as
f.A**m.(x) = f.A.(x) ** m
This operator is used to model linguistic hedges. [2, 19]
How big is a fuzzy set ? The size or cardinality of A, M(A), equals the sum of the fit values of A:
card(A) = M(A) = Sum.i.1.n(m.A(xi))
For instance, the count of A = (1/3 1/4) equals M(A) = 1/3 + 1/4 = 13 / 12. The measure M has a natural geometric interpretation in the set-as-points framework. M(A) equals the magnitude of the vector drawn from the origin to the fuzzy set.
M(A) = Sum.i.1.n(|m.A.(xi) - m.O.(xi)|) = l1(A, O)
(Fuzzy Hamming distance) [3, 275]
. PROPERTIES OF FUZZY SETS
1. Commutativity : A U B = B U A ; A | B = B | A
2. Associativity : A U (B U C) = (A U B) U C ;
A | (B | C) = (A | B) | C
3. Idempotency : A U A = A ; A | A = A
4. Distributivity : A U (B | C) = (A U B) | (A U C) ,
( Max [f.A, Min [f.B, f.C]] =
Min [Max [f.A, f.B], Max [f.A, f.C]] ) ;
A | (B U C) = (A | B) U (A | C) ,
( Min [f.A, Max [f.B, f.C]] =
Max [Min [f.A, f.B], Min [f.A, f.C]] )
5. A U O = A ; A | X = A
6. Absorption : A U (A | B) = A ; A | (A U B) = A
7. De Morgan's Laws : !(A U B) = !A | !B ,
( 1 - Max [f.A, f.B] = Min [1 - f.A, 1 - f.B] ) ;
!(A | B) = !A U !B ,
( 1 - Min [f.A, f.B] = Max [1 - f.A, 1 - f.B] )
8. Involution : !(!A) = A
9. Equivalence Formula :
(!A U B) | (A U !B) = (!A | !B) U (A | B)
10. Symmetrical Difference Formula : (Exclusive Disjunction)
(!A | B) U (A | !B) = (!A U !B) | (A U B)
The only law of ordinary fuzzy set theory that is no longer true is the excluded-middle law :
A | !A != 0 ; A U !A != X [2, 15] [1, 342]
Since the fuzzy set A has no definite boundary and neither has !A, it may seem natural that A and A overlap. However, the overlap is limited, since
W A, W x, Min [f.A.(x), f.!A.(x)] <= 1/2. For the same reason, A U !A do not exactly cover X; however, W A, W x, Max [f.A.(x), f.!A.(x)] >= 1/2. [2, 16]
Fuzzy Relation. A relation (which is a generalization of a function) is defined as a set of ordered pairs, e.g. the set of all ordered pairs of real numbers x and y such that x >= y. In the concept of fuzzy sets, a fuzzy relation in X is a fuzzy set in the product space X x X.
More generally, one can define an n-ary fuzzy relation in X as a fuzzy set A in the product space X x X x .... x X. [1, 345]
In PROLOG notation, we can express fuzzy relations as arrays enumerating all elements of the Cartesian product along with their numerical values. For example:
[ [x1, y1, 1.0] [x1, y2, 0.7] [x1, y3, 0.0]
[x2, y1, 0.1] [x2, y2, 0.3] [x2, y3, 0.9] ] [4, 26]
A fuzzy expression is a function from [0,1]n to [0,1] defined by the
following rules only :
1. 0,1, and variables xi,1 = 1, n, are fuzzy expressions;
2. if f is a fuzzy expression, then !f is a fuzzy expression;
3. if f and g are fuzzy expressions, then f & g and f V g are
too. [2, 152]
Since excluded-middle is no longer hold on ([0,1], &, V, !), there is no unique way to represent a fuzzy expression as a disjunction of phrases. [2, 153]
Boolean Karnaugh maps have also been extended to deal with fuzzy expressions. [2, 156]
. GRAPHICAL INTERPRETATION OF FUZZY SETS
The Geometry of Fuzzy Sets: Sets as Points. Fuzzy theorists often picture membership functions as two dimensional graphs, with the domain X represented as a one-dimensional axis. The geometry of fuzzy sets involves both the domain X = {x1,.., x2} and the range [0,1] of
mappings m.A: X -> [0,1]. The geometry of fuzzy sets aids us when we describe fuzziness, define concepts, and prove fuzzy theorems. Visualising this geometry may by itself provide the most powerful argument for fuzziness. [3, 269]
Sets and fuzzy sets defined in a finite universe of discourse, card(X) = n, have an interesting and transparent geometrical interpretation. It is obvious that any set defined in X is equivalent to a string of bits (0 or 1) of fixed length n. This in turn can be viewed as a point situated at one of the corners of the unit hypercube [0,1].n. [4, 12]
Fuzzy sets constitute a genuine generalization of sets, making the interior of the square (or hypercube, in general) accessible. [4, 12]
Fuzzy sets form finite strings composed of any numbers between 0 and 1 (so-called fits). [4, 12]
What does the fuzzy power set F(2**x), the set of all fuzzy subsets of
X look like ? It looks like a cube. What does a fuzzy set look like ? A point in a cube. The set of all fuzzy subsets equals the unit hypercube I.n = [0,1].n . A fuzzy set is any point (Kosko, 1987) in the cube I.n . [3, 269]
Vertices of the cube I.n define nonfuzzy sets. So the ordinary power set 2**X, the set of all 2**n nonfuzzy subsets of X, equals the Boolean n-cube B.n: 2**X = B.n . Fuzzy sets fill in the lattice B.n to produce the solid cube I.n: F(2**X) = I.n . [3, 270]
The midpoint of the cube I.n is maximally fuzzy. All its membership values equal 1/2. The midpoint is unique in two respects. First, the midpopint is the only set A that not only equals its own opposite !A but equals its own overlap and underlap as well:
A = A | !A = A U !A = !A
Second, the midpoint is the only point in the cube I.n equidistant to each of the 2**n vertices of the cube. The nearest corners are also farthest. [3, 270]
Laws of contradiction and excluded middle holds only at the 2**n vertices of I.n . [3, 271]
At the midpoint nothing is distinguishable. At the vertices everything is distinguishable. These extremes represent the two ends of the spectrum of logic and set theory, In this sense the midpoint represents the black hole of set theory. [3, 271]
. FUZZY-VALUED LOGICS
A fuzzy-valued logic is a many-valued logic where the truth space is the set of the fuzzy numbers on the interval [0,1]; i.e the truth value of a proposition is a fuzzy number whose suppport is included in [0,1]. Such fuzzy numbers may model linguistic truth values whose names are "true", "very true", "borderline", "false", etc. [2, 171]
The problem of inference is less straightforward in fuzzy-valued logic
than in multivalent logic, i.e. find v(Q) when you know v(P) and v(P |=>
Q) where |=> is some implication connective. [2, 173]
We notice that in a chain of approximate inferences, truth and precision progres in the same sense, conclusions are always less precise true than premises. [2, 173]
Many authors have used the expression "fuzzy logic" to denominate some multivalent logics, especially Lukaziewicz's continuous valued logics, which underlies Zadeh's fuzzy set theory. Zadeh employs "fuzzy logic" to designate a logic on which a theory of approximate reasoning is based.
[2, 169]
Zadeh's fuzzy logic theory appears to be a promising methodology for modelling human reason. [2, 151]
. PARADOXES AND FUZZY LOGIC
The paradoxes have the same form. A statement S and its negation not-S have the same truth-value t(S):
t(S) = t(not-S).
This violates the laws of noncontradiction and excluded middle.
t(S) = 1 - t(not-S), and
t(not-S) = 1 - t(S).
But in fuzzy or multivalued interpretation :
t(S) = 1 - t(S),
t(S) = 1/2 = t(not-S)
So the paradoxes reduce to half-truths. Geometrically, the fuzzy approach places the paradoxes at the midpoint of the one-dimensional unit hypercube [0,1]. More general paradoxes reside at the midpoint of n-dimensional hypercubes, the unique point equidistant to all 2**n vertices. [3, 4]
Multivauedness also resolves the classical Sorites paradoxes. Consider a heap of sand. Is it still a heap if we remove ine grain of sand ? How about two grains ? Three ? We transition gradually, not abruptly, from a thing to its oppposite. We arrive again at the degrees of truth. [3, 5]
. FUZZINESS VERSUS RANDOMNESS
(Differences between Fuzzy set theory and Probabilistic set theory)
Randomness and fuzziness differ conceptually and theoretically. But, they also have similarities. Both systems describe uncertainty with numbers in the unit interval [0,1]. This ultimately means that both systems describes uncertainty numerically. Both systems combine sets and propositions associatively, commutatively, and distributively. The key
distinction concerns how the systems jointly treat a set A and its opposite !A. Classical set theory demands A | !A = O, and probability theory conforms:
P(A | !A) = P(O) = 0.
So A | !A represents a probabilistically impossible event. But fuzziness begins when A | !A != O.
Fuzziness describes event ambiguity. It measures the degree to which an event occurs, not whether it occurs. Randomness describes the uncertainty of event occurance. Whether an event occurs is random. To what degree it occurs is fuzzy. [3, 265]
Consider parking your car in a parking lot with pinted parking spaces. You can park in any space with some probability. Your car will totally occupy one space and totally unoccupay all other spaces. The probability number reflects a frequency history or Bayesian brain state that summarizes which parking space your car will totally occupy. Alternatively, you can park in every space to some degree. Your car will partially, and deterministically, occupy every space. In practice your car will occupy most spaces to zero degree. Finally, we can use numbers in [0,1] to describe, for each parking space, the occurance probability of each degree of partial occupancy -probabilities of fuzzy events. [3, 266]
Fuzziness is a type of deterministic uncertainity. Ambiguity is a property of physical phenomena. Unlike fuzziness, probability dissipates with increasing information. [3, 267]
Is uncertainty the same as randomness ? Many people, trained in probability and statistics, belive so. Especially people in Bayesian camp of statistics, where probabilists view probability not as a frequency or other
objective testable quantity, but as a subjective state of knowledge,
defends this idea. [3, 264]
. MEASURES OF FUZZINESS
How fuzzy is a fuzzy set ? Various authors have proposed scalar indices to measure the degree of fuzziness of a fuzzy set. The degree of fuzziness is assumed to express on a global level the difficulty of deciding which elements belong and which do not belong to a given fuzzy set.
[2, 32]
Mathematically, a measure of fuzziness is a mapping d from fuzzy universe, X, to [0, +inf) satisfying the conditions :
1. d(A) = 0 iff A is an ordinary subset of X;
2. d(A) is maximum iff f.A.(x) = 1/2, W xEX;
3. d(*A) <= d(A), where *A is any sharpened version of A, that's f.*A.(x) <= f.A.(x) if f.A.(x) <= 1/2 , and f.*A.(x) >= f.A.(x) if f.A.(x) >= 1/2 ;
4. d(A) = d(!A) (!A is as fuzzy as A) . [2, 32]
Particular forms of d are :
Index of fuzziness (Kaufmann, 1975) : d(A) is the
distance between A and the closest ordinary subset of X to A
using a Hamming distance, i.e
d(A) = Sum.i.1.|M| (|f.A.(xi) - f.A_1/2.(xi)|)
where A_1/2 is the 1/2-cut of A. [2, 33]
Note. Measures of fuzziness evaluate A and !A at the same time. They can be extended to evaluate a whole fuzzy partition in order to give a rating of the total amount of ambiguity that arises when deciding to which of A1,...,Am an element x belongs.
Remark. Instead of using a quantitive measure of fuzziness, we may simply employ a qualitative typology, as suggested by Kaufman (1975), in order to classify fuzzy sets in rough categories such as "slightly fuzzy",
"almost precise", "very fuzzy".
The Fuzzy Entropy Theorem : One of most common measures of fuzziness entropy. Entropy is a generic notion. It need not be probabilistic. Entropy measures the uncertainty of a system or message. Its uncertainty equals its fuzziness.
The fuzzy entropy of A, E(A), varies from 0 to 1 on the unit hypercube I.n . The only cube vertices have zero entropy, since nonfuzzy sets are unambiguous. The cube midpoint uniquely has unity or maximum entropy. Fuzzy entropy smoothly increases as a set point moves from any vertex to the midpoint.
Simple geometric considerations lead to a ratio for the fuzzy entropy (Kosko, 1986). The closer the fuzzy set A is to the nearest vertex A.near, the farther A is from the farthest vertex A.far . The farthest vertex A.far resides opposite the long diagonal from the nearest vertex A.near . Then fuzzy entropy:
E(A) = l1(A, A.near) / l1(A, A.far) = a / b
Ex. A = (1/3 3/4)
A.near = (0,1) , A.far = (1, 0)
a = 1/3 + 1/4 = 7/12
b = 2/3 + 3/4 = 17/12
E(A) = a / b = 7/17 [3, 275]
Fuzzy Entropy Theorem : E(A) = M(A | !A) / M(A U !A)
[3, 277]
Fuzzy entropy differs from the average-information measure of probabilitistic entropy, which the uniform distribution maximizes uniquely.
The event x can be ambiguous or clear. It is ambiguous if f equals approximately 1/2 and clear if f equals approximately 1 or 0. If an ambiguous event occurs, then it is maximally informative: E(f) = E(1/2) = 1. If a clear event occurs, it is minimally informative:
E(f) = E(0) = E(1) = 0. [3, 278]
. FUZZY REASONING
Informally, by approximate or, equivalently fuzzy reasoning we mean the process or processes by which a possibly imprecise conclusion is deduced from a collection of imprecise premises. Such reasoning is, for the most part, qualitative rather than quantitative in nature and almost all
of it falls outside the domain of applicability of classical logic. [2, 173]
Consider statements like P : "X is A" is a fuzzy set on T inducing a possibility distribution pd.h.(x) = pd.h = f.A . h is an attribute of X and T is the measurement scale of h. For example, in "X is tall", A = "tall" is modeled by a fuzzy set on the universe T of heights. In fact, the statement can be viewed as equivalent to an infinity of statements P.t : "t
is the height of X" with v(P1) = f.A.(t), tET, since t belongs to the fuzzy set A of large heights. If t is s fuzzy set height t (for instance "approximately 5"),
v(Pi) = ||(t) = hgt(A | T)
where || is the possibility measure associated with f.A .
In order to perform approximate reasoning with statements similar to "X is A", but more complex, we need translation rules so as to model them as possibility distributions, modifier rules in order to perhaps transform them in semantically equivalent possibility distributions, and rules of inference to deduce new possibility distributions. We are not interested here in the question of retranslating these possibility distributions in natural language (that's linguistic approximation). [2,174]
.. Translation Rules
By translation is meant a set of rules that yield the translation of a modified composite proposition from the translations of its constituents, e.g. from P => pd.X = f.A and Q => pd.Y = f.B deduce P & Q => pd.(X,Y) . There are four types of translation rules.
1. Modifier rules for simple propositions. Given the proposition P : "X
is A such that pd.x = f.A, find pd2.x = f.A2 related to "x is mA" where m is a modifier such as "not", "very", "more or less", ... : A2 is given by A2 = mA. Each modifier is related to a function g such that
f.A2 = g o f.A ("not": g(x)=1-x , "very": g(x)=x**2 , "more or less":
f.(x)=sqrt(x))
2. Composition rules. They pertain to the translation of a proposition
P that is a composition of propositions Q and R, such as conjunction, disjunction, implication.
3. Quantification rules. These rules work on propositions of the form P:
"X are A" where F is a fuzzy quantifier (e.g. "most", "many", "few", "some"...). F is a fuzzy set on [0,1] usually. F indicates a fuzzy proportion. There arises two problems which we deal with separately.
a. Knowing A and F, fuzzy sets respectively on T and on [0,1], find the possible density functions that are compatible with the statement "FX are A".
b. Find F from knowledge of a density function pd on T = R made out of a set of measurements (h(X), XEU) and of a fuzzy bound B E fuzzy lattice.
More generally, we can translate propositions like "FX in C are A" where C is a fuzzy set on U acting as a fuzzy restriction on the values of X. For instance, F = "many", C is the fuzzy set of the tall men. A means "fat": "many tall men are fat". We are interested in the proportion of X that are in C. [2, 174]
4. Qualification rules. Among pertinent qualifications for propositions
Zadeh considered three of them in particular:
a. Linguistic truth qualification. A truth-qualified version of a proposition such as "X is A" is a proposition expressed as "X is A is k" where k is a linguistic truth value.
b. Linguistic probability qualification. A probability-qualified version of a proposition such as "X is A" is a proposition expressed as "X is A is y" where y is a linguistic probability value such as "likely", "very likely"... This may be interpreted as "P(A) is y" where A is viewed as a fuzzy event whose probability is P(A). [2, 176]
c. Linguistic possibility qualification. A possibility-qualified version of proposition such as "X is A" is a proposition expressed "X is A is w" where w is a linguistic possibility value such as "possible", "very
possible", "almost possible"... w is viewed as a fuzzy restriction on
the nonfuzzy possibility values ||(A) of the fuzzy event A. [2, 177]
According to Zadeh (1977) these rules should be regarded as provisional in nature. Their relationships to the theory of possibilities and (fuzzy) modal logic have not yet been clear. [2, 177]
.. Modifier Rules
a. Semantic equivalence and entailment. P and Q are said to be
semantically equivalent iff pd.P = pd.Q, which is denoted by P <=> Q.
P semantically entails Q, that's P => Q, iff pd.P =C pd.Q
b. Modifier rules for propositions. If m is a modifier and P is a
proposition, then mP is semantically equivalent to the proposition that results from applying m to the possibility distribution induced by P.
i. Simple propositions. m("X is A") <=> "X is mA"
ii. Composed propositions. m("X is A and Y is B") <=> (X,Y) is
m(A x B)
iii. Quantified propositions. m("FX are A") <=> "(mF)X are A"
iv. Qualified propositions. m("X is A is d") <=> "X is A is md"
.. Rules of Inference
The main rules of inference in approximate reasoning are
1. the projection principle. For instance A: "tall", B: "fat", from P: "John
is tall and fat" we infer "John is tall" provided that hgt(A) = hgt(B).
2. the particularization / conjunction principle. It may be viewed as a
special case of a somewhat more general principle, which will be referred to as the conjunction principle.
This is the extended version of ordinary logics "conjunction introduction" principle.
3. the entailment principle. It asserts that from any proposition P, we
can infer a proposition Q, if the possibility distribution induced by P is contained in the possibility distribution induced by Q. For instance, from
P:"X is very large" we can infer Q: "X is large".
Once combined the first two lead to generalized modus ponens.
4. Compositional rule of inference. The compositional rule of inference
consists in the successive application of the particularization / conjunction principle followed by that of the projection principle. [2, 182]
An important special case of the compositional rule of inference is obtained when P and Q are of the form P:"X is A" , Q:"If X is A, then Y is B" . [2, 182]
Generalized Modus Ponens: (schematically)
P:"X is A2"
Q:"If X is A, then Y is B"
R:"Y is A2 o (c(A) |=> c(B))" , where |=> denotes any of implication, where c(A) and c(B) are cylindiric extensions of A and B.
In the classical modus ponens: A2 = A and the inferred
proposition is "Y is B". [2, 183]
The modus ponens rule allows Q to be inferred from P and P => Q in propositional calculus. In multivalent logics the problem is to compute v(Q) given v(P) and v(P |=> Q) where |=> is any given multivalent implication. [2, 167]
Generalized modus ponens may be viewed as a generalized interpolation. [2, 184]
One interesting questions, which have not been completely solved yet are: consistency of the rules, redundancy of the set of rules, and the converse problem, i.e. determining the rules form knowledge of R. Lastly, the compositional rule of inference has been extended to possibility-qualified propositions of the form "X is A is 1-possible". [2, 184]
.. More on Inference Rules
Ordinary logic's inference rules:
Modus Ponens:
We have (If A then B) and we know that A is true. From these we can infer B.
Modus Tollens:
We have (If A and B) and we know that B is false. From these we can infer !A.
Modus Tollendo Ponens:
We have (A or B) and we know that A is false. From these we can infer B.
Addition:
If we have a true proposition, then any or combination of it is true
Conjunction Introduction:
If we have n true propositions, then their and combinations is true.
Conjunction Elimination:
If we have a combined true proposition consists of n propositions all of which are connected via "and" operator, then each of these n propostions is true.
. A SURVEY OF POTENTIAL APPLICATIONS
a. Artificial Intelligence and Robotics
According to Zadeh, "The key elements in human thinking are not numbers but labels of fuzzy sets". Examples of research subjects (most of them has been implemented):
Construction of robust systems, i.e. systems "able to respond without program modification to slightly perturbed, or to somewhat inexactly specified situations".
Modeling natural language for man-machine communication.
Guiding robots using fuzzy instructions.
Designing systems that able to "understand" sentences that fuzzily designates objects.
Implementation of a flexible language to modifgy graphic facial images.
Construction of an interactive robust system that is able to recognize slightly mispelled words (but the use of fuzzy concepts is limited to the idea of similarity)
Employment of fuzzy automata and fuzzy grammars for coordination and task task organization in hierarchical control of prosthetic devices. [2, 358]
b. Image Processing and Speech Recognition
Examples:
A fuzzy relaxation approach to scene labeling.
Using local max and min operations for noise removal on gray-scale pictures.
Detecting moving objects in a sequence of images by means of heuristic rules involving fuzzy texture indices on the level of gray of the pixels.
A computer aided system for art-oriented image generation.
Speech understanding systems for lexial classification and for semantic analysis of sentences.
Vowel and speaker recognition.
c. Biological and Medical Sciences
d. Control
e. Applied Operations Research
f. Economics and Geography
g. Sociology
h. Psychology
i. Linguistics
j. Semiotics
etc.
. PROBLEMS
Quite some research has been done in order to find methods to determine the precise shape of the fuzzy set should have. Some techniques are based on statistical observations (if at all possible) others are more subjective. However none of these techniques is very satisfactory since in the process of determining the fuzzy sets in the actual meaning of the numerical value of the fuzzy set in particular
points becomes undetermined. [5, 13]
In general, given a basic set X, what seems to be required is a kind of metric structure on X giving a distance between points or more generally a distance from points to sets. Once such a structure is given the determination of a particular fuzzy set then depends on at least two further choices:
1. the determination of an ideal set J, a set of points absolutely (with
degree one) fulfilling the fuzzy proposition,
2. the determination of a shape for the fuzzy set on X\J subject to the
condition that the numerical values decrease with increasing distance to J.
It is our contention that whereas the determination of the metriclike structure on X and the determination of the ideal set J shall be strongly dictated by the problem at hand and consequently have a low "degree of arbitrariness", the determination of the shape of the fuzzy set on X\J on the contrary is totally arbitrary. The fact that so many ad hoc techniques are devised to produce these numerical values is one more proof of this claim. We therefore also believe that the theory might be served by the omission of this third and quite unnecessary step. There are two steps we can omit:
1. we do not make the transition distance -> degree of membership
2. we do not squeeze the numerical information into the unit interval
For 1. this means that if the distance from a point x to an ideal set J is small then we shall maintain this small numerical value just as it is
instead of associating with it in some ad hoc manner a number close to 1. [5, 15]
.. Philosophical Problems
The most appearent one is the directly usage of numbers as degrees of membership. If we will use set theory to provide ontological bases to mathematics, each concept we will use for this purpose should be well defined. So, we should define concepts of numbers before using them. (I also should remark that, almost every time, this is done by aximatization; but axiomatization is another subject of discussion).In bivalent logics concept of numbers -beginning with natural ones- is given using cardinality notion.
Concepts of universal set and empty set are seemed to have problems, too. I leave these to "philosophical aspects" section.
- *** A PROPOSAL FOR ***
*** BIVALENT INTERPRETATION OF FUZZY LOGIC ***
*** AND FUZZY SET THEORIES ***
Assume a set of objects consisting of n elements. Define n alternative (or possible) worlds. Give priorities to this worlds between that of w0 and wp, such that w0 having the greatest and wp having the least priorities.
w0 : world of generalities or ideal world; in which every proposition is either true or false (or a set of which an object is just its element or not)
wp : world of paradoxes or neutral world; in which any proposition is neither true nor false -or both true and false- (or a set of which an object is neither its element nor not -or both its element and not)
Basic notation I will use in this section:
P(wi) : A proposition valid in the world with a priority related to i.
v(P(wi)) = v(Pi) = v(P): Truth value of a proposition
valid in the world with a priority related to i.
wi(t) : A true proposition in world i.
wi(f) : A false proposition in world i.
. Logical Operations.
Negation : P(wi) -> !P(wi) (Just as ordinary case)
v(!P) = 1 - v(P)
That is, !wi(t) = wi(f), and !wi(f) = wi(t).
And
P(wi) & Q(wi) (Ordinary)
P(wi) & Q(wj) (wj has a higher priority) :
wi(t) & wj(t) = wi(t)
wi(t) & wj(f) = wj(f)
wi(f) & wj(t) = wi(f)
wi(f) & wj(f) = wj(f)
Or
P(wi) V Q(wi) (Ordinary)
P(wi) V Q(wj) (wj has a higher priority)
wi(t) V wj(t) = wj(t)
wi(t) V wj(f) = wi(t)
wi(f) V wj(t) = wj(t)
wi(f) V wj(f) = wi(f)
. Set Theoretic Operations
wi : A set in an alternative world i; it may also be the alternative world itself.
Compliment : wi -> !wi
Intersection :
wi | wi = wi (Ordinary)
wi | !wi = !wi (An alternate world's compliment
is an empty set for that world)
wj has a higher priority :
wi | wj = wi
wi | !wj = !wj
!wi | wj = !wi
!wi | !wj = !wj
Union :
wi U wi = wi (Ordinary)
wi U !wi = wi (Every alternative world is a
universal set of itself.)
wj has greater priority :
wi U wj = wj
wi U !wj = wi
!wi U wj = !wj
!wi U !wj = !wi
The relation between the alternative worlds is :
wp C wn C .......C w1 C wo
My definition brings a new point of view to the fuzzy set and logic theories. In this way, we are getting rid of dealing with numbers directly. This approach seems more convinient especially to represent or simulate daily life situations in which linguistic terminology are dominant.
Let me clarify my approach by giving an example :
Assume a teacher and a student as our alternative worlds. Surely, teacher's priority is greater than student's. They are preparing for a multiple choice exam together. Our aim is to measure the success.
t(t) means what teacher teached is true.
t(f) .. .. .. .. .. false.
"and" defines who is successful or unsuccessful
"or" who we expect is successful or unsuccesful
Cases:
1. t(t) & s(t) = s(t)
In this case we can infer that what student answered is true.
t(t) V s(t) = t(t)
We infer (or expect) that what teacher teached is true.
2. t(t) & s(f) = s(f)
What student answered is false.
t(t) V s(f) = t(t)
What teacher teached is true.
3. t(f) & s(t) = t(f)
What teacher teached is false.
t(f) V s(t) = s(t)
What student answered is true.
4. t(f) & s(f) = t(f)
What teacher teached is false.
t(f) V s(f) = s(f)
What student answered is false.
- PHILOSOPHICAL ASPECTS
My bivalent approach also has philosophical dimensions. At first, it disappears directly usage of numbers. And hence, since it takes fuzzy logic's technical cover a bit away, fuzzy theories will become more attractive for philosophers.
My approach seems to that of Kripke's modal logic systems, which uses possible worlds notion with possiblity and necessity notions, but they are different.
My approach is a completely pragmatic one, just as the spirit of fuzziness.
Its epistemologic interpretation is :
unlike bivalent logics, you can not generalize the concept of truthness (and falseness). It may even be atomic. It is not necessary that a trut is valid for each element of an universe of discourse. But in decision processes these have some hierarchic structure; just as most of the real life situations.
I want to postpone to discuss the ontological dimension of fuzzy set and logic theories. It seems it's more mystic than the other ones.
References :
1. Fuzzy Sets
by L.A. Zadeh
in Information and Control, 1965, 8, pg. 338-353
2. Fuzzy Sets and Systems :
Theory and Applications
by Didier Dubois and Henri Prade
Academic press, Inc., ..... (year)
3. Neural Networks and Fuzzy Systems:
A Dynamical Systems Approach To Machine Intelligence
by Bart Kosko
Prentice-Hall Int., Inc., 1992
4. Fuzzy Control and Fuzzy Systems
by Witold Pedryez
Research Studies Press Ltd., 2nd, Extended ed., 1993
John Wiley and Sons Inc.
5. Mathematics and Fuzziness
by R.Lowen
in Fuzzy Sets Theory and Application, pg. 3-37
edited by A. Kaufman, and H.J.Zimmerman
NATO ASI Series, 1985
6. A History of Set Theory
by P.E. Johnson, 1972
Prindle, Weber, & Schmidt Inc.
Notation Used in This Paper:
E : "is element / member of"
W : "for all"
TES : "There exist some"
O : "Empty set"
C : "is included in"
U : "set union"
| : "set intersection"
! : "set complement", "not"
& : "logical and"
f.A.(x) or f.A : "membership function of set A"
inv(x) : "inverse of x"
=> : "implication", "if"
<=> : "double implication", "if and only if", "iff"
Sum.i.1.n : "Arithmetical summation
with index i=1 to i=n"
Int.X : "Integral over X"
inf : infinity
inf() : greatest lower bound (lattice theory)
sup() : least upper bound ( .. .. )
y ** x : "y to the power x"
