Formal fuzzy logic: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Giangiacomo Gerla
mNo edit summary
 
(292 intermediate revisions by 10 users not shown)
Line 1: Line 1:
{{TOC-right}}
{{subpages}}
== Formal fuzzy logic ==
{{TOC|right}}
"Formal fuzzy logic" or "fuzzy logic in narrow sense" is a relatively new chapter of formal logic. Its aim is to represent predicates as ''big'', ''near'', ''similar'' which are vague in nature and to formalize the reasonings involving these predicates. The notion of ''[[fuzzy subset]]'', proposed by L. A. Zadeh,  plays a crucial role since a vague predicate is interpreted by a fuzzy subset. In the sequel we will write "fuzzy logic" instead of "formal fuzzy logic" but notice that in literature the name ''"fuzzy logic"'' comprises a large series of topics based on the notion of a fuzzy subset and which are usually devoted to applications.


More precisely, we can consider fuzzy logic as an evolution and an enlargement of multi-valued logic. Indeed, all the multi-valued logics defined in literature are also considered in fuzzy logic. Nevertheless, there are fuzzy logics such as [[similarity logic]] and  [[necessity logic]] that are completely new topics and that have no truth-functional semantics. Moreover, fuzzy logic, as proposed by J. A. Goguen, J. Pavelka and many authors, is totally out of line with the tradition of multi-valued logic in the idea of deduction. Indeed, the notions of fuzzy inference rule and of [[approximate reasoning]] lead to define a deduction operator working on a fuzzy set of proper axioms (the available information) and giving the corresponding fuzzy subset of consequences.
'''Fuzzy [[logic]]''' is a relatively new chapter of [[formal]] logic whose aim is to formalize the reasonings involving predicates that are vague in nature (as an example ''small'', ''near'', ''similar''). An example of such kind of reasoning is


== Fuzzy logics: the semantics ==
: ''If a tomato is red, then the tomato is ripe. Since this tomato is very red, this tomato is very ripe.''
We obtain the semantics for a fuzzy logic by interpreting the logical connectives by suitable operations in [0,1]. As an example, if <math>, \wedge, \Rightarrow, \neg </math> are the logical connectives, then in Lukasievicz logic the corresponding operations are defined by the equations


<math> x\otimes y = max\{x+y-1,0\} </math>,
Further examples of reasonings involving vague predicates are in the item ''[[Paradoxes and fuzzy logic]]'' and in the section ''Fuzzy logic with no truth-functional semantics''. The main tool for fuzzy logic is the notion of a ''[[fuzzy subset]]'', since a vague predicate is interpreted by a fuzzy subset. Notice that in literature the name ''"fuzzy logic"'' also denotes a large series of topics based on an informal usage of the notion of a fuzzy subset, and which are usually devoted to applications.


<math> x\rightarrow y = max\{1-x+y,1\} </math>,
As a matter of fact, fuzzy logic is an evolution and an enlargement of [[multi-valued logic]] since all the definitions and results in the literature on multi-valued logic are also considered in fuzzy logic. In particular, as in multi-valued logic, the starting point is a fixed ''valuation structure'', i.e. a bounded [[lattice (order)|lattice]] ''L'' equipped with suitable operations to interpret the logical connectives. The minimum 0 means ''''False'''', the maximum 1 means ''''True'''', the remaining elements are interpreted as intermediate truth values. The following is the main class of valuation structures (see Hájek 1998, Novák et al. 1999 and Gottwald 2005) corresponding to the connectives <math>\wedge</math> and <math>\rightarrow </math>.


<math>\nu(x) = 1-x </math>,


respectively. More in general, usually one assumes that <math> \otimes </math> is a continuous [[triangular norm]], i.e. a continuous, associative, commutative, order preserving operation in [0,1] such that <math> x\otimes 1 = 1 </math>. Moreover, one defines <math> \rightarrow </math> as the residuation operation, i.e. by setting <math> x\rightarrow y = sup\{z | x\otimes z\le y\} </math> and <math>\nu</math> by setting <math>\nu(x) = x\rightarrow 0</math> (see Hájek 1998, Novák et al. 1999 and Gottwald 2005). It is also possible to consider languages with logical constants to denote truth values. Once an interpretation of the logical connectives is given, the semantics of the corresponding propositional calculus is defined in a truth-functional way as usual. The semantics of the corresponding first order fuzzy logic is defined as in classical logic. The only difference is that the interpretation of a ''n''-ary predicate symbol is an ''n''-ary fuzzy relation in ''D'', i.e. a map ''r'' from <math>D^n</math> to [0,1]. This enables us to represent properties which are "vague" in nature. In the following we denote by ''L'' a first order language and by ''F'' the corresponding set of formulas.
'''Definition.''' A ''standard algebra'' is an algebraic structure ([0,1], ʘ, →, 0,1) where ʘ is a continuous triangular norm, i.e. a continuous, associative, commutative, order preserving operation such that ''x''ʘ1 = 1 and → is the related residuation, i.e. ''x''→''y'' = sup{''z'' | ''x''ʘ''z'' ≤ ''y''}.




'''Definition. ''' Given a first order language ''L'', a '' fuzzy interpretation'' is a pair (''D'',''I'') such that ''D'' is a nonempty set and ''I'' a map associating
The main examples of standard algebras are obtained by assuming that ʘ is the minimum (Zadeh logic), the usual product (product logic) or that ''x''ʘ''y'' = ''Max{x+y-1,0}'' (Łukasievicz logic). In addition, several authors consider also languages with logical constants to denote rational truth values. Once a valuation structure is fixed, the semantics of the corresponding propositional calculus is defined in a truth-functional way as usual. In first order fuzzy logic the semantics is defined as follows.
- every operation name ''h'' with arity ''n'' with an n-ary operation ''I(h)'' in ''D'',  
 
- every constant ''c'' with an element ''I''(''c'') in ''D''
 
- every n-ary predicate name ''r'' with an ''n''-ary fuzzy relation ''I(r)'' : ''D''<math>^n\rightarrow </math> ''D'' in ''D''.
 
 
In order to evaluate the fomulas in a given fuzzy interpretation, given a term ''t'', we denote by <math>I(t)</math> the corresponding function we define as in classical logic.
 
 
'''Definition.''' Given a formula <math>\alpha\in F</math> whose free variables are in <math>\{x_1,...x_n\}</math>, we define the truth degree <math>Val(I,\alpha,d_1,...,d_n)</math> of <math>\alpha</math> by induction on the complexity of <math>\alpha</math> by setting
 
<math> 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))</math>
<math>Val(I,\alpha\wedge\beta,d_1,...,d_n) = Val(I,\alpha,d_1,...,d_n)\otimes Val(I,\beta,d_1,...,d_n) </math>
<math>Val(I,\alpha\Rightarrow\beta,d_1,...,d_n) = Val(I,\alpha,d_1,...,d_n)\rightarrow Val(I,\beta,d_1,...,d_n)</math>
<math>Val(I,\neg \alpha,d_1,...,d_n) = \nu(Val(I,\alpha,d_1,...,d_n)) </math>
<math>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)</math>.
 
As usual, if <math> \alpha</math> is a closed formula, then its valuation does not depend on the elements <math>d_1,...,d_n</math> and we write <math> Val(I,\alpha)</math> instead of <math> Val(I,\alpha,d_1,...,d_n)</math>. More in general, given any formula <math>\alpha</math>, we denote by  <math>Val(I,\alpha)</math>, the valuation of the universal closure of <math> \alpha</math>.
 
Now, in defining the semantical notions we can consider the traditional approach inerithed from multi-valued logic and the Pavelka-style approach which is a characteristic of fuzzy logic.
 
'''Definition''' (''Traditional approach''). One says that a formula <math>\alpha</math> is ''valid'' in a fuzzy interpretation (''D,I'') if <math> Val(I,\alpha) = 1</math>. The formula <math>\alpha</math> is ''logically true'' if it is valid in every fuzzy interpretation.  Let ''T'' be a theory and <math> \alpha </math> a formula, then we write <math> T |= \alpha </math> if every model of ''T'' is also a model of <math> \alpha </math>. In such a case we say that <math> \alpha </math> is a ''logical consequence'' of ''T''.
 
Once we admit these definitions as the basic ones, given a deduction apparatus, a ''"standard"'' completeness theorem claims that the class of logically true formulas coincides with the class of provable formulas. An ''extended'' completeness theorem claims that a formula is a logical consequence of a theory ''T'' if and only if it is derivable from ''T''. The notions of compactness and of effectivenes are not different from the classical ones.
 
Such an approach is perhaps not completely satisfactory. In fact in fuzzy logic we will elaborate (uncomplete) information on vague predicates (i.e. constraints on the truth values of the formulas) to obtain further information (inproved constraints on the truth values) on these formulas. A more appropriate definition was proposed by Pavelka.
'''Definition. ''' Consider a fuzzy subset ''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 <math>(D,I) \models s</math> if <math> Val(I,\alpha)\geq s(\alpha)</math>. The ''logical consequence operator'' is the map <math>Lc : [0,1]^F\rightarrow [0,1]^F</math> defined by setting
 
<math>Lc(s)(\alpha) = Sup\{Val(I,\alpha) : (D,I) \models s\}</math>.
 
Then the meaning of a fuzzy subset of proper axioms ''s'' is that for every sentence <math>\alpha</math>, the value <math>s(\alpha )</math> is a ''constraint"'' on the unknown truth value of <math>\alpha</math>. More precisely <math>s(\alpha )</math> is a lower bound for such a value. Again, the value <math>Lc(s)(\alpha )</math> is a ''"constraint"'' on the unknown truth value of <math>\alpha</math>. As a matter of fact it is the better constraint we can find given the information ''s''.
 
== The deduction apparatus: approximate reasonings ==
Once the logical consequence operator ''Lc'' is defined, we have to search for a "deduction apparatus" able to calculate ''Lc(s)'' in some ''"effective"'' way. As an example, by extending the Hilbert's aproach for classical logic, we can define a deduction apparatus by a fuzzy subset of formulas <math>la</math>, we call ''fuzzy subset of logical axioms'', and by a set ''R'' of fuzzy inference rules. In turn, a ''fuzzy inference rule'' is a pair (''sy'',''se'') where ''sy'', the ''syntactical part'', is a partial ''n''-ary operation in ''F'' (i.e. an inference rule in the usual sense) and ''se'', the ''semantical part'', is an ''n''-ary operation in [0,1]. The meaning of an inference rule is:
 
- if we are able to prove <math>\alpha_1,...,\alpha_n</math> at degree <math>\lambda_1,...,\lambda_n</math>, respectively
 
- and we can apply ''sy'' to <math>\alpha_1,...,\alpha_n</math>
 
- then we can prove <math>sy(\alpha_1,...,\alpha_n)</math> at degree <math>se(\lambda_1,...,\lambda_n )</math>.
 
As an example, let <math>\otimes</math> be an operation in [0,1] able to interpret the conjunction. Then the ''fuzzy Modus Ponens'' is defined as by assuming that the domain of ''sy'' is the set <math>\{(\alpha,\alpha\rightarrow \beta : \alpha,\beta\in F\}</math>, by setting  <math>sy(\alpha,\alpha\rightarrow\beta) = \beta</math> and by assuming that ''se'' coincides with <math>\otimes</math>, i.e. <math>se(\lambda_1,\lambda_2) = \lambda_1\otimes\lambda_2</math>. This rule says that if we are able to prove <math>\alpha</math> and <math>\alpha\rightarrow\beta</math> at degree <math>\lambda_1</math> and <math>\lambda_2</math>, respectively, then we can prove <math>\beta</math> at degree <math>\lambda_1\otimes \lambda_2</math>.
The ''fuzzy'' <math>\and</math>''-introduction rule'' is a totally defined rule such that ''sy''(<math>\alpha_1,\alpha_2) = \alpha_1\and \alpha_2 </math> and again ''se'' coincides with <math>\otimes</math>. This rule says that if we are able to prove <math>\alpha_1</math> and <math>\alpha_2</math> at degree <math>\lambda_1</math> and <math>\lambda_2</math>, respectively, then we can prove <math>\alpha_1\and \alpha_2</math> at degree <math>\lambda_1\otimes \lambda_2</math>.
 
'''Definition'''. A ''proof'' <math>\pi</math> of a formula <math>\alpha</math> is a
sequence <math>\alpha_1,...,\alpha_m</math> of formulas such that <math>\alpha_m=\alpha </math>,
together with a sequence of related ''justifications''. This means that, for
every formula <math>\alpha_i</math>, we have to specify whether
 
i) <math>\alpha_i</math> is assumed as a logical axiom or;
 
ii) <math>\alpha_i</math> is assumed as a proper axiom or;
 
iii) <math>\alpha_i</math> is obtained by a rule (in this case we have to indicate
also the rule and the formulas from <math>\alpha_1,...,\alpha_{i-1}</math> used to
obtain <math>\alpha_i</math>).
 
The justifications are necessary to valuate the proofs. Indeed, let ''s'' be the fuzzy subset of proper axioms and, for every <math>i\leq m</math> denote by <math>\pi (i)</math> the proof <math>
\alpha_1,...,\alpha_i</math>. Then the valuation <math>Val(\pi ,s)</math> of <math>\pi</math> with
respect to ''s'' is defined by induction on ''m'' by setting
 
<math>Val(\pi ,s) = la(\alpha_m)</math> if <math>\alpha _m</math> is assumed as a logical axiom
 
<math> Val(\pi ,s) = s(\alpha_m)</math> if <math>\alpha _m</math> is assumed as a proper axiom


<math>Val(\pi ,s) = se(Val(\pi(i_1),s),...,Val(\pi (i_n),s))</math> if there is a fuzzy rule <math>(sy,se)</math> such that <math>
\alpha_m = sy(\alpha_{i(1)},...,\alpha_{i(n)})</math> with <math>i_1 < m,...,i_n < m</math>.


Now, unlike the crisp deduction systems, in a fuzzy deduction system
'''Definition. ''' A ''fuzzy interpretation'' of a first order language is a pair (''D'',''I'') such that ''D'' is a nonempty set and ''I'' a map associating (as in the classical case) every ''n''-ary operation name ''h'' with an ''n''-ary operation in ''D'' and every constant ''c'' with an element ''I''(''c'') in ''D''. Moreover, ''I'' associates every ''n''-ary predicate name ''r'' with an ''n''-ary ''L''-relation ''I''(''r'') : ''D<sup>n</sup>''<math>\rightarrow</math> ''L'' in ''D''.  
different proofs of a same formula <math>\alpha</math> may give different contributions to the degree of validity of <math>\alpha</math>. This suggests setting


<math>
D(s)(\alpha)= Sup\{Val(\pi ,s)|\pi </math> ''is a proof of'' <math>\alpha\}</math>.


This formula defines an operator, the ''deduction operator'', able to associate every fuzzy subset of axiom ''s'' with the fuzzy subset ''D(s) of formulas deduced from s''.
Then the only difference with classical logic is that the interpretation of an ''n''-ary predicate symbol is an ''n''-ary [[fuzzy subset|fuzzy relation]] in ''D''. This enables us to represent properties which are "vague" in nature. Given a fuzzy interpretation we can evaluate the formulas as follows where, given a term ''t'' whose variables are in ''x''<sub>1</sub>,...,''x''<sub>n</sub>, we denote by <math>I(t)</math> the corresponding ''n''-ary function we define as in classical logic.
'''Definition.''' A fuzzy logic is ''axiomatizable'' if there is a fuzzy deduction system such that ''Lc = D''.


Notice that under some natural hypotheses, a fuzzy propositional logic is axiomatizable if and only if the logical connectives are interpreted by continuous functions (see Biacino and Gerla 2002). As was shown in Hajek 1998, completeness results for first order fuzzy logic can be find if one adds a constant for every rational value in [0,1].


== Paradoxes ==
'''Definition.''' Let (''D,I'') be a fuzzy interpretation, α a formula whose free variables are in ''x''<sub>1</sub>,...,''x''<sub>n</sub> and ''d''<sub>1</sub>,...,''d''<sub>n</sub> elements in ''D''. Then we define the truth degree ''Val''(''I'',α,''d''<sub>1</sub>,...,''d''<sub>n</sub>) by induction as follows :


=== The heap paradox ===
:''Val''(''I'', ''r''(''t''<sub>1</sub>,...,''t''<sub>''p''</sub>), ''d''<sub>1</sub>,...,''d''<sub>''n''</sub>) = ''I''(''r'')(''I''(''t''<sub>1</sub>)(''d''<sub>1</sub>,...,''d''<sub>''n''</sub>), ..., ''I''(''t''<sub>''p''</sub>)(''d''<sub>1</sub>,...,''d''<sub>''n''</sub>))
To show an example of reasoning in fuzzy logic we refer to the famous ''"heap paradox"''. Let ''n'' be a natural number and denote by Small(''n'') a sentence whose intended meaning is ''"a heap with n stones is small"''. Then it is natural to assume the validity of the atomic formula


(a)   Small(1)
:''Val''(''I'',α <math>\wedge</math> β, ''d''<sub>1</sub>,...,''d''<sub>''n''</sub>) = ''Val''(''I'',α,''d''<sub>1</sub>,...,''d''<sub>''n''</sub>)ʘ''Val''(''I'',β,''d''<sub>1</sub>,...,''d''<sub>''n''</sub>)


and, for every ''n'', the validity of the formulas
:''Val''(''I'',α → β, ''d''<sub>1</sub>,...,''d''<sub>''n''</sub>) = ''Val''(''I'',α, ''d''<sub>1</sub>,...,''d''<sub>''n''</sub>) → ''Val''(''I'',β,''d''<sub>1</sub>,...,''d''<sub>''n''</sub>)


(b)  Small(''n'') <math>\rightarrow</math> Small(''n''+1).
:''Val''(''I'',<math>\forall </math> ''x<sub>i</sub>''α, ''d''<sub>1</sub>,...,''d''<sub>''n''</sub>) = ''Inf<sub> dєD</sub>Val''(''I'',α,''d''<sub>1</sub>,...,''d''<sub>''i''-1</sub>,''d'',''d''<sub>''i''+1</sub>,...,''d''<sub>''n''</sub>).


In the case there is a propositional constant ''c<sup>*</sup>'' corresponding to a truth value ''c'', we set


On the other hand from these formulas we can prove that, given any natural number ''n'', a heap with ''n'' stones is small. Indeed,
:''Val''(''I'', ''c<sup>*</sup>'',''d''<sub>1</sub>,...,''d''<sub>''n''</sub>) = ''c''.


Observe that in the case ''L'' is not complete it is possible that a quantified formula cannot be evaluated. We call ''safe'' an interpretation such that all the formulas are evaluated. As usual, if α is a closed formula, then its valuation does not depend on the elements ''d''<sub>1</sub>,...,''d<sub>n</sub>'' and we write ''Val''(''I'',α) instead of ''Val''(''I'',α,''d''<sub>1</sub>,...,''d''<sub>''n''</sub>). More in general, given any formula α, we denote by ''Val''(''I'', α) the valuation of the universal closure of α.


- from  Small(1)  and   Small(1)<math>\rightarrow</math> Small(2) by MP we may state Small(2);
== Two approaches ==
There are two basic approaches to fuzzy logic. The first one, proposed by P. Hajek and followed by Di Nola, Esteva, Gottwald, Godo, Montagna, Mundici and by a large series of students, is very close to the tradition of multi-valued logic. Indeed the deduction apparatus works on a set of hypotheses to give the corresponding set of logical consequences. This is obtained, as it is usual in multi-valued logic, once a set of designed truth values is fixed. We call, ''ungraded approach'' such a way to face fuzzy logic. Another approach was proposed by J. A. Goguen, J. Pavelka, V. Novak, G. Gerla and further authors and it is rather out of line with the tradition of multi-valued logic. Indeed, the deduction apparatus works on a given fuzzy subset of hypotheses (the available information) to give the related fuzzy subset of logical consequences. We call ''graded approach'' such a way to face fuzzy logic.


=== The ungraded approach ===
   
   
- from  Small(2)  and  Small(2)<math>\rightarrow</math> Small(3) by MP we may state Small(3),
In the ungraded approach a subset ''Des'' of [0,1] is fixed whose elements are called ''designed truth degrees''. The interpretation is that in ''Des'' there are the truth degrees which one considers sufficient to claim the validity of a formula. Usually one sets ''Des'' = {1}.
 
…


- from  Small(''n''-1)  and  Small(''n''-1)<math>\rightarrow</math> Small(''n'') by MP we may state Small(''n'').


'''Definition'''. Let ([0,1], ʘ, →, 0, 1) be a fixed standard algebra, and α be a formula. Then we say that a fuzzy interpretation (''D,I'') ''satisfies'' α  provided that ''Val''(''I'',α) is a designed value. Let ''T'' be a theory, then (''D,I'') is a ''model of T'' if every formula in ''T'' is satisfied in (''D,I''). We write ''T'' <math>\models</math><sub>ʘ</sub> α if every model of ''T'' satisfies α.


Obviously, a conclusion like Small(20.000) is contrary to our intuition in spite of the fact that the reasoning is correct and the premises appear very reasonable. Clearly, the core of such a paradox lies in the vagueness of the predicate " small" and therefore, as proposed by Goguen, we can refer to the notion of approximate reasoning to face it. Indeed it is a fact that everyone is convinced that the implications Small(''n'')<math>\rightarrow</math> Small(''n''+1) are near-true but not completely true, in general. We can try to "respect" this conviction by assigning to these formulas a truth value <math>\lambda</math> different from 1 (but very close to 1). Then, for example, we can express the axioms for the heap paradox as follows
The deduction apparatus in the ungraded approach is defined by adopting the same paradigm of classical logic, i.e. a ''deduction relation'' <math>\vdash</math> is defined by a suitable set of logical axioms and suitable inference rules. The fuzzy logic defined by ʘ is ''axiomatizable'' provided that a deduction apparatus exists such that <math>\vdash</math> coincides with <math>\models</math><sub>ʘ</sub>. Unfortunately, the main fuzzy logics are not axiomatizable.




Small(1) [to degree 1] 
'''Theorem.''' In all the main fuzzy logics (in particular in Łukasievicz logic) the entailment relation <math>\models</math><sub>ʘ</sub> is not compact. This entails that these logics are not axiomatizable.


Small(2) [to degree 1] 


...
As an attempt to bypass such an obstacle, in the ungraded approach one proposes a different entailment relation related with the variety generated by a given triangular norm.  


Small(10.000) [to degree 1] 


Small(10.000)<math>\rightarrow</math> Small(10.001)   [to degree <math>\lambda</math>]
'''Definition.''' Given a standard algebra ([0,1], ʘ, →,0,1), denote by ''Varl''(ʘ) the class of all linearly ordered algebras in the variety generated by ([0,1], ʘ, →, 0, 1). Then a ''Varl(ʘ)-interpretation'' is an interpretation in a valuation algebra belonging to ''Varl''(ʘ). Given a set ''T'' of formulas and a formula α, we write ''T'' <math>\models</math><sub>''Varl''(ʘ)</sub> α provided that every safe ''Varl''(ʘ)-model of ''T'' is a safe ''Varl''(ʘ)-model of α. 


Small(10.001)<math>\rightarrow</math> Small(10.002)  [to degree <math>\lambda</math>]


...
In such a case, the resulting logic works well. In fact, the following theorem holds true.




In accordance, the Heap Paradox argument can be restated as follows where we assume that <math>\otimes</math> is associative and we denote by <math>\lambda^{(n)}</math> the ''n''-power of <math>\lambda</math> with respect to <math>\otimes</math>.
'''Theorem'''. In all the main fuzzy logics (in particular in Łukasievicz logic) the entailment relation <math>\models</math><sub>''Varl''(ʘ)</sub> is compact. This is in accordance with the fact that these logics are axiomatizable (provided that they are defined by referring to this relation).




-  Since Small(10.000) [to degree 1]
'''Criticisms.''' A criticism for the ungraded approach, philosophical in nature, concerns its adequateness to represent the daily reasonings in which vague predicates occur. Moreover the structures in ''Varl''(ʘ) look rather unnatural. For example, in ''Varl''(ʘ) there are structures with infinitesimal truth values. Another criticism is that, while the completeness of [0,1] assures that all the formulas are valuated, in the case we refer to the variety ''Varl''(ʘ), we are forced to admit interpretations for which there are unvaluated formulas.


=== The graded approach: approximate reasonings ===


and  
The aim of any logic is to elaborate (uncomplete) information to obtain more explicit information. Now, in the case of fuzzy logic it is natural to admit an information like ''"the truth values of α is between λ and μ"'', i.e. a constraint on the possible truth value of a formula. Now, observe that if we admit the usual interpretation of the negation, then ''Val''(''I'',α)''≤ λ'' if and only if ''Val''(''I'',<math>\neg</math> α)''≥ 1-μ''. Then we can reduce all the interval constraints to lower bound constraints. In accordance in the graded approach one proposes the following definition.
 
 
Small(10.000)<math>\rightarrow</math> Small(10.001)          [to degree <math>\lambda</math>]
   
   
'''Definition '''. Consider a fuzzy theory ''s'', i.e. a fuzzy subset of formulas. Then a fuzzy interpretation (''D,I'') is a ''model of s'', in brief (''D,I'') <math>\models </math>'' s'' if ''Val''(''I'',α) ≥ ''s''(α). The ''logical consequence operator'' is the map ''Lc'' : [0,1]<sup>''F''</sup> → [0,1]<sup>''F''</sup> defined by setting


we state
:''Lc''(''s'')(α) = ''Inf''{''Val''(''I,α'') : (''D,I'') <math> \models </math> ''s''}.
 
 
Small(10.001) [to degree  <math>1\otimes \lambda = \lambda^{(1)} </math>]
 
 
-  since Small(10.001) [to degree <math>\lambda</math>] 
 


and 
Equivalently, we can refer to a ''graded entailment relation'' <math> \models </math><sup>λ</sup> by writng ''s'' <math> \models </math><sup>λ</sup> α  where λ = ''Inf''{''Val''(''I,α'') : (''D,I'') <math>\models </math> ''s''}.


These definitions are in accordance with the fact that ''s'' represents a system of ''"lower bound constraints"'' on the unknown truth value of the formulas. Moreover, ''Lc''(''s'') is the better lower bound constraint we can find given ''s''. In the graded approach we can obtain a deduction apparatus by extending Hilbert's approach as follows.


Small(10.001)<math>\rightarrow</math> Small(10.002)       [to degree <math>\lambda</math>]
'''Definition.''' A ''fuzzy inference rule'' is a pair ''r'' = (''syn'',''sem'') where ''syn'', the ''syntactical part'', is a partial ''n''-ary operation in ''F'' (i.e. an inference rule in the usual sense) and ''sem'', the ''semantic part'', is an ''n''-ary join-preserving operation in [0,1]. An ''evaluated syntax'' is a structure (''la'',''R'') where ''la'' is a fuzzy set of formulas we call ''fuzzy subset of logical axioms'', and ''R'' is a set of fuzzy inference rules.


Usually, ''n'' = 2 and ''sem''(λ<sub>1</sub>,λ<sub>2</sub>) is a product like λ<sub>1</sub>ʘ λ<sub>2</sub>. As an example, the ''fuzzy Modus Ponens'' is defined by assuming that the domain of ''syn'' is the set {(α, α→β):  α,β are in ''F''}, by setting  ''syn''(α, α→β) = β and by assuming that ''sem''(λ,μ) = λʘμ. This rule says that


we state
: - if we are able to prove  α at degree λ
: - and α → β at degree μ
: - then we can prove β at degree λʘμ.




Small(10.002) [to degree <math>\lambda\otimes \lambda = \lambda^{(2)} </math>]
'''Definition'''. A ''proof'' π of a formula α is a
sequence α<sub>1</sub>,...,α<sub>''m''</sub> of formulas such that α<sub>''m''</sub> = α,
together with a sequence of related ''justifications''. This means that, for every formula α<sub>''i''</sub>, we have to specify whether


:''i'') α<sub>''i''</sub> is assumed as a logical axiom or;
:''ii'') α<sub>''i''</sub> is assumed as an hypothesis or;
:''iii'') α<sub>''i''</sub> is obtained by a rule (in this case we have to indicate the rule and the formulas from α<sub>1</sub>,...,α<sub>''i''-1</sub> used to obtain α<sub>''i''</sub>).


. . .  
The justifications are necessary to valuate the proofs. Indeed, let ''s'' be the fuzzy subset of proper axioms and, for every ''i ≤ m'' denote by π(''i'') the proof α<sub>1</sub>,...,α<sub>''i''</sub>. Then the information furnished by π given ''s'' is the value ''Val''(π,''s'') is defined by induction on ''m'' by setting


:''Val''(π, ''s'') = ''la''(α<sub>''m''</sub>) if α<sub>''m''</sub> is assumed as a logical axiom
:''Val''(π, ''s'') = ''s''(α<sub>''m''</sub>) if α<sub>''m''</sub> is assumed as an hypothesis
:''Val''(π,''s'') = ''sem''(''Val''(π(i<sub>1</sub>),''s''),...,''Val''(π(''i''<sub>''n''</sub>),''s''))  if there is a fuzzy rule (''syn'',''sem'') such that α<sub>''m''</sub> = ''syn''(α<sub>''i''<sub>1</sub></sub>,...,α<sub>''i''<sub>''n''</sub></sub>) with ''i''<sub>1</sub> < ''m'',...,''i''<sub>''n''</sub> < ''m''.


-  since Small(10.000+''n''-1) [to degree <math>\lambda\otimes \lambda^{(n-1)}</math>] 
Now, unlike the usual deduction systems, in a fuzzy deduction system, different proofs of a same formula α may give different pieces of information on the truth degree of α. Then, we have to ''"fuse"'' all these informations.


'''Definition'''. The ''deduction operator'' is the operator ''D'' defined by setting
:''D''(''s'')(α)= ''Sup''{''Val''(π,''s'')| π is a proof of α}.
A fuzzy logic is ''axiomatizable'' if there is a fuzzy deduction system such that ''Lc = D''.


and
In Novak 2007 one proves the following basic result.


'''Proposition'''. In the graded approach Łukasiewicz first order logic is axiomatizable.


Small(10.000+''n''-1)<math>\rightarrow</math> Small(10.000+''n'')  [to degree <math>\lambda</math>]
Notice also that, under some natural hypotheses, a fuzzy propositional logic is axiomatizable if and only if the logical connectives are interpreted by continuous functions (see Gerla 2001).


'''Criticisms.''' A criticism for such an approach is that is not sufficiently flexible. As an example let (''D,I'') be a fuzzy model of a fuzzy theory ''s''. It is evident that both the assignments (''D,I'') and ''s'' cannot be considered definitive and precise since both depends on a subjective valuation. Assume that either (''D,I'') or ''s'' is subject to a slightly variation as a consequence of a tuning process, an essential component in all the applications in fuzzy mathematics. Then it is possible that (''D,I'') ceases completely to be a model of ''s''  while it should be natural to expect (''D,I'') is again a model of ''s'' at some degree.


we state
== Continuous logic ==
A very important precursor of fuzzy logic is the '' Continuous logic'' proposed by Chang and Keisler since 1966. In their book all the model theoretical notions of classical logic are extended to first order multi-valued logic. As an example, the notions of quotient, direct product, ultraproduct are defined and examined. Recently, an interesting reformulation of continuous logic was proposed to give a basis for a model theory for the various kinds of ''"metric"'' structures arising in functional analysis and probability theory (see for example Ben I. Y. et al. 2008). Such a reformulation is obtained by referring to the interval [0,1] and by interpreting the logical connectives by a class of continuous functions able to define a ''complete'' approximation system. Also one considers models in which a pseudo-metric is defined to interpret the symbol =. One assumes that all the predicates and function symbols are uniformly continuous with respect such a pseudo-metric. As an example, the finitely additive probabilities can be considered models of a continuous logic once we consider a language for Boolean algebras equipped with a vague monadic predicate ''p'' such that the interpretation of ''p''(''x'') is ''"the event x is probable"''.


== Fuzzy logic with no truth-functional semantics ==
Fuzzy logic extends beyond the truth-functional tradiction of multi-valued logic. The following are two examples.


Small(10.000+''n'')  [to degree <math>\lambda^{n-1}\otimes \lambda = \lambda^{(n)}</math>].
In particular, we can prove Small(10.000+10.000) at degree  <math> \lambda^{(10.000)} </math>. Now, this is not paradoxical. Indeed if <math>\otimes</math> is the Lukasievicz triangular norm, then <math>\lambda^{(n)}</math> = max {<math>n\lambda-n+1, 0</math>}. As a consequence, we have that <math>\lambda^{(n)} = 0</math> for every <math>n \geq 1/(1-\lambda)</math>.  Assume that <math>\lambda = 1-10^{-4}</math> then <math> \lambda^{(10.000)} = 0</math>.
In this way we get a formal representation of heap argument preserving its intuitive content but avoiding its paradoxical character.
=== The Poincaré paradox ===
(to be included)
=== The liar paradox ===
(to be included)
== Fuzzy logic with no semantics ==
=== Necessity logic ===
=== Necessity logic ===
This very simple fuzzy logic is obtained by an obvious fuzzyfication of first order classical logic. Indeed, assume, for example, that the deduction apparatus of classical first order logic is presented by a suitable set ''Al'' of logical axioms, by the MP-rule and the Generalization rule and denote by <math> \vdash </math> the related consequence relation. Then a fuzzy deduction system is obtained by considering as fuzzy subset of logical axioms the characteristic function of ''Al'' and as fuzzy inference rules the extension of ''MP'' obtained by assuming that <math> \otimes </math> is the minimum operator <math> \wedge </math>. Moreover, an extension of the Generalization rule is obtained by assuming that if we prove <math> \alpha </math> at degree <math> \lambda </math> then we obtain <math> \forall x\alpha(x) </math> at the same degree <math> \lambda </math>.
Assume that the deduction apparatus of classical first order logic is presented by a suitable set ''la'' of logical axioms, by the MP-rule and the Generalization rule. Then a fuzzy deduction system is obtained by considering as a fuzzy subset of logical axioms the characteristic function of ''la'' and as fuzzy inference rules the fuzzy Modus Ponens and the extension of the Generalization Rule obtained by assuming that if we prove α at degree λ then we obtain <math> \forall</math>xα(x) at the same degree λ. In suh a case it is easy to see that if ''s'' is a fuzzy theory, then
Assume that ''D'' is the deduction operator of such a fuzzy logic and that ''s'' is a fuzzy set of proper axioms. Then one proves that <math>D(s)( \alpha) = 1</math> for every logically true formula <math>\alpha </math>. Otherwise,  
 
<math>D(s)( \alpha) = Sup\{s(\alpha_1)\wedge ...\wedge s(\alpha_n) : \alpha_1,..., \alpha_n \vdash \alpha\}</math>.
 
By recalling that the existential quantifier is interpreted by the supremum operator, such a formula arises from a multivalued valuation of the (metalogical) claim:
''"<math> \alpha</math> is a consequence of the fuzzy subset s of axioms if there are formulas <math>\alpha_1, ...,\alpha_n</math> in s able to prove <math>\alpha </math>"''


It is apparent that in such a case the vagueness originates from ''s'', i.e., from the notion of "hypothesis". Moreover <math>s(\alpha) </math> is not a truth degree but rather a degree of "preference" or "acceptability" for <math> \alpha</math>. For example, let ''T'' be a system of axioms for set theory and assume that the choice axiom ''CA'' does not depend on ''T''. Then we can consider the fuzzy subset of axioms ''s'' defined by setting
: ''D''(''s'')(α) = 1 i α is a logically true formula,  
:''D''(''s'')(α) = ''Sup''{''s''(α<sub>1</sub>)ʘ ...ʘ''s''(α<sub>''n''</sub>) : α<sub>1</sub>,..., α<sub>''n''</sub> <math>\vdash</math>α}, otherwise.


<math> s(\alpha) = 1 </math> if <math> \alpha \in T </math>,
By recalling that the existential quantifier is interpreted by the supremum operator, such a formula arises from a multivalued valuation of the (metalogical) claim: ''"α is a consequence of the fuzzy subset ''s'' of axioms provided there are formulas α<sub>1</sub>, ...,α<sub>n</sub> in ''s'' able to prove <math>\alpha </math>"''. In such a case the vagueness originates from ''s'', i.e., from the notion of "hypothesis". Moreover ''s''(α) is not a truth degree but rather a degree of "preference" or "acceptability" for α. For example, let ʘ be the minimum, ''T'' be a system of axioms for set theory such that the choice axiom ''CA'' does not depend on ''T''.  Then we can consider the fuzzy subset of axioms ''s'' defined by setting


<math> s(\alpha) = 0.8 </math>  if <math> \alpha = CA </math>,
:''s''(α) = 1  if α є ''T'',
 
:''s''(α) = 0.8 if α = ''CA'' ,
<math> s(\alpha) = 0 </math> otherwise.
:''s''(α) = 0 otherwise.


A simple calculation shows that:
A simple calculation shows that:


<math> D(s)(\alpha) = 1 </math> if we can prove <math> \alpha </math>  from T, otherwise
:''D''(''s'')(α) = 1   if α is a theorem of ''T'',
:''D''(''s'')(α) = 0.8 if we cannot prove α from ''T'' but α is a theorem of ''T + CA'',
:''D''(''s'')(α) = 0 otherwise .


<math> D(s)(\alpha) = 0.8 </math>  if  we can prove <math> \alpha </math> from T + CA, otherwise
Then, despite the fact that no vague predicate is considered in set theory, in the metalanguage we can consider a vague meta-predicate as "is acceptable" and to represent it by a suitable fuzzy subset ''s''.
 
<math> D(s)(\alpha) = 0 </math> .
 
Fuzziness in this case is not semantical in nature. Indeed, it is evident that the number <math> s(\alpha) </math>  is a degree of acceptability for <math> \alpha </math> and not a truth degree. In this sense, by recalling the Euclidean distinction between axiom and postulate, perhaps it's better to say ''s'' is the fuzzy subset of the accepted postulates. Thus, despite the fact that no vague predicate is considered in set theory, in the metalanguage we can consider a vague predicate as "is acceptable" and to represent it by a suitable fuzzy subset ''s''. Equivalently, we can interpret <math> s(\alpha) </math> as the degree of preference for <math> \alpha </math> since the only reason we assign to CA the degree 0.8 instead of 1 is that we do not like to use CA.
 
(to be completed)


=== Similarity logic ===
=== Similarity logic ===
In accordance with the ideas of M. S. Ying [1994] we can extend necessity logic by introducing a similarity relation among the predicates. As an example, consider an inference like
In accordance with the ideas of M. S. Ying (1994) we can extend necessity logic by introducing a similarity relation among the predicates (see also Biacino, Gerla, Ying (2002)). As an example, consider an inference like
   
   
1.     x is a thriller  <math>\Rightarrow</math>  x good for me          +
:'''Since'''     ''x is a thriller'' <math>\Rightarrow</math>  ''x good for me''         +
:'''and'''                    ''b is a detective story''                +
:'''and'''  ''"detective story"'' is synonymous of  ''"thriller"''
:'''then'''  ''"b is good for me"''.


2.                   b is a detective story                +
Now the synonymy is a vague notion we can represent by a suitable similarity in the set ''W'' of English worlds, i.e. a fuzzy relation ''e'' such that


3.   "detective story" is synonymous of  "thriller"  
: (a)  ''e''(''x'',''x'') = 1  (reflexivity),
: (b)  ''e''(''x'',''z'')ʘ''e''(''z'',''y'') ≤ ''e''(''x'',''y'')    (transitivity),
: (c)  ''e''(''x'',''y'') = ''e''(''y'',''x'')                  (symmetry).
 
Also, as it is usual in fuzzy logic, it is natural to admit that the truth degree of the conclusion "b is good for me" depends on the degree of similarity between the predicates "detective story" and "thriller", obviously. The structure of the corresponding fuzzy inference rule is:


therefore
:'''If''' α  was proven at degree λ,
:'''and''' α’→ β at degree μ,
:'''then''' β is proven at degree λʘμʘ''e''(α,α’).


    "b is good for me".
Every inference rule can be extended in a similar way, i.e. by relaxing the precise matching of the identity with the approximate matching of a similarity. These ideas are also on the basis for a similarity-based [[fuzzy logic programming]].


Now the synonymy is a vague notion we can represent by a suitable similarity e in the set W of English worlds, i.e. a fuzzy relation e such that
== Effectiveness ==


(a)  e(x,x) = 1                          (reflexivity),
A test to analyze the effectiveness in the ungraded approach to fuzzy logic is to refer to the set of tautologies. Now, since two entailment relations are defined, we have to consider two corresponding notions of tautology.


(b)  e(x,z)<math>\otimes</math>  e(z,y) ≤ e(x,y)    (transitivity),


(c)   e(x,y) = e(y,x)                   (symmetry).
'''Definition''' Given a standard algebra ([0,1], ʘ, →, 0, 1) a formula α is a ''standard tautology'' if it is satisfied in every fuzzy interpretation in ([0,1], ʘ, →, 0, 1). The formula α is a ''general tautology'' if it is satisfied in every safe ''Varl''(ʘ)-interpretation.  


Also, as it is usual in fuzzy logic, it is natural to admit that the truth degree of the conclusion "b is good for me" depends on the degree of similarity between the predicates "detective story" and "thriller", obviously. The structure of the corresponding fuzzy inference rule is:


if α  was proven at degree λ
In the first case the following negative result holds true.


and α’→ β at degree μ


then
'''Theorem.''' In the case of Łukasiewicz and product logic the set of standard tautologies is not recursively enumerable (see B. Scarpellini (1962)).


β is proven at degree λ<math>\otimes</math> μ <math>\otimes</math> e(α,α’).


Every inference rule can be extended in a similar way, i.e. by relaxing the precise matching of the identity with the approximate matching of a similarity. These ideas are on the basis of a similarity based logic programming.
Such a fact gives a further confirm on the impossibility of an axiomatization of the entailment relation <math>\models</math> and it leads to focalize the attention on <math>\models</math><sub>''Varl''(ʘ)</sub>. At this regard one proves the following theorem.


== Rational Pavelka logic ==
(to be included)


== Effectiveness ==
'''Theorem.''' For each continuous t-norm ʘ, the set of general ʘ-tautologies in first order logic is Σ<sub>1</sub>-complete (and therefore recursively enumerable).


=== Effectiveness for fuzzy subsets ===
In the case of the graded approach to face the question of the effectiveness we have to refer to the notion of effectiveness for [[fuzzy subset]] theory. A first proposal in such a direction was made by [[E.S. Santos]] by the notions of ''fuzzy [[Turing machine]]''. Successively, in Biacino and Gerla 2006 the following definition was proposed where ''Ü'' denotes the set of rational numbers in [0,1].
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] and <math>-s</math> is the complement of the fuzzy subset <math>s</math> defined by setting <math>-s(x) = 1-s(x)</math> .


'''Definition''' A fuzzy subset μ : ''S'' <math>\rightarrow</math>[0,1] of a set ''S'' is ''recursively enumerable'' if a recursive map ''h'' : ''S''×''N'' <math>\rightarrow</math>''Ü'' 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 G. Gerla (2006) where one refers to the theory of effective domains.
'''Definition''' A fuzzy subset ''s'' : ''S'' <math>\rightarrow</math>[0,1] of a set ''S'' is ''recursively enumerable'' if a recursive map ''h'' : ''S''×''N'' <math>\rightarrow</math>''Ü'' exists such that, for every ''x'' in ''S'', the function ''h''(''x'',''n'') is increasing with respect to ''n'' and ''s''(''x'') = ''lim h''(''x'',''n'').
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).
We say that s is ''decidable'' if both s and its complement –s are recursively enumerable.  


=== 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 (1962)). 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.
An extension of such a theory to the general case of the L-subsets is proposed in Gerla (2006) where one refers to the theory of effective domains. It is an open question to give supports for a ''Church thesis'' for fuzzy set theory claiming that the proposed notion of recursive enumerability for fuzzy subsets is the adequate one.  


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.
In Gerla (2001) one proves the following theorem where we refer to fuzzy logics whose deduction apparatus satisfies some obvious effectiveness properties.  


== Basic Fuzzy Logic ==
(to be included)


== Is fuzzy logic a proper extension of classical logic ? ==
'''Theorem.''' Given an axiomatizable fuzzy logic, its fuzzy subset ''D''(Ø) of tautologies is recursively enumerable. In particular the fuzzy subset of tautologies in Łukasievicz logic is recursively enumerable in spite of the non recursive enumerability of its cut {α : ''D''(Ø)(α) = 1}. 


Obviously, the question of the connection between classical and fuzzy logic arises. Now, we can consider this question from two point of views. Firstly, the interpretation of the logical connectives in fuzzy logic is ''conservative''. This means that these interpretations  coincide with the classical ones in the case we confine ourselves to truth values in {0,1}. So, in such a sense fuzzy logic is a conservative proper extension of classical logic. On the other hand fuzzy logic is defined by using elementary notions of mathematics and therefore it is a (small) part of classical logic. From such a point of view, differently from intuitionistic logic, fuzzy logic is not an alternative to classical mathematics. Rather, its relation with classical mathematics is similar in nature with the one between recursive and classical mathematics.


== See also ==
It is an open question to use the notion of recursively enumerable fuzzy subset to extend  [[Gödel]]’s limitative theorems to fuzzy logic.
* [[Fuzzy subalgebra]]
* [[Fuzzy associative matrix]]
* [[Fuzzy programming logic]]
* [[Fuzzy set]]
* [[Paradoxes]]
* [[Rough set]]
* [[Similarity logic]]
* [[Necessity logic]]
* [[MV-algebras]]
* [[Basic logic]]


== Bibliography ==
==Links==
* Biacino L., Gerla G., Ying M. S.: Approximate reasoning based on similarity, Math. Log. Quart., 46 (2000), 77-86.
* 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.
* Elkan C.. ''The Paradoxical Success of Fuzzy Logic''. November 1993. Available from [http://www.cse.ucsd.edu/users/elkan/ 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.
* Hájek P., Novák V., The sorites paradox and fuzzy logic, ''Internat. J. General Systems'', 32 (2003) 373-383.
* 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
* Formato F., Gerla G., Sessa M., Similarity-based unification, ''Fundamenta Informaticae'', 41 (2000), 393-414.
* Gerla G., Effectiveness and Multivalued Logics, ''Journal of Symbolic Logic'', 71 (2006) 137-162.
* Goguen J. A., The logic of inexact concepts, ''Synthese'', 19 (1968/69) 325-373.
* Gottwald S., ''A Treatise on Many-Valued Logics, Studies in Logic and Computation'', Research Studies Press, Baldock, 2001.
* Gottwald S., Mathematical fuzzy logic as a tool for the treatment of vague information, ''Information Sciences'', 72, (2005) 41-1.
* 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).
* Santos E. S., Fuzzy algorithms, ''Inform. and Control'', 17,(1970), 326-339.
* Pavelka, On fuzzy logic, I-III, ''Zeitschr. Math. Logik Grundl. Math.'', 25, (1979), 45-52, 119-134, 447-464.
* Scarpellini B., Die Nichaxiomatisierbarkeit des unendlichwertigen Prädikatenkalküls von Łukasiewicz, ''J. of Symbolic Logic'', 27,(1962), 159-170.
* Wiedermann J. , Characterizing the super-Turing computing power and efficiency of classical fuzzy Turing machines, ''Theor. Comput. Sci.'' 317, (2004), 61-69.
* Ying M. S., A logic for approximate reasoning, ''J. Symbolic Logic'', 59 (1994).
* Zadeh L. A., Fuzzy Sets, ''Information and Control'', 8 (1965) 338­-353.
* Zadeh L. A., Fuzzy algorithms, ''Information and Control'', 5,(1968), 94-102.
* Zimmermann H., ''Fuzzy Set Theory and its Applications'' (2001), ISBN 0-7923-7435-5.


http://www.ggerla.it/


[[category:CZ Live]]
https://en.wikipedia.org/wiki/Fuzzy_logic[[Category:Suggestion Bot Tag]]
[[category:Computers Workgroup]]
[[category:Mathematics Workgroup]]
[[category:Philosophy Workgroup]]

Latest revision as of 16:01, 17 August 2024

This article is developing and not approved.
 Main Article
 Discussion
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
 
https://en.citizendium.org/wiki/index.php?title=Formal_fuzzy_logic&printable=yes
This editable Main Article is under development and subject to a disclaimer.

Fuzzy logic is a relatively new chapter of formal logic whose aim is to formalize the reasonings involving predicates that are vague in nature (as an example small, near, similar). An example of such kind of reasoning is

If a tomato is red, then the tomato is ripe. Since this tomato is very red, this tomato is very ripe.

Further examples of reasonings involving vague predicates are in the item Paradoxes and fuzzy logic and in the section Fuzzy logic with no truth-functional semantics. The main tool for fuzzy logic is the notion of a fuzzy subset, since a vague predicate is interpreted by a fuzzy subset. Notice that in literature the name "fuzzy logic" also denotes a large series of topics based on an informal usage of the notion of a fuzzy subset, and which are usually devoted to applications.

As a matter of fact, fuzzy logic is an evolution and an enlargement of multi-valued logic since all the definitions and results in the literature on multi-valued logic are also considered in fuzzy logic. In particular, as in multi-valued logic, the starting point is a fixed valuation structure, i.e. a bounded lattice L equipped with suitable operations to interpret the logical connectives. The minimum 0 means 'False', the maximum 1 means 'True', the remaining elements are interpreted as intermediate truth values. The following is the main class of valuation structures (see Hájek 1998, Novák et al. 1999 and Gottwald 2005) corresponding to the connectives and .


Definition. A standard algebra is an algebraic structure ([0,1], ʘ, →, 0,1) where ʘ is a continuous triangular norm, i.e. a continuous, associative, commutative, order preserving operation such that xʘ1 = 1 and → is the related residuation, i.e. x→y = sup{z | xʘz ≤ y}.


The main examples of standard algebras are obtained by assuming that ʘ is the minimum (Zadeh logic), the usual product (product logic) or that xʘy = Max{x+y-1,0} (Łukasievicz logic). In addition, several authors consider also languages with logical constants to denote rational truth values. Once a valuation structure is fixed, the semantics of the corresponding propositional calculus is defined in a truth-functional way as usual. In first order fuzzy logic the semantics is defined as follows.


Definition. A fuzzy interpretation of a first order language is a pair (D,I) such that D is a nonempty set and I a map associating (as in the classical case) every n-ary operation name h with an n-ary operation in D and every constant c with an element I(c) in D. Moreover, I associates every n-ary predicate name r with an n-ary L-relation I(r) : Dn L in D.


Then the only difference with classical logic is that the interpretation of an n-ary predicate symbol is an n-ary fuzzy relation in D. This enables us to represent properties which are "vague" in nature. Given a fuzzy interpretation we can evaluate the formulas as follows where, given a term t whose variables are in x1,...,xn, we denote by the corresponding n-ary function we define as in classical logic.


Definition. Let (D,I) be a fuzzy interpretation, α a formula whose free variables are in x1,...,xn and d1,...,dn elements in D. Then we define the truth degree Val(I,α,d1,...,dn) by induction as follows :

Val(I, r(t1,...,tp), d1,...,dn) = I(r)(I(t1)(d1,...,dn), ..., I(tp)(d1,...,dn))
Val(I,α β, d1,...,dn) = Val(I,α,d1,...,dn)ʘVal(I,β,d1,...,dn)
Val(I,α → β, d1,...,dn) = Val(I,α, d1,...,dn) → Val(I,β,d1,...,dn)
Val(I, xiα, d1,...,dn) = Inf dєDVal(I,α,d1,...,di-1,d,di+1,...,dn).

In the case there is a propositional constant c* corresponding to a truth value c, we set

Val(I, c*,d1,...,dn) = c.

Observe that in the case L is not complete it is possible that a quantified formula cannot be evaluated. We call safe an interpretation such that all the formulas are evaluated. As usual, if α is a closed formula, then its valuation does not depend on the elements d1,...,dn and we write Val(I,α) instead of Val(I,α,d1,...,dn). More in general, given any formula α, we denote by Val(I, α) the valuation of the universal closure of α.

Two approaches

There are two basic approaches to fuzzy logic. The first one, proposed by P. Hajek and followed by Di Nola, Esteva, Gottwald, Godo, Montagna, Mundici and by a large series of students, is very close to the tradition of multi-valued logic. Indeed the deduction apparatus works on a set of hypotheses to give the corresponding set of logical consequences. This is obtained, as it is usual in multi-valued logic, once a set of designed truth values is fixed. We call, ungraded approach such a way to face fuzzy logic. Another approach was proposed by J. A. Goguen, J. Pavelka, V. Novak, G. Gerla and further authors and it is rather out of line with the tradition of multi-valued logic. Indeed, the deduction apparatus works on a given fuzzy subset of hypotheses (the available information) to give the related fuzzy subset of logical consequences. We call graded approach such a way to face fuzzy logic.

The ungraded approach

In the ungraded approach a subset Des of [0,1] is fixed whose elements are called designed truth degrees. The interpretation is that in Des there are the truth degrees which one considers sufficient to claim the validity of a formula. Usually one sets Des = {1}.


Definition. Let ([0,1], ʘ, →, 0, 1) be a fixed standard algebra, and α be a formula. Then we say that a fuzzy interpretation (D,I) satisfies α provided that Val(I,α) is a designed value. Let T be a theory, then (D,I) is a model of T if every formula in T is satisfied in (D,I). We write T ʘ α if every model of T satisfies α.

The deduction apparatus in the ungraded approach is defined by adopting the same paradigm of classical logic, i.e. a deduction relation is defined by a suitable set of logical axioms and suitable inference rules. The fuzzy logic defined by ʘ is axiomatizable provided that a deduction apparatus exists such that coincides with ʘ. Unfortunately, the main fuzzy logics are not axiomatizable.


Theorem. In all the main fuzzy logics (in particular in Łukasievicz logic) the entailment relation ʘ is not compact. This entails that these logics are not axiomatizable.


As an attempt to bypass such an obstacle, in the ungraded approach one proposes a different entailment relation related with the variety generated by a given triangular norm.


Definition. Given a standard algebra ([0,1], ʘ, →,0,1), denote by Varl(ʘ) the class of all linearly ordered algebras in the variety generated by ([0,1], ʘ, →, 0, 1). Then a Varl(ʘ)-interpretation is an interpretation in a valuation algebra belonging to Varl(ʘ). Given a set T of formulas and a formula α, we write T Varl(ʘ) α provided that every safe Varl(ʘ)-model of T is a safe Varl(ʘ)-model of α.


In such a case, the resulting logic works well. In fact, the following theorem holds true.


Theorem. In all the main fuzzy logics (in particular in Łukasievicz logic) the entailment relation Varl(ʘ) is compact. This is in accordance with the fact that these logics are axiomatizable (provided that they are defined by referring to this relation).


Criticisms. A criticism for the ungraded approach, philosophical in nature, concerns its adequateness to represent the daily reasonings in which vague predicates occur. Moreover the structures in Varl(ʘ) look rather unnatural. For example, in Varl(ʘ) there are structures with infinitesimal truth values. Another criticism is that, while the completeness of [0,1] assures that all the formulas are valuated, in the case we refer to the variety Varl(ʘ), we are forced to admit interpretations for which there are unvaluated formulas.

The graded approach: approximate reasonings

The aim of any logic is to elaborate (uncomplete) information to obtain more explicit information. Now, in the case of fuzzy logic it is natural to admit an information like "the truth values of α is between λ and μ", i.e. a constraint on the possible truth value of a formula. Now, observe that if we admit the usual interpretation of the negation, then Val(I,α)≤ λ if and only if Val(I, α)≥ 1-μ. Then we can reduce all the interval constraints to lower bound constraints. In accordance in the graded approach one proposes the following definition.

Definition . Consider a fuzzy theory s, i.e. a fuzzy subset of formulas. Then a fuzzy interpretation (D,I) is a model of s, in brief (D,I) s if Val(I,α) ≥ s(α). The logical consequence operator is the map Lc : [0,1]F → [0,1]F defined by setting

Lc(s)(α) = Inf{Val(I,α) : (D,I) s}.

Equivalently, we can refer to a graded entailment relation λ by writng s λ α where λ = Inf{Val(I,α) : (D,I) s}.

These definitions are in accordance with the fact that s represents a system of "lower bound constraints" on the unknown truth value of the formulas. Moreover, Lc(s) is the better lower bound constraint we can find given s. In the graded approach we can obtain a deduction apparatus by extending Hilbert's approach as follows.

Definition. A fuzzy inference rule is a pair r = (syn,sem) where syn, the syntactical part, is a partial n-ary operation in F (i.e. an inference rule in the usual sense) and sem, the semantic part, is an n-ary join-preserving operation in [0,1]. An evaluated syntax is a structure (la,R) where la is a fuzzy set of formulas we call fuzzy subset of logical axioms, and R is a set of fuzzy inference rules.

Usually, n = 2 and sem(λ1,λ2) is a product like λ1ʘ λ2. As an example, the fuzzy Modus Ponens is defined by assuming that the domain of syn is the set {(α, α→β): α,β are in F}, by setting syn(α, α→β) = β and by assuming that sem(λ,μ) = λʘμ. This rule says that

- if we are able to prove α at degree λ
- and α → β at degree μ
- then we can prove β at degree λʘμ.


Definition. A proof π of a formula α is a sequence α1,...,αm of formulas such that αm = α, together with a sequence of related justifications. This means that, for every formula αi, we have to specify whether

i) αi is assumed as a logical axiom or;
ii) αi is assumed as an hypothesis or;
iii) αi is obtained by a rule (in this case we have to indicate the rule and the formulas from α1,...,αi-1 used to obtain αi).

The justifications are necessary to valuate the proofs. Indeed, let s be the fuzzy subset of proper axioms and, for every i ≤ m denote by π(i) the proof α1,...,αi. Then the information furnished by π given s is the value Val(π,s) is defined by induction on m by setting

Val(π, s) = la(αm) if αm is assumed as a logical axiom
Val(π, s) = s(αm) if αm is assumed as an hypothesis
Val(π,s) = sem(Val(π(i1),s),...,Val(π(in),s)) if there is a fuzzy rule (syn,sem) such that αm = syn(αi1,...,αin) with i1 < m,...,in < m.

Now, unlike the usual deduction systems, in a fuzzy deduction system, different proofs of a same formula α may give different pieces of information on the truth degree of α. Then, we have to "fuse" all these informations.

Definition. The deduction operator is the operator D defined by setting

D(s)(α)= Sup{Val(π,s)| π is a proof of α}.

A fuzzy logic is axiomatizable if there is a fuzzy deduction system such that Lc = D.

In Novak 2007 one proves the following basic result.

Proposition. In the graded approach Łukasiewicz first order logic is axiomatizable.

Notice also that, under some natural hypotheses, a fuzzy propositional logic is axiomatizable if and only if the logical connectives are interpreted by continuous functions (see Gerla 2001).

Criticisms. A criticism for such an approach is that is not sufficiently flexible. As an example let (D,I) be a fuzzy model of a fuzzy theory s. It is evident that both the assignments (D,I) and s cannot be considered definitive and precise since both depends on a subjective valuation. Assume that either (D,I) or s is subject to a slightly variation as a consequence of a tuning process, an essential component in all the applications in fuzzy mathematics. Then it is possible that (D,I) ceases completely to be a model of s while it should be natural to expect (D,I) is again a model of s at some degree.

Continuous logic

A very important precursor of fuzzy logic is the Continuous logic proposed by Chang and Keisler since 1966. In their book all the model theoretical notions of classical logic are extended to first order multi-valued logic. As an example, the notions of quotient, direct product, ultraproduct are defined and examined. Recently, an interesting reformulation of continuous logic was proposed to give a basis for a model theory for the various kinds of "metric" structures arising in functional analysis and probability theory (see for example Ben I. Y. et al. 2008). Such a reformulation is obtained by referring to the interval [0,1] and by interpreting the logical connectives by a class of continuous functions able to define a complete approximation system. Also one considers models in which a pseudo-metric is defined to interpret the symbol =. One assumes that all the predicates and function symbols are uniformly continuous with respect such a pseudo-metric. As an example, the finitely additive probabilities can be considered models of a continuous logic once we consider a language for Boolean algebras equipped with a vague monadic predicate p such that the interpretation of p(x) is "the event x is probable".

Fuzzy logic with no truth-functional semantics

Fuzzy logic extends beyond the truth-functional tradiction of multi-valued logic. The following are two examples.

Necessity logic

Assume that the deduction apparatus of classical first order logic is presented by a suitable set la of logical axioms, by the MP-rule and the Generalization rule. Then a fuzzy deduction system is obtained by considering as a fuzzy subset of logical axioms the characteristic function of la and as fuzzy inference rules the fuzzy Modus Ponens and the extension of the Generalization Rule obtained by assuming that if we prove α at degree λ then we obtain xα(x) at the same degree λ. In suh a case it is easy to see that if s is a fuzzy theory, then

D(s)(α) = 1 i α is a logically true formula,
D(s)(α) = Sup{s(α1)ʘ ...ʘs(αn) : α1,..., αn α}, otherwise.

By recalling that the existential quantifier is interpreted by the supremum operator, such a formula arises from a multivalued valuation of the (metalogical) claim: "α is a consequence of the fuzzy subset s of axioms provided there are formulas α1, ...,αn in s able to prove ". In such a case the vagueness originates from s, i.e., from the notion of "hypothesis". Moreover s(α) is not a truth degree but rather a degree of "preference" or "acceptability" for α. For example, let ʘ be the minimum, T be a system of axioms for set theory such that the choice axiom CA does not depend on T. Then we can consider the fuzzy subset of axioms s defined by setting

s(α) = 1 if α є T,
s(α) = 0.8 if α = CA ,
s(α) = 0 otherwise.

A simple calculation shows that:

D(s)(α) = 1 if α is a theorem of T,
D(s)(α) = 0.8 if we cannot prove α from T but α is a theorem of T + CA,
D(s)(α) = 0 otherwise .

Then, despite the fact that no vague predicate is considered in set theory, in the metalanguage we can consider a vague meta-predicate as "is acceptable" and to represent it by a suitable fuzzy subset s.

Similarity logic

In accordance with the ideas of M. S. Ying (1994) we can extend necessity logic by introducing a similarity relation among the predicates (see also Biacino, Gerla, Ying (2002)). As an example, consider an inference like

Since x is a thriller x good for me +
and b is a detective story +
and "detective story" is synonymous of "thriller"
then "b is good for me".

Now the synonymy is a vague notion we can represent by a suitable similarity in the set W of English worlds, i.e. a fuzzy relation e such that

(a) e(x,x) = 1 (reflexivity),
(b) e(x,z)ʘe(z,y) ≤ e(x,y) (transitivity),
(c) e(x,y) = e(y,x) (symmetry).

Also, as it is usual in fuzzy logic, it is natural to admit that the truth degree of the conclusion "b is good for me" depends on the degree of similarity between the predicates "detective story" and "thriller", obviously. The structure of the corresponding fuzzy inference rule is:

If α was proven at degree λ,
and α’→ β at degree μ,
then β is proven at degree λʘμʘe(α,α’).

Every inference rule can be extended in a similar way, i.e. by relaxing the precise matching of the identity with the approximate matching of a similarity. These ideas are also on the basis for a similarity-based fuzzy logic programming.

Effectiveness

A test to analyze the effectiveness in the ungraded approach to fuzzy logic is to refer to the set of tautologies. Now, since two entailment relations are defined, we have to consider two corresponding notions of tautology.


Definition Given a standard algebra ([0,1], ʘ, →, 0, 1) a formula α is a standard tautology if it is satisfied in every fuzzy interpretation in ([0,1], ʘ, →, 0, 1). The formula α is a general tautology if it is satisfied in every safe Varl(ʘ)-interpretation.


In the first case the following negative result holds true.


Theorem. In the case of Łukasiewicz and product logic the set of standard tautologies is not recursively enumerable (see B. Scarpellini (1962)).


Such a fact gives a further confirm on the impossibility of an axiomatization of the entailment relation and it leads to focalize the attention on Varl(ʘ). At this regard one proves the following theorem.


Theorem. For each continuous t-norm ʘ, the set of general ʘ-tautologies in first order logic is Σ1-complete (and therefore recursively enumerable).

In the case of the graded approach to face the question of the effectiveness we have to refer to the notion of effectiveness for fuzzy subset theory. A first proposal in such a direction was made by E.S. Santos by the notions of fuzzy Turing machine. Successively, in Biacino and Gerla 2006 the following definition was proposed where Ü denotes the set of rational numbers in [0,1].


Definition A fuzzy subset s : S [0,1] of a set S is recursively enumerable if a recursive map h : S×N Ü exists such that, for every x in S, the function h(x,n) is increasing with respect to n and s(x) = lim h(x,n). We say that s is decidable if both s and its complement –s are recursively enumerable.


An extension of such a theory to the general case of the L-subsets is proposed in Gerla (2006) where one refers to the theory of effective domains. It is an open question to give supports for a Church thesis for fuzzy set theory claiming that the proposed notion of recursive enumerability for fuzzy subsets is the adequate one.

In Gerla (2001) one proves the following theorem where we refer to fuzzy logics whose deduction apparatus satisfies some obvious effectiveness properties.


Theorem. Given an axiomatizable fuzzy logic, its fuzzy subset D(Ø) of tautologies is recursively enumerable. In particular the fuzzy subset of tautologies in Łukasievicz logic is recursively enumerable in spite of the non recursive enumerability of its cut {α : D(Ø)(α) = 1}.


It is an open question to use the notion of recursively enumerable fuzzy subset to extend Gödel’s limitative theorems to fuzzy logic.

Links

http://www.ggerla.it/

https://en.wikipedia.org/wiki/Fuzzy_logic

Retrieved from "https://citizendium.org/wiki/index.php?title=Formal_fuzzy_logic&oldid=972404"