Formal fuzzy logic

Fuzzy logics: the semantics

In the tradition of multi-valued logic, we obtain a semantics for a fuzzy logic by interpreting the logical connectives by suitable operations in [0,1]. As an example, if $,\wedge ,\Rightarrow ,\neg$ are the logical connectives, then in Lukasievicz logic the corresponding operations are defined by the equations

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

respectively. More in general, usually one assumes that $\otimes$ is a continuous triangular norm, i.e. a continuous, associative, commutative, order preserving operation in [0,1] such that x $\otimes$ 1 = 1. Moreover, one defines → as the residuation operation, i.e. by setting x → y = sup{z | x $\otimes$ z ≤ y}. Finally, $\neg$ is interpreted by the function ~ defined by setting ~x = x → 0 (see Hájek 1998, Novák et al. 1999 and Gottwald 2005). Several authors consider also logical constants to denote the rational 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 by the notion of fuzzy interpretation.

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 I(h) : Dⁿ → 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 fuzzy relation I(r) : Dⁿ → [0,1] in D.

Then, the only difference with the classical notion of interpretation is that the interpretation of an 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. Given a fuzzy interpretation we can evaluate the formulas as follows where, given a term t, we denote by $I(t)$ the corresponding function we define as in classical logic.

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

Val(I, $r(t_{1},...,t_{p}),d_{1},...,d_{n})=I(r)(I(t_{1})(d_{1},...,d_{n}),...,I(t_{p})(d_{1},...,d_{n}))$

Val(I,α $\wedge$ β, $d_{1},...,d_{n}$ ) = Val(I,α, $d_{1},...,d_{n})\otimes$ Val(I,β, $d_{1},...,d_{n})$

Val(I,α $\Rightarrow$ β, $d_{1},...,d_{n}$ ) = Val(I,α, $d_{1},...,d_{n}$ ) → Val(I,β, $d_{1},...,d_{n})$

Val(I, $\neg$ α, $d_{1},...,d_{n})$ = ~(Val(I,α, $d_{1},...,d_{n}))$

Val(I, $\exists$ x_i α, $d_{1},...,d_{n}$ ) = sup_{d $\in$ D}Val(I,α, $d_{1},...,d_{i-1},d,d_{i+1},...,d_{n})$ .

As usual, if α is a closed formula, then its valuation does not depend on the elements $d_{1},...,d_{n}$ and we write Val(I,α) instead of Val(I,α, $d_{1},...,d_{n})$ . More in general, given any formula α, we denote by Val(I,α), the valuation of the universal closure of α. Now, in defining the basic semantical notions we can consider either the traditional approach inerithed from multi-valued logic or the Pavelka-style approach which was inspired to a basic paper of J. A. Goguen. In the sequel we denote by F the set of closed formulas of the considered first order language and we call a theory any subset T of F.

Definition (Traditional approach). One says that a formula α is valid in a fuzzy interpretation (D,I) if Val(I,α) = 1. The formula α is logically true if it is valid in every fuzzy interpretation. Let T be a theory, i.e. a set of sentences, and let α be a formula, then we say that (D,I) is a model of T is every formula in T is valid in (D,I). We write T $\models$ α if every model of T is also a model of α. In such a case we say that α is a logical consequence of T. The logical consequence operator is the map Lc : {0,1}^F → {0,1}^F defined by setting Lc(T) = {α $\in$ F: T $\models$ α}.

Such an approach perhaps is not sufficiently close to the spirit of fuzzy logic. In fact the aim of any logic is to eleborate (uncomplete) information and, in the case of fuzzy logic should be 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. Taking in account that for a large class of fuzzy semantics we can split it into the two constraints "the truth values of α is greather or equal to λ" and "the truth values of $\neg$ α is greather or equal to 1-μ", we consider the following definitions.

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

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

Then the meaning of a fuzzy theory s is that for every sentence α, the value s(α) is a constraint" on the unknown truth value of α. More precisely s(α) is a lower bound for such a value. Again, the value Lc(s)(α) is a "constraint" on the unknown truth value of α. As a matter of fact it is the better constraint we can find given the information s.

Note. We interpret a fuzzy theory s as a fuzzy subset of (proper) axioms. Now, the word "axiom" originates from the fact that formal logic was usually considered as a tool for mathematics. In the case of fuzzy logic, which is related with everyday experience, perhaps expressions as "hypothesis", "assumptions", "partial information", "postulate" are more adequate.

The evaluated syntax: approximate reasonings

In the traditional approach to fuzzy logic a deduction apparatus is devoted either to generate the set of logically true formulas (completeness theorem) or to calculate the logical consequence operator (extended completeness theorem). In both the cases, the resulting notions of compactness and effectivenes are not different from the classical ones. In Pavelka's approach a completeness theorem claims that the deduction apparatus is adequate to "calculate" the values of Lc(s) by an effective approximation process. We can obtain such an apparatus, as an example, by extending the Hilbert's approach as follows.

Definition. A fuzzy inference rule is a pair r = (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 joing-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.

The meaning of an inference rule r 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})$ .

Usually, sy(λ₁,...,λ_n) is a product like λ₁ $\otimes$ ... $\otimes$ λ_n. As an example, the fuzzy Modus Ponens is defined by assuming that the domain of sy is the set {(α, α→β: α,β are in F}, by setting sy(α, α→β) = β and by assuming that se(λ,μ) = λ $\otimes$ μ. This rule says that if we are able to prove α and α →β at degree λ and μ, respectively, then we can prove β at degree λ $\otimes$ μ. Likewise, the fuzzy $\land$ -introduction rule is a totally defined rule such that sy(α,β) = α $\land$ β and se(λ,μ) = λ $\otimes$ μ. This rule says that if we are able to prove α and β at degree λ and μ, respectively, then we can prove α $\land$ β at degree λ $\otimes$ μ.

Definition. A proof π of a formula α is a sequence $\alpha _{1},...,\alpha _{m}$ of formulas such that $\alpha _{m}$ = α, 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 an hypothesis 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 ≤ m denote by π(i) the proof $\alpha _{1},...,\alpha _{i}$ . Then the valuation Val(π,s) of π 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 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 _m} is assumed as an hypothesis

Val(π,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 se(Val(\pi(i_1),s),...,Val(\pi (i_n),s))} if there is a fuzzy rule 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 (sy,se)} such 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 \alpha_m = sy(\alpha_{i(1)},...,\alpha_{i(n)})} with i(1) < m,...,i(n) < m.

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

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

This formula defines an operator, the deduction operator, able to associate every fuzzy theory s with the fuzzy subset D(s) of formulas deduced from s.

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 Gerla 2001). 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

The heap paradox

To show an example of approximate 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" (n is a numeral to denote n). Then it is natural to assume the validity of the atomic formula Small(1) and, for every n, the validity of Small(n) → Small(n+1).

On the other hand from these formulas given any natural number n, by applying MP (Modus Ponens) rule several times we can prove that a heap with n stones is small. Indeed,

- from Small(1) and Small(1)→ Small(2) by MP we may state Small(2);

- from Small(2) and Small(2)→ Small(3) by MP we may state Small(3),

…

- from Small(n-1) and Small(n-1)→ 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 (1968/69), 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) → Small(n+1) are very close to the truth but not completely true, in general. We can try to "respect" this conviction by assigning to these formulas a truth value λ very close to 1 but different from 1. Then, for example, we can express the hypothesis of the heap paradox by the following fuzzy theory

Small(1) [to degree 1]

Small(2) [to degree 1]

...

Small(10.000) [to degree 1]

Small(10.000)→ Small(10.001) [to degree λ]

Small(10.001)→ Small(10.002) [to degree λ]

...

In accordance, the Heap Paradox argument can be restated as follows where we denote by λ⁽ⁿ⁾ the n-power of λ with respect 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 \otimes} .

Since Small(10.000) [to degree 1]

and Small(10.000)→ Small(10.001) [to degree λ]

we state Small(10.001) [to degree 1Failed 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} λ = λ⁽¹⁾]

since Small(10.001) [to degree λ]

and Small(10.001)→ Small(10.002) [to degree λ]

we state Small(10.002) [to 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 \otimes} λ = λ⁽²⁾]

. . .

since Small(10.000+n-1) [to degree λ^(n-1)]

and Small(10.000+n-1) → Small(10.000+n) [to degree λ]

we state Small(10.000+n) [to degree λ^(n-1)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} λ = λ⁽ⁿ⁾].

In particular, we can prove Small(10.000+10.000) at degree λ^(10.000). Now, this is not paradoxical. Indeed 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 \otimes} is the Lukasievicz triangular norm, then λ⁽ⁿ⁾ = max {nλ-n+1, 0}. As a consequence, we have that λ⁽ⁿ⁾ = 0 for every n ≥ 1/(1-λ). Assume that λ = 1-10^-4 then λ^(10.000) = 0. In this way we get a formal representation of heap argument preserving its intuitive content but avoiding its paradoxical character.

The falsity of the induction principle

In classic mathematics the induction principle is expressed by the schema A(1) → ((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 \forall} n(A(n) → A(n+1)) → 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 \forall} nA(n)) where A is a property defined in the set of natural numbers. The argument on the basis of heap paradox enables us to show an interesting fact:

"the induction principle is not valid in fuzzy logic, i.e. we cannot extend such a principle to vague properties".

In fact, assume that such a principle is satisfied at degree μ ≠ 0 and let λ ≠ 1 such 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 \otimes} μ ≠ 0. Also, consider a vague predicate A such that A(1) is valid, 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 \forall} n(A(n)) is false 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 \forall} n(A(n) → A(n+1)) is true to degree λ (as in the Heap Paradox). Then, by two application of MP 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 \forall} nA(n) to 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 \otimes} μ ≠ 0. This contradicts the fact 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 \forall} nA(n) is false.

Notice that in previous solution of the heap paradox the induction principles was avoided by assuming as an hypothesis the infinite set of ground formulas Small(p)→ Small(p+1), p = 1,2,... and not the 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 \forall} n Small(n)→Small(n+1). From such an infinite set, we cannot 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 \forall} n Small(n) in spite of the fact that, given any natural number p, we can prove Small(p).

The Poincaré paradox

The so called “paradox” of Poincaré refers to indistinguishability by emphasizing that, in spite of common intuition, this relation is not transitive. In fact, let d₁,…, d_m be a sequence of objects such that we are not able to distinguish d_i from d_i+1 and that, nevertheless, that we have no difficulty in distinguishing d₁ from d_m. Also, consider a first order language with a predicate symbol E to denote the indistinguishability relation and, for every i in N, with a constant c_i to denote d_i. Then it is natural to consider the theory defined by the following formulas:

E(c₁,c₂),…, E(c_i-1,c_i),..., 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 \neg} E(c₁,c_m), E(x,z)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 \and} E(z,y) 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} E(x,y).

From such a theory, by suitable applications of the 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 \and} -introduction rule, particularization and MP, we can prove E(c₁,c_m) and this contradicts the hypothesis 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 \neg} E(c₁,c_m). Consider a value λ very close to 1 and such that λ^(m-1) = 0. Then in fuzzy logic we can formalize Poincaré argument as follows:

Step 1.

Since E(c₁,c₂) [at degree λ]

and E(c₂,c₃) [at degree λ]

we can state E(c₁,c₂)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 \and} E(c₂,c₃) [at degree λ⁽²⁾].

Therefore, since E(c₁,c₂)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 \and} E(c₂,c₃)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} E(c₁,c₃) [at degree 1]

we can state E(c₁,c₃) [at degree λ⁽²⁾].

Step 2.

Since E(c₁,c₃) [at degree λ⁽²⁾]

and E(c₃,c₄) [at degree λ]

we can state E(c₁,c₃)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 \and} E(c₃,c₄) [at degree λ⁽³⁾]

Therefore, since E(c₁,c₃)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 \and} E(c₃,c₄)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} E(c₁,c₄) [at degree 1]

we can state E(c₁,c₄) [at degree λ⁽³⁾]

...

Step m-2.

Since E(c₁, c_m-1) [at degree λ^(m-2)]

and E(c_m-1,c_m) [at degree λ]

we can state E(c₁, c_m-1)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 \and} E(c_m-1, c_m) [at degree λ^(m-1)]

Therefore, since E(c₁, c_m-1)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 \and} E(c_m-1, c_m)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} E(c₁, c_m) [at degree 1]

we can state E(c₁, c_m) [at degree λ^(m-1)].

Thus, such a proof entails that the conclusion E(c₁,c_m) is true at least at degree λ^(m-1) = 0 (no information). This is not paradoxical.

The liar paradox

(to be included)

Fuzzy logics with a truth-functional semantics

Rational Pavelka logic

(to be included)

Basic Fuzzy Logic

(to be included)

Fuzzy logic with no semantics

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 la of logical axioms, by the MP-rule and the Generalization rule and 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 \vdash } the related consequence relation. Then a fuzzy deduction system is obtained by considering as fuzzy subset of logical axioms the characteristic function of la and as fuzzy inference rules the extension of MP obtained by assuming 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 \otimes } is the minimum operator 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 \wedge } . Moreover, an extension of the Generalization rule is obtained by assuming that if we prove α at degree λ then we obtain 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 \forall} xα(x) at the same degree λ. Assume that D is the deduction operator of such a fuzzy logic and that s is a fuzzy theory. Then D(s)(α) = 1 for every logically true formula α and, otherwise,

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(s)( \alpha) = Sup\{s(\alpha_1)\wedge ...\wedge s(\alpha_n) : \alpha_1,..., \alpha_n \vdash \alpha\}} .

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 if there are formulas 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} in s 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 } "

It is apparent that in such a case the vagueness originates from s, i.e., from the notion of "hypothesis". 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 s(\alpha) } is not a truth degree but rather a degree of "preference" or "acceptability" for 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} . 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(α) = 1 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 \in } 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 .

Fuzziness in this case is not semantical in nature. Indeed, it is evident that the number 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(\alpha) } is a degree of acceptability for 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 } 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 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(\alpha) } as the degree of preference for 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 } since the only reason we assign to CA the degree 0.8 instead of 1 is that we do not like to use CA.

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 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} 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 e 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)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} 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 λ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} μ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} 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

Effectiveness for fuzzy subsets

Notions as the ones of a "decidable subset" and a "recursively enumerable subset" are basic ones for classical logic. Then, the question of a suitable extension of such concepts for fuzzy logic 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 : 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 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 G. 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. 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

Denote by Lt the set of logically true formulas, then it is possible to prove that among the usual first order logics only Gödel logic has a recursively enumerable set of valid formulas. In the case of Lukasiewicz and product logic, for example, Lt 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, there are two possible answers to this criticism. The first one is suggested by the distinction between tautologies and general tautologies in accordance with Hájek’s ideas. We refer to the class of standard algebras, i.e. valuation structures whose domain is [0,1] and whose operations coincide with a given continuous t-norm 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} together with the related residuum 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} . The following definition works well both for propositional and first order calculus.

Definition. Given a standard algebra ([0,1], 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} , 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} ), a standard 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} –tautology is a formula assuming the truth value 1 for every interpretation in ([0,1], 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} , 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} ). A general 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} -tautology is a formula assuming the truth value 1 for every interpretation in a valuation structure belonging to the variety generated by ([0,1], 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} , 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} ).

Then the general tautologies of the main fuzzy logics refer to the MV-algebras (Lukasiewicz logic), Gödel algebras (Gödel logic), product algebras (product logic) and so on.

Theorem. For each continuous t-norm 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} , the set of general 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} -tautologies in first order logic is Σ₁-complete (and therefore recursively enumerable).

A different answer is necessary if we will consider Pavelka’s approach to fuzzy logic. Indeed, if we refer to Pavelka's approach to fuzzy logic and to the just exposed notion of effectiveness for fuzzy sets, then the following theorem holds true. It is intended that we refer to fuzzy logics in which a completeness theorem holds true and whose deduction apparatus 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 Lt 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.

Is fuzzy logic a proper extension of classical logic ?

Obviously, the question of the connection between classical and fuzzy logic arises. Now, we can consider this question from two points of views. Firstly, in a fuzzy logics with a truth-functional semantics the interpretation of the logical connectives 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 can be reduced to classical logic. From such a point of view, differently from intuitionistic logic, fuzzy logic does not expresses an alternative philosophy. Rather, it is an attempt to express the vagueness phenomena through classical mathematics and therefore through classical logic.

Bibliography

Biacino L., Gerla G., Ying M. S.: Approximate reasoning based on similarity, Math. Log. Quart., 46 (2000), 77-86.
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., Arithmetical complexity of fuzzy predicate logics – a survey, Soft Computing, 9(2005) 935-941.
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., Fuzzy logic: Mathematical Tools for Approximate Reasoning, Kluwer 2001 ISBN 0-7923-6941-6.
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.
Montagna F., On the predicate logic of continuous t-norm BL-algebras, Archive for Math. Logic, 44 (2005) 97-114.
Novák V., Perfilieva I, Mockor J., Mathematical Principles of Fuzzy Logic, Kluwer Academic Publishers, Dordrecht, (1999).
Novák V., Fuzzy logic with countable evaluated syntax revisited, Fuzzy Sets and Systems, 158 (2007) 929-936.
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.

Formal fuzzy logic

Contents

Fuzzy logics: the semantics

The evaluated syntax: approximate reasonings

Paradoxes

The heap paradox

The falsity of the induction principle

The Poincaré paradox

The liar paradox

Fuzzy logics with a truth-functional semantics

Rational Pavelka logic

Basic Fuzzy Logic

Fuzzy logic with no semantics

Necessity logic

Similarity logic

Effectiveness

Effectiveness for fuzzy subsets

Effectiveness for fuzzy logic

Is fuzzy logic a proper extension of classical logic ?

See also

Bibliography

Navigation menu

Formal fuzzy logic

Fuzzy logics: the semantics

The evaluated syntax: approximate reasonings

Paradoxes

The heap paradox

The falsity of the induction principle

The Poincaré paradox

The liar paradox

Fuzzy logics with a truth-functional semantics

Rational Pavelka logic

Basic Fuzzy Logic

Fuzzy logic with no semantics

Necessity logic

Similarity logic

Effectiveness

Effectiveness for fuzzy subsets

Effectiveness for fuzzy logic

Is fuzzy logic a proper extension of classical logic ?

See also

Bibliography

Navigation menu

Search