This file contains two responses to Elkan's paper, one by Enrique
Ruspini and the other by Didier Dubois & Henri Prade.

----- Begin Included Message -----
From: ruspini@sunset.ai.sri.com (Enrique Ruspini)
Subject: Re: Responses to 'The Paradoxical Success of Fuzzy Logic'
Date: 3 Aug 93 00:18:55

After reading for a while rather curious comments and opinions
regarding Elkan's paper, I am posting herein a recent evaluation of
that work prepared at the request of a number of colleagues.

I am posting this message in reply to Lucke's message as a matter of
convenience (I cannot remember how to post an original message and my
News help file has disappeared) and, therefore, this message is
intended to address the whole issue rather than simply respond to
Lucke's message.  Since he is, however, my avenue to enter Usenet I
begin by addressing his concerns:

* Lucke's does not understand how a logic where formulas such as "p OR
not-p" can have a degree of truth other than 1 can be useful.

He is, however, confining his thoughts to uncertainty and probability.
If, for example, the degree of truth of the proposition "object O is
red" were to be measured (in RGB scale) by the relative proportion of
red in O, then a purple object (50% red, 50% blue) will be half red
and half not-red. Thus, if he and his friend, not knowing the color of
O, were to bet that O is red, they will have to agree to some
fair resolution procedure in case that the object is partially red.

Simply, FL is not a substitute for probability but a methodology to
represent the degree by which a statement matches or resembles
another. Its roots lie in notions of similarity and resemblance, not
on those of likelihood or propensity. For example, if the wealth of
Mr. M is one million dollars stating that he is worth $999,999 is less
of a mistake than stating that he is worth $1000 (although, in
classical logic, both propositions are strictly false).

* Zadeh's logic is distributive and, therefore, the roots of Elkan's
mistake do not lie on distributivity but on failure of the law of the
excluded middle (as correctly pointed out by Kroger).

* Whoever posted a message wondering about "sepulchral silence" in the
FL community was a bit overconcerned. Rather, we were both amused and
perplexed as to how Elkan's paper (ignoring results so well known that
they appear in textbooks) not only passed the referres but actually
won an award.

Normally, we would not bother to clarify a simple matter that is
otherwise obvious to anybody that actually bothers to learn about FL
before trying to criticize it (FL skeptics keep popping up repeating
worn arguments that were disqualified long ago---we are rather busy
doing positive things and cannot answer to all of them). The notoriety
that NCAI has given to this work requires, on the other hand, some
response.

I am afraid, however, that while I will try to answer and clarify
valid technical concerns, I will refrain (mainly because of lack of
time) to answer opinions based on ignorance of either classical or
multivalued logics.  In particular, I pledge to stay away from
claims based on the notion that the purported paradox
requires explanations based on esoteric mysticisms.

I hope that you will find the following writeup enlightening and
informative.

Enrique H. Ruspini

----------------



On the purportedly paradoxical nature of fuzzy logic

Enrique H. Ruspini
Artificial Intelligence Center
SRI International

The publication of a recent paper by C. Elkan ("The paradoxical
success of fuzzy logic," Proceedings of the National Conference on
Artificial Intelligence Conference, MIT and AAAI Press, pp. 698- 703,
1993) has been brought to my attention.

This work has received particular attention from non-specialists since
it was the only paper on fuzzy logic presented at the 1993 National
Conference on Artificial Intelligence, being also the recipient of one
of the "best paper" awards.

In this paper, the author purportedly shows that an axiomatization of
fuzzy logic, proposed by Gaines, cannot be consistent with valuations
over a propositional system if truth values other than zero or one are
allowed; i.e., fuzzy logic collapses into conventional logic.
Reasonably, many have asked if this paper signals the demise of fuzzy
logic.

Perplexed by the fact that fuzzy logic has attained considerable
success in applications despite this lack of formal soundness, Elkan
devotes most of his paper to account for this paradox. His conclusion
is that, so far, the inadequacies of FL ".. have not been harmful in
practice because fuzzy controllers are far simpler than other
knowledge-based systems."

This is an extraordinary assertion because fuzzy logic has been
successfully applied to synthesize controllers for rather complex
systems (e.g., Sugeno's application to helicopter control).
Furthermore, some of these controllers have considerably more
elaborate architectures than those mentioned by Elkan in his paper. At
any rate, even if all the fuzzy controllers developed to date were
simple, as Elkan thinks, it is arguable that reliance on a single
inferential step would make them less prone to failure.

It is altogether too bad that Elkan spent so much time and effort to
justify this unwarranted conclusion because, had he spent a fraction
of it getting acquainted with some basic results in fuzzy and
multivalued logics, he would have found that his theorem is based on
incorrect assumptions, his paradox non existent, and his subsequent
discussion meaningless.

I am bemused, on the other hand, by the efforts of some who have
recently posted messages in bulletin boards, trying to explain Elkan's
errors on the basis of arguments rooted on Eastern mysticism and on
the limitations of the "Western mindset," following a recent trend
initiated by questionable articles and books about fuzzy logic written
by "philosophers" and "experts."

Anybody acquainted with the foundations of fuzzy logic, however, would
not have had much difficulty discovering Elkan's mistake as it is well
known that many tautologies of propositional logic fail to be valid in
fuzzy logic. Assuming therefore that "equivalent" (in Gaines' Axiom 4)
means equivalence in the sense of classical logic is bound to lead to
error.

Perhaps the most famous of the valid formulas of propositional logic
that fails to be valid in fuzzy logic is the "law of the excluded
middle" asserting the validity of the formula "alpha OR not-alpha,"
or, equivalently, that of the formula

		"alpha OR not-alpha IF AND ONLY IF true,"

where "true" is the propositional symbol denoting the tautological
proposition.

One does not need to resort to the Elkan's lengthy proof to see that
if all tautologies in the classical propositional calculus extended to
fuzzy logic, then the only possible truth values are zero and one. To
see this in a rather straightforward fashion, note that application of
the axioms of fuzzy logic to the formula above leads to

			max(t(alpha), 1-t(alpha)) = 1,

from which it follows immediately that either t(alpha)=0 or t(alpha)=1. 

Many theorems of classical propositional logic may also be used to
derive this result .  Elkan's proof---based on the equivalence, in
conventional propositional logic, of the formulas "NOT-( a AND NOT-b)"
and "b OR (NOT-a and NOT-b)" ---actually assumes the validity of the
law of the excluded middle [To see this, simply expand "b OR (NOT-a
AND NOT-b)" and note the conjunct "b OR NOT-b"].

One can only wonder to what kind of analysis, if any, this claim was
subjected by the NCAI referees, when the author claims, in the
discussion following his theorem, that "What all formal fuzzy logics
have in common is that they reject at least one classical tautology,
namely, the law of the excluded middle," while basing his main
argument on an equivalent assertion.

Even such a claim about the encompassing lack of validity of the law
of the excluded middle is false as can be seen by considering
Lukasiewicz's continuous logic L-Aleph-1, which satisfies both the
laws of the excluded middle and contradiction while failing to satisfy
idempotence and distributivity properties.

Applying Elkan's method to this logic, which is based on the
functionals

			t(NOT p) = 1 -t(p),
			t(p OR q) = min(t(p) + t(q), 1),
			t(p AND q) = max(t(p) + t(q) -1, 0),

it may also be seen that it also collapses into classical logic, as
the idempotence property of the disjunction

			p OR p IF AND ONLY IF p,

leads to the equation

			  min(2 t(p),1)=t(p), 

which again can only be satisfied by t(p)=0 or t(p)=1.


Elkan's purportedly shocking discoveries have been long known, being
discussed in elementary textbooks on fuzzy and multivalued logics.

It is well known, for example (Klir, G. and Folger,N., "Fuzzy Sets,
Uncertainty, Information," Prentice Hall, 1988, pp. 52-59), that if (C,U,I)
are complement, union, and intersection operators, respectively, i.e.,

			t(NOT p) = C(t(p)),
			t(p OR q) = U(t(p), t(q)),
			t(p AND q)= I(t(p),t(q)),

that satisfy the laws of excluded middle and contradiction, then the
corresponding logics canbe neither idempotent nor distributive.  If
Elkan had probed further, he could have proved that all continuous
truth-functional multivalued logics "collapse" as well.

All of this should give everybody a certain measure of relief but this
explanation still does not answer a basic question: What is the
meaning, then, of the word "equivalent" in Gaines' Axiom 4 :

		t(a) = t(b) if a and b are logically equivalent,

that led Elkan so far astray? 

Elkan's discussion certainly indicates that he suspect that it may
mean something differentt from equivalence in classical propositional
calculus as he assumes in his main result. He seems to think, however,
that this is an open question that fuzzy logicians have not pondered
about enough.

The fact that classical propositional systems do not include, in their
semantics, an axiom that mirrors Axiom 4 should have been a sign that
deeper insights into the problem were required.  In classical logic,
logical equivalence between two formulas "alpha" and "beta" is defined
as the validity of the formula

		"alpha IF AND ONLY IF beta," 

i.e., the truth of that formula when all possible truth values are
assigned to their atomic propositional symbols (For example "(p AND q)
IF AND ONLY IF (q AND p)" is always true, regardless of whether p or q
are true or false).

Another way of defining logical equivalence (in classical logic) is to
say that "alpha" and "beta" are equivalent when the truth value of
"alpha" is the same as that of "beta," regardless of the truth
assignments to the propositional symbols appearing in those formulas.
A quick inspection of the truth table of the "IF AND ONLY IF"
connective shows this definition to be equivalent to that of the
previous paragraph.

While this is very reasonable something seems, however, to be amiss
here. How can we consider an axiom such as Axiom 4 before we even
define logical equivalence?  If equivalence means that the truth value
of "alpha" is always equal to that of "beta," why do we need an axiom
to state that this should be the case?

In multivalued logics, however, equivalence in the sense of the truth
of "IF AND ONLY IF" is not the same as equivalence in the sense of
truth-value equality. Although the notions yield the same relation in
the Lukasiewicz L3 logic, they are not equivalent in the 3-valued
logic of Bochvar (where, if "alpha" and "beta" have the third value
1/2, then "alpha IF AND ONLY IF beta" also has the third value 1/2)

In multivalued logics, it is possible to consider several
characterizations of the notion of logical equivalence--- each being a
reflexive, symmetric, and transitive relation between formulas and
each having different formal properties (For a discussion of various
possible formulations of the concept of logical equivalence in
multivalued logic, see N. Rescher's, "Many-valued logic", McGraw Hill,
1969, pp. 138ff).

In multivalued logics, in general, and in fuzzy logic, in particular,
equivalence is usually defined in terms of the semantics of the "IF
AND ONLY IF" connective, itself defined by that of the "IF"
connective. Several such definitions have been proposed. Zadeh, for
example, originally defined

			t(p ->q) = max(1-t(p), t(q)),

clearly seeking to extend material implication. Trillas and Valverde
noted some problems with this definition, proposing instead two
families of implication operators with more desirable properties (Cf.,
R. Lopez de Mantaras, Approximate Reasoning, Ellis Horwood).

Seeking a wide characterization of fuzzy logics, Gaines did not choose
to specify a particular semantics for the implication operator,
requiring only, in his Axiom 4, the use of a reasonable notion of
equivalence compatible with equality of truth values. This is the
case, for example, when equivalence is defined using the implications
families of Trillas and Valverde.

It is important to remark, however, that each proponent of a formal
approach must define logical equivalence---on the basis of the
semantics of that formal system--- in order to provide meaning to
Axiom 4. Elkan, however, puts the cart before the horse, with
disastrous consequences.

Other portions of Elkan's discussion also indicate lack of familiarity
with the basic ideas and concepts of fuzzy logic.

For example, asserting that an object x has the property "red" to the
degree 0.5 (i.e., it is half-red, e.g., purple, in some
color-measuring scale) is confused with the probabilistic strength of
evidence supporting the assertion that the object has the color red,
i.e.,
			Prob(x is red)=0.5.

Elkan also argues, incorrectly, that truth-functionality implies
intrinsic inability to describe correlation between properties of the
objects in a domain of discourse. Such correlations are described, of
course, by the "IF .. THEN .." rules of that particular domain (i.e.,
its "knowledge base"). Although substantive arguments, of a different
nature, may be made for the relaxation of truth-functionality, Elkan's
deliberations in this regard are way off the mark.

Elkan is also misled by the relatively small size of rule-sets in
fuzzy controllers. It is generally agreed that the compactness of
fuzzy knowledge-bases is the consequence of their inherent ability to
describe complex systems by introduction of powerful approximation
tools into an inferential framework. By contrast, conventional
inferential techniques generally require, in a control problem, the
specification of a control value for each conceivable value of the
state. Elkan confuses what is a desirable property of fuzzy systems
with a supposed lack of important applications of the technology.

Much has been said recently about overzealous hype among those
propounding fuzzy logic. While quite a few of these claims are
certainly true, it is clear from papers such as Elkan that not enough
is being done in certain forums to assure that papers dealing with
fuzzy logic, either pro or con, are subjected to a fair and competent
review process.

Many technical conferences and meetings are, in the views of many in
the fuzzy-logic community, unfairly hostile to fuzzy logic, while
being, on the other hand, ready to accept the work of skeptics with
nary an effort to determine its value.  Elkan's paper should have
never survived the refereeing process, let alone be awarded a prize.
----- End Included Message -----


----- Begin Included Message -----
Date: Thu, 9 Sep 1993 20:32:33 +0200
From: prade@irit.irit.fr
Subject: Elkan's AAAI paper

For your information, please find an answer to be posted to comp.ai.fuzzy.

Elkan's AAAI paper : an example of common misunderstanding about
fuzzy logic. 

There have been already many reactions (some very confusing, but also 
some very good, e.g. by E. Ruspini) to the recent paper "The paradoxical 
success of fuzzy logic" by Charles Elkan at AAAI Conference this Summer. 

In the following we just want to briefly repeat the points made orally
at Elkan' presentation at AAAI'93 and in more details at IJCAI'93's 
pannel on Fuzzy Logic and AI.


What is fuzzy logic ? Fuzzy set-based logic has at least two very different 
technical. It may refer to

- a logic of VAGUE PREDICATES, with respect to a complete
state of information,

- a logic of ordinal UNCERTAINTY with respect to incomplete state of 
knowledge, called POSSIBILISTIC logic.


1. Fuzzy Predicates

In the first kind of logic, we are concerned with the degree of satisfaction 
of GRADUAL properties expressed by vague predicates (e.g. tall, 
young,...), graded on the scale [0,1]. It allows for fully compositional set 
operations, in the sense that, for two vague propositions P, Q (such as
"John is tall")

degree of truth of (P * Q) = F* (degree of truth(P), degree of truth(Q))

where * stands for any binary connective and F* for the associated 
operation. This is due to the fact that the vague (also called fuzzy) 
propositions P and Q are no longer elements of a Boolean algebra and 
that some properties of a Boolean algebra like the extended-middle law : 

        degree of truth of (P or not P) = 1, 

or idempotency : 

        degree of truth of (P and P) = degree of truth of (P) 

have to be relaxed if we want a non-trivial calculus on the interval [0,1]. 
This has been pointed out in the fuzzy set literature for a long time 

(e.g. Bellman and Giertz "On the analytic formalism of the theory of 
fuzzy sets", Information Science, 5, 1973, 149-156, and Dubois and 
Prade "New results about properties and semantics of fuzzy set-theoretic 
operators", in : Fuzzy Sets - Theory and Applications to Policy Analysis 
and Information Systems (P.P. Wang, S.K. Chang, eds.), Plenum Press, 
New York, 1980, 59-75).


Idempotency is preserved by using min and max for intersection and union 
respectively but not the excluded middle law, which can be in turn be 
preserved by choosing max(0, 1 + b - 1) and min(a + b, 1) INSTEAD and 
then sacrifying idempotency. 

Said in purely mathematical terms, there are no operations for equipping the 
real interval [0,1] with a Boolean lattice structure.

Note that the impossibility theorem as stated by Elkan is over constrained :
it is enough to assume either the excluded middle law or the contradiction
low instead of the fourth assumption (since De Morgan laws follow from
the 3 first assumptions), in order to get the triviality result.

Elkan points out that his assumptions are not compatible with intuitionistic
logic. This should not be surprizing since the negation that he uses is
involutive.


2. Possibilistic Logic

The interval [0,1] can be also used for grading uncertainty pertaining
to CLASSICAL propositions (so obeying to ALL the properties of a
Boolean algebra). Then due to the incompatibility between Boolean
structure and the interval [0,1] already pointed out, the calculus
can be compositional with respect to SOME of the connectives only.
We can preserve this compositionality with respect to 

- negation, this is the case with probability calculus where

                Probability(P) = 1 - Probability(not P)

but neither Prob(P U Q) nor Prob(P & Q) are functions of Prob(P) and 
Prob(Q) except under special supplementary hypotheses on P and Q

- disjunction, this is the case of possibility measures introduced by
Zadeh ("Fuzzy sets as a basis for a theory of possibility", Fuzzy
Sets and Systems, 1, 1978, 3-28), which are such that

                Possibility(P or Q) = max(Possibility(P), Possibility(Q))

but Possibility(P and Q) is only LESS than or equal to 

                min(Possibility(P), Possibility(Q))

- conjunction, this is the case of the dual necessity measures defined 
by      Necessity(P) = 1 - Possibility(not P), which are such that
          Necessity(P and Q) = min(Necessity(P), Necessity(Q)) 
(but are not compositional with respect to disjunction).

Possibilistic logic has been extensively developed by our research
group and applied to Uncertain, Hypothetical and Default Reasoning.
Possibilistic logic is closely related to non-monotonic reasoning
concerns (an important class of non-monotonic inferences can  indeed 
be encoded in possibilistic logic). See
* Dubois D., Lang J., Prade H. "Advances in automated reasoning
using possibilistic logic", in Fuzzy Expert Systems (A. Kandel, ed.),
CRC Press, Boca Raton, Fl., 1992, 125-134.
* Dubois D., Prade H. "Possibilistic logic, preferential models, non-
monotonicity and related issues", Proc. of the 12th Inter. Joint
Conf. on Artificial Intelligence (IJCAI'91), Sydney, Aug. 24-30,
419-424.
* Benferhat S., Dubois D., Prade H. "Representing default rules
in possibilistic logic", Proc. of the 3rd Inter. Conf. on Principles
of Knowledge Representation and Reasoning (KR'92), Cambridge,
Oct. 25-29, 673-684.
* Dubois D., Lang J., Prade H. "A possibilistic assumption-based
truth maintenance system with uncertain justifications, and its
application to belief revision", in Truth Maintenance Systems
(ECAI'90 Workshop, Stockholm, Aug. 1990) (J.P. Martins,
M. Reinfrank, eds.), Springer Verlag, 1991, 87-106.

In the most general case we have both to deal with vague predicates
and incomplete information. This can be handled both theoretically
and practically in the general Zadeh's approximate reasoning
framework based on possibility theory. But again compositionality
is lost in that extended framework.


                                                  Didier Dubois & Henri Prade



----- End Included Message -----