Difference between revisions of "Formal fuzzy logic"
m |
m |
||
Line 48: | Line 48: | ||
== Two approaches == | == Two approaches == | ||
− | There are two basic approaches to fuzzy logic. The first one, proposed by P. Hajek and by a large series of students, is strictly closed to the tradition of multi-valued logic. Indeed the entailment relation is a crisp one, equivalently, the logical consequence operator works on a given classical subset of hypotheses to give the related classical 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'' | + | There are two basic approaches to fuzzy logic. The first one, proposed by P. Hajek and by a large series of students, is strictly closed to the tradition of multi-valued logic. Indeed the entailment relation is a crisp one, equivalently, the logical consequence operator works on a given classical subset of hypotheses to give the related classical 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 and many authors and it is rather out of line with the tradition of multi-valued logic. Indeed, the entailment relation is a fuzzy relation. Equivalently, the logical consequence operator 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 === | === The ungraded approach === | ||
Line 78: | Line 78: | ||
=== The graded approach: approximate reasonings === | === The graded approach: approximate reasonings === | ||
− | The graded approach is perhaps closer to the spirit of fuzzy logic. In fact the aim of any logic is to | + | The graded approach is perhaps closer to the spirit of fuzzy logic. In fact the aim of any logic is to elaborate (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 such an interval constraint into the two lower bound constraints ''"the truth values of α is greater or equal to λ"'' and ''"the truth value of <math> \neg</math>α is greater or equal to 1-μ"'', the following definitions are proposed. |
Line 92: | Line 92: | ||
− | '''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 '' | + | '''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. |
Line 341: | Line 341: | ||
== Effectiveness == | == Effectiveness == | ||
− | A test to | + | A test to analyze the effectiveness in the ungraded approach is to refer to the set of tautologies. Now, since two entailment relations are defined, we have to consider two corresponding notions of tautology. |
Revision as of 08:33, 23 November 2008
To be Completed !! Template:TOC-right
Contents
Introduction
Fuzzy logic is a relatively new chapter of formal logic. Its aim is to represent predicates which are vague in nature as big, near, or similar (for example), and to formalize the reasonings involving these predicates. As an example, the aim of fuzzy logic is to manage pieces of information like
IF temperature IS very cold THEN stop fan
IF temperature IS cold THEN turn down fan
IF temperature IS normal THEN maintain level
IF temperature IS hot THEN speed up fan
where "very cold", "cold" ... "speed up" are all vague notions. The main tool for fuzzy logic is the notion of a fuzzy subset, proposed by L. A. Zadeh since 1965. Indeed, 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.
We can consider fuzzy logic as 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. Indeed, as in multi-valued logic, the starting point is a 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 intermediate truth values. The following is the main class of valuation structures (see Hájek 1998, Novák et al. 1999 and Gottwald 2005).
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) : D^{n} L in D.
Then, the only difference with classical logic is that the interpretation of an n-ary predicate symbol is an n-ary L-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, we denote by the corresponding function we define as in classical logic.
Definition. Let (D,I) be a fuzzy interpretation, then for every 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}) by induction as follows
- 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,α β,d_{1},...,d_{n}) = Val(I,α,d_{1},...,d_{n})ʘVal(I,β,d_{1},...,d_{n})
- Val(I,α → β, d_{1},...,d_{n}) = Val(I,α, d_{1},...,d_{n}) → Val(I,β,d_{1},...,d_{n})
- Val(I, x_{i} α,d_{1},...,d_{n}) = Inf_{ }d є D Val(I,α,d_{1},...,d_{i-1},d,d_{i+1},...,d_{n}).
In the case there is a propositional constant c^{*} corresponding to a truth value c, we set
- Val(I, c^{*},d_{1},...,d_{n}) = 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_{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 α.
Two approaches
There are two basic approaches to fuzzy logic. The first one, proposed by P. Hajek and by a large series of students, is strictly closed to the tradition of multi-valued logic. Indeed the entailment relation is a crisp one, equivalently, the logical consequence operator works on a given classical subset of hypotheses to give the related classical 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 and many authors and it is rather out of line with the tradition of multi-valued logic. Indeed, the entailment relation is a fuzzy relation. Equivalently, the logical consequence operator 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 (L, ʘ, →, 0, 1) be a fixed standard algebra. Then we say that a fuzzy interpretation (D,I) is a model of a formula α 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 is a model of α.
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 almost all the fuzzy logics (for example Łukasievicz logic) the entailment relation _{ʘ} is not compact. This entails that these logic 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 almost all the fuzzy logics (for example Łukasievicz logic) the entailment relation _{Varl(ʘ)} is compact. This is in accordance with the fact that, once we refer to this relation, these logics are axiomatizable.
A criticism for such a solution is that in Varl(ʘ) there are unnatural valuation structures. For example, structures with infinitesimal truth values. This is rather far from the uman intuition. Moreover, 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 unsafe interpretations.
The graded approach: approximate reasonings
The graded approach is perhaps closer to the spirit of fuzzy logic. In fact the aim of any logic is to elaborate (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 such an interval constraint into the two lower bound constraints "the truth values of α is greater or equal to λ" and "the truth value of α is greater or equal to 1-μ", the following definitions are proposed.
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 define a graded entailment relation by setting s ^{λ} α provided that λ = Inf{Val(I,α) : (D,I) s}. Such a definition is in accordance with the fact that the information carried on by 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.
In the graded approach we can obtain a deduction apparatus by extending the 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.
The meaning of an inference rule r is:
- - IF we are able to prove α_{1},...,α_{n} at degree λ_{1},...,λ_{n}, respectively
- - AND we can apply syn to α_{1},...,α_{n}
- - THEN we can prove syn(α_{1},...,α_{n}) at degree sem(λ_{1},...,λ_{n}).
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 α and α → β at degree λ and μ, respectively, 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
also 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(π(i_{1}),s),...,Val(π(i_{n}),s)) if there is a fuzzy rule (syn,sem) such that α_{m} = syn(α_{i1},...,α_{in}) 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 the following definition.
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.
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 Novak 2007, the following axiomatizability theorem holds true.
Proposition. In the graded approach Łukasiewicz first order logic is axiomatizable.
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 λ^{(n)} the n-power of λ with respect to ʘ.
- Since Small(10.000) [to degree 1]
- and Small(10.000)→ Small(10.001) [to degree λ]
- we state Small(10.001) [to degree 1ʘλ = λ^{(1)}]
- since Small(10.001) [to degree λ]
- and Small(10.001)→ Small(10.002) [to degree λ]
- we state Small(10.002) [to degree λʘλ = λ^{(2) }]
- . . .
- 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)}ʘλ = λ^{(n)}].
In particular, we can prove Small(10.000+10.000) at degree λ^{(10.000) }. Now, this is not paradoxical. Indeed if is Łukasievicz triangular norm, then λ^{(n)} = max {nλ-n+1, 0}. As a consequence, we have that λ^{(n)} = 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 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 the formula
- Small(1) → ((n(Small(n) → Small(n+1)) → n Small(n))
is satisfied at degree μ ≠ 0 and let λ ≠ 1 such that λʘμ ≠ 0. Then, by two applications of MP we can prove n Small(n) to degree λʘμ ≠ 0. This contradicts the fact that n Small(n) is false.
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_{1},…, 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_{1} 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_{1},c_{2}),…, E(c_{i-1},c_{i}),..., E(c_{1},c_{m}), E(x,z)E(z,y) E(x,y).
From such a theory, by suitable applications of the -introduction rule, particularization and MP, we can prove E(c_{1},c_{m}) and this contradicts the hypothesis E(c_{1},c_{m}). Consider a value λ very close to 1 and such that λ^{(m-1)} = 0. Then in fuzzy logic we can formalize Poincaré's argument as follows:
Step 1.
- Since E(c_{1},c_{2}) [at degree λ]
- and E(c_{2},c_{3}) [at degree λ]
- we can state E(c_{1},c_{2})E(c_{2},c_{3}) [at degree λ^{(2)}].
- Therefore, since
E(c_{1},c_{2})E(c_{2},c_{3}) E(c_{1},c_{3}) [at degree 1]
- we can state
E(c_{1},c_{3}) [at degree λ^{(2)}].
Step 2.
- Since E(c_{1},c_{3}) [at degree λ^{(2)}]
- and E(c_{3},c_{4}) [at degree λ]
- we can state
- E(c_{1},c_{3})E(c_{3},c_{4}) [at degree λ^{(3)}]
- Therefore, since
- E(c_{1},c_{3})E(c_{3},c_{4}) E(c_{1},c_{4}) [at degree 1]
- we can state E(c_{1},c_{4}) [at degree λ^{(3)}]
- ...
Step m-2.
- Since E(c_{1}, c_{m-1}) [at degree λ^{(m-2)}]
- and E(c_{m-1},c_{m}) [at degree λ]
- we can state E(c_{1}, c_{m-1})E(c_{m-1}, c_{m}) [at degree λ^{(m-1)}]
- Therefore, since E(c_{1}, c_{m-1})E(c_{m-1}, c_{m})E(c_{1}, c_{m}) [at degree 1]
- we can state E(c_{1}, c_{m}) [at degree λ^{(m-1)}].
Thus, such a proof entails that the conclusion E(c_{1},c_{m}) is true at least at degree λ^{(m-1)} = 0 (no information). This is not paradoxical.
The Liar paradox
In the Liar paradox one considers a sentence S that asserts its own untruth. More precisely, if S* is a name for such a sentence, then such a sentence satisfies
S ↔ ¬True(S*).
If we admit, in accordance with Tarski's point of view, the equivalence
True(S*) ↔ S,
we can infer
(*) True(S*) ↔ ¬True(S*).
This is a contradiction in classical logic. In multi-valued logic (and therefore in fuzzy logic) such a conclusion is not paradoxical at all since it is sufficient to admit that the truth value of True(S*) is 0.5 (see Zadeh 1979). Indeed in fuzzy logic usually one interprets the negation with the function 1-x and therefore in such a case both the sentences True(S*) and ¬True(S*) assume the value 0.5. In accordance the formula True(S*) ↔ ¬True(S*) holds true.
It is well known that the proof of Gödel's incompleteness theorem uses a self-referential statement which is similar to the one in the Liar paradox. Namely, instead of True(S*) one considers Theorem(S*). A depth analysis of such a such a sentence in the framework of fuzzy logic and related with Peano arithmetic can be find in Hájek et al. 2000.
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
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 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 ʘ is the minimum operator . Moreover, an extension of the Generalization Rule is obtained by assuming that if we prove α at degree λ then we obtain 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,
- D(s)(α) = Sup{s(α_{1})s(α_{n}) : α_{1},..., α_{n} α}.
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 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 α є 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 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 give a suitable notion of effectiveness for fuzzy sets. 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.
See also
- [[Fuzzy Control
- Fuzzy subalgebra
- Fuzzy associative matrix
- Fuzzy Logic Programming
- Fuzzy set
- Paradoxes
- Rough set
- MV-algebras
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., Fuzzy logic and arithmetical hierarchy, Fuzzy Sets and Systems, 3 (1995) 359-363.
- Hájek P., Metamathematics of fuzzy logic. Kluwer 1998.
- Hájek P., Paris J. B., Shepherdson J.C., The Liar Paradox and Fuzzy Logic, Journal of Symbolic Logic, 65 (2000) 339-346.
- Hájek P., Novák V., The sorites paradox and fuzzy logic, Internat. J. General Systems, 32 (2003) 373-383.
- Hájek P., Arithmetical complexity of fuzzy predicate logics – a survey, Soft Computing, 9 (2005) 935-941.
- 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.
- Pavelka, On fuzzy logic, I-III, Zeitschr. Math. Logik Grundl. Math., 25 (1979) 45-52, 119-134, 447-464.
- Santos E. S., Fuzzy algorithms, Inform. and Control, 17 (1970), 326-339.
- 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.
- Zadeh L.A., Liar’s paradox and truth-qualiﬁcation principle”. ERL Memo M79/34, 1979.
- Zimmermann H., Fuzzy Set Theory and its Applications (2001), ISBN 0-7923-7435-5.