Formal fuzzy logic

From Citizendium
Revision as of 09:26, 2 August 2007 by imported>Giangiacomo Gerla (→‎Formal fuzzy logic: a new chapter of multi-valued logic)
Jump to navigation Jump to search

Template:TOC-right

Formal fuzzy logic: a new chapter of multi-valued logic

Under the name "fuzzy logic" one denotes a series of topics related with the notion of fuzzy subset. Usually fuzzy logic is devoted to the applications, nevertheless, under the name "formal fuzzy logic" or "fuzzy logic in narrow sense" one denotes a new chapter of formal logic. Its aim is to represent in a formal way the vagueness of the natural language and to formalize the reasonings involving notions which are vague in nature. We can also consider formal fuzzy logic as an evolution and enlargement of multi-valued logic. In fact, from the semantical point of view, fuzzy logic admits the usual truth-functional semantics of first order multi-valued logic. In addition it admit also semantics which are not truth-functional (as an example, see necessity logic and probability logic) and also the possibility of logics whith no semantics (see similarity logic). In any case tha main differences one manifests in the deduction apparatus. This since in multi-valued logic the deduction operator is a tool to associate every (classical) set of axioms with the related (classical) set of theorems. From such a point of view the paradigm of the deduction in multi-valued logic is not different in nature from the one of classical logic. Instead in fuzzy logic the notion of approximate reasoning is crucial. This notion enables us to define a deduction operator which associates any fuzzy set of proper axioms with the related fuzzy subset of consequences.

The semantics

Consider a first order language L whose set of formulas we denote by F. As in classical logic, in fuzzy logic an interpretation of L is obtained by a domain D and by a function I associating every constant in L with an element of D and every n-ary operation symbol in L with an n-ary function in D. Instead, the interpretation of the predicate names is different since an n-ary predicate symbol is interpreted by an n-ary fuzzy relation in D, i.e. a map r from Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D^n} to [0,1]. This is done in order to represent properties which are "vague".

Definition. Given a first order language F, a fuzzy interpretation is a pair (D,I) such that D is a nonempty set and I a map associating

- every operation name h with arity n with an n-ary operation Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle I(h) : D^n\rightarrow D} in D,

- every constant c with an element I(c) in D

- every n-ary predicate name r with an n-ary fuzzy relation Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle I(r) : D^n\rightarrow [0,1] } in D.

Every fuzzy interpretation defines a valuation of the set F of formulas. Given a term t its interpretation is a function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle I(t)} one defines as in classical logic.

Definition. Given a formula Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha\in F} whose free variables are in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{x_1,...x_n\}} , we define the truth degree Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Val(I,\alpha,d_1,...,d_n)} of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha} by induction on the complexity of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha} by setting

- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Val(I,r(t_1,...,t_n),d_1,...,d_m) = I(r)(I(t_1)(d_1,...,d_n), ..., I(t_n)(d_1,...,d_n))}

- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Val(I,\alpha\vee\beta,d_1,...,d_n) = Val(I,\alpha,d_1,...,d_n)\oplus Val(I,\beta,d_1,...,d_n).}

- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Val(I,\alpha\wedge\beta,d_1,...,d_n) = Val(I,\alpha,d_1,...,d_n)\otimes Val(I,\beta,d_1,...,d_n)}

- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Val(I,\neg \alpha,d_1,...,d_n) = } ~ Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Val(I,\alpha,d_1,...,d_n)}

- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Val(I,\exists x_i\alpha,d_1,...,d_n) = Sup_{d\in D} Val(I,\alpha,d_1,...,d_{i-1},d,d_{n+1},...,d_n).}


As usual, if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha} is a closed formula, then its valuation does not depend on the elements Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d_1,...,d_n} and we write Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Val(I,\alpha)} instead of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Val(I,\alpha,d_1,...,d_n)} . More in general, given any formula Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha} , we denote by Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Val(I,\alpha)} , the valuation of the universal closure of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha} .


Definition. Consider a fuzzy set 's' of formulas we interpret as the fuzzy subset of proper axioms. Then we say that a fuzzy interpretation (D,I) is a model of s, in brief Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (D,I) \models s} if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Val(I,\alpha)\geq s(\alpha)} .


Then the meaning of a fuzzy subset of proper axioms s is that for every sentence Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha} , the value Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v(\alpha )} is a "lower bound constraint" on the unknown truth value of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha} .

Definition. The logical consequence operator is the map Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Lc : [0,1]^F\rightarrow [0,1]^F} defined by setting

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Lc(s)(\alpha) = Sup\{Val(I,\alpha) : (D,I) \models s\}} .

Again, the value Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Lc(s)(\alpha )} is a "lower bound constraint" on the unknown truth value of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha} . As a matter of fact this is the better constraint we can find given the information s. It is easy to see that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Lc(s)} is a closure operator, i.e. that

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s\subseteq Lc(s)}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s\subseteq t \Rightarrow Lc(s)\subseteq Lc(t)}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Lc(Lc(s)) = Lc(s)} .

= The deduction apparatus: approximate reasonings

Once we have defined the logical consequence operator, we have to search for a "deduction apparatus" able to calculate Ic(s) in some way. As an example, we can define a deduction apparatus by a fuzzy subset of formulas la we call fuzzy subset of logical axioms and by a set R of fuzzy inference rules. In turn, and inference rule is a pair (r,s) where r is a partial n-ary operation in F and s is an n-ary operation in [0,1]. The meaning of an inference rule is:

- if we are able to prove Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha_1,...,\alpha_n} at degree Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lambda_1,...,\lambda_n} , respectively

- and we can apply r to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha_1,...,\alpha_n}

- then we can prove Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r(\alpha_1,...,\alpha_n)} at degree Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s(\lambda_1,...,\lambda_n )} .

As an example a fuzzy Modus Ponens is defined as a pair Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (r,s)} in which the domain of r is the set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{(\alpha,\alpha\rightarrow \beta : \alpha,\beta\in F\}} , moreover Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r(\alpha,\alpha\rightarrow\beta) = \beta} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s(\lambda_1,\lambda_2) = \lambda_1\otimes\lambda_2} where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \otimes} is an operation in [0,1] able to interpret the conjunction. . . . (to be continued) ...

Is fuzzy logic a proper extension of classical logic ?

The interpretation of the logical connectives in fuzzy logic is conservative in the sense that its restriction to {0,1} coincides with the classical one. This fact can be interpreted by saying that fuzzy logic is conservative and that it is a proper extension of classical logic. On the other hand it is evident also that fuzzy logic is defined inside classical mathematics and therefore inside classical logic. Then, as a matther of fact fuzzy logic is a (small) chapter of classical mathematics. This means that, differently from intuitionistic logic, fuzzy logic cannot be considered as an alternative philosophy in a trict sense.

Approximate reasonings

In fuzzy logic a deduction apparatus is given by a fuzzy subset of logical axioms and a set of fuzzy inference rules. . . .

Effectiveness for fuzzy subsets

The notions of a "decidable subset" and "recursively enumerable subset" are basic ones for classical mathematics and classical logic. Then, the question of a suitable extension of such concepts to fuzzy set theory arises. A first proposal in such a direction was made by E.S. Santos by the notions of fuzzy Turing machine, Markov normal fuzzy algorithm and fuzzy program. Successively, L. Biacino and G. Gerla proposed the following definition where Ü denotes the set of rational numbers in [0,1].

Definition A fuzzy subset μ : S Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \rightarrow} [0,1] of a set S is recursively enumerable if a recursive map h : S×N Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \rightarrow} Ü exists such that, for every x in S, the function h(x,n) is increasing with respect to n and μ(x) = lim h(x,n). We say that μ is decidable if both μ and its complement –μ are recursively enumerable.

An extension of such a theory to the general case of the L-subsets is proposed in a paper by G. Gerla where one refers to the theory of effective domains. It is an open question to give supports for a Church thesis for fuzzy logic claiming that the proposed notion of recursive enumerability for fuzzy subsets is the adequate one. To this aim, further investigations on the notions of fuzzy grammar and fuzzy Turing machine should be necessary (see for example Wiedermann's paper).

Effectiveness for fuzzy logic

Define the set Val of valid formulas as the set of formulas assuming constantly value equal to 1. Then it is possible to prove that among the usual first order logics only Goedel logic has a recursively enumerable set of valid formulas. In the case of Lukasiewicz and product logic, for example, Val is not recursively enumerable (see B. Scarpellini, Belluce). Such a fact was extensively examined in the book of Hajek. Neverthless, from these results we cannot conclude that these logics are not effective and therefore that an axiomatization is not possible. Indeed, if we refer to the just exposed notion of effectiveness for fuzzy sets, then the following theorem holds true (provided that the deduction apparatus of the fuzzy logic satisfies some obvious effectiveness property).

Theorem. Any axiomatizable fuzzy theory is recursively enumerable. In particular, the fuzzy set of logically true formulas is recursively enumerable in spite of the fact that the crisp set of valid formulas is not recursively enumerable, in general. Moreover, any axiomatizable and complete theory is decidable.

It is an open question to utilize the notion of recursively enumerable fuzzy subset to find an extension of Gödel’s theorems to fuzzy logic.

See also

Bibliography

  • Biacino L., Gerla G., Fuzzy logic, continuity and effectiveness, Archive for Mathematical Logic, 41, (2002), 643-667.
  • Chang C. C.,Keisler H. J., Continuous Model Theory, Princeton University Press, Princeton, 1996.
  • Cignoli R., D’Ottaviano I. M. L. , Mundici D. , ‘’Algebraic Foundations of Many-Valued Reasoning’’. Kluwer, Dordrecht, 1999.
  • Cox E., The Fuzzy Systems Handbook (1994), ISBN 0-12-194270-8
  • Elkan C.. The Paradoxical Success of Fuzzy Logic. November 1993. Available from Elkan's home page.
  • Hájek P., Metamathematics of fuzzy logic. Kluwer 1998.
  • Hájek P., Fuzzy logic and arithmetical hierarchy, Fuzzy Sets and Systems, 3, (1995), 359-363.
  • Klir G. and Folger T., Fuzzy Sets, Uncertainty, and Information (1988), ISBN 0-13-345984-5.
  • Klir G. and Bo Yuan, Fuzzy Sets and Fuzzy Logic (1995) ISBN 0-13-101171-5
  • Gerla G., Effectiveness and Multivalued Logics, Journal of Symbolic Logic, 71 (2006) 137-162.
  • Montagna F., Three complexity problems in quantified fuzzy logic. Studia Logica, 68,(2001), 143-152.
  • Novák V., Perfilieva I, Mockor J., Mathematical Principles of Fuzzy Logic, Kluwer Academic Publishers, Dordrecht, (1999).
  • Scarpellini B., Die Nichaxiomatisierbarkeit des unendlichwertigen Prädikatenkalküls von Łukasiewicz, J. of Symbolic Logic, 27,(1962), 159-170.
  • Zimmermann H., Fuzzy Set Theory and its Applications (2001), ISBN 0-7923-7435-5.
  • Kevin M. Passino and Stephen Yurkovich, Fuzzy Control, Addison Wesley Longman, Menlo Park, CA, 1998.
  • Wiedermann J. , Characterizing the super-Turing computing power and efficiency of classical fuzzy Turing machines, Theor. Comput. Sci. 317, (2004), 61-69.
  • Zadeh L.A., Fuzzy algorithms, Information and Control, 5,(1968), 94-102.
  • Zadeh L.A., Fuzzy Sets, ‘’Information and Control’’, 8 (1965) 338­353.
  • Zemankova-Leech, M., Fuzzy Relational Data Bases (1983), Ph. D. Dissertation, Florida State University.
Retrieved from "https://citizendium.org/wiki/index.php?title=Formal_fuzzy_logic&oldid=250507"