Many-valued logics - implications and semantic consequences

Ac a Uni . Sapien iae, In o ma ica, 5, 2 (2013) xx–yy Many- alued logics – implica ions and seman ic consequences Ka alin P´asz o Va ga E¨o ¨os Lo ´and Uni e si y email: [email p o ec ed] G´abo Alagi1 E¨o ¨os Lo ´and Uni e si y email: [email p o ec ed] Magda V´a e ´esz Deb ecen Uni e si y email: [email p o ec ed] Abs ac . In his pape an applica ion o he well-known ma ix me hod o an ex ension o he classical logic o many- alued logic is discussed: we con- side an n- alued p oposi ional logic as a p oposi ional logic language wi h a logical ma ix o e n u h- alues. The algeb a o he logical ma- ix has ope a ions expanding he ope a ions o he classical p oposi ional logic. The e o e we look o e he Lukasiewicz, Pos , Hey ing and Rosse s yle expansions o he ope a ions nega ion, conjunc ion, disjunc ion and wi h a special emphasis on implica ion. In he ames o consequence ope a ion, some no ions o seman ic consequence a e examined. Then we con inue wi h he decision p oblem and he logical calculi. We show ha he cause o di icul ies wi h he no ions o seman ic consequence is he weakness o he e iewed expan- sions o nega ion and implica ion. Finally, we in oduce an app oach o inding implica ions ha p ese e bo h modus ponens and he deduc ion heo em wi h espec o ou de ini ions o consequence. Compu ing Classi ica ion Sys em 1998: F.4.1 Ma hema ics Subjec Classi ica ion 2010: 03B50 Key wo ds and ph ases: many- alued logic, ex ensions o implica ion, no ions o conse- quence 1Cu en a ilia ion o he au ho : Max Planck Ins i u e ¨u In o ma ik, email: [email p o ec ed] 1 2K. P. Va ga, G. Alagi, M. V´a e ´esz 1 In oduc ion The cons uc ion o p oposi ional logics can ollow se e al me hodological ways. The algeb aic me hod is undamen al and also p io o any o he s. One such an algeb aic ool o cons uc ing a logic is he logical ma ix me hod. We begin wi h a b ie su ey o ela ed no ions and no a ions. A e de ining he no ion o consequence ope a ion, we show ha he seman ic consequence o he classical p oposi ional logic esul s a consequence ope a ion. La e , we ou line he con en ional axioma ic ea men o logic o a gi en logic lan- guage. He e, we p o e ha he usual de i a ion no ion is also a consequence ope a ion. A e his, we discuss he n- alued p oposi ional logics (n > 2). I is desi - able o ob ain an algeb aic s uc u e close o a Boolean algeb a by expansion o he classical logical ma ix o n alues. He e, we de ine wo no ions o se- man ic consequence, and p o e ha bo h a e consequence ope a ions. Because he usual expansion o conjunc ion is he minimum unanimously, and he ex- pansion o disjunc ion is he maximum in he same way, we deal only wi h he Lukasiewicz, Pos , Hey ing and Rosse s yle expansions o implica ion. Finally, we conside in wha manne we can gi e an implica ion o a gene al consequence such ha bo h modus ponens and he deduc ion heo em emain alid. 2 Logical ma ices Le Ube any nonemp y se . A mapping o:Um→U, de ined on he Ca esian p oduc o mcopies o U, wi h alues in U, is called an m-a gumen (o an m-a y) ope a ion in U( o m=0, 1, . . .). By an algeb a we mean a pai hU, (o1, o2,...,ok)i(k≥1), whe e Uis a (nonemp y) se , called he uni e se o he algeb a, and each ojis an mj-a gumen ope a ion o e U. A uple (m1, m2,...,mk)associa ed o he ope a ions is called he signa u e o he algeb a. We conside an a bi a y logic language L=hV, (c1, c2,...,ck), Fi, whe e Vis he se o p oposi ional a iables; c1, c2,...,cka e logical connec i es; F is he se o o mulas gene a ed by he a iables and he connec i es in he s anda d way. A he same ime, he se Fo he o mulas can also be ega ded as he uni e se o an algeb a wi h conca ena ion ope a ions induced by he connec i es. I we can connec mj o mulas wi h he connec i e cj, he induced ope a ion has mja gumen s, and he signa u e o he algeb a eely gene a ed by Vis (m1, m2,...,mk). This algeb a is a logic language algeb a. Many- alued logics . . . 3 A logic sys em is seman ically de e mined, i we ha e an in e p e a ion no- ion in he sense ha e e y o mula has some u h- alue wi h espec o each such in e p e a ion. A basic assump ion in classical logics is he p inciple o composi ionali y: he u h- alue o a compound o mula is a unc ion o he u h- alues o i s immedia e sub o mulas (e e y o mula ep esen s a unc ion in o he se o u h- alues). Hence he mos essen ial seman ical decision is he de e mina ion o he ope a ions o e he u h- alue se which cha ac e - izes he connec i es. La e , he algeb aic s uc u e o he u h- alue se will play an impo an ole. De ini ion 1 [5] By a logical ma ix M o a logic language algeb a Lwi h a signa u e (m1, m2,...,mk)we mean a iple hU, (o1, o2,...,ok), U∗i, whe e hU, (o1, o2,...,ok)iis an algeb a wi h he signa u e (m1, m2, . . . , mk), and U∗is a nonemp y subse o U.Uis he se o u h- alues, he elemen s o U∗a e called designa ed u h- alues. A e his, we de ine he seman ics as a co espondence be ween he se o connec i es and ope a ions using he signa u e. This is ollowed by an in e - p e a ion I:V→U. The in e p e a ion Ican uniquely be ex ended o a homomo phism (called a alua ion o o mulas) om he se o o mulas F o he uni e se U: (a) | |I=I( ) o ∈V; (b) |cj(α1,...,αmj)|I=oj(|α1|I,...,|αmj|I) o e e y mj-a y connec i e cj and o all α1,...,αmj∈F. In e e y in e p e a ion, a o mula assigns u h- alues o he u h- alues o he a iables occu ing in he o mula. Thus, a o mula exp esses a u h- unc ion Un→U(an n- a iable ope a ion o e U). I we wan o handle e e y po en ial u h- unc ion wi h he logic language, hen he se o ope a ions in he logical ma ix should be unc ionally comple e. We say ha a se o ope a ions is unc ionally comple e, when e e y u h- unc ion Un→Ucan be exp essed by a o mula using only he logical connec i es co esponding o hese ope a ions. Now and hen, a no ion o pa ial in e p e a ion Ip :V0→U(V0⊆V)is con enien . I V0=V, he pa ial in e p e a ion Ip is a ( o al) in e p e a ion. And, i he domain o Ip con ains all he a iables occu ing in a se Xo 4K. P. Va ga, G. Alagi, M. V´a e ´esz o mulas, hen Ip is o al wi h espec o X. Some imes la e , i is simplie o handle an (pa ial) in e p e a ion Ip as a ela ion Ip ⊆V×U, whe e o all pai ( 1, u1)and ( 2, u2)in Ip, i u16=u2, hen 16= 2. In his no a ion, we can o malize an ex ension o he pa ial in e pe a ion Ip o he a iable /∈Dom(Ip)wi h Ip ∪{( , u)}, whe e u∈U. In o de ha a logic language and i s ma ix can become a logic sys em, he consequence no ion and he decision p oblem a e ine i able. In [7], Ta ski de eloped an abs ac heo y o logical sys ems. He in oduced a ini a y clo- su e ope a ion on he se s o o mulas, called consequence ope a ion. Le P(F) deno e he powe se o F. De ini ion 2 The consequence ope a ion Cn :P(F)→P(F)in Lis an ope a- ion which sa is ies he ollowing condi ions o any X, Y ⊆Fand α, β ∈F: (1) X⊆Cn(X)⊆F; (2) i X⊆Cn(Y) hen Cn(X)⊆Cn(Y); (3) i α∈Cn(X) hen he e exis s a ini e se Ysuch ha Y⊆Xand α∈Cn(Y). No e ha Cn(Cn(X)) ⊆Cn(X)holds o e e y consequence ope a ion, because Cn(X)⊆Cn(X)and (2). Le αbe a o mula and le Xbe a se o o mulas. The decision p oblem is o decide whe he α∈Cn(X). To sum i up, by a p oposi ional logic we mean a quad uple hL, M, In, P i, whe e Lis a logic language algeb a, Mis a logical ma ix o L,In is he se o in e p e a ions o L,P is a consequence ope a ion. Example 3 A classical wo- alued p oposi ional logic (CPL) is a quad uple L, M, In, P 0, whe e (a) Lis a language algeb a hV, (¬,∧,∨), Fiwi h signa u e (1, 2, 2). (b) Mis a logical ma ix h{0, 1},(¬0,∧0,∨0),{1}i, whe e he alues 0and 1 a e u h- alues, 1 s ands o ue, 0 s ands o alse. The ope a ion ∧0 Many- alued logics . . . 5 is he classical conjunc ion (minimum), ∨0is he classical disjunc ion (maximum), and ¬0is he classical nega ion. This ope a ion se is unc- ionally comple e. (We ema k, i we use he de ini ion x⊃0y¬0x∨0y in M, he se {¬0,⊃0}is also unc ionally comple e.) The s uc u e {0, 1},¬0,∧0,∨0, 0, 1 yields a Boolean algeb a. The se {0, 1}is he uni e se o he Boolean algeb a, he ope a ions ∧0and ∨0a e la ice ope a ions, he una y ope - a ion ¬0is he complemen a ion, and 1 is he uni , 0 is he ze o elemen . (c) In ={I|I:V→{0, 1}is an in e p e a ion o L}. (d) P 0is he usual seman ic consequence: α∈P 0(X)i and only i |α|I=1, whene e |β|I=1 o e e y o mula βin X. Nex , we e i y ha P 0is a consequence ope a ion. P oposi ion 4 P 0sa is ies he condi ions (1)-(3) in De ini ion 2. P oo . (1) is ob ious. (2) Le InXbe he se o in e p e a ions, whe e |β|I=1 o e e y o mula β in X. I elemen s o Xa e consequences o Y, hen InY⊆InX. Whe eas InX⊆InP 0(X), hus InY⊆InP 0(X). (3) I α∈P 0(X), hen InX∩In¬α=∅. Because o compac ness heo em in CPL, i InX∩In¬α=∅, hen he e exis s a ini e se Ysuch ha Y⊆X and InY∩In¬α=∅also. Thus, Yis a ini e subse o Xand α∈P 0(Y).  3 Axioma ic ea men o logics Ano he me hod o cons uc logics is he axioma ic (syn ax-based) way. Le Lbe a logic language wi h he se Fo o mulas. De ini ion 5 A ini e subse Ao o mulas is called an axiom sys em. 6K. P. Va ga, G. Alagi, M. V´a e ´esz De ini ion 6 A ule o e Fis a nonemp y ela ion ⊆{(α1,...,αm, α)|α1,...,αm, α ∈F}. De ini ion 7 Le Abe an axiom sys em, Ra se o ules and Xany se o o mulas. A o mula αis de i ed om Xi he e is a ini e sequence o o mulas α1,...,αksuch ha (1) αk=α, and (2) o each i(1≤i≤k),ei he αi∈X∪A, o he e exis indices i1,...,il smalle han isuch ha (αi1,...,αil, αi)∈ o some ule ∈R. P oposi ion 8 P ∗:X→{α|αis de i ed om X}sa is ies condi ions (1)- (3) in De ini ion 2. P oo . (1) is ob ious. (3) can be seen easily. I α∈P ∗(X), he de i a ion o αis a ini e sequence o o mulas. Le Ybe he se o o mulas o Xoccu ing in his de i a ion. Clea ly, αcan be de i ed om Y, as well. (2) I αcan be de i ed om X, because o (3), he e is a ini e Z⊆Xsuch ha αcan be de i ed om Z. Bu e e y elemen o Zcan be de i ed om Y, i.e. om some ini e subse o Y. I we conca ena e he de i a ions o he elemen s o Z om Yand u he mo e, we add he de i a ion o α om Z o i , hen he esul is a de i a ion o α om Y. He ewi h, condi ion (2) holds.  In o mally, a p oposi ional logic is axioma ically gi en by hL, A, R, P ∗i, i i s language algeb a Lis speci ied, an axiom sys em Ais ixed, a ini e se Ro de i a ion ules is speci ied and P ∗is he consequence ope a ion. An axioma ically gi en p oposi ional logic (calculus) hL, A, R, P ∗iis said o be (s ongly) adequa e o a p oposi ional logic hL, M, In, P ii hei conse- quence ope a ions a e he same. Many- alued logics . . . 7 Example 9 By a classical p oposi ional calculus we mean a quad uple hL∗, A, R, P ∗i, whe e (a) L∗is he ee language algeb a hV, (¬,⊃), Fiwi h signa u e (1, 2); (b) he axiom sys em Aconsis s o he axioms {α⊃(β⊃α),(α⊃(β⊃γ)) ⊃((α⊃β)⊃(α⊃γ)), (¬α⊃β)⊃((¬α⊃¬β)⊃α)}; (c) he se Rcon ains he single de i a ion ule α, α ⊃β β; (d) and P ∗:X→{α|αis de i ed om X}is he consequence ope a ion. The classical p oposi ional calculus hL∗, A, R, P ∗iis adequa e o he classical p oposi ional logic hL∗, M∗, In, P 0i, whe e M∗is a logical ma ix o L∗. 4 P oposi ional many- alued logics By he li e a u e [1], [2] and [3], a non-classical logic may be an ex ended logic and/o a de ian logic. ”Ex ended logics expand classical logic by addi ional logical cons uc s. Fo example, in modal logic modal ope a o s a e added o classical logic o exp ess modal no ions. In con as , de ian logics a e i als o classical logic ha gi e up some classical p inciples. In many- alued logics, we allow o many u h- alues ins ead o wo u h- alues (we gi e up he p inciple o bi alence)”. This de ia ion leads o he ex ension o he ope a ions o he classical wo- alued logic. An ope a ion is ex ended i , whene e he a gumen s a e classical u h- alues, he esul has he same u h- alue as i does in classical logic. ”In his sense, classical logic can be hough o as a special case o many- alued logic.” Le Unbe a se o u h- alues {0, 1, 2, . . . , n −1}(n≥2). Fo mally, we can de ine a p oposi ional many- alued logic (MVPL) as a quad uple hL, M, In, P ni, whe e 8K. P. Va ga, G. Alagi, M. V´a e ´esz (a) L=hV, Con, Fiis a language algeb a wi h a signa u e σ. (b) M=hUn, Op, U∗ niis a logical ma ix o L, whe e hUn, Opiis an algeb a o e Unwi h he signa u e σ, as well. Mo eo e , le S∈Un. Then U∗ n={S+1,...,n−1}is he se o he designa ed u h- alues, and 0, 1, . . . , S a e called non-designa ed ones. (c) In ={I|I:V→Unis an in e p e a ion o L}. (d) P n:P(F)→P(F)should be a consequence ope a ion. Now, we look o a consequence ope a ion. Le L=hV, Con, Fibe a language algeb a and le M=hUn, Op, U∗ nibe a logical ma ix o he language L. De ini ion 10 A o mula αis a weak seman ic consequence o a se Xo o mulas, deno ed as X|=Sα, i o any in e p e a ion in which he u h- alue o e e y o mula β∈Xis designa ed, he u h- alue o αis also designa ed. I Xis he emp y se , we ha e no cons ain o he in e p e a ions. Thus, αis said o be an S- au ology (∅|=Sα) i he u h- alue o αis designa ed o e e y in e p e a ion. We can gi e a mo e igo ous no ion o he consequence ela ion i we also ake he ex en o u h- alues o o mulas in o conside a ion. De ini ion 11 A o mula αis a s ong seman ic consequence o a se Xo o mulas, deno ed as X|=S∗α, i o any in e p e a ion in which he u h- alue o e e y o mula β∈Xis designa ed, he u h- alue o αis also designa ed wi h a leas he same u h- alue as he minimum o he u h- alues o o mulas in Xin he unde lying in e p e a ion. We need some u he no ions and a lemma o discuss he cha ac e is ic o he consequence ela ion simply. De ini ion 12 Le a pa ial in e p e a ion Ip be a o al in e p e a ion wi h espec o he se X∪{α}o o mulas. Xis app op ia e o αin Ip i he u h- alue o αis no less han he minimum o he u h- alues o o mulas in X, whene e his minimum is designa ed. Many- alued logics . . . 9 De ini ion 13 Xis ini ely bad o αwi h espec o a pa ial in e p e a ion Ip i o all ini e subse s Yo X he e exis s an ex ension o Ip in which Yis no app op ia e o α. Lemma 14 I Xis ini ely bad o αwi h espec o a pa ial in e p e a ion Ip and he a iable has no alue in Ip ye , hen he e is some j∈Unsuch ha Xis also ini ely bad o αwi h espec o he pa ial in e p e a ion Ip∪{( , j)}. P oo . O he wise, Xis no ini ely bad o αwi h espec o any pa ial in e p e a ion Ip ∪{( , i)}(i∈Un). So o all i, a ini e subse Yio Xwould exis such ha Yiwould be app op ia e o αin all o al ex ension o Ip∪{( , i)}. Thus, ∪n−1 i=0Yiis a ini e se and app op ia e o αin all o al ex ension o Ip. I means ha Xis no ini ely bad o αwi h espec o a pa ial in e p e a ion Ip. I is a con adic ion.  P oposi ion 15 P n S:X→{α|X|=Sα}and P n S∗:X→{α|X|=S∗α}a e consequence ope a ions. P oo . (1) is ob ious. (2) Fo e e y in e p e a ion I0, whe e q=minα∈X|α|I0> S,|γ|I0≥qholds o any γ∈P n S(X). Now, le Ibe an in e p e a ion, whe e |β|I> S o e e y o mula βin Y, and le pbe minβ∈Y|β|I. Acco ding o condi ion X⊆P n S(Y), we ge |α|I≥p>S o e e y α∈X. Thus, Iis an in e - p e a ion, whe e |γ|I≥pholds o all γ∈P n S(X). I means, we ha e P n S(X)⊆P n S(Y). (3) Now, le αbe a s ong consequence o X. Then αis also a weak conse- quence o X. Le us de ine a special kind o nega ion: ¬x0i x∈U∗ n, (n−1)o he wise Mo eo e , le InXcon ain all he in e p e a ions in which e e y o mula in Xhas designa ed u h- alue. I is clea ha X|=Sαi and only i InX∩In¬α=∅. Because o he compac ness heo em in MVPL (see in [4]), i InX∩In¬α=∅, hen he e exis s a ini e se Y0such ha Y0⊆Xand InY0∩In¬α=∅. 16 K. P. Va ga, G. Alagi, M. V´a e ´esz P oo . Le Ibe an in e p e a ion in which e e y o mula om Xand αa e designa ed. Acco ding o he condi ion, α⊃ ∗βis designa ed wi h u h- alue a leas minγ∈X{|γ|}. Because αis designa ed, i |α|≤|β|, hen |β|is designa ed wi h u h- alue a leas minγ∈X{|γ|,|α|}. In he case |α|>|β|,|α⊃ ∗β|=|β|, hus βis designa ed wi h u h- alue a leas min γ∈X{|γ|} ≥min γ∈X{|γ|,|α|}, as well.  Finally, all wha was p o ed abou examined implica ions a his sec ion we summa ized in he ollowing able: ⊃L⊃P⊃H⊃R⊃ ∗ modus ponens - + + + + deduc ion heo em wi h |=S- - - + + deduc ion heo em wi h |=S∗- - - - + 6 Sui able implica ion o a gi en consequence I is desi able ha bo h modus ponens and he deduc ion heo em hold wi h espec o he unde lying consequence. Now, we conside in wha manne we can gi e an implica ion o a gene ally gi en consequence such ha bo h modus ponens and he deduc ion heo em a e alid. Now, le ψ:U×U→{0, 1}be an a bi a y classical u h- alued unc ion wi h he ollowing p ope ies: (a) ψ(x, x) = 1 o all x∈U, (b) i ψ(x, y)∧ψ(y, z) = 1, hen ψ(x, z) = 1 o all x, y, z ∈U. Then, de ine he consequence as below: De ini ion 24 A o mula αis a o mal seman ic consequence o a se Xo o mulas, deno ed as X|=α, i _ γ∈X ψ(|γ|I,|α|I) = 1 o any in e p e a ion I, whe e Wγ∈Xψ(|γ|I,|α|I)deno es he sup emum o {ψ(|γ|I,|α|I)|γ∈X}. Many- alued logics . . . 17 P oposi ion 25 P :X→{α|X|=α}sa is ies condi ions (1)-(3) in De ini- ion 2. P oo . (1) Now o p o e he condi ion (1), le α∈X. Since in any in e p e a ion ψ(|α|,|α|) = 1, he e o e Wγ∈Xψ(|γ|,|α|) = 1, so X|=α. I means ha X⊆P (X). (2) Nex , le X⊆P (Y) o some X, Y ⊆F. We show ha P (X)⊆P (Y). –Fo any α∈P (X),since _ γ∈X ψ(|γ|I,|α|I) = 1, so _ γ∈P (Y) ψ(|γ|I,|α|I) = 1. I means P (X)⊆P (P (Y)). –Now, we show ha P (P (Y)) = P (Y). Since P (Y)⊆P (P (Y)) by he p ope y (1), i is enough o p o e, ha α∈P (Y) o all α∈P (P (Y)). Ob iously Y⊆P (Y). Le Y0deno e he se P (Y) Yand le α∈ P (P (Y)). Then _ γ∈P (Y) ψ(|γ|I,|α|I) = _ γ∈Y0∪Y ψ(|γ|I,|α|I) = 1. I _ γ∈Y0 ψ(|γ|I,|α|I) = 0, hen _ γ∈Y ψ(|γ|I,|α|I) = 1. And i _ γ∈Y0 ψ(|γ|I,|α|I) = 1, hen he e exis s a γ0∈Y0 o which ψ(|γ0|I,|α|I) = 1. Bu γ0∈ P (Y)also holds, hus _ γ∈Y ψ(|γ|I,|γ0|I) = 1 mus hold, i.e. he e exis s a γ00 ∈Y o which ψ(|γ00|I,|γ0|I) = 1. Using he p ope y (b) o ψwe ge ψ(|γ00|I,|α|I) = 1, ha is _ γ∈Y ψ(|γ|I,|α|I) = 1. Thus in bo h cases, we ge α∈P (Y). 18 K. P. Va ga, G. Alagi, M. V´a e ´esz –Since X⊆P (Y), hus P (X)⊆P (P (Y)), and he eby P (X)⊆ P (Y)mus hold. (3) We p o e compac ness by educing he p oblem o he compac ness o i s -o de logic wi h equali y. Fi s , le us de ine he language o ou encoding: –We ha e a single bina y p edica e symbol ^ ψ. –Fo each many- alued ope a ion o, we ha e a co esponding unc- ion symbol ^owi h he same a i y. –Fo each a iable , we ha e a co esponding cons an c . –Fo each u h- alue u, we ha e an addi ional cons an ^u. Gi en his language, we migh ix he in e p e a ion o ou symbols by de ining a se Σo he ollowing axioms: (i) ∀x(x= ^u1∨x= ^u2∨· · · ∨x= ^un)i U={u1, u2,...,un} (ii) ^u6=^ u0 o each u, u0∈Uwi h u6=u0 (iii) ^ ψ(^u, ^ u0)i ψ(u, u0) = 1and u, u0∈U (i ) ¬^ ψ(^u, ^ u0)i ψ(u, u0) = 0and u, u0∈U ( ) ^o( ^a1,^a2,..., ^ak) = ^ui ois an ope a o wi h a i y k,a1, a2,..., ak, u ∈U, and o(a1, a2, . . . , ak) = u Since Uis ini e, Σis a ini e se o i s -o de o mulas as well. I is easy o see ha i ^ Iis a i s -o de model o Σ, hen he e is a co esponding many- alued in e p e a ion Iwhich assigns he same alues o a iables as did ^ I o he co esponding cons an s. Le ^αdeno e he encoding o a o mula αin his language, i.e. he i s -o de o mula we ge om αby subs i u ing each symbol wi h he co esponding i s -o de symbol. By ou de ini ions, i Iand ^ Ia e co - esponding many- alued and i s -o de in e p e a ions, |α|I=ui and only i |^α|^ I= ^u. Thus, o each α,β, we ha e ψ(|α|I,|β|I)holds i and only i ^ ψ(^α, ^ β)holds in ^ I. Now, by ou assump ions, X|=αi and only i Wγ∈Xψ(|γ|I,|α|I)holds o all in e p e a ion I. This, on he o he hand, holds i and only i he se Γ={ ¬ ψ(|γ|I,|α|I)|γ∈X}is no sa is ied unde any in e p e a ion I. Conside he i s -o de se ^ Γ=Σ∪{ ¬ ^ ψ(^γ, ^α)|γ∈X} Many- alued logics . . . 19 F om ou conside a ions i ollows ha ^ Γis unsa is iable i and only i he o iginal Γis unsa is iable. Then, by he compac ness o i s -o de logic, we know ha he e is a ini e ^ Γ0⊆^ Γsuch ha ^ Γ0is unsa is iable. Since Σis ini e, we migh assume Σ⊆^ Γ0. Now, le X0 he ini e se {γ∈X| ¬ ^ ψ(^γ, ^α)∈^ Γ0}. We know ha he co esponding se Γ0={ ¬ ψ(|γ|I,|α|I)|γ∈X0}is no sa is ied by any Iei he . The e o e, X0|=αmus hold whe e X0is a ini e subse o X.  P oposi ion 26 Le ⊃be an implica ion ope a ion o e U. I ψ(x1, x2)∨ψ(y, x2) = ψ(y, x1⊃x2) o all x1, x2, y ∈U, hen ⊃admi s modus ponens and he deduc ion heo em. P oo . Fi s , we p o e modus ponens, i.e. we show, ha {α, α ⊃β} |=βholds o any o mulas α, β. Fo all α, β ∈Fand o all I∈In we ge ψ(|α|I,|β|I)∨ψ(|α⊃β|I,|β|I). Fo all x1, x2∈U, by applying he p oposed equali y ψ(x1, x2)∨ψ(x1⊃x2, x2) = ψ(x1⊃x2, x1⊃x2) = 1. To p o e he deduc ion heo em, we ha e o show o any α, β, X X, α |=βi and only i X|=α⊃β. Again, applying ou assump ions o bo h sides, we ge o all I∈In _ γ∈X ψ(|γ|I,|β|I)∨ψ(|α|I,|β|I) = _ γ∈X (ψ(|γ|I,|β|I)∨ψ(|α|I,|β|I)) i and only i o all I∈In _ γ∈X ψ(|γ|I,|α|I⊃|β|I). F om ou assump ion wi h y=|γ|I, x1=|α|I, x2=|β|I, we ge ψ(|γ|I,|β|I)∨ψ(|α|I,|β|I) = ψ(|γ|I,|α|I⊃|β|I), om which he desi ed equi alence immedia ely ollows.  In he emaining pa o he sec ion we apply his p oposi ion o he ea lie de ined seman ic consequences. 20 K. P. Va ga, G. Alagi, M. V´a e ´esz Example 27 By De ini ion 10, X|=Sαi and only i min γ∈X{|γ|I}≤S∨S < |α|I o all I∈In. Thus, o his case we ge ψ(x, y) = (x≤S∨S<y).To ind a sui able implica ion, i is enough o sa is y (x1≤S∨S<x2)∨(y≤S∨S<x2)i and only i (y≤S∨S<x1⊃x2) o all x1, x2, y ∈U. Le , h :U×U→Usuch ha o all x1> S and x2≤S (x1, x2)≤Sand i x1≤So x2> S, hen h(x1, x2)> S. Then, as we ha e seen abo e, he implica ion de ined below admi s modus ponens and he deduc ion heo em: x1⊃ ,h ∗x2h(x1, x2)i x1≤So x2> S, (x1, x2)o he wise. Example 28 By De ini ion 11, X|=S∗αi and only i min γ∈X{|γ|I}≤S∨min γ∈X{|γ|I}≤|α|I o all I∈In. Fo his case we ge ψ(x, y) = x≤S∨x≤y. Thus o ind a sui able implica- ion, i is enough o sa is y (x1≤S∨x1≤x2)∨(y≤S∨y≤x2)i and only i (y≤x1⊃x2∨y≤S) o all x1, x2, y ∈U. The possible alues o x1⊃x2migh be deduced as ollows: •x1≤S∨x1≤x2: since he igh side mus also hold, e en o y=n−1, we ge x1⊃x2=n−1, which is indeed a good choice. •x1≥x2> S: o y=x2we ge x2≤x1⊃x2, and o y=x2+1 x1⊃x2< x2+1. Thus only x1⊃x2=x2is possible, and i indeed sa is ies he equali y in his case. •x1> S ≥x2: o y > S we ge x1⊃x2≤S. In his case any alue smalle han Ssa is ies he equali y. Le :U×U→Ube such ha o all x1> S and x2≤S (x1, x2)≤S. Then, as we ha e seen abo e, he implica ion de ined below admi s modus ponens and he deduc ion heo em: x1⊃ ∗x2   n−1i x1≤So x1≤x2, x2i x1> x2> S, (x1, x2)o he wise. Many- alued logics . . . 21 7 Summa y In his pape we demons a ed ha bo h seman ic and syn ac ic consequences o classical logic esul consequence ope a o s. We p o ed simila p oposi ions abou he weak and s ong consequences in he many- alued logic. A e his, we in es iga ed he Lukasiewicz, Pos , Hey ing and Rosse s yle many- alued implica ions whe he he modus ponens ule and he deduc ion heo em a e alid beside o ou consequence ela ions. By he s ong consequence, he de- duc ion heo em is no alid wi h none o hem. Howe e , he implica ion amily ⊃ ∗de ined in ou pape ound o comply wi h he modus ponens and he deduc ion heo em by he s ong consequence as well. The las sec ion, we in oduced a gene al o mal consequence ela ion and showed, ha i also leads o a consequence ope a o . The weak and s ong consequence de ini ions a e ealiza ions o his gene al consequence no ion. I would be p o i able o conside wha addi ional ealiza ions a e possible. By his gene al consequence, we also ga e a sui able implica ion which admi s he modus ponens and he deduc ion heo em as well. Acknowledgemen s The publica ion is suppo ed by he T´ AMOP-4.2.2/B-10/1-2010-0024 p ojec . The p ojec is co- inanced by he Eu opean Union and he Eu opean Social Fund. Re e ences [1] M. Be gmann,An In oduc ion o Many-Valued and Fuzzy Logic: Seman ics, Algeb as, and De i a ion Sys ems,Camb idge Uni e si y P ess, 2008. ⇒7 [2] L. Bolc, P. Bo owik, Many- alued Logics. Vol.1. Theo e ical Founda ions, Sp inge -Ve lag, Be lin, 1992. ⇒7 [3] R. H¨ahnle,G.Escalada-Imaz,Deduc ion in Many- alued Logics: a Su ey, Ma h- wa e and So Compu ing 4, 2 (1997) 69-97. ⇒7 [4] J.-L. Lee, On compac ness heo em, p esen ed in: Taiwan Philosophical Associ- a ion 2006 Annual Mee ing, (2006) pp. 1-11. ⇒9 [5] K. P´asz o Va ga, M. V´a e ´esz,Many- alued logic, mappings, ICF g aphs, no - mal o ms, Annales Uni . Sci. Budapes . de R. E¨o ¨os Nom. Sec . Compu a o ica 31 (2009) 185–202. ⇒3 [6] J. B. Rosse , A. R. Tu que e, Many- alued Logics. S udies in Logic and Foun- da ions o Ma h., No h-Holland Publishing Co., Ams e dam, 1952. ⇒13 22 K. P. Va ga, G. Alagi, M. V´a e ´esz [7] A. Ta ski, On some undamen al concep s o me ama hema ics, in: Logic, Se- man ics and Me ama h., Cla endon P ess, Ox o d, 1956, pp. 30–38. ⇒4 Recei ed: •Re ised: