Fuzzy Sets and Systems 161 (2010) 1926 – 1940 www.elsevier.com/locate/fss
Paraconsistent semantics for Pavelka style fuzzy sentential logic夡 E. Turunena,∗ , M. Öztürkb , A. Tsoukiásc a Tampere University of Technology, P.O. Box 553, 33101 Tampere, Finland b CRIL, Univ. d’Artois, F-62307 Lens, France c LAMSADE-CNRS, Univ. Paris Dauphine, 75775 Paris Cedex 16, France
Received 20 July 2009; received in revised form 28 December 2009; accepted 30 December 2009 Available online 7 January 2010
Abstract The root of this work is on the one hand in Belnap’s four valued paraconsistent logic, and on the other hand on Pavelka’s papers further developed by Turunen. We do not introduce a new non-classical logic but, based on a related study of Perny and Tsoukiás, we introduce paraconsistent semantics of Pavelka style fuzzy sentential logic. Restricted to Łukasiewicz t-norm, our approach and the approach of Perny and Tsoukiás partly overlap; the main difference lies in the interpretation of the logical connectives implication and negation. The essential mathematical tool proved in this paper is a one–one correspondence between evidence couples and evidence matrices that holds in all injective MV-algebras. Evidence couples associate to each atomic formula p two values a and b that can be interpreted as the degrees of pros and cons for p, respectively. Four values t, f, k, u, interpreted as the degrees of the truth, falsehood, contradiction and unknownness of p, respectively, can then be calculated by means of a and b and finally, the degrees of the truth, falsehood, contradiction and unknownness of any well formed formula are available. The obtained logic is Pavelka style fuzzy sentential logic. In such an approach truth and falsehood are not each others complements. Moreover, we solve some open problems presented by Perny and Tsoukiás. © 2010 Elsevier B.V. All rights reserved. Keywords: Mathematical fuzzy logic; Paraconsistent sentential logic; MV-algebra
1. Introduction Quoting from Stanford Encyclopedia of Philosophy [16]. The contemporary logical orthodoxy has it that, from contradictory premises, anything can be inferred. To be more precise, let be a relation of logical consequence, defined either semantically or proof-theoretically. Call explosive if it validates {A, ¬A} B for every A and B (ex contradictione quodlibet). The contemporary orthodoxy, i.e. classical logic, is explosive, but also some ‘non-classical’ logics such as intuitionist logic and most other standard logics are explosive. The major motivation behind paraconsistent logic is to challenge this orthodoxy. A logical consequence relation, , is said to be paraconsistent if it is not explosive. Thus, if is paraconsistent, then even if we are in certain circumstances where the available information is inconsistent, the inference relation does not explode into triviality. 夡 This paper is part of research project COST Action I0602 Algorithmic Decision Theory. ∗ Corresponding author.
E-mail address: esko.turunen@tut.fi (E. Turunen). 0165-0114/$ - see front matter © 2010 Elsevier B.V. All rights reserved. doi:10.1016/j.fss.2009.12.017
E. Turunen et al. / Fuzzy Sets and Systems 161 (2010) 1926 – 1940
1927
Thus, paraconsistent logic accommodates inconsistency in a sensible manner that treats inconsistent information as informative. In Belnap’s paraconsistent logic [2], four possible values associated with atomic formulas are interpreted as told only True, told only False, both told True and told False and neither told True nor told False, respectively. However, we call them for simplicity true, false, contradictory and unknown: if there is evidence for and no evidence against , then obtains the value true and if there is no evidence for and evidence against , then obtains the value false. A value contradictory corresponds to a situation where there is simultaneously evidence for and against and, finally, is labeled by value unknown if there is no evidence for nor evidence against . More formally, the values are associated with ordered couples T = 1, 0 , F = 0, 1 , K = 1, 1 and U = 0, 0 , respectively. In [19] Tsoukiás introduced a first order extension of Belnap’s logic (named DDT) most importantly because the corresponding algebra of Belnap’s original logic is not a Boolean algebra, while the extension is. Indeed, in that paper it was introduced and defined the missing connectives in order to obtain a Boolean algebra. Moreover, it was explained why we get such a structure. Among others it was shown that negation, which was reintroduced in [19] in order to recover some well known tautologies in reasoning, is not a complementation. In [14,11], a continuous valued extension of DDT logic was studied. The authors imposed reasonable conditions this continuous valued extension should obey and, after a careful analysis, they came to the conclusion that the graded values are to be computed via t( ) = min{a, 1 − b},
(1)
k( ) = max{a + b − 1, 0},
(2)
u( ) = max{1 − a − b, 0},
(3)
f ( ) = min{1 − a, b},
(4)
where an ordered couple a, b , called evidence couple, is given. The intuitive meaning of a and b is the degree of evidence for a statement and against , respectively. Moreover, the set of 2 × 2 evidence matrices of a form f ( ) k( ) u( ) t( ) is denoted by M. The values f ( ), k( ), u( ) and t( ) are values on the real unit interval [0, 1] such that f ( ) + k( ) + u( )+t( ) = 1. Their intuitive meaning is f ( ) = falsehood, k( ) = contradictory, u( ) = unknown and t( ) = tr uth of the statement . One of the most important features of paraconsistent logic is that truth and falsehood are not each others complements. In [14] it is shown how such a fuzzy version of Belnap’s logic can be applied in preference modeling. In [22] we show how paraconsistency is related to data mining. However, in [14] the authors listed some open problems and future work including: • a missing complete truth calculus for logics conceived as fuzzy extensions of four valued paraconsistent logics; • a more thorough investigation of valued sets and valued relations (when the valuation domain is M) and their potential use in the context of preference modeling. In this paper we accept the challenge to answer some of these questions. We show that, instead of a Boolean structure, the valuation domain M should be equipped with a more general algebraic structure called injective MV-algebra. The standard Łukasiewicz structure is an example of an injective MV-algebra. This associates fuzzy extensions of four valued paraconsistent logics with Pavelka style fuzzy sentential logic [13], called fuzzy logic with evaluated syntax in [10] as syntax in this logic is also generalized so that axioms can be not fully true and, therefore, giving rise to concepts such as fuzzy set of axioms, provability degree, degree of theoremhood and evaluated proof. As a consequence a complete truth calculus is obtained. Indeed, our basic observation is that the algebraic operations in (1)–(4) are expressible only by the Łukasiewicz t-norm and the corresponding residuum, i.e. in the standard Łukasiewicz structure. This fact was implicitly shown in the analysis done in [14,11]. Thus, if we would start with some other t-norm conjunction and an involutive negation then the reasonable conditions a continuous valued extension of paraconsistent logic should obey would cease to hold.
1928
E. Turunen et al. / Fuzzy Sets and Systems 161 (2010) 1926 – 1940
Pavelka’s ideas were extended to interval [0, 1]-valued first order fuzzy logic with evaluated syntax by Novák, for a complete discourse, see [10]. Turunen generalized Pavelka’s ideas to another direction by introducing a Pavelka style fuzzy sentential logic with truth values in an injective MV-algebra, thus generalizing [0, 1]-valued logic. Indeed, in [20] it is proved that Pavelka style fuzzy sentential logic is a complete logic in a sense that if the truth value set L forms an injective MV-algebra L, then the set of a-tautologies and the set of a-provable formulae coincide for all a ∈ L. For a complete description, see the textbook [21, Chapter 3]. However, such a completeness theorem of a general injective MV-algebra valued first order logic is an open problem. We therefore consider the problem that, given a set (of evidence values) which is an injective MV-algebra, is it possible to transfer an injective MV-structure to the set M, too. The answer turns out to be affirmative, consequently, the corresponding paraconsistent sentential logic is Pavelka style fuzzy logic with new semantics. Thus, a rich semantics and syntax is available. For example, Łukasiewicz tautologies as well as Intuitionistic tautologies can be expressed in the framework of this logic. This follows by the fact that we have two sorts of logical connectives conjunction, disjunction, implication and negation interpreted either by the monoidal operations , , −→,∗ or by the lattice operations ∧, ∨, ⇒, , respectively (however, neither nor ∗ is a lattice complementation). Besides, there are many other logical connectives available. For other studies related to Belnap’s logic we mention the following. Arieli and Avron [1] developed a logical system based on a class of bilattices (cf. [5]), called logical bilattices, and provided a Gentzen-style calculus for it. This logic is, in essence, an extension of Belnap’s four-valued logic to the standard language of bilattices, but differs from it for some interesting properties. However, our approach differs from that of Arieli and Avron [1]. Other studies on Belnap’s logic are investigated by Shramko and Wansing [17,18], Rivieccio [15] and Odintsov [12]. In Odintsov’s paper functions corresponding to f ( ), k( ), u( ), t( ) are functions from Belnap’s four values into the set of classical truth values. Recently Dubois [4] published a critical study on Belnap’s approach. According to Dubois, the main difficulty lies in the confusion between truth-values and information states. We emphasize that we study paraconsistent logic from a purely formal point of view without any deeper philosophical interpretation. Possible applications of our approach are discussed at the end of the paper. 2. Algebraic preliminaries We start by recalling some basic definitions and properties of MV-algebras; all detail can be found in [9,21]. We also prove some new results that we will utilize later. An MV-algebra L = L , ⊕,∗ , 0 is a structure such that L , ⊕, 0 is a commutative monoid, i.e. x ⊕ y = y ⊕ x,
(5)
x ⊕ (y ⊕ z) = (x ⊕ y) ⊕ z,
(6)
x ⊕0= x
(7)
holds for all elements x, y, z ∈ L and, moreover, x ∗∗ = x, ∗
(8) ∗
x ⊕0 =0 , (x ∗ ⊕ y)∗ ⊕ y = (y ∗ ⊕ x)∗ ⊕ x.
(9) (10)
Denote x y = (x ∗ ⊕ y ∗ )∗ and 1 = 0∗ . Then L , , 1 is another commutative monoid and hence x y = y x,
(11)
x (y z) = (x y) z,
(12)
x 1= x
(13)
holds for all elements x, y, z ∈ L. It is obvious that x ⊕ y = (x ∗ y ∗ )∗ , thus the triple ⊕,∗ , satisfies De Morgan laws. A partial order on the set L is introduced by x≤y iff x ∗ ⊕ y = 1 iff x y ∗ = 0.
(14)
E. Turunen et al. / Fuzzy Sets and Systems 161 (2010) 1926 – 1940
1929
By setting x ∨ y = (x ∗ ⊕ y)∗ ⊕ y, ∗
∗ ∗
(15) ∗
∗
x ∧ y = (x ∨ y ) [= (x y) y]
(16)
for all x, y, z ∈ L the structure L , ∧, ∨ is a lattice. Moreover, x ∨ y = (x ∗ ∧ y ∗ )∗ holds and therefore the triple ∧,∗ , ∨ , too, satisfies the De Morgan laws. However, the unary operation ∗ called complementation is not a lattice complementation. By stipulating x → y = x∗ ⊕ y
(17)
the structure L , ≤∧, ∨, , →, 0, 1 is a residuated lattice with the bottom and top elements 0, 1, respectively. In particular, a residuation x y≤z iff x≤y → z
(18)
holds for all x, y, z ∈ L. The couple , → is an adjoint couple. Notice that the lattice operations on L can be expressed also via x ∨ y = (x → y) → y,
(19)
x ∧ y = x (x → y).
(20)
The standard example of an MV-algebra is the standard Łukasiewicz structure L; the underlying set is the real unit interval [0, 1] equipped with the usual order and, for each x, y ∈ [0, 1], x ⊕ y = min{x + y, 1},
(21)
x ∗ = 1 − x.
(22)
Moreover, x y = max{0, x + y − 1},
(23)
x ∨ y = max{x, y},
(24)
x ∧ y = min{x, y},
(25)
x → y = min{1, 1 − x + y},
(26)
x y ∗ = max{x − y, 0}.
(27)
For any natural number m≥2, a finite chain 0 < 1/m < · · · < (m − 1)/m < 1 can be equipped with MV-algebra operations by defining n/m ⊕ k/m = min{(n + k)/m, 1} and (n/m)∗ = (m − n)/m. Finally, a structure L ∩ Q with the Łukasiewicz operations is an example of a countable MV-algebra called rational Łukasiewicz structure. All these examples are linear MV-algebras, i.e. the corresponding order is a total order. Moreover, they are MV-subalgebras of the structure L. A Boolean algebra is an MV-algebra such that the monoidal operations ⊕, and the lattice operations ∨, ∧ coincide, respectively. An MV-algebra L is called complete if {ai |i ∈ }, {ai |i ∈ } ∈ L for any subset {ai : i ∈ } ⊆ L. Complete MV-algebras are infinitely distributive, that is, they satisfy x∧ yi = (x ∧ yi ), x ∨ yi = (x ∨ yi ), (28) i∈
i∈
i∈
i∈
for any x ∈ L, {yi |i ∈ } ⊆ L. Thus, in a complete MV-algebra we can define another adjoint couple ∧, ⇒ , where the operation ⇒ is defined via x⇒y= {z|x ∧ z≤y}. (29) In particular, x = x ⇒ 0 defines another complementation (called weak complementation) in complete MV-algebras. However, weak complementation needs not to be lattice complementation. A Heyting algebra H is a bounded lattice
1930
E. Turunen et al. / Fuzzy Sets and Systems 161 (2010) 1926 – 1940
such that for all a, b ∈ H there is a greatest element x in H such that a ∧ x≤b. Thus, to any complete MV-algebra L , ⊕,∗ , 0 there is an associated Heyting algebra L , ∧, , 0, 1 with an adjoint couple ∧, ⇒ . The Łukasiewicz structure and all finite MV-algebras are complete as well as the direct product of complete MV-algebras is a complete MV-algebra. However, the rational Łukasiewicz structure is not complete. A fundamental fact demonstrated by Chang (cf. [3]) is that the standard Łukasiewicz structure generates as a quasivariety the class of all MV algebras. Thus, to prove that a quasi-equation holds in all MV-algebras, it is enough to show that it holds in the standard Łukasiewicz structure L. This fact is used in proving the following three propositions. Proposition 1. In an MV-algebra L the following holds for all x, y ∈ L: (x y) ∧ (x ∗ y ∗ ) = 0,
(30)
(x ∗ ∧ y) ⊕ (x y) ⊕ (x ∗ y ∗ ) ⊕ (x ∧ y ∗ ) = 1.
(31)
Proof. Consider the Łukasiewicz structure L. Let x, y ∈ [0, 1]. If x y > 0 then x + y − 1 > 0, thus 1 − x − y < 0, hence (1 − x) + (1 − y) − 1 < 0 and therefore x ∗ y ∗ = 0, so (30) holds in L and, consequently in all MV-algebras. To show that (31) holds in L, assume first that x y = 0. Then, by residuation (18), x≤y ∗ , y≤x ∗ and (x ∗ ∧ y) ⊕ (x y) ⊕ (x ∗ y ∗ ) ⊕ (x ∧ y ∗ ) = y ⊕ 0 ⊕ (x ⊕ y)∗ ⊕ x = 1. Similarly, if x ∗ y ∗ = 0 then x ∗ ≤y, y ∗ ≤x and (x ∗ ∧ y) ⊕ (x y) ⊕ (x ∗ y ∗ ) ⊕ (x ∧ y ∗ ) = x ∗ ⊕ (x ∗ ⊕ y ∗ )∗ ⊕ 0 ⊕ y ∗ = 1. The proof is complete. Proposition 2. Assume x, y, a, b are elements of an MV-algebra L such that the following system of equations holds: ⎧ ∗ x ∧ y = a ∗ ∧ b, ⎪ ⎪ ⎪ ⎪ ⎨ x y = a b, ( A) ⎪ x ∗ y ∗ = a ∗ b∗ , ⎪ ⎪ ⎪ ⎩ x ∧ y ∗ = a ∧ b∗ . Then x = a and y = b. Proof. Since the standard MV-algebra L generates the variety of MV-algebras as a quasi-variety, it is enough to show that Proposition 2 holds in that structure. Assume therefore that x, y, a, b ∈ [0, 1] and (A) holds. If x y = a b = 0 then x≤y ∗ , a≤b∗ and x = x ∧ y ∗ = a ∧ b∗ = a. Moreover, y≤x ∗ , b≤a ∗ and y = x ∗ ∧ y = a ∗ ∧ b = b. On the other hand if x y = a b > 0 then, by Proposition 1, x ∗ y ∗ = a ∗ b∗ = 0 and therefore x ∗ ≤y, a ∗ ≤b, y ∗ ≤x, b∗ ≤a. In a symmetric manner this implies x ∗ = a ∗ and y ∗ = b∗ and therefore x = a and y = b. The proof is complete. Proposition 3. Assume x, y are elements of an MV-algebra L such that ⎧ ∗ x ∧ y = f, ⎪ ⎪ ⎪ ⎪ ⎨ x y = k, (B) ⎪ x ∗ y ∗ = u, ⎪ ⎪ ⎪ ⎩ x ∧ y ∗ = t. Then (C) x = t ⊕ k, y = f ⊕ k and (D) x = ( f ⊕ u)∗ , y = (t ⊕ u)∗ . Proof. Again it is enough to show that Proposition 3 holds in the structure L. Assume therefore that x, y ∈ [0, 1] and (B) holds. By (30), either k = 0 or u = 0.
E. Turunen et al. / Fuzzy Sets and Systems 161 (2010) 1926 – 1940
1931
Assume k = 0. Then x y = 0 and therefore x≤y ∗ , hence x = x ∧ y ∗ = t = t ⊕ k. Similarly y≤x ∗ , hence y = y ∧ x ∗ = f = f ⊕ k, consequently (C) holds. Moreover, x ∗ = x ∗ ∨ y = (x ⊕ y)∗ ⊕ y = (x ∗ y ∗ ) ⊕ y = u ⊕ f, y ∗ = y ∗ ∨ x = (y ⊕ x)∗ ⊕ x = (y ∗ x ∗ ) ⊕ x = u ⊕ t, and (D) follows. If k > 0 then u = 0 and (C) and (D) hold by symmetric reasoning. The proof is complete. Propositions 2 and 3 put ordered couples x, y and values f, k, u, t defined by (B) into a one–one correspondence. Definition 4. A complete MV-algebra L is injective (cf. [6]) if, for any a ∈ L and any natural number n, there is an element b ∈ L, called the n-divisor of a, such that nb = b ⊕ ¡ ¡ ¡ ⊕ b = a and (a ∗ ⊕ (n − 1)b)∗ = b. n times
All n-divisors are unique (cf. [8]). The Ĺ ukasiewicz structure L is an injective MV-algebra, moreover, a finite product of injective MV-algebras is an injective MV-algebra (cf. [21]). 3. Evidence couples and evidence matrices Let L = L , ⊕,∗ , 0 be an MV-algebra. The product set L Ă— L can be equipped with an MV-structure by setting a, b ⊗ c, d = a ⊕ c, b d , ⊼
∗
(32)
∗
a, b = a , b ,
(33)
0 = 0, 1
(34)
for each ordered couple a, b , c, d ∈ L Ă— L. Indeed, the axioms (5)–(9) hold trivially and, to prove that the axiom (10) holds, it is enough to realize that ( a, b ⊼ ⊗ c, d )⊼ ⊗ c, d = a ∨ c, b ∧ d = c ∨ a, d ∧ b = ( c, d ⊼ ⊗ a, b )⊼ ⊗ a, b . It is routine to verify that the order on L Ă— L is defined via a, b ≤ c, d if and only if a≤c, d≤b,
(35)
the lattice operation by a, b ∨ c, d = a ∨ c, b ∧ d ,
(36)
a, b ∧ c, d = a ∧ c, b ∨ d ,
(37)
and an adjoint couple , by a, b c, d = a c, b ⊕ d ,
(38)
a, b c, d = a → c, (d → b)∗ . Notice that a → c =
a∗
⊕ c and (d →
b)∗
(39) =
(d ∗
⊕ b)∗
=d
b∗
=
b∗
d.
Definition 5. Given an MV-algebra L, denote the structure described via (32)–(39) by L EC and call it the MV-algebra of evidence couples induced by L. Definition 6. Given an MV-algebra L, denote a ∗ ∧ b a b M= a, b ∈ L Ă— L a ∗ b∗ a ∧ b∗ and call it the set of evidence matrices induced by evidence couples.
1932
E. Turunen et al. / Fuzzy Sets and Systems 161 (2010) 1926 – 1940
By Propositions 2 and 3 we have Theorem 7. There is a one–to–one correspondence between L × L and M: if A, B ∈ M are two evidence matrices induced by evidence couples a, b and x, y , respectively, then A = B if and only if a = x and b = y. The MV-structure descends from L EC to M in a natural way: if A, B ∈ M are two evidence matrices induced by evidence couples a, b and x, y , respectively, then the evidence couple a ⊕ x, b y induces an evidence matrix (a ⊕ x)∗ ∧ (b y) (a ⊕ x) (b y) C= . (a ⊕ x)∗ (b y)∗ (a ⊕ x) ∧ (b y)∗ Thus, we may define a binary operation on M by a∗ ∧ b a b x ∗ ∧ y x y = C. a ∗ b∗ a ∧ b∗ x ∗ y∗ x ∧ y∗ Similarly, if A ∈ M is an evidence matrix induced by an evidence couple a, b , then the evidence couple a ∗ , b∗ induces an evidence matrix a ∧ b∗ a ∗ b∗ ⊥ . A = a b a∗ ∧ b In particular, the evidence couple 0, 1 induces the following evidence matrix: 0∗ ∧ 1 0 1 1 0 F= = . 0∗ 1∗ 0 ∧ 1∗ 0 0 Moreover, it is easy to verify that the evidence couples 1, 0 , 1, 1 and 0, 0 induce the following evidence matrices: 0 0 0 1 0 0 T = , K = , U= , 0 1 0 0 1 0 respectively. Theorem 8. Let L be an MV-algebra. The structure M = M, the MV-algebra of evidence matrices).
⊥ , , F as defined above is an MV-algebra (called
Proof. The MV-axioms (5)–(9) are straightforward to verify and the axiom (10) follows by the fact that Eqs. (10) and (16) hold in L as b ∧ y = y ∧ b. This completes the proof. Assume A=
a∗ ∧ b
a b
a ∗ b∗ a ∧ b∗
,
B=
x∗ ∧ y
x y
x ∗ y∗ x ∧ y∗
∈ M.
Then it is obvious that the lattice operations ∧, ∨, the monoidal operation defined via (a ∧ x)∗ ∧ (b ∨ y) (a ∧ x) (b ∨ y) , A∧B= (a ∧ x)∗ (b ∨ y)∗ (a ∧ x) ∧ (b ∨ y)∗ (a ∨ x)∗ ∧ (b ∧ y) (a ∨ x) (b ∧ y) A∨B= , (a ∨ x)∗ (b ∧ y)∗ (a ∨ x) ∧ (b ∧ y)∗
and the residual operation −→ are
E. Turunen et al. / Fuzzy Sets and Systems 161 (2010) 1926 – 1940
A
B=
A −→ B =
(a x)∗ ∧ (b ⊕ y)
(a x) (b ⊕ y)
(a x)∗ (b ⊕ y)∗ (a x) ∧ (b ⊕ y)∗
,
(a → x)∗ ∧ (y → b)∗ (a → x) (y → b)∗ (a → x)∗ (y → b)
1933
(a → x) ∧ (y → b)
.
If the original MV-algebra L is complete, then the structure M is a complete MV-algebra, too, and suprema and infima are defined by evidence couples { ai , bi } = ai , bi , { ai , bi } = ai , bi . i∈
i∈
i∈
i∈
i∈
i∈
Thus, we may define another residual operation ⇒ on M via (a ⇒ x)∗ ∧ (b∗ ⇒ y ∗ )∗ (a ⇒ x) (b∗ ⇒ y ∗ )∗ . A⇒B= (a ⇒ x)∗ (b∗ ⇒ y ∗ ) (a ⇒ x) ∧ (b∗ ⇒ y ∗ ) To verify this last claim, assume a, b ∧ x, y ≤ c, d in L EC , which is equivalent to a ∧ x≤c and d≤b ∨ y, that is, a≤x ⇒ c and (b ∨ y)∗ = b∗ ∧ y ∗ ≤d ∗ , i.e. a≤x ⇒ c and b∗ ≤y ∗ ⇒ d ∗ , or equivalently, a≤x ⇒ c and (y ∗ ⇒ d ∗ )∗ ≤b, i.e. a, b ≤ x ⇒ c, (y ∗ ⇒ d ∗ )∗ in L EC . Therefore, if A is induced by a, b and B is induced by x, y then the evidence matrix A ⇒ B is induced by the evidence couple a ⇒ x, (b∗ ⇒ y ∗ )∗ . In particular, the weak complementation on M is defined via A = A ⇒ F and induced by 1, 0 if a 0, 0 if a 1, 1 if a 0, 1 if a
= 0, b = 1, then > 0, b = 1, then = 0, b < 1, then > 0, b < 1, then
A A A A
= T, = U, = K, = F.
The matrices F, T, K , U correspond to Belnap’s original values false, true, contradictory, unknown, respectively. Theorem 9. L is an injective MV-algebra if, and only if the corresponding MV-algebra of evidence matrices M is an injective MV-algebra. Proof. Assume an evidence matrix A ∈ M is induced by an evidence couple a, b ∈ L × L, where L is an injective MV-algebra. We show that there is an n-divisor x, y ∈ L × L of a, b . Then it is obvious that the n-divisor B ∈ M of A is induced by an evidence couple x, y . Indeed, x, y ∈ L × L is an n-divisor of a, b if 1. a, b = n x, y = nx, y n , i.e. a = nx, b = y n and 2. x, y = [ a, b ⊥ ⊗ (n − 1) x, y ]⊥ = [ a ∗ , b∗ ⊗ (n − 1) x, y ]⊥ = [ a ∗ , b∗ ⊗ (n − 1)x, y n−1 ]⊥
(40)
1934
E. Turunen et al. / Fuzzy Sets and Systems 161 (2010) 1926 – 1940
= [ a ∗ ⊕ (n − 1)x, b∗ y n−1 ]⊥ = (a ∗ ⊕ (n − 1)x)∗ , (b∗ y n−1 )∗ , i.e. x = (a ∗ ⊕ (n − 1)x)∗ , y = (b∗ y n−1 )∗ .
(41)
Trivially x is the n-divisor of a. The n-divisor y of b is the element z ∗ , where z is the n-divisor of b∗ . Indeed, b∗ = nz and, therefore, b = (nz)∗ = (z ∗ )n . Moreover, z = [b∗∗ ⊕ (n − 1)z]∗ = [b ⊕ (n − 1)z]∗ = b∗ [(n − 1)z]∗ = b∗ (z ∗ )n−1 , hence z ∗ = [b∗ (z ∗ )n−1 ]∗ . By the above construction we also see that if M is an injective MV-algebra, then L is an injective, too. This completes the proof. Remark 10. Some of the proofs in this section would be shorter after realizing that the structure introduced in Definition 5 is, up to isomorphism, the well known MV-algebra L × Ldual , where Ldual is obtained by reversing the order. For the convenience of those readers who are not familiar with MV-algebras we have, however, presented some proofs in detail. 4. Paraconsistent Pavelka style fuzzy logic Now we briefly demonstrate Pavelka style fuzzy logic with the above introduced paraconsistent semantics. For a complete description of injective MV-algebra valued Pavelka style sentential logic, see [21]. 4.1. Pavelka style fuzzy sentential logic A standard approach in mathematical sentential logic is the following. After introducing atomic formulae, logical connectives and the set of well-formed formulae, these formulae are semantically interpreted in suitable algebraic structures. In classical logic these structures are Boolean algebras, in Hájek’s Basic fuzzy logic [7], for example, the suitable structures are standard BL-algebras. Tautologies of a logic are those formulae that obtain the top value 1 in all interpretations in all suitable algebraic structures; for this reason tautologies are sometimes called 1-tautologies. For example, tautologies in Basic fuzzy logic are exactly the formulae that obtain value 1 in all interpretations in all standard BL-algebras. The next step in usual mathematical logic is to fix the axiom schemata and the rules of inference: a well-formed formula is a theorem if it is either an axiom or obtained recursively from axioms by using finitely many times rules of inference. Completeness of the logic means that tautologies and theorems coincide; classical sentential logic and basic fuzzy sentential logic, for example, are complete logics. In Pavelka style fuzzy sentential logic [13] the situation is somewhat different. We start by fixing a set of truth values, in fact an algebraic structure—in Pavelka’s own approach this structure is the Łukasiewicz structure L—in [20,21] the structure is a more general (but fixed!) injective MV-algebra L. Consider a zero order language F with a set of infinitely many propositional variables p, q, r, . . . , and a set of internal truth values {a|a ∈ L} (also called truth constants) corresponding to the elements in the set L. As proved in [7], if the set of truth values is the whole real interval [0, 1] then it is enough to include inner truth values corresponding to rationals belonging to [0, 1]. In two-valued logic inner truth values correspond to the truth constants ⊥ and . Propositional variables and truth constants constitute the set Fa of atomic formulae. The elementary logical connectives are implication imp and conjunction and. The set of all well formed formulae (wffs) is obtained in the natural way: atomic formulae are wffs and if , are wffs, then imp , and are wffs. As shown in [21], we can introduce many other logical connectives by abbreviations, e.g. disjunction or, negation non, equivalence equiv and exclusive or xor are possible. Also the connectives weak implication imp, weak conjunction and, weak disjunction or, weak negation non, weak equivalence equiv and weak exclusive or xor are available in this logic. We call the logical connectives without bar Łukasiewicz connectives, those with bar are Intuitionistic connectives. Semantics in Pavelka style fuzzy sentential logic is introduced in the following way: any mapping v : Fa L such that v(a) = a for all inner truth values a can be extended recursively into the whole F by setting v( imp ) = v( ) → v( )
E. Turunen et al. / Fuzzy Sets and Systems 161 (2010) 1926 – 1940
1935
and v( and ) = v( ) v( ). Such mappings v are called valuations. The degree of tautology of a wff is the infimum of all values v( ), that is C sem ( ) = {v( )|v is a valuation}. We may fix some set T ⊆ F of wffs and make it fuzzy by associating each formula ∈ T with a value T ( ) in L, and T ( ) = 0 for wffs not in T , and call the result a fuzzy theory T , see Example 2 below. Then we consider valuations v such that T ( )≤v( ) for all wffs ∈ F. If such a valuation exists, then the fuzzy theory T is satisfiable. We say that formulae ∈ F such that T ( ) 0 are the non-logical axioms of the fuzzy theory T . Then we consider values {v( )|v is a valuation, T satisfies v}. C sem (T )( ) = The set of logical axioms, denoted by A, is composed of the following 11 forms of formulae (see [21, p. 88]) (Ax.1) imp , (Ax.2) ( imp ) imp [( imp ) imp ( imp )], (Ax.3) ( 1 imp 1 ) imp {( 2 imp 2 ) imp [( 1 imp 2 )] imp [( 1 imp 2 )]}, (Ax.4) imp 1, (Ax.5) 0 imp , (Ax.6) ( and non- ) imp 0, (Ax.7) a, (Ax.8) imp ( imp ), (Ax.9) (1 imp ) imp , (Ax.10) [( imp ) imp ] imp [( imp ) imp ], (Ax.11) (non- imp non- ) imp ( imp ). All the axiom formulae in (Ax.1)–(Ax.6) and (Ax.8)–(Ax.11) are 1-tautogies, that is C sem ( ) = 1 and, for axioms (Ax.7), C sem (a) = a ∈ L. Notice that, corresponding to different (non-isomorphic) injective MV-algebra valued fuzzy logics, the set of logical axioms are not different except, of course, axioms (Ax.7). A fuzzy rule of inference is a scheme 1 , . . . , n , syn r ( 1 , . . . , n )
a1 , . . . , an , sem r (a1 , . . . , an )
where the wffs 1 , . . . , n are premises and the wff r syn (a1 , . . . , an ) is the conclusion. The values a1 , . . . , an and r sem (a1 , . . . , an ) ∈ L are the corresponding truth values. The mappings L n L are semi-continuous, i.e. sem r , ... , a , ... , = r sem ( , . . . , a , . . . , ) 1
ki
i∈
n
1
ki
n
i∈
holds for all 1≤k≤n. Moreover, the fuzzy rules are required to be sound in a sense that r sem (v( 1 ), . . . , v( n ))≤v(r syn ( 1 , . . . , n )) holds for all valuations v. The following are examples of fuzzy rules of inference, denoted by a set R: Generalized Modus Ponens: , imp ,
a, b a b
a-Consistency testing rules: a , 0
b , c
where a is an inner truth value and c = 0 if b≤a and c = 1 elsewhere.
1936
E. Turunen et al. / Fuzzy Sets and Systems 161 (2010) 1926 – 1940
a-Lifting rules: , a imp
b , a→b
where a is an inner truth value. Rule of Bold Conjunction: , , and
A, B . A B
A meta proof w of a wff in a fuzzy theory T is a finite sequence 1 .. .
, a1 .. .
m , a m , where (i) m = , (ii) for each i, 1≤i≤m, i is a logical axiom, or is a non-logical axiom, or there is a fuzzy rule of inference in R and wff formulae i1 , . . . , in with i 1 , . . . , i n < i such that i = r syn ( i1 , . . . , in ), (iii) for each i, 1≤i≤m, the value ai ∈ L is given by ⎧ a if i is the axiom a, ⎪ ⎪ ⎪ ⎪ ⎨1 if i is some other logical axiom in the set A, ai = ⎪ if i is a non-logical axiom, ⎪ T ( i ) ⎪ ⎪ ⎩ sem r (a , . . . , a ) if = r syn ( , . . . , ). i1
in
i
i1
in
The value am is called the degree of the meta proof w. Since a wff may have various meta proofs with different degrees, we define the degree of deduction of a formula to be the supremum of all such values, i.e. {am |w is a meta proof for in the fuzzy theory T }. C syn (T )( ) = A fuzzy theory T is consistent if C sem (T )(a) = a for all inner truth values a. By Proposition 94 in [21], any satisfiable fuzzy theory is consistent. Theorem 25 in [21] now states the completeness of Pavelka style fuzzy sentential logic: If a fuzzy theory T is consistent, then C sem (T )( ) = C syn (T )( ) for any wff . Thus, in Pavelka style fuzzy sentential logic we may talk about tautologies of a degree a and theorems of a degree a for all truth values a ∈ L, and these concepts coincide. Notice that the axiom schemata (Ax.1)–(Ax.11) and the set R of fuzzy rules of inference are sufficient to guarantee the completeness theorem irrespective of the choice of the injective MV-algebra. This completeness result remains valid if we extend the language to contain Intuitionistic connectives and or or. However, it does not hold if the language is extended by the Intuitionistic connectives imp or non. 4.2. Paraconsistent Pavelka logic The above construction can be carried out in any injective MV-algebra thus, in particular, in the injective MV-algebra M of evidence matrices induced by an injective MV-algebra L. Indeed, semantics is introduced by associating to each atomic formula p an evidence couple pro, con or simply a, b ∈ L EC . The evidence couple a, b induces a unique evidence matrix A ∈ M and therefore valuations are mappings v such that v(p) = A for propositional variables and v(I) = I for inner truth values (∈ M). A valuation v is then extended recursively to whole F via v( imp ) = v( ) −→ v( ), v( and ) = v( ) v( ). (42)
E. Turunen et al. / Fuzzy Sets and Systems 161 (2010) 1926 – 1940
Similar to the procedure in [21, Chapter 3.1] we can show that v( or ) = v( ) v( ), v(non- ) = [v( )]⊥ ,
1937
(43)
v( equiv ) = [v( ) −→ v( )] ∧ [v( ) −→ v( )], v( xor ) = [v( ) v( )] ∧ [v( ) −→ v( )⊥ ] ∧ [v( ) −→ v( )⊥ ],
(45)
v( and ) = v( ) ∧ v( ), v( or ) = v( ) ∨ v( ),
(46)
(44)
v( imp ) = v( ) ⇒ v( ), v(non- ) = v( ) ,
(47)
v( equiv ) = [v( ) ⇒ v( )] ∧ [v( ) ⇒ v( )].
(48)
Example 1. Let L be the Łukasiewicz structure L. Assume and are associated with evidence couples 0.8, 0.4 and 0.7, 0.2 , respectively. Then 0.2 0.2 0.6 0 v( ) = , v(non- ) = , 0 0.6 0.2 0.2 0.2 0 0.7 0.1 v( ) = , v(non- ) = , 0.1 0.7 0 0.2 0.5 0.1 0 0 v( and ) = , v( or ) = (= T ), 0 0.4 0 1 0 0 0.4 0 v( imp ) = , v( imp non- ) = , 0.1 0.9 0.1 0.5 0.4 0 0 0.2 , v( imp ) = , v( imp non- ) = 0.1 0.5 0 0.8 0.1 0.1 0.4 0 v( equiv ) = , v( xor ) = , 0 0.8 0.1 0.5 1 0 1 0 v(non- ) = , v(non- ) = , 0 0 0 0 0.3 0.1 0.2 0 v( and ) = , v( or ) = , 0 0.6 0 0.8 0 0 0 0.4 v( imp ) = , v( imp ) = , 0.3 0.7 0 0.6 0.3 0.1 v( equiv ) = . 0 0.6 The obtained continuous valued paraconsistent logic is a complete logic in the Pavelka sense. The logical axioms are the axiom schemata (Ax.1)–(Ax.11) and rules of inference are the fuzzy rules of inference in the set R. Thus, we have a solid syntax available and e.g. all the many-valued extensions of classical rules of inference are available; 25 such rules are listed in [21]. For example, the following are sound rules of inference. Generalized Modus Tollendo Tollens; non- , imp , non-
A, B . A B
1938
E. Turunen et al. / Fuzzy Sets and Systems 161 (2010) 1926 – 1940
Generalized Simplification Law 1; and ,
A . A
Generalized Simplification Law 2; and ,
A . A
Rule of Bold Conjunction; , A, B , . and A B Generalized De Morgan Law 1; (non- ) and (non- ) , non-( or )
A . A
Generalized De Morgan Law 2; non-( or ) , (non- ) and (non- )
A . A
If the MV-algebra L is the Łukasiewicz structure, then the evidence couples coincide with the ordered pairs B( ), B(¬ ) discussed in [14]. Moreover, the evidence matrices coincide with the matrices f ( ) k( ) v( ) = , u( ) t( ) where t( ), k( ), u( ), f ( ) are defined via Eqs. (1)–(4) [14, Eqs. (38)–(41)]. In particular, the computation of values v( ∧ ) and v( ∨ ) [14, Proposition 3.3] coincide with our Eqs. (46). Example 2. To illustrate the use of this logic, assume we have an L-valued fuzzy theory T with the following four non-logical axioms and evidence couples: Statement (1) If wages rise or prices rise there will be inflation (2) If there will be inflation, the Government will stop it or people will suffer (3) If people will suffer the Government will lose popularity (4) The Government will not stop inflation and will not lose popularity
Formally ( p or q) imp r r imp (s or t) t imp w non-s and non-w
Evidence 1, 0 0.9, 0.1 0.8, 0.1 1, 0
We have interpreted the logical connectives or and and to be the Lukasiewicz ones, however, they could be Intuitionistic or and and too. Moreover, the inclusive or connective could be the exclusive disjunction xor as well. 1. We show that T is satisfiable and therefore consistent. By Theorem 7 it is enough to consider evidence couples; focus on the following Statement Wages rise Prices rise There will be inflation Government will stop inflation People will suffer Government will lose popularity
Atomic formula p q r s t w
Evidence couple 0.3, 0.8 0, 1 0.3, 0.8 0, 1 0.2, 0.9 0, 1
By direct computation we realize that they lead to the same evidence couples as in the fuzzy theory T . Indeed, for example the evidence for the first non-logical axiom [( p or q) imp r ] is (0.3 ⊕ 0) → 0.3 = 1 and evidence against the axiom [( p or q) imp r ] is (0.8 1)∗ 0.8 = 0. Similarly for the other axioms. Thus, T is satisfiable and consistent.
E. Turunen et al. / Fuzzy Sets and Systems 161 (2010) 1926 – 1940
1939
2. What can be said on logical grounds about the claim wages will not rise, formally expressed by non- p? The above consideration on evidence couples associates with (non- p) an evidence couple 0.3, 0.8 ⊥ = 0.7, 0.2 and the corresponding valuation v is given by the evidence matrix v(non- p) =
0.7∗ ∧ 0.2
0.7 0.2
=
0.7∗ 0.2∗ 0.7 ∧ 0.2∗
0.2
0
0.1 0.7
,
and the degree of tautology of (non- p) is less than or equal to v(non- p). 3. We prove that the degree of tautology of the wff (non- p) cannot be less that v(non- p), thus it is equal to v(non- p). To this end consider the following meta proof: (1) ( p or q) imp r (2) r imp (s or t) (3) t imp w (4) non-s and non-w (5) non-w (6) non-s (7) non-t (8) non-s and non-t (9) non-(s ort) (10) non-r (11) non-( p or q) (12) non- p and non-q (13) non- p
1, 0 0.9, 0.1 0.8, 0.1 1, 0 1, 0 1, 0 0.8, 0.1 0.8, 0.1 0.8, 0.1 0.7, 0.2 0.7, 0.2 0.7, 0.2 0.7, 0.2
non-logical axiom non-logical axiom non-logical axiom non-logical axiom (4), GS2 (4), GS1 (+5), (3), GMTT (6), (7), RBC (8), GDeM1 (9), (2), GMTT (10), (1) GMTT (11), GDeM2 (12), GS1
4. By completeness of T we conclude C sem (T )(non- p) = C syn (T )(non- p) =
0.2
0
0.1 0.7
.
We interpret this result by saying that, from a logical point of view, the claim wages will not rise is (much) more true than false, is not contradictory but lacks some information. 5. Discussion (1) Quite recently Dubois [4] published a critical view of the significance of Belnap’s four-valued logic. Dubois’ critique is not exactly in the area of our competence. However, we feel obliged to comment on some of Dubois’ viewpoints and observations. Dubois writes Although some may be tempted to found new mathematics on many-valued logics, this grand purpose still looks out of reach if not delusive. It sounds like a paradox of its own since we use classical mathematics to formally model many-valued logic notations. We share this criticism. For us various many-valued logics are just formal mathematical systems whose meta logic is classical Boolean logic. For example the Completeness Theorem of Pavelka logic has exactly the same status as the Central Limit Theorem has in probability theory; there is no uncertainty or many-valuedness involved, they are matters of exact proof. Moreover, Dubois discusses meritoriously about the philosophical differences between truth and belief and points out that there is a confusion in the use of these concepts in Belnap’s approach. We feel that this critique does not concern our approach as for us the introduced continuous valued logic is just a formal tool mainly developed for decision making purposes (see [22]). Indeed, given an evidence couple, we may interpret the values t, f, k and u of the corresponding evidence matrix M e.g. by Make the resolution, Do not make the resolution, Information is contradictory and There is a lack of information, respectively. We have available a language which maps sentences to four possible states (or the infinite combinations between them) and we show how is it possible to make a consistent calculus on that e.g. in preference modeling.
1940
E. Turunen et al. / Fuzzy Sets and Systems 161 (2010) 1926 – 1940
Finally, Dubois observes an anomaly in Belnap’s approach as ( and ) or (not- and ) or ( and not- ) or (not- and not- )
(49)
is not a tautology but obtains the same value of truth as F (false). This is due to the fact that, in Belnap’s approach, the negation of U (unknown) is U and the negation of K (contradiction) is K. Our approach avoids this pitfall as we use residual negation. Indeed, as one can easily be convinced, (49) obtains the top value 1 in any valuation v. (2) Assuming L is a linearly ordered injective MV-algebra, the condition (B) in Proposition 3 implies that, for any formula , either k has the bottom value 0 or u has the bottom value, which might sound counter intuitive. If k and u represent information or epistemic states this is, however, not surprising. Intuitively speaking we either have a situation of information overload (contradiction) or of missing information (unknown), but never both. However, there might be situations where there is not enough information and even the existing piece of information contains contradictions. In such cases we simply assume that L is not linear as, in general, k ∧ u = 0 does not imply that k = 0 or u = 0. (3) As a possible direction of future work we mention a more detailed discussion about the resolution of the problems encountered in [14] as well as a more detailed presentation of the relevance of all that for preference modeling and decision making purposes. Acknowledgements The authors are grateful to Rostislav Horˇcík for his valuable comments when preparing this paper. Moreover, the anonymous reviewers gave us useful instructions for writing the final version of the paper. References [1] O. Arieli, A. Avron, Reasoning with logical bilattices, Journal of Logic, Language and Information 5 (1996) 25–63. [2] N.D. Belnap, A useful four-valued logic, in: G. Epstein, J. Dumme (Eds.), Modern Uses of Multiple Valued Logics, D. Reidel, Dordrecht, 1977, pp. 8–37. [3] C.C. Chang, Algebraic analysis of many-valued logics, Transactions of the American Mathematical Society 88 (1958) 476–490. [4] D. Dubois, On ignorance and contradiction considered as truth-values, Logic Journal of IGPL 16 (2) (2008) 195–216. [5] M.K. Ginsberg, Multivalued logics: a uniform approach to inference in artificial intelligence, Computational Intelligence 4 (1988) 265–316. [6] D. Gluschankof, Prime deductive systems and injective objects in the algebras of Łukasiewicz infinite-valued calculi, Algebra Universalis 29 (1992) 354–377. [7] P. Hájek, Metamathematics of Fuzzy Logic, Kluwer Academic Publishers, Dordrecht, 1998. [8] P. Kukkurainen, E. Turunen, Many-valued similarity reasoning. An axiomatic approach, International Journal of Multiple Valued Logic 8 (2002) 751–760. [9] R. Cignoli, I.M.L. D’Ottaviano, D. Mundici, Algebraic foundations of many-valued reasoning, in: Trends in Logic, Vol. 7, Kluwer Academic Publishers, Dordrecht, 2000. [10] V. Novák, I. Perfilieva, J. Mockor, Mathematical Principles of Fuzzy Logic, Kluwer Academic Publishers, Boston, 1999. [11] M. Öztürk, A. Tsoukiás, Modeling uncertain positive and negative reasons in decision aiding, Decision Support Systems 43 (2007) 1512–1526. [12] S.P. Odintsov, On axiomatizing Shramko–Wansing’s logic, Studia Logica 93 (2009) 407–428. [13] J. Pavelka, On fuzzy logic I, II, III, Zeitschrift für Mathematische Logik 25 (1979) 45–52 119–134, 447–464. [14] P. Perny, A. Tsoukiás, On the continuous extensions of four valued logic for preference modeling, in: Proc. IPMU Conf., 1998, pp. 302–309. [15] U. Rivieccio, Neutrosophic logics: prospects and problems, Fuzzy Sets and Systems 159 (2008) 1860–1868. [16] http://plato.stanford.edu/entries/logic-paraconsistent/ . [17] Y. Shramko, H. Wansing, Some useful 16-valued logics: how a computer network should think, Journal of Philosophical Logic 34 (2005) 121–153. [18] Y. Shramko, H. Wansing, Hypercontradictions, generalized truth values, and logics of truth and falsehood, Journal of Logic, Language and Information 15 (2006) 403–424. [19] A. Tsoukiás, A first order, four valued, weakly Paraconsistent logic and its relation to rough sets semantics, Foundations of Computing and Decision Sciences 12 (2002) 85–108. [20] E. Turunen, Well-defined fuzzy sentential logic, Mathematical Logic Quarterly 41 (1995) 236–248. [21] E. Turunen, Mathematics Behind Fuzzy Logic, Springer, Berlin, 1999. [22] E. Turunen, Interpreting GUHA data mining logic in paraconsistent fuzzy logic framework, in: A. Tsoukiás, F. Rossi (Eds.), Algorithmic Decision Theory, Lecture Notes in Computer Science, Vol. 5783, Springer, Berlin, Heidelberg, 2009, pp. 284–293.