Many-valued logics - implications and semantic consequences

Acta Univ. Sapientiae, Informatica, 5, 2 (2013) xx–yy Many-valued logics – implications and semantic consequences Katalin P´asztor Varga E¨otv¨os Lor´and University email: [email protected] G´abor Alagi1 E¨otv¨os Lor´and University email: [email protected] Magda V´arter´esz Debrecen University email: [email protected] Abstract. In this paper an application of the well-known matrix method to an extension of the classical logic to many-valued logic is discussed: we consider an n-valued propositional logic as a propositional logic language with a logical matrix over ntruth-values. The algebra of the logical matrix has operations expanding the operations of the classical propositional logic. Therefore we look over the Lukasiewicz, Post, Heyting and Rosser style expansions of the operations negation, conjunction, disjunction and with a special emphasis on implication. In the frames of consequence operation, some notions of semantic consequence are examined. Then we continue with the decision problem and the logical calculi. We show that the cause of difficulties with the notions of semantic consequence is the weakness of the reviewed expansions of negation and implication. Finally, we introduce an approach to finding implications that preserve both modus ponens and the deduction theorem with respect to our definitions of consequence. Computing Classification System 1998: F.4.1 Mathematics Subject Classification 2010: 03B50 Key words and phrases: many-valued logic, extensions of implication, notions of consequence 1Current affiliation of the author: Max Planck Institute f¨ur Informatik, email: [email protected] 1 2K. P. Varga, G. Alagi, M. V´arter´esz 1 Introduction The construction of propositional logics can follow several methodological ways. The algebraic method is fundamental and also prior to any others. One such an algebraic tool for constructing a logic is the logical matrix method. We begin with a brief survey of related notions and notations. After defining the notion of consequence operation, we show that the semantic consequence for the classical propositional logic results a consequence operation. Later, we outline the conventional axiomatic treatment of logic for a given logic language. Here, we prove that the usual derivation notion is also a consequence operation. After this, we discuss the n-valued propositional logics (n > 2). It is desirable to obtain an algebraic structure close to a Boolean algebra by expansion of the classical logical matrix to nvalues. Here, we define two notions of semantic consequence, and prove that both are consequence operations. Because the usual expansion of conjunction is the minimum unanimously, and the expansion of disjunction is the maximum in the same way, we deal only with the Lukasiewicz, Post, Heyting and Rosser style expansions of implication. Finally, we consider in what manner we can give an implication for a general consequence such that both modus ponens and the deduction theorem remain valid. 2 Logical matrices Let Ube any nonempty set. A mapping o:Um→U, defined on the Cartesian product of mcopies of U, with values in U, is called an m-argument (or an m-ary) operation in U(for m=0, 1, . . .). By an algebra we mean a pair hU, (o1, o2,...,ok)i(k≥1), where Uis a (nonempty) set, called the universe of the algebra, and each ojis an mj-argument operation over U. A tuple (m1, m2,...,mk)associated to the operations is called the signature of the algebra. We consider an arbitrary logic language L=hV, (c1, c2,...,ck), Fi, where Vis the set of propositional variables; c1, c2,...,ckare logical connectives; F is the set of formulas generated by the variables and the connectives in the standard way. At the same time, the set Fof the formulas can also be regarded as the universe of an algebra with concatenation operations induced by the connectives. If we can connect mjformulas with the connective cj, the induced operation has mjarguments, and the signature of the algebra freely generated by Vis (m1, m2,...,mk). This algebra is a logic language algebra. Many-valued logics . . . 3 A logic system is semantically determined, if we have an interpretation notion in the sense that every formula has some truth-value with respect to each such interpretation. A basic assumption in classical logics is the principle of compositionality: the truth-value of a compound formula is a function of the truth-values of its immediate subformulas (every formula represents a function into the set of truth-values). Hence the most essential semantical decision is the determination of the operations over the truth-value set which characterizes the connectives. Later, the algebraic structure of the truth-value set will play an important role. Definition 1 [5] By a logical matrix Mfor a logic language algebra Lwith a signature (m1, m2,...,mk)we mean a triple hU, (o1, o2,...,ok), U∗i, where hU, (o1, o2,...,ok)iis an algebra with the signature (m1, m2, . . . , mk), and U∗is a nonempty subset of U.Uis the set of truth-values, the elements of U∗are called designated truth-values. After this, we define the semantics as a correspondence between the set of connectives and operations using the signature. This is followed by an interpretation I:V→U. The interpretation Ican uniquely be extended to a homomorphism (called a valuation of formulas) from the set of formulas Fto the universe U: (a) |v|I=I(v)for v∈V; (b) |cj(α1,...,αmj)|I=oj(|α1|I,...,|αmj|I)for every mj-ary connective cj and for all α1,...,αmj∈F. In every interpretation, a formula assigns truth-values to the truth-values of the variables occurring in the formula. Thus, a formula expresses a truthfunction Un→U(an n-variable operation over U). If we want to handle every potential truth-function with the logic language, then the set of operations in the logical matrix should be functionally complete. We say that a set of operations is functionally complete, when every truth-function Un→Ucan be expressed by a formula using only the logical connectives corresponding to these operations. Now and then, a notion of partial interpretation Ip :V0→U(V0⊆V)is convenient. If V0=V, the partial interpretation Ip is a (total) interpretation. And, if the domain of Ip contains all the variables occurring in a set Xof 4K. P. Varga, G. Alagi, M. V´arter´esz formulas, then Ip is total with respect to X. Sometimes later, it is simplier to handle an (partial) interpretation Ip as a relation Ip ⊆V×U, where for all pair (v1, u1)and (v2, u2)in Ip, if u16=u2, then v16=v2. In this notation, we can formalize an extension of the partial interpetation Ip to the variable v /∈Dom(Ip)with Ip ∪{(v, u)}, where u∈U. In order that a logic language and its matrix can become a logic system, the consequence notion and the decision problem are inevitable. In [7], Tarski developed an abstract theory of logical systems. He intoduced a finitary closure operation on the sets of formulas, called consequence operation. Let P(F) denote the power set of F. Definition 2 The consequence operation Cn :P(F)→P(F)in Lis an operation which satisfies the following conditions for any X, Y ⊆Fand α, β ∈F: (1) X⊆Cn(X)⊆F; (2) if X⊆Cn(Y)then Cn(X)⊆Cn(Y); (3) if α∈Cn(X)then there exists a finite set Ysuch that Y⊆Xand α∈Cn(Y). Note that Cn(Cn(X)) ⊆Cn(X)holds for every consequence operation, because Cn(X)⊆Cn(X)and (2). Let αbe a formula and let Xbe a set of formulas. The decision problem is to decide whether α∈Cn(X). To sum it up, by a propositional logic we mean a quadruple hL, M, In, Pri, where Lis a logic language algebra, Mis a logical matrix for L,In is the set of interpretations of L,Pr is a consequence operation. Example 3 A classical two-valued propositional logic (CPL) is a quadruple L, M, In, Pr0, where (a) Lis a language algebra hV, (¬,∧,∨), Fiwith signature (1, 2, 2). (b) Mis a logical matrix h{0, 1},(¬0,∧0,∨0),{1}i, where the values 0and 1 are truth-values, 1 stands for true, 0 stands for false. The operation ∧0 Many-valued logics . . . 5 is the classical conjunction (minimum), ∨0is the classical disjunction (maximum), and ¬0is the classical negation. This operation set is functionally complete. (We remark, if we use the definition x⊃0y¬0x∨0y in M, the set {¬0,⊃0}is also functionally complete.) The structure {0, 1},¬0,∧0,∨0, 0, 1 yields a Boolean algebra. The set {0, 1}is the universe of the Boolean algebra, the operations ∧0and ∨0are lattice operations, the unary operation ¬0is the complementation, and 1 is the unit, 0 is the zero element. (c) In ={I|I:V→{0, 1}is an interpretation of L}. (d) Pr0is the usual semantic consequence: α∈Pr0(X)if and only if |α|I=1, whenever |β|I=1for every formula βin X. Next, we verify that Pr0is a consequence operation. Proposition 4 Pr0satisfies the conditions (1)-(3) in Definition 2. Proof. (1) is obvious. (2) Let InXbe the set of interpretations, where |β|I=1for every formula β in X. If elements of Xare consequences of Y, then InY⊆InX. Whereas InX⊆InPr0(X), thus InY⊆InPr0(X). (3) If α∈Pr0(X), then InX∩In¬α=∅. Because of compactness theorem in CPL, if InX∩In¬α=∅, then there exists a finite set Ysuch that Y⊆X and InY∩In¬α=∅also. Thus, Yis a finite subset of Xand α∈Pr0(Y).  3 Axiomatic treatment of logics Another method to construct logics is the axiomatic (syntax-based) way. Let Lbe a logic language with the set Fof formulas. Definition 5 A finite subset Aof formulas is called an axiom system. 6K. P. Varga, G. Alagi, M. V´arter´esz Definition 6 A rule over Fis a nonempty relation r⊆{(α1,...,αm, α)|α1,...,αm, α ∈F}. Definition 7 Let Abe an axiom system, Ra set of rules and Xany set of formulas. A formula αis derived from Xif there is a finite sequence of formulas α1,...,αksuch that (1) αk=α, and (2) for each i(1≤i≤k),either αi∈X∪A, or there exist indices i1,...,il smaller than isuch that (αi1,...,αil, αi)∈rfor some rule r∈R. Proposition 8 Pr∗:X→{α|αis derived from X}satisfies conditions (1)- (3) in Definition 2. Proof. (1) is obvious. (3) can be seen easily. If α∈Pr∗(X), the derivation of αis a finite sequence of formulas. Let Ybe the set of formulas of Xoccuring in this derivation. Clearly, αcan be derived from Y, as well. (2) If αcan be derived from X, because of (3), there is a finite Z⊆Xsuch that αcan be derived from Z. But every element of Zcan be derived from Y, i.e. from some finite subset of Y. If we concatenate the derivations of the elements of Zfrom Yand furthermore, we add the derivation of αfrom Zto it, then the result is a derivation of αfrom Y. Herewith, condition (2) holds.  Informally, a propositional logic is axiomatically given by hL, A, R, Pr∗i, if its language algebra Lis specified, an axiom system Ais fixed, a finite set Rof derivation rules is specified and Pr∗is the consequence operation. An axiomatically given propositional logic (calculus) hL, A, R, Pr∗iis said to be (strongly) adequate for a propositional logic hL, M, In, Priif their consequence operations are the same. Many-valued logics . . . 7 Example 9 By a classical propositional calculus we mean a quadruple hL∗, A, R, Pr∗i, where (a) L∗is the free language algebra hV, (¬,⊃), Fiwith signature (1, 2); (b) the axiom system Aconsists of the axioms {α⊃(β⊃α),(α⊃(β⊃γ)) ⊃((α⊃β)⊃(α⊃γ)), (¬α⊃β)⊃((¬α⊃¬β)⊃α)}; (c) the set Rcontains the single derivation rule α, α ⊃β β; (d) and Pr∗:X→{α|αis derived from X}is the consequence operation. The classical propositional calculus hL∗, A, R, Pr∗iis adequate for the classical propositional logic hL∗, M∗, In, Pr0i, where M∗is a logical matrix for L∗. 4 Propositional many-valued logics By the literature [1], [2] and [3], a non-classical logic may be an extended logic and/or a deviant logic. ”Extended logics expand classical logic by additional logical constructs. For example, in modal logic modal operators are added to classical logic to express modal notions. In contrast, deviant logics are rivals to classical logic that give up some classical principles. In many-valued logics, we allow for many truth-values instead of two truth-values (we give up the principle of bivalence)”. This deviation leads to the extension of the operations of the classical two-valued logic. An operation is extended if, whenever the arguments are classical truth-values, the result has the same truth-value as it does in classical logic. ”In this sense, classical logic can be thought of as a special case of many-valued logic.” Let Unbe a set of truth-values {0, 1, 2, . . . , n −1}(n≥2). Formally, we can define a propositional many-valued logic (MVPL) as a quadruple hL, M, In, Prni, where 8K. P. Varga, G. Alagi, M. V´arter´esz (a) L=hV, Con, Fiis a language algebra with a signature σ. (b) M=hUn, Op, U∗ niis a logical matrix for L, where hUn, Opiis an algebra over Unwith the signature σ, as well. Moreover, let S∈Un. Then U∗ n={S+1,...,n−1}is the set of the designated truth-values, and 0, 1, . . . , S are called non-designated ones. (c) In ={I|I:V→Unis an interpretation of L}. (d) Prn:P(F)→P(F)should be a consequence operation. Now, we look for a consequence operation. Let L=hV, Con, Fibe a language algebra and let M=hUn, Op, U∗ nibe a logical matrix for the language L. Definition 10 A formula αis a weak semantic consequence of a set Xof formulas, denoted as X|=Sα, if for any interpretation in which the truth-value of every formula β∈Xis designated, the truth-value of αis also designated. If Xis the empty set, we have no constraint for the interpretations. Thus, αis said to be an S-tautology (∅|=Sα) if the truth-value of αis designated for every interpretation. We can give a more rigorous notion of the consequence relation if we also take the extent of truth-values of formulas into consideration. Definition 11 A formula αis a strong semantic consequence of a set Xof formulas, denoted as X|=S∗α, if for any interpretation in which the truth-value of every formula β∈Xis designated, the truth-value of αis also designated with at least the same truthvalue as the minimum of the truth-values of formulas in Xin the underlying interpretation. We need some further notions and a lemma to discuss the characteristic of the consequence relation simply. Definition 12 Let a partial interpretation Ip be a total interpretation with respect to the set X∪{α}of formulas. Xis appropriate for αin Ip if the truthvalue of αis not less than the minimum of the truth-values of formulas in X, whenever this minimum is designated. Many-valued logics . . . 9 Definition 13 Xis finitely bad for αwith respect to a partial interpretation Ip if for all finite subsets Yof Xthere exists an extension of Ip in which Yis not appropriate for α. Lemma 14 If Xis finitely bad for αwith respect to a partial interpretation Ip and the variable vhas no value in Ip yet, then there is some j∈Unsuch that Xis also finitely bad for αwith respect to the partial interpretation Ip∪{(v, j)}. Proof. Otherwise, Xis not finitely bad for αwith respect to any partial interpretation Ip ∪{(v, i)}(i∈Un). So for all i, a finite subset Yiof Xwould exist such that Yiwould be appropriate for αin all total extension of Ip∪{(v, i)}. Thus, ∪n−1 i=0Yiis a finite set and appropriate for αin all total extension of Ip. It means that Xis not finitely bad for αwith respect to a partial interpretation Ip. It is a contradiction.  Proposition 15 Prn S:X→{α|X|=Sα}and Prn S∗:X→{α|X|=S∗α}are consequence operations. Proof. (1) is obvious. (2) For every interpretation I0, where q=minα∈X|α|I0> S,|γ|I0≥qholds for any γ∈Prn S(X). Now, let Ibe an interpretation, where |β|I> S for every formula βin Y, and let pbe minβ∈Y|β|I. According to condition X⊆Prn S(Y), we get |α|I≥p>Sfor every α∈X. Thus, Iis an interpretation, where |γ|I≥pholds for all γ∈Prn S(X). It means, we have Prn S(X)⊆Prn S(Y). (3) Now, let αbe a strong consequence of X. Then αis also a weak consequence of X. Let us define a special kind of negation: ¬x0if x∈U∗ n, (n−1)otherwise Moreover, let InXcontain all the interpretations in which every formula in Xhas designated truth-value. It is clear that X|=Sαif and only if InX∩In¬α=∅. Because of the compactness theorem in MVPL (see in [4]), if InX∩In¬α=∅, then there exists a finite set Y0such that Y0⊆Xand InY0∩In¬α=∅. 16 K. P. Varga, G. Alagi, M. V´arter´esz Proof. Let Ibe an interpretation in which every formula from Xand αare designated. According to the condition, α⊃f ∗βis designated with truth-value at least minγ∈X{|γ|}. Because αis designated, if |α|≤|β|, then |β|is designated with truth-value at least minγ∈X{|γ|,|α|}. In the case |α|>|β|,|α⊃f ∗β|=|β|, thus βis designated with truth-value at least min γ∈X{|γ|} ≥min γ∈X{|γ|,|α|}, as well.  Finally, all what was proved about examined implications at this section we summarized in the following table: ⊃L⊃P⊃H⊃R⊃f ∗ modus ponens - + + + + deduction theorem with |=S- - - + + deduction theorem with |=S∗- - - - + 6 Suitable implication for a given consequence It is desirable that both modus ponens and the deduction theorem hold with respect to the underlying consequence. Now, we consider in what manner we can give an implication for a generally given consequence such that both modus ponens and the deduction theorem are valid. Now, let ψ:U×U→{0, 1}be an arbitrary classical truth-valued function with the following properties: (a) ψ(x, x) = 1for all x∈U, (b) if ψ(x, y)∧ψ(y, z) = 1, then ψ(x, z) = 1for all x, y, z ∈U. Then, define the consequence as below: Definition 24 A formula αis a formal semantic consequence of a set Xof formulas, denoted as X|=α, if _ γ∈X ψ(|γ|I,|α|I) = 1for any interpretation I, where Wγ∈Xψ(|γ|I,|α|I)denotes the supremum of {ψ(|γ|I,|α|I)|γ∈X}. Many-valued logics . . . 17 Proposition 25 Pr :X→{α|X|=α}satisfies conditions (1)-(3) in Definition 2. Proof. (1) Now to prove the condition (1), let α∈X. Since in any interpretation ψ(|α|,|α|) = 1, therefore Wγ∈Xψ(|γ|,|α|) = 1, so X|=α. It means that X⊆Pr(X). (2) Next, let X⊆Pr(Y)for some X, Y ⊆F. We show that Pr(X)⊆Pr(Y). –For any α∈Pr(X),since _ γ∈X ψ(|γ|I,|α|I) = 1, so _ γ∈Pr(Y) ψ(|γ|I,|α|I) = 1. It means Pr(X)⊆Pr(Pr(Y)). –Now, we show that Pr(Pr(Y)) = Pr(Y). Since Pr(Y)⊆Pr(Pr(Y)) by the property (1), it is enough to prove, that α∈Pr(Y)for all α∈Pr(Pr(Y)). Obviously Y⊆Pr(Y). Let Y0denote the set Pr(Y)\Yand let α∈ Pr(Pr(Y)). Then _ γ∈Pr(Y) ψ(|γ|I,|α|I) = _ γ∈Y0∪Y ψ(|γ|I,|α|I) = 1. If _ γ∈Y0 ψ(|γ|I,|α|I) = 0, then _ γ∈Y ψ(|γ|I,|α|I) = 1. And if _ γ∈Y0 ψ(|γ|I,|α|I) = 1, then there exists a γ0∈Y0for which ψ(|γ0|I,|α|I) = 1. But γ0∈ Pr(Y)also holds, thus _ γ∈Y ψ(|γ|I,|γ0|I) = 1 must hold, i.e. there exists a γ00 ∈Yfor which ψ(|γ00|I,|γ0|I) = 1. Using the property (b) of ψwe get ψ(|γ00|I,|α|I) = 1, that is _ γ∈Y ψ(|γ|I,|α|I) = 1. Thus in both cases, we get α∈Pr(Y). 18 K. P. Varga, G. Alagi, M. V´arter´esz –Since X⊆Pr(Y), thus Pr(X)⊆Pr(Pr(Y)), and thereby Pr(X)⊆ Pr(Y)must hold. (3) We prove compactness by reducing the problem to the compactness of first-order logic with equality. First, let us define the language of our encoding: –We have a single binary predicate symbol ^ ψ. –For each many-valued operation o, we have a corresponding function symbol ^owith the same arity. –For each variable v, we have a corresponding constant cv. –For each truth-value u, we have an additional constant ^u. Given this language, we might fix the interpretation of our symbols by defining a set Σof the following axioms: (i) ∀x(x= ^u1∨x= ^u2∨· · · ∨x= ^un)if U={u1, u2,...,un} (ii) ^u6=^ u0for each u, u0∈Uwith u6=u0 (iii) ^ ψ(^u, ^ u0)if ψ(u, u0) = 1and u, u0∈U (iv) ¬^ ψ(^u, ^ u0)if ψ(u, u0) = 0and u, u0∈U (v) ^o( ^a1,^a2,..., ^ak) = ^uif ois an operator with arity k,a1, a2,..., ak, u ∈U, and o(a1, a2, . . . , ak) = u Since Uis finite, Σis a finite set of first-order formulas as well. It is easy to see that if ^ Iis a first-order model of Σ, then there is a corresponding many-valued interpretation Iwhich assigns the same values to variables as did ^ Ito the corresponding constants. Let ^αdenote the encoding of a formula αin this language, i.e. the first-order formula we get from αby substituting each symbol with the corresponding first-order symbol. By our definitions, if Iand ^ Iare corresponding many-valued and first-order interpretations, |α|I=uif and only if |^α|^ I= ^u. Thus, for each α,β, we have ψ(|α|I,|β|I)holds if and only if ^ ψ(^α, ^ β)holds in ^ I. Now, by our assumptions, X|=αif and only if Wγ∈Xψ(|γ|I,|α|I)holds for all interpretation I. This, on the other hand, holds if and only if the set Γ={ ¬ ψ(|γ|I,|α|I)|γ∈X}is not satisfied under any interpretation I. Consider the first-order set ^ Γ=Σ∪{ ¬ ^ ψ(^γ, ^α)|γ∈X} Many-valued logics . . . 19 From our considerations it follows that ^ Γis unsatisfiable if and only if the original Γis unsatisfiable. Then, by the compactness of first-order logic, we know that there is a finite ^ Γ0⊆^ Γsuch that ^ Γ0is unsatisfiable. Since Σis finite, we might assume Σ⊆^ Γ0. Now, let X0the finite set {γ∈X| ¬ ^ ψ(^γ, ^α)∈^ Γ0}. We know that the corresponding set Γ0={ ¬ ψ(|γ|I,|α|I)|γ∈X0}is not satisfied by any Ieither. Therefore, X0|=αmust hold where X0is a finite subset of X.  Proposition 26 Let ⊃be an implication operation over U. If ψ(x1, x2)∨ψ(y, x2) = ψ(y, x1⊃x2) for all x1, x2, y ∈U, then ⊃admits modus ponens and the deduction theorem. Proof. First, we prove modus ponens, i.e. we show, that {α, α ⊃β} |=βholds for any formulas α, β. For all α, β ∈Fand for all I∈In we get ψ(|α|I,|β|I)∨ψ(|α⊃β|I,|β|I). For all x1, x2∈U, by applying the proposed equality ψ(x1, x2)∨ψ(x1⊃x2, x2) = ψ(x1⊃x2, x1⊃x2) = 1. To prove the deduction theorem, we have to show for any α, β, X X, α |=βif and only if X|=α⊃β. Again, applying our assumptions to both sides, we get for all I∈In _ γ∈X ψ(|γ|I,|β|I)∨ψ(|α|I,|β|I) = _ γ∈X (ψ(|γ|I,|β|I)∨ψ(|α|I,|β|I)) if and only if for all I∈In _ γ∈X ψ(|γ|I,|α|I⊃|β|I). From our assumption with y=|γ|I, x1=|α|I, x2=|β|I, we get ψ(|γ|I,|β|I)∨ψ(|α|I,|β|I) = ψ(|γ|I,|α|I⊃|β|I), from which the desired equivalence immediately follows.  In the remaining part of the section we apply this proposition to the earlier defined semantic consequences. 20 K. P. Varga, G. Alagi, M. V´arter´esz Example 27 By Definition 10, X|=Sαif and only if min γ∈X{|γ|I}≤S∨S < |α|Ifor all I∈In. Thus, for this case we get ψ(x, y) = (x≤S∨S<y).To find a suitable implication, it is enough to satisfy (x1≤S∨S<x2)∨(y≤S∨S<x2)if and only if (y≤S∨S<x1⊃x2) for all x1, x2, y ∈U. Let f, h :U×U→Usuch that for all x1> S and x2≤S f(x1, x2)≤Sand if x1≤Sor x2> S, then h(x1, x2)> S. Then, as we have seen above, the implication defined below admits modus ponens and the deduction theorem: x1⊃f,h ∗x2h(x1, x2)if x1≤Sor x2> S, f(x1, x2)otherwise. Example 28 By Definition 11, X|=S∗αif and only if min γ∈X{|γ|I}≤S∨min γ∈X{|γ|I}≤|α|Ifor all I∈In. For this case we get ψ(x, y) = x≤S∨x≤y. Thus to find a suitable implication, it is enough to satisfy (x1≤S∨x1≤x2)∨(y≤S∨y≤x2)if and only if (y≤x1⊃x2∨y≤S) for all x1, x2, y ∈U. The possible values for x1⊃x2might be deduced as follows: •x1≤S∨x1≤x2: since the right side must also hold, even for y=n−1, we get x1⊃x2=n−1, which is indeed a good choice. •x1≥x2> S: for y=x2we get x2≤x1⊃x2, and for y=x2+1 x1⊃x2< x2+1. Thus only x1⊃x2=x2is possible, and it indeed satisfies the equality in this case. •x1> S ≥x2: for y > S we get x1⊃x2≤S. In this case any value smaller than Ssatisfies the equality. Let f:U×U→Ube such that for all x1> S and x2≤S f(x1, x2)≤S. Then, as we have seen above, the implication defined below admits modus ponens and the deduction theorem: x1⊃f ∗x2   n−1if x1≤Sor x1≤x2, x2if x1> x2> S, f(x1, x2)otherwise. Many-valued logics . . . 21 7 Summary In this paper we demonstrated that both semantic and syntactic consequences of classical logic result consequence operators. We proved similar propositions about the weak and strong consequences in the many-valued logic. After this, we investigated the Lukasiewicz, Post, Heyting and Rosser style many-valued implications whether the modus ponens rule and the deduction theorem are valid beside of our consequence relations. By the strong consequence, the deduction theorem is not valid with none of them. However, the implication family ⊃f ∗defined in our paper found to comply with the modus ponens and the deduction theorem by the strong consequence as well. The last section, we introduced a general formal consequence relation and showed, that it also leads to a consequence operator. The weak and strong consequence definitions are realizations of this general consequence notion. It would be profitable to consider what additional realizations are possible. By this general consequence, we also gave a suitable implication which admits the modus ponens and the deduction theorem as well. Acknowledgements The publication is supported by the T´ AMOP-4.2.2/B-10/1-2010-0024 project. The project is co-financed by the European Union and the European Social Fund. References [1] M. Bergmann,An Introduction to Many-Valued and Fuzzy Logic: Semantics, Algebras, and Derivation Systems,Cambridge University Press, 2008. ⇒7 [2] L. Bolc, P. Borowik, Many-valued Logics. Vol.1. Theoretical Foundations, Springer-Verlag, Berlin, 1992. ⇒7 [3] R. H¨ahnle,G.Escalada-Imaz,Deduction in Many-valued Logics: a Survey, Mathware and Soft Computing 4, 2 (1997) 69-97. ⇒7 [4] J.-L. Lee, On compactness theorem, presented in: Taiwan Philosophical Association 2006 Annual Meeting, (2006) pp. 1-11. ⇒9 [5] K. P´asztor Varga, M. V´arter´esz,Many-valued logic, mappings, ICF graphs, normal forms, Annales Univ. Sci. Budapest. de R. E¨otv¨os Nom. Sect. Computatorica 31 (2009) 185–202. ⇒3 [6] J. B. Rosser, A. R. Turquette, Many-valued Logics. Studies in Logic and Foundations of Math., North-Holland Publishing Co., Amsterdam, 1952. ⇒13 22 K. P. Varga, G. Alagi, M. V´arter´esz [7] A. Tarski, On some fundamental concepts of metamathematics, in: Logic, Semantics and Metamath., Clarendon Press, Oxford, 1956, pp. 30–38. ⇒4 Received: •Revised: