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: