Formal fuzzy logic

Formal fuzzy logic

"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 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 by fixing truth-functional valuations 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 is totally out of line with the tradition of multi-valued logic in the idea of deduction. Indeed, usually in multi-valued logic the deduction apparatus is devoted to generate the (classical) set of valid formulas. Sometimes it leads to define a deduction operator which enables us 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 (and consequently the notions of compactness and effectiveness) is not different in nature from the one of classical logic. Instead, in fuzzy logic 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. This leads to define more appropriate notions of compactness and effectiveness.

Fuzzy logics: the semantics

We obtain a fuzzy logic by interpreting the logical connectives $,\vee ,\wedge ,\Rightarrow ,\neg$ by suitable binary operations $\otimes ,\oplus ,\rightarrow ,\nu$, respectively. As an example, in Lukasievicz logic we set

$x\otimes y=max\{x+y-1,0\}$,

$x\oplus y=\nu (\nu (x)\otimes \nu (y))=min\{x+y,1\},$

$x\rightarrow y=max\{1-x+y,1\}$,

$\nu (x)=1-x$.

Sometimes logical constants are also admitted and some of the logical connectives are defined from the remaining ones (see Hájek 1998 and Novák 1999). Once an interpretation of the logical connectives is given, the semantics of propositional calculus is defined in a truth-functional way as usual. In the case first order fuzzy logic, given a first order language, an interpretation 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 $D^{n}$ to [0,1]. This enables us to represent properties which are "vague" in nature.

Definition. Given a first order language, 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 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^{n}\rightarrow D$ in D.

In the following, given a term t, we denote by $I(t)$ the corresponding function we define as in classical logic.

Definition. Given a formula $\alpha \in F$ whose free variables are in $\{x_{1},...x_{n}\}$, we define the truth degree $Val(I,\alpha ,d_{1},...,d_{n})$ of $\alpha$ by induction on the complexity of $\alpha$ by setting

$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}))$ $Val(I,\alpha \wedge \beta ,d_{1},...,d_{n})=Val(I,\alpha ,d_{1},...,d_{n})\otimes Val(I,\beta ,d_{1},...,d_{n})$ $Val(I,\alpha \vee \beta ,d_{1},...,d_{n})=Val(I,\alpha ,d_{1},...,d_{n})\oplus Val(I,\beta ,d_{1},...,d_{n})$ $Val(I,\alpha \Rightarrow \beta ,d_{1},...,d_{n})=Val(I,\alpha ,d_{1},...,d_{n})\rightarrow Val(I,\beta ,d_{1},...,d_{n})$ $Val(I,\neg \alpha ,d_{1},...,d_{n})=\nu (Val(I,\alpha ,d_{1},...,d_{n}))$ $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 $\alpha$ is a closed formula, then its valuation does not depend on the elements $d_{1},...,d_{n}$ and we write $Val(I,\alpha )$ instead of $Val(I,\alpha ,d_{1},...,d_{n})$. More in general, given any formula $\alpha$, we denote by $Val(I,\alpha )$, the valuation of the universal closure of $\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 $(D,I)\models s$ if $Val(I,\alpha )\geq s(\alpha )$.

Then the meaning of a fuzzy subset of proper axioms s is that for every sentence $\alpha$, the value $s(\alpha )$ is a constraint" on the unknown truth value of $\alpha$. More precisely $s(\alpha )$ is a lower bound for such a value.

Definition. The logical consequence operator is the map $Lc:[0,1]^{F}\rightarrow [0,1]^{F}$ defined by setting

$Lc(s)(\alpha )=Sup\{Val(I,\alpha ):(D,I)\models s\}$.

Again, the value $Lc(s)(\alpha )$ is a "constraint" on the unknown truth value of $\alpha$. 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 $la$, 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 $\alpha _{1},...,\alpha _{n}$ at degree $\lambda _{1},...,\lambda _{n}$, respectively

- and we can apply sy to $\alpha _{1},...,\alpha _{n}$

- then we can prove $sy(\alpha _{1},...,\alpha _{n})$ at degree $se(\lambda _{1},...,\lambda _{n})$.

As an example, let $\otimes$ 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 $\{(\alpha ,\alpha \rightarrow \beta :\alpha ,\beta \in F\}$, by setting $sy(\alpha ,\alpha \rightarrow \beta )=\beta$ and by assuming that se coincides with $\otimes$, i.e. $se(\lambda _{1},\lambda _{2})=\lambda _{1}\otimes \lambda _{2}$. This rule says that if we are able to prove $\alpha$ and $\alpha \rightarrow \beta$ at degree $\lambda _{1}$ and $\lambda _{2}$, respectively, then we can prove $\beta$ at degree $\lambda _{1}\otimes \lambda _{2}$. The fuzzy $\land$-introduction rule is a totally defined rule such that sy($\alpha _{1},\alpha _{2})=\alpha _{1}\land \alpha _{2}$ and again se coincides with $\otimes$. This rule says that if we are able to prove $\alpha _{1}$ and $\alpha _{2}$ at degree $\lambda _{1}$ and $\lambda _{2}$, respectively, then we can prove $\alpha _{1}\land \alpha _{2}$ at degree $\lambda _{1}\otimes \lambda _{2}$.

A proof $\pi$ of a formula $\alpha$ is a sequence $\alpha _{1},...,\alpha _{m}$ of formulas such that $\alpha _{m}=\alpha$, together with a sequence of related justifications. This means that, for every formula $\alpha _{i}$, we have to specify whether

i) $\alpha _{i}$ is assumed as a logical axiom or;

ii) $\alpha _{i}$ is assumed as a proper axiom or;

iii) $\alpha _{i}$ is obtained by a rule (in this case we have to indicate also the rule and the formulas from $\alpha _{1},...,\alpha _{i-1}$ used to obtain $\alpha _{i}$).

The justifications are necessary to valuate the proofs. Indeed, let s be the fuzzy subset of proper axioms and, for every $i\leq m$ denote by $\pi (i)$ the proof $\alpha _{1},...,\alpha _{i}$. Then the valuation $Val(\pi ,s)$ of $\pi$ with respect to s is defined by induction on m by setting

$Val(\pi ,s)=la(\alpha _{m})$ if $\alpha _{m}$ is assumed as a logical axiom

$Val(\pi ,s)=s(\alpha _{m})$ if $\alpha _{m}$ is assumed as a proper axiom

$Val(\pi ,s)=se(Val(\pi (i_{1}),s),...,Val(\pi (i_{n}),s))$ if there is a fuzzy rule $(sy,se)$ such that $\alpha _{m}=sy(\alpha _{i(1)},...,\alpha _{i(n)})$ with $i_{1}<m,...,i_{n}<m$.

Now, unlike the crisp deduction systems, in a fuzzy deduction system different proofs of a same formula $\alpha$ may give different contributions to the degree of validity of $\alpha$. This suggests setting

$D(s)(\alpha )=Sup\{Val(\pi ,s)|\pi$ is a proof of $\alpha \}$.

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.

Definition. We say that 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).

The heap paradox

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)

and, for every n, the validity of the formulas

(b) Small(n) $\rightarrow$ Small(n+1).

On the other hand from these formulas we can prove that, given any natural number n, a heap with n stones is small. Indeed,

- from Small(1) and Small(1)$\rightarrow$ Small(2) by MP we may state Small(2);

- from Small(2) and Small(2)$\rightarrow$ Small(3) by MP we may state Small(3),

…

- from Small(n-1) and Small(n-1)$\rightarrow$ Small(n) by MP we may state Small(n).

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)$\rightarrow$ 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 $\lambda$ different from 1 (but very close to 1). Then, for example, we can express the axioms for the heap paradox as follows

Small(1) [to degree 1]

Small(2) [to degree 1]

...

Small(10.000) [to degree 1]

Small(10.000)$\rightarrow$ Small(10.001) [to degree $\lambda$]

Small(10.002)$\rightarrow$ Small(10.003) [to degree $\lambda$]

...

In accordance, the Heap Paradox argument can be restated as follows where we assume that $\otimes$ is associative and we denote by $\lambda ^{(n)}$ the n-power of $\lambda$ with respect to $\otimes$.

- Since Small(10.000) [to degree 1]

and

Small(10.000)$\rightarrow$ Small(10.001) [to degree $\lambda$]

we state

Small(10.001) [to degree $1\otimes \lambda =\lambda ^{(1)}$]

- since Small(10.001) [to degree $\lambda$]

and

Small(10.001)$\rightarrow$ Small(10.002) [to degree $\lambda$]

we state

Small(10.002) [to degree $\lambda \otimes \lambda =\lambda ^{(2)}$]

. . .

- since Small(10.000+n-1) [to degree $\lambda \otimes \lambda ^{(''n''-1)}$]

and

Small(10.000+n-1)$\rightarrow$ Small(10.000+n) [to degree $\lambda$]

we state

Small(10.000+n) [to degree $\lambda ^{''n''-1}\otimes \lambda =\lambda ^{(''n'')}$].

In particular, we can prove Small(10.000+10.000) at degree $\lambda ^{(10.000)}$. Now, this is not paradoxical. Indeed if $\otimes$ is the Lukasievicz triangular norm, then $\lambda ^{(n)}$ = max {n $\lambda -n+1,0$}. As a consequence, we have that $\lambda ^{(n)}=0$ for every $n\geq 1/(1-\lambda )$. Assume that $\lambda =1-10^{-4}$ then $\lambda ^{(10.000)}=0$. In this way we get a formal representation of heap argument preserving its intuitive content but avoiding its paradoxical character.

The liar paradox

(to be included)

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 $\vdash$ 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 $\otimes$ is the minimum operator $\wedge$. Moreover, the extension of the Generalization rule is obtained by assuming that if we prove $\alpha$ at degree $\lambda$ then we obtain $\forall x\alpha (x)$ at the same degree $\lambda$. Assume that D is the deduction operator in such a logic and that s is a fuzzy set of proper axioms. Then one proves that if $\alpha$ is a logcally true formula, then $D(s)(\alpha )=1$ and otherwise,

$D(s)(\alpha )=Sup\{s(\alpha _{1})\wedge ...\wedge s(\alpha _{n}):\alpha _{1},...,\alpha _{n}\vdash \alpha \}$.

Such a formula is a multivalued valuation of the (metalogical) claim:

"$\alpha$ is a consequence of the fuzzy subset s of axioms if there are formulas $\alpha _{1},...,\alpha _{n}$ in s able to prove $\alpha$"

(recall that the existential quantifier is interpreted by the supremum operator). It is evident that in such a case the vagueness originates from s, i.e., from the notion of "hypothesis". Moreover $s(\alpha )$ is not a truth degree but rather a degree of "preference" or "acceptability" for $\alpha$. 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

$s(\alpha )=1$ if $\alpha \in T$,

$s(\alpha )=0.8$ if $\alpha =CA$,

$s(\alpha )=0$ otherwise.

A simple calculation shows that:

$D(s)(\alpha )=1$ if we can prove $\alpha$ from T, otherwise

$D(s)(\alpha )=0.8$ if we can prove $\alpha$ from T + CA, otherwise

$D(s)(\alpha )=0$ .

Fuzziness in this case is not semantical in nature. Indeed, it is evident that the number $s(\alpha )$ is a degree of acceptability for $\alpha$ 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 postulates we accept. Thus, despite the fact that no vague predicate is considered in set theory, in the metalanguage it is reasonable to consider a vague predicate as "is acceptable" and to represent it by a suitable fuzzy subset s. Equivalently, we can interpret $s(\alpha )$ as the degree of preference for $\alpha$ 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)

Rational Pavelka logic

(to be included)

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 $\rightarrow$[0,1] of a set S is recursively enumerable if a recursive map h : S×N $\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.

Basic Fuzzy Logic

(to be included)

Is fuzzy logic a proper extension of classical logic ?

We can compare fuzzy logic and classical logic from two different 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 extension of classical logic. On the other hand fuzzy logic is defined by using elementary notions of mathematics. In such a sense it is a (small) chapter of classical logic. This means that, differently from intuitionistic logic, fuzzy logic is not an alternative to classical mathematics. Rather it is an attempt to extend its range to represent the vagueness phenomenon. In such a sense, the relationhsip between fuzzy and classical mathematics is similar in nature with the one between recursive and classical mathematics.

See also

• Fuzzy subalgebra
• Fuzzy associative matrix
• Fuzzy programming logic
• Fuzzy set
• Paradoxes
• Rough set
• Similarity logic
• Necessity logic
• MV-algebras
• Basic logic

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.
• 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.

• 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
• 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.
• 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.
• 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.