LOGIKA hetkoznapi jelentese: a rendszeresseg, kovetkezetesseg szinonimaja { Ez logikus beszed volt. { Nincs benne logika. { Mas logika szerint gondolkodik. tudomanyszak elnevezese, melynek
feladata
a helyes kovetkeztetes { fogalmanak szabatos meghatarozasa, { torvenyeinek feltarasa.
Kovetkeztetes gondolati eljaras adott ismeretek
=)
uj ismeret
#
nyelvi megnyilvanulas
#
kijelent}o mondatok
premisszak
kijelent}o mondat
konkluzio
Helyes a kovetkeztetes (koznapi ertelemben!), ha a premisszak igaz volta eseten a konkluzio is igaz. Pelda. (premissza:) Imrenek tud}ogyulladasa van. (konkluzio:) Imrenek antibiotikumot kell szednie. A logika nem tartalmaz egyetlen mas szaktudomanyt sem, gy nem ismerheti ezek eredmenyeit!! potpremissza: Ha valakinek tud}ogyulladasa van, antibiotikumot kell szednie. Pelda. (1. premissza:) Erika Sandornak a felesege. (2. premissza:) Katalin Sandornak az edesanyja. (konkluzio:) Katalin Erikanak az anyosa. A logika nem vizsgalja a (magyar) nyelv szavainak jelenteset!! potpremissza: Ha x y-nak a felesege, es z y-nak az edesanyja, akkor z x-nek az anyosa.
Egy kovetkeztetes logikai vizsgalata soran mit hasznalunk fel a mondatokbol? logikai szavakat: nem : negacio es ^ konjunkcio vagy _ diszjunkcio ha : : : akkor implikacio minden 8 univerzalis kvantor van 9 egzisztencialis kvantor a mondatreszek, szavak jelentese kozombos, helyettuk
{ termek { atomi formulak
+
LOGIKAI NYELV Miert van szuksege a logikanak sajat nyelvre? a logika nem tartozhat egyetlen nemzeti nyelvhez sem; a termeszetes nyelvek nyelvtani rendszerei kulonboz}oek es bonyolultak; a logika sajat nyelveben minden (abc, nyelvtani szabalyok, kategoriak) a logika feladatanak ellatasat szolgalhatja.
Logikai nyelv
szintaktika ! szemantika
A lltas: olyan kijelent}o mondat, melyr}ol modunkban all egyertelm}uen eldonteni, hogy igaz vagy hamis. Pelda.
alltas
nem alltas
5<3 XV. Lajos parokat viselt.
x<3
A most uralkodo francia kiraly parokat visel. Peter hazudik. Most epp hazudok. A Fold a Nap korul kering. Nincs elet a Foldon kvul. Klasszikus szemantika: (Arisztotelesz) az ellentmondastalansag elve: Egyetlen alltas sem lehet igaz is es hamis is. a kizart harmadik elve: Nincs olyan alltas, amely sem nem igaz, sem nem hamis. modern logika - szimbolikus logika - mat. logika
Logikai szavak A negacio: Alfred diak. Alfred nem diak. DE: A javaslatot az ellenzek buktatta meg. A javaslatot nem az ellenzek buktatta meg. Nem igaz, hogy a javaslatot az ellenzek buktatta meg. A konjunkcio: Amalia es Bella kerteszek. "Lement a nap. De csillagok nem jottenek." (Pet}o ) Juli is, Mari is tancol. Kevesre vitte, noha becsuletesen dolgozott. DE: Amalia es Bella testverek. A diszjunkcio: Esik az es}o, vagy fuj a szel. Vagy busszal jott, vagy taxival.
Az implikacio:
Ha megtanulom a lecket, akkor otosre felelek. Csak akkor felelek otosre, ha megtanulom a lecket.
Gyakran az egyszer}u alltasok szerkezetet is fel kell tarnunk. Dezs}o postas. Amalia es Bella testverek. Az Erzsebet hd osszekoti Budat Pesttel. predikatum + objektumnevek
Az univerzalis kvantor: Amalia mindegyik testvere lany. Az egzisztencialis kvantor: Amalianak van testvere.
Az els}orend}u logikai nyelv
A llando szimbolumok logikai jelek: : ^ _ 8 9 elvalaszto jelek: ( ) ; De nialando szimbolumok (negy halmazba sorolva)
=< Srt; Cnst; Fn; Pr > Srt, elemei a tpusok. Minden 2 Srt tpushoz tartoznak valtozok: x ; x ; : : : Cnst konstansok halmaza. Minden c 2 Cnst valamely 2 Srt tpushoz tartozik. Fn fuggvenyszimbolumok halmaza. Minden f 2 Fn fuggvenyszimbolumot a ( ; ; : : : ; k ! ) un. alakja jellemez. (k 1) Pr 6= ; predikatumszimbolumok halmaza. Minden P 2 Pr predikatumszimbolumhoz egy ( ; ; : : : ; k ) alakot rendelunk. (k 0) 1
1
2
1
2
2
Peldak logikai nyelvekre 1. A Geom nyelv Srt = fpt (ponttpus); et (egyenestpus); st (sktpus)g pt tpusu valtozok: A; B; C ; : : : et tpusu valtozok: e; f; g; : : : st tpusu valtozok: a, b, c,: : : Cnst = ; Fn = ; Pr = fP pt;pt ; Q pt;et ; R pt;st g Megjegyzes: a geometriaban a P; Q; R szimbolumok helyett rendre az =; 2; 2 jeleket szokas inkabb hasznalni. 2. Az Ar nyelv Srt = fszt (szamtpus)g szt tpusu valtozok: x; y; z; : : : Cnst = fnullag Fn = ff szt!szt ; g szt;szt!szt ; h szt;szt!szt g Pr = fP szt;szt g Megjegyzes: az aritmetikaban a g es h szimbolumok helyett a + es jeleket, P helyett pedig az = jelet szokas hasznalni. 3. nulladrend}u nyelvek
=< ;; ;; ;; Pr >, ahol minden P 2 Pr alakja (), azaz P propozcionalis bet}u. (
)
(
(
(
)
)
)
(
(
)
)
(
)
logikai kifejezesek tpusu termek c, ha c 2 Cnst; x, ha x valtozo; f (t ; t ;: : : ; tk ), ha f ( ; ; : : : ; k ! ) 2 Fn 1
1
2
2
es t 1 ; t 2 ; : : : ; tkk termek; minden term { vagy a nyelv konstansa, vagy valtozoja, { vagy az indukcios lepes veges sokszori alkalmazasaval bel}oluk nyerhet}o. 1
2
formulak P (t ; t ; : : : ; tk) atomi formula , ha P ; ;:::; 2 Pr es t ; t ; : : : ; tk termek; (A ^ B ); (A _ B ); (A B ) es :A; 1
2
( 1
2
k)
1
1
2
2
k
ha A es B formulak; 8xA es 9xA; ha A formula es x tetsz}oleges valtozo; minden formula { vagy atomi formula, { vagy az indukcios lepesek veges sokszori alkalmazasaval atomi formulakbol megkaphato.
Peldak logikai kifejezesekre 1. A Geom nyelv kifejezesei: termek: A; f; b atomi formulak: a geometriaban szokasosan P (A; B) (A = B) Q(B; e) (B 2 e) R(A; a) (A 2 a) formula: 9A(Q(A; e)^Q(A; f )) 9A((A 2 e)^(A 2 f )) 2. Az Ar nyelv kifejezesei: termek: az arimetikaban szokasosan nulla; x; f (nulla) g(x; f (nulla)) (x + f (nulla)) h(f (f (x)); x) (f (f (x)) x) atomi formula: P (g(x; f (nulla)); nulla) ((x+f (nulla)) = nulla) formula: 9uP (g(x; u); y) 9u((x + u) = y)
kozvetlen reszterm valtozonak es konstansnak nincs kozvetlen resztermje; az f (t ; t ; : : : ; tk) term kozvetlen resztermjei a 1
2
t ; t ; : : : ; tk termek. 1
2
Jeloles:
4 Q ^_ 89 kozvetlen reszformula atomi formulanak nincs kozvetlen reszformulaja; a :A kozvetlen reszformulaja az A formula; az (A4B ) formula kozvetlen reszformulai az A es a B formulak; a QxA formula kozvetlen reszformulaja az A formula.
reszkifejezes maga a kifejezes; a kozvetlen reszkifejezesek; reszkifejezesek reszkifejezesei.
funkcionalis osszetettseg (jele: ~l(t)) ) 0; ha t = c 2 Cnst; vagy t = x, akkor ~l(t) * ) Pki ~l(ti) + 1: ~l(f (t ; t ; : : : ; tk)) * logikai osszetettseg (jele: l(A)) ) 0; ha A atom, l(A) * ) l(A) + 1; l(:A) * ) l(A) + l(B ) + 1; l(A4B ) * ) l(A) + 1: l(QxA) * 1
2
=1
A formulak lerasakor szokasos rovidtesek: formula-kombinaciok helyett specialis jelolesek; Pelda. ) ((A B ) ^ (B A)) (A B ) * kuls}o zarojelek elhagyasa; logikai jelek prioritasa csokken}o sorrendben:
8:_ 9 ^
azonos prioritas eseten a jobbra allo az er}osebb; jobbrol allo pont jeloli a zarojelen beluli leggyengebb logikai jelet.
Qx A
""
kvantoros el}otag a kvantor hataskore Egy valtozo valamely el}ofordulasa a formulaban kotott: Egy atomi formula egyetlen valtozoja sem kotott. A :A-ban x egy adott el}ofordulasa kotott, ha A-ban x-nek ez az el}ofordulasa kotott. Az A4B -ben x egy adott el}ofordulasa kotott, ha ez az el}ofordulas vagy A-ban van, es ott kotott, vagy B -ben van, es ott kotott. A QxA-ban x minden el}ofordulasa kotott, es az x-t}ol kulonboz}o y egy adott el}ofordulasa kotott, ha ez az el}ofordulas A-ban kotott. Egy valtozo valamely el}ofordulasa a formulaban szabad, ha nem kotott. Ha egy valtozonak egy formulaban van szabad el}ofordulasa, akkor ez a valtozo a formula parametere. Jelolesek: Fv(A): az A formula parametereinek a halmaza. A(x ; x ; : : : ; xn): formula, melyben legfeljebb az x ; x ; : : : ; xn valtozok lehetnek parameterek. 1
1
2
2
A kotott valtozok atnevezese
A QxA-ban x-nek a Q kvantor altal kotott minden el}ofordulasat az x-szel azonos tpusu y valtozora cserelve kapunk egy QyAxy formulat. Milyen formulat eredmenyez ez az atalaktas? Az Ar nyelven a termeszetes szamok halmazaban a 9x(u + x = v); 9y(u + y = v); 9z(u + z = v) formulak mindegyike a (u v) relaciot fejezi ki. Vigyazat!! A
9u(u + u = v)
formula viszont v parossagat alltja. A jelentesvaltozas oka a valtozoutkozes. Pelda: 8x(P (x; z) 9yR(x; y)) Az x y-ra atnevezesevel a 8y(P (y; z) 9yR(y; y)) formulat kapjuk!!
A kotott valtozok szabalyosan vegrehajtott atnevezese
Ha a QxA formulaban az y nem parameter, es az x valtozo egyetlen Q altal kotott el}ofordulasa sem tartozik egyetlen y-t kot}o kvantor hataskorebe sem, akkor a QxA-bol a QyAxy formulat az x kotott valtozo szabalyosan vegrehajtott atnevezesevel kaptuk. Az A es A0 kongruens formulak, ha egymastol csak kotott valtozok szabalyosan vegrehajtott atnevezeseben kulonboznek. Jelolese: A A0 A kongruencia egy nyelv formulai halmazaban re exv, szimmetrikus es tranzitv relacio. Osztalyozast general: az egy kongruenciaosztalyba tartozo formulak kozott a logikaban nem teszunk kulonbseget.
Hogyan donthetjuk el, hogy ket formula kongruense? a formula osszetettsege szerinti indukcioval: { Egy atomi formula egyetlen mas formulaval sem kongruens, csak onmagaval. { :A :A0, ha A A0. { A 4 B A0 4 B 0, ha A A0 es B B 0. { QxA QyA0, ha minden z -re, mely kulonbozik QxA es QyA0 (kotott es szabad) valtozoitol, Axz A0yz . a formula vazaval { rajzoljuk be a formulaban a kotesi viszonyokat; { hagyjuk el az osszekotott valtozokat. Ket formula pontosan akkor lesz egymassal kongruens, ha megegyez}o a vazuk.
Egy formula valtozo-tiszta, ha benne a kotott valtozok nevei kulonboznek a szabad valtozok neveit}ol; barmely ket kvantor kulonboz}o nev}u valtozokat kot meg.
Lemma.
Legyen A egy formula es S valtozoknak egy veges halmaza. Ekkor konstrualhato olyan valtozo-tiszta A0 formula, hogy A A0 , es A0 egyetlen kotott valtozojanak neve sem eleme S -nek.
A szabad valtozok helyettestese termekkel
Az Ar nyelvben a termeszetes szamok halmazaban szeretnenk kifejezni az (x z z ) relaciot. Ha az (x y)-t kifejez}o 9u(x + u = y) formulaban y helyere z z -t helyettestunk, a kvant 9u(x + u = z z) formula megkaphato. Vigyazat! Ha az (x z u) relaciot akarjuk kifejezni hasonlo modon eljarva, nem a kvant formulat, hanem az 9u(x + u = z u) kapjuk. A problema oka a valtozoutkozes. Megoldas: Nevezzuk at a kotott valtozot peldaul w-re, es csak utana hajtsuk vegre a termhelyettestest: 9w(x + w = z u)
A formalis helyettestes
Egy x valtozonak es egy vele megegyez}o tpusu t termnek a parosat bindingnek nevezzuk. Jelolese: x=t. A formalis helyettestes bindingek egy = fx =t ; x =t ; : : : ; xk =tk g halmaza, ahol xi 6= xj ; ha i 6= j (i; j = 1; 2; : : : ; k; k 0): 1
1
2
2
A helyettestest megadhatjuk meg tablazattal: 0
1 k CC A
= BB@ xt xt :: :: :: xt ; k amit egy sorba is rhatunk: = (x ; x ; : : : ; xk jjt ; t ; : : : ; tk ): A helyettestes ertelmezesi tartomanya: dom = fx ; x ; : : : ; xkg ertekkeszlete: rng = ft ; t ; : : : ; tkg 1
2
1
2
1
2
1
2
1
1
2
2
Egy kifejezesbe valo formalis helyettestes eredmenye Legyen K logikai kifejezes, = fx =t ; x =t ; : : : ; xk =tk g 1
1
2
2
formalis helyettestes. Az xi valtozok osszes K -beli szabad el}ofordulasat helyettestsuk egyidej}uleg K ban a ti termekkel. Az gy kapott kifejezes a K ba valo formalis helyettestesenek eredmenye. Jelolese: ;:::;xk K ; vagy Ktx11;:::;t k Egy kifejezesbe valo formalis helyettestes eredmenyenek meghatarozasa: 8 > <x x 62 dom x = >: (x) ha ha x 2 dom f (t ; t ; : : : ; tk ) = f (t ; t ; : : : ; tk ) P (t ; t ; : : : ; tk) = P (t ; t ; : : : ; tk) (:A) = :(A) (A4B ) = A4B (QxA) = Qx(A( , x)), ahol , x azt a helyettestest jeloli, melyre dom ( , x) = (dom ) n fxg; es ( , x)(z ) = (z ) minden z 2 dom ( , x)-re. 1
1
2
2
1
2
1
2
Egy kifejezes szamara megengedett helyettestes megengedett a K kifejezes szamara, ha egyetlen xi 2 dom -nak egyetlen K -beli szabad el}ofordulasa sem esik a (xi) term valamely valtozoja szerinti kvantor hataskorebe. Pelda. A 9u(x + u = y) formula szamara fy=z zg megengedett, de fy=z ug nem. Annak meghatarozasa, hogy egy helyettestes megengedett-e egy kifejezes szamara: Termek es atomi formulak szamara minden megengedett. :A szamara megengedett, ha megengedett A szamara. A4B szamara megengedett, ha megengedett mind A, mind B szamara. QxA szamara megengedett, ha { , x megengedett A szamara, es { egyetlen z 2 Fv(QxA) \ dom eseten sem szerepel x a (z ) termben.
A szabalyos helyettestes
Legyen K egy kifejezes, es egy helyettestes. Keressunk K -val kongruens olyan K 0 kifejezest, mely szamara a helyettestes megengedett. Ekkor a K 0 kifejezes a szabalyos helyettestesenek eredmenye K -ba. Jelolese: [K ]. A szabalyos helyettestes eredmenyenek meghatarozasa: Ha K term vagy atomi formula, akkor [K ] = K . [(:A)] = :[A] [(A4B )] = [A]4[B ] { Ha egyetlen z 2 Fv(QxA) \ dom eseten sem szerepel x a (z ) termben, akkor [(QxA)] = Qx[A( , x)]. { Ha van olyan z 2 Fv(QxA) \ dom , hogy x parameter (z )-ben, akkor valasszunk egy uj valtozot, peldaul u-t, mely nem szerepel sem QxA-ban, sem -ban, es [(QxA)] = Qu[(Axu)( , x)].
A logikai nyelv klasszikus szemantikaja
Az =< Srt; Cnst; Fn; Pr > els}orend}u logikai nyelv I interpretacioja (modellje, algebrai strukturaja) egy olyan d d d d I =< Srt; Cnst; Fn; Pr > fuggvenynegyes, melyben d d dom Srt = Srt; es Srt : 7! D , ahol a D objektumtartomany a tpusu objektumok nemures halmaza; d d dom Cnst = Cnst; es a Cnst : c 7! c~ fuggveny olyan, hogy ha a c tpusu konstans, akkor c~ 2 D ; d d dom Fn = Fn; es az Fn : f 7! f~ fuggveny minden f 1;2;:::;k! fuggvenyszimbolumhoz olyan f~ fuggvenyt rendel, melyben dom f~ = D1 D2 : : : Dk , es rng f~ = D , azaz f~ : D1 D2 : : : Dk ! D ; d d dom Pr = Pr; es a Pr : P 7! P~ fuggveny olyan, hogy a P 1;2;:::;k (k 1) predikatumszimbolum eseten, P~ : D1 D2 : : : Dk ! f0; 1g, ha pedig P propozcionalis bet}u, akkor P~ vagy 0, vagy 1. (
)
(
)
Legyen az nyelv I interpretaciojaban d ) 2[Srt D n fc~jCnst D* (c) = c~; c 2 Cnstg:
B}ovtsuk ki a nyelvet az objektumtartomanyok objektumait jelol}o uj konstansokkal:
(D) =< Srt; Cnst(D); Fn; Pr >; ahol ) Cnst[faja az a 2 D-hoz rendelt uj szimbolumg: Cnst(D) * Az (D) nyelv zart logika kifejezeseit I -beli ertekelhet}o kifejezeseinek nevezzuk. Az (D) nyelv formalis helyettesteset I -beli ertekel}o helyettestesenek nevezzuk, ha Fv(rng ) = ;: Egy ertekel}o helyettestes minden K kifejezes szamara megengedett. Ha a ertekel}o helyettestes es a K kifejezes olyanok, hogy Fv(K ) dom ; akkor K ertekelhet}o kifejezese -nak, es -at K I -beli ertekelesenek nevezzuk.
Pelda. 1. Az Ar nyelv termeszetes interpretacioja d Srt (szt) = N d Cnst (nulla) = 0 d Fn (f ) = f;~ ahol f~ : N ! N ; es f~(n) = n + 1; ( ha n 2 N ) d Fn (g) = g~; ahol g~ : N N ! N ; es g~(n; m) = n + m; ( ha n; m 2 N ) d Fn (h) = h~ ; ahol h~ : N N ! N ; es h~ (n; m) = n m; ( ha n; m 2 N ) d ~ ahol P~ : N N ! f0; 1g; Pr (P ) = P; es (ha n; m 2 N ); 8 > < 1 ha n = m ~ P (n; m) = >: 0 egyebkent 2. A Subset nyelv Srt = frh (egy alaphalmaz reszhalmazai) g rh tpusu valtozok: x; y; z : : : Cnst = ; Fn = ; Pr = fP rh;rh g A Subset nyelv egy interpretacioja d Srt (rh) = f a fpiros, kek, zoldg alaphalmaz reszhalmazai g d ~ ahol, ha S; Z az alaphalmaz ket reszhalmaza Pr (P ) = P; (
8 > < > :
)
1 ha S Z ~ P (S; Z ) = 0 egyebkent
Legyen I egy interpretacioja. Az tpusu, ertekelhet}o termenek erteke I ben egy D -beli objektum. Jelolese: jtjI d ) c~. { Ha Cnst (c) = c~, akkor jcjI * { Ha a 2 Cnst(D) az a 2 D objektumhoz ) a. rendelt uj a szimbolum, akkor jajI * { Ha f (t ; t ; : : : ; tk) ertekelhet}o term, ahol a t ; t ; : : : ; tk termek ertekei I -ben rendre d jt jI ; jt jI ; : : : ; jtkjI , es f~ = Fn (f ), akkor 1
1
2
2
1
2
) f~(jt jI ; jt jI ; : : : ; jtk jI ). jf (t ; t ; : : : ; tk)jI * Az ertekelhet}o formulajanak erteke I -ben vagy 0, vagy 1. Jelolese: jjC jjI { Ha P (t ; t ; : : : ; tk ) ertekelhet}o atomi formula, 1
2
1
1
2
2
ahol a t ; t ; : : : ; tk termek ertekei I -ben rendd re jt jI ; jt jI ; : : : ; jtk jI , es P~ = Pr (P ), akkor 1
1
2
2
) P~ (jt jI ; jt jI ; : : : ; jtk jI ). jjP (t ; t ; : : : ; tk )jjI * 1
2
1
2
{ Ha :A ertekelhet}o formula, ahol az A formula erteke jjAjjI , akkor ) 1 , jjAjjI : jj:AjjI * { Ha A4B ertekelhet}o formula, ahol az A es B formulak ertekei rendre jjAjjI ; jjB jjI , akkor ) minfjjAjjI ; jjB jjI g jjA ^ B jjI * ) maxfjjAjjI ; jjB jjI g jjA _ B jjI * ) maxf1 , jjAjjI ; jjB jjI g jjA B jjI * { Ha 8xA ertekelhet}o formula, ahol x tpusu valtozo, akkor 8 xjj = 1; > < 1; ha minden a 2 D eset e n jj A a I )> jj8xAjjI *
0 egyebkent. { Ha 9xA ertekelhet}o formula, ahol x tpusu valtozo, akkor 8 > < 1; ha van olyan a 2 D hogy jjAxajjI = 1; ) >: 0 egyebkent. jj9xAjjI * > :
Legyen I egy interpretacioja es A ertekelhet}o formula. Az A formula igaz I -ben (jelolese: I j= A), amikor jjAjjI = 1, egyebkent hamis I -ben.
Pelda. 1. Az Ar nyelv termeszetes interpretaciojaban
jnullaj = 0 jf (nulla)j = f~(jnullaj) = 1 ! ~ j(f (1) + 3)j!= g~ (jf (1)j; j3j) = g~ f (j1j); 3 = = g~ f~(1); 3 = g~(2; 3) = 5
jj ((f (nulla) 3) = (f (f (nulla)) + 1)) jj = P~ (jf (nulla) 3j; jf (f (nulla)) + 1j) = ! P~ h~ (jf (nulla)j; j3j) ; g~ (jf (f!!(nulla)) j; j1j) = ! P~ h~ (1; 3); g~ f~(jf (nulla)j); 1 = P~ 3; g~(f~(1); 1) = P~ (3; g~(2; 1)) = P~ (3; 3) = 1
jj9u ((3 + u) = 4) jj = 1; mert az 1 2 N olyan, hogy jj ((3 + u) = 4)u jj = jj (3 + 1 = 4) jj = P~ (j3 + 1j; j4j) = P~ (~g(j3j; j1j) ; 4) = P~ (~g(3; 1); 4) = P~ (4; 4) = 1 1
2. A Subset nyelv el}obbi interpretaciojaban
jjP (fpiros,zoldg; fpiros,kekg)jj = P~ (jfpiros,zoldgj; jfpiros,kekgj) = P~ (fpiros,zoldg; fpiros,kekg) = 0 jj8yP (y; fpiros,kek,zoldg)jj = 1;
mert minden S reszhalmazra jjP (S; fpiros,kek,zoldg)jj = P~ (jS j; jfpiros,kek,zoldgj) = P~ (S; fpiros,kek,zoldg) = 1
jj8yP (y; fpiros,kekg)jj = 0; mert peldaul az fzoldg reszhalmazra jjP (fzoldg; fpiros,kekg)jj = P~ (jfzoldgj; jfpiros,kekgj) = P~ (fzoldg; fpiros,kekg) = 0 3. A Subset nyelv egy olyan interpretaciojaban, ahol d Srt (rh) = ffpiros, kek, zold, sargag reszhalmazai g
jj8yP (y; fpiros,kek,zoldg)jj = 0; mert peldaul a fsargag reszhalmazra jjP (fsargag; fpiros,kek,zoldg)jj = P~ (jfsargagj; jfpiros,kek,zoldgj) = P~ (fsargag; fpiros,kek,zoldg) = 0
Lemma.
Legyen I az nyelv egy interpretacioja es r egy olyan term, melyben legfeljebb egy parameter, a tpusu x szerepel. Legyen a t tpusu ertekelhet}o term erteke jtjI . Ekkor jrfx=tgjI = jrfx=jtjI gjI ; azaz egy ertekelhet}o term erteke csak resztermjei ertekeit}ol fugg.
Lemma.
Legyen I az nyelv egy interpretacioja es A egy olyan formula, melyben legfeljebb egy parameter, a tpusu x szerepel. Legyen a t tpusu ertekelhet}o term erteke jtjI . Ekkor I j= [Afx=tg] akkor es csak akkor, ha I j= Afx=jtjI g:
Logikai torveny, logikai ellentmondas Az nyelv egy A formulaja logikai torveny, ha
barmely I interpretaciojaban es A barmely I -beli ertekelese eseten I j= A. Jelolese: j= A. Az nyelv egy A formulaja logikai ellentmondas, ha barmely I interpretaciojaban es A barmely I beli ertekelese eseten A hamis. Jelolese: =j A.
Lemma. =j A akkor es csak akkor, ha j= :A. Az nyelv egy A formulaja kielegthet}o, ha van
-nak olyan I interpretacioja es ertekelese, amelyre I j= A.
Lemma.
Az A formula pontosan akkor kielegthet}o, ha nem igaz, hogy j= :A. Az A es B formulak logikailag ekvivalensek, ha j= A B: Jelolese: A B .
A Boole-kombinacio Legyenek A ; A ; : : : ; An; n 1 az nyelv for1
2
mulai. A ; A ; : : : ; An Boole-kombinacioja Ai barmelyik 1 i n-re; :B , ha B A ; A ; : : : ; An Boole-kombinacioja; B 4C , ha ha B es C is A ; A ; : : : ; An Boolekombinacioi. Pelda. 8xP (x) _ 9yQ(x; y) a 8xP (x) es a 9yQ(x; y) Boole-kombinacioja. 1
2
1
2
1
2
A Quine-tablazat
Legyen B az A ; A ; : : : ; An Boole-kombinacioja. Kesztsuk el a kovetkez}o, 2n kulonboz}o sort tartalmazo tablazatot: 1
2
A A :::::: 0 0 :::::: 0 0 :::::: 0 0 :::::: 0 0 :::::: .. .. : : : : : : 1 1 :::::: 1
2
An, An, An B 0 0 0 0 .. 1
2
0 0 1 1 .. 1
1
0 1 0 1 .. 1
Megjegyzes: A sorok az A ; A ; : : : ; An formulak osszes kulonboz}o lehetseges ertekeit tartalmazzak, fuggetlenul attol, hogy van-e olyan interpretacio es kozos ertekeles, melyre ilyen ertekek adodnanak. Olyan interpretacio es kozos ertekeles viszont nincs, ahol a formulak ertekei rendre ne lennenek megtalalhatok valamely sorban. 1
2
Toltsuk ki a B alatti f}ooszlopot: minden sorban szamoljuk ki B erteket a kombinalotenyez}ok sorbeli ertekeinek fuggvenyeben. A Boole-kombinacio propozcionalis tautologia, ha a Quine-tablaja f}ooszlopaban csupa 1 ertek van.
Lemma.
Ha egy Boole-kombinacio propozcionalis tautologia, akkor logikai torveny.
Lemma.
Ha a Boole-kombinalo tenyez}ok propozcionalis bet}uk, es a Boole-kombinacio logikai torveny, akkor propozcionalis tautologia.
Pelda. 1. Vizsgaljuk az (A B ) :(A ^ :B ) formulat, mint az A es B formulak Boole-kombinaciojat. (A B ) : (A ^ : B ) 0 0 0 0 0 1 0 1 1 0 1 0 1 1 1 1 (A B ) : (A ^ : B ) 0 1 0 1 1 0 0 1 0 0 1 1 1 1 0 0 0 1 1 0 0 1 0 1 1 1 0 1 1 1 1 1 1 0 0 1 A Boole-kombinacio propozcionalis tautologia, tehat a formula logikai torveny. 2. Dontsuk el, hogy A^:A logikai ellentmondas-e?
: (A ^ : A)
: (A ^ : A)
0 0 1 0 0 1 0 1 1 1 1 0 0 1 :(A^:A) propozcionalis tautologia, azaz logikai torveny, tehat A ^ :A logikai ellentmondas.
3. Vizsgaljuk a 9x(A(x)^B (x)) 9xA(x)^9xB (x) formulat, mint a 9x(A(x) ^ B (x)); 9xA(x) es a 9xB (x) formulak Boole-kombinaciojat. 9x(A(x) ^ B (x)) 9xA(x) ^ 9xB (x) 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1
9x(A(x) ^ B (x)) 9xA(x) ^ 9xB (x)
0 1 0 0 0 0 1 0 0 1 0 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 0 0 0 1 1 0 1 0 0 1 1 1 1 1 A Boole-kombinacio nem propozcionalis tautologia, pedig logikai torveny.
4. Lassuk be, hogy j= 9x(A(x) ^ B (x)) 9xA(x) ^ 9xB (x): Bizonytas: Tekintsunk egy tetsz}oleges I interpretaciot es ertekelest. Vizsgalnunk kell a jj (9x(A(x) ^ B (x)) 9xA(x) ^ 9xB (x)) jjI = jj (9x(A(x) ^ B (x))) (9xA(x))^(9xB (x))jjI = jj (9x(A(x)( , x) ^ B (x)( , x)) 9x(A(x)( , x)) ^ 9x(B (x)( , x))jjI = jj9x(A0(x) ^ B 0(x)) 9xA0(x) ^ 9xB 0(x)jjI erteket. Ha jj9x(A0(x) ^ B 0(x))jjI = 0; akkor az implikacio erteke 1; Ha jj9x(A0(x) ^ B 0(x))jjI = 1; akkor van olyan a 2 Dx ; hogy jj (A0(x) ^ B 0(x))xa jjI = jjA0(x)xa ^ B 0(x)xajjI = 1: Ekkor viszont jjA0(x)xajjI = 1 es jjB 0(x)xajjI = 1; azaz jj9xA0(x)jjI = 1 es jj9xB 0(x)jjI = 1; gy jj9xA0(x) ^ 9xB 0(x)jjI = 1: Mivel az implikacio utotagja 1 ertek}u, az implikacio erteke most is 1.
5. Lassuk be, hogy 6j= 9xA(x) ^ 9xB (x) 9x(A(x) ^ B (x)): Bizonytas: Tekintsunk egy olyan I interpretaciot, melyben d Srt (x) = f;; fpirosgg d ~ ahol, ha S; Z 2 f;; fpirosgg Pr(P ) = P; 8 > < > :
SZ P~ (S; Z ) = 10 ha egyebkent ) 8uP (x; u) A(x) * ) 8uP (u; x) B (x) * Ebben az interpretacioban jj9xA(x)jjI = 1 es jj9xB (x)jjI = 1; mert peldaul jjA(;)jjI = 1 es jjB (fpirosg)jjI = 1: Ugyanakkor jj9x(A(x) ^ B (x))jjI = 0; mert jjA(;) ^ B (;)jjI = 0 es jjA(fpirosg) ^ B (fpirosg)jjI = 0:
6. A 9xA(x) ^9xB (x) 9x(A(x) ^ B (x)) formula kielegthet}o. Bizonytas: Legyen most az interpretacionk az el}oz}ohoz hasonlo, csak ) A(x) * 8u (P (u; x) (8zP (u; z) _ (P (u; x) ^ P (x; u)))) : Ebben az interpretacioban jj9xA(x)jjI = 1; mert jjA(fpirosg)jjI = 1, es jj9x(A(x) ^ B (x))jjI = 1; mert jjA(fpirosg) ^ B (fpirosg)jjI = 1:
Nehany fontos logikai torveny
asszociativitas
A ^ (B ^ C ) (A ^ B ) ^ C A _ (B _ C ) (A _ B ) _ C
kommutativitas
A^B B^A A_B B_A
disztributivitas A ^ (B _ C ) (A ^ B ) _ (A ^ C ) A _ (B ^ C ) (A _ B ) ^ (A _ C ) idempotencia eliminacio
A^A A A_A A
A ^ (B _ A) A A _ (B ^ A) A
De Morgan torvenyei :(A ^ B ) :A _ :B :(A _ B ) :A ^ :B
negacio az implikacioban :(A B ) A ^ :B
A :A :A :A A A j= :(A :A)
logikai jelek kozotti osszefuggesek A ^ B :(:A _ :B ) A ^ B :(A :B ) A _ B :(:A ^ :B ) kontrapozcio
A _ B :A B A B :(A ^ :B ) A B :A _ B
A B :B :A
ketszeres tagadas
::A A
implikacios el}otagok felcserelese A (B C ) B (A C ) implikacio konjunktv el}otaggal A ^ B C A (B C )
) C _:C; ? * ) C ^:C ) kiszamtasi torvenyek (> * A^> A_> A> >A
A
> > A
A^? A_? A? ?A
?
A :A
>
az azonossag torvenye j= A A b}ovtes el}otaggal j= A (B A) az implikacio ondisztributivitasa A (B C ) (A B ) (A C ) esetelemzes A _ B C (A C ) ^ (B C ) tranzitivitas j= (A B ) ^ (B C ) (A C ) reductio ad absurdum j= (A B ) ^ (A :B ) :A az ellentmondasbol barmi kovetkezik j= A (:A B )
a kizart harmadik torvenye j= A _ :A az ellentmondas torvenye j= :(A ^ :A) Pierce-torveny j= ((A B ) A) A ktv kvantorok Ha x 62 Fv(A) , akkor
8xA A 9xA A
az egyforma kvantorok helycsereje 8x8yA(x; y) 8y8xA(x; y) 9x9yA(x; y) 9y9xA(x; y) kvantor-csere implikacioban j= 8xA(x) 9xA(x) j= 9y8xA(x; y) 8x9yA(x; y) De Morgan kvantoros torvenyei :9xA(x) 8x:A(x) :8xA(x) 9x:A(x)
kvantor-felcsereles
9xA(x) :8x:A(x) 8xA(x) :9x:A(x)
kvantorok egyoldali kiemelese Ha x 62 Fv(A) , akkor A ^ 8xB (x) 8x(A ^ B (x)) A ^ 9xB (x) 9x(A ^ B (x)) A _ 8xB (x) 8x(A _ B (x)) A _ 9xB (x) 9x(A _ B (x)) A 8xB (x) 8x(A B (x)) A 9xB (x) 9x(A B (x)) 8xB (x) A 9x(B (x) A) 9xB (x) A 8x(B (x) A) kvantorok ketoldali kiemelese 8xA(x) ^ 8xB (x) 8x(A(x) ^ B (x)) 9xA(x) _ 9xB (x) 9x(A(x) _ B (x)) j= 8xA(x) _ 8xB (x) 8x(A(x) _ B (x)) j= 9x(A(x) ^ B (x)) 9xA(x) ^ 9xB (x) kongruens formulak ekvivalenciaja Ha A B; akkor A B:
helyettesteskor fellep}o kvantorok j= 8xA [Axt] j= [Axt] 9xA kvantorhataskor-atjeloles Ha y 62 Fv(A) , akkor 8xA 8y[Axy] 9xA 9y[Axy] kvantor-redukcio Ha x es y azonos tpusu valtozok, akkor j= 8x8yA 8x[Ayx] j= 9x[Ayx] 9x9yA helyettestes ekvivalens formulakba Ha A B; akkor [Axt] [Btx]
A logikai kovetkezmeny Legyenek A ; A ; : : : ; An (n 1) es B az nyelv 1
2
tetsz}oleges formulai. A B formula logikai (szemantikai) kovetkezmenye az A ; A ; : : : ; An formulaknak, ha minden olyan I interpretaciojaban es az A ; A ; : : : ; An es B formulak tetsz}oleges olyan I -beli ertekelese eseten, amikor I j= A ; I j= A ; : : : ; I j= An; akkor I j= B : Jelolese: A ; A ; : : : ; An j= B: 1
2
1
1
1
2
2
2
Lemma. (a) A ; A ; : : : ; An j= B akkor es csak akkor, ha j= A ^ A ^ : : : ^ An B . 1
2
1
2
(b) A ; A ; : : : ; An j= B akkor es csak akkor, ha =j A ^ A ^ : : : ^ An ^ :B . 1
2
1
2
Lemma. A B pontosan akkor, ha A j= B es B j= A.
Pelda. Bizonytsuk be, hogy helyesen kovetkeztettunk: P Nehany republikanus kedvel minden demokratat. P Nincs olyan republikanus, aki szeretne a szocialistakat. K Tehat egyik demokrata sem szocialista. Kesztsunk alkalmas logikai nyelvet. Legyenek x; y; z; : : : embereket jelol}o valtozok; R(x) jelentse, hogy x republikanus; D(x) jelentse, hogy x demokrata; S (x) jelentse, hogy x szocialista; K (x; y) jelentse, hogy x kedveli y-t. 1 2
Ezen e nyelven formalizalva az alltasokat: P 9x(R(x) ^ 8y(D(y) K (x; y))) P :9x(R(x) ^ 9z (S (z ) ^ K (x; z ))) K :9y(D(y) ^ S (y)) Rogztsunk tetsz}olegesen egy olyan I interpretaciot, melyben jjP jjI = 1 es jjP jjI = 1: 1 2
1
2
Ekkor jjP jjI = 1 miatt van olyan a 2 D; hogy jj(R(x) ^ 8y(D(y) K (x; y)))xajjI = 1; azaz jjR(a)jjI = 1 es minden b 2 D -re jj(D(y) K (a; y))ybjjI = 1: 1
jjP jjI = 1 miatt viszont minden b 2 D-re, gy 2
eppen a-ra is jj(R(x) ^ 9z(S (z) ^ K (x; z)))xajjI = 0; azaz mivel jjR(a)jjI = 1; ezert jj9z(S (z) ^ K (a; z)))jjI = 0: Ez azt jelenti, hogy minden b 2 D-re jj(S (z) ^ K (a; z)))zb jjI = 0: Ez a konjunkcio vagy azert 0, mert b olyan, hogy jjS (b)jjI = 0; de ekkor jj(D(y) ^ S (y))yb jjI = 0; vagy azert, mert b olyan, hogy jjK (a; b)jjI = 0: Ilyen b-re viszont, mivel jj(D(y) K (a; y))yb jjI = 1; at ilyenkor is jjD(b)jjI = 0; teh jj(D(y) ^ S (y))ybjjI = 0: Azaz minden b 2 D-re jj(D(y)^S (y))yb jjI = 0; tehat jj9y(D(y) ^ S (y))jjI = 0; azaz jj:9y(D(y) ^ S (y))jjI = 1:
A logikai kalkulus
Fel lehet epteni a logikat szemantikai fogalmakra hivatkozas nelkul is: szintaktika szemantika logikai nyelv interpretacio formula logikai ertek levezethet}oseg kovetkezmeny A levezethet}oseg fogalmat kalkulus megadasaval de nialhatjuk. Egy kalkulus megadasakor felsoroljuk az alapsemait es a levezetesi szabalyait. Ekkor de nialhato a , = fA ; A ; : : : ; Ang (n 0) formulahalmazbol valo levezethet}oseg fogalma: ha B alapformula, vagy B 2 ,; akkor levezethet}o ,-bol; jelolese: , ` B ha ,-bol levezet}o B ; B ; : : : ; akkor a levezetesi szabalyok megmondjak, hogy mely tovabbi formulak lesznek meg levezethet}ok. Egy kalkulus helyes, ha , ` B; akkor , j= B: Egy kalkulus teljes, ha , j= B; akkor , ` B: Egy kalkulus adekvat, ha helyes is, teljes is. 1
1
2
2
Egy logikai rendszer megalkotasakor el}oszor egy szemantikai rendszert de nialunk, majd megkserlunk ehhez legalabb helyes, de ha lehet, adekvat logikai kalkulust szerkeszteni.
A predikatumkalkulus
Alapsemak: 1. A (B A) 2. (A (B C )) ((A B ) (A C )) 3. A (B A ^ B ) 4. A ^ B A 5. A ^ B B 6. (A C ) ((B C ) (A _ B C )) 7. A A _ B 8. B A _ B 9. (A B ) ((A :B ) :A) 10. ::A A 11. 8xA(x) A(x)xt 12. 8x(C A(x)) (C 8xA(x)); x 62 Fv(C ) 13. A(x)xt 9xA(x) 14. 8x(A(x) C ) (9xA(x) C ); x 62 Fv(C )
Levezetesi szabalyok:
A A B modus ponens B A altalanostasi szabaly 8xA
A semakban es szabalyokban az A; B; C formulakkal; x valtozoval; t x-szel azonos tpusu termmel helyettesthet}o be. Az alapsemakbol gy alapformulakat kapunk. Lemma. A predikatumkalkulus minden alapformulaja logikai torveny. Lemma.
A; A B j= B Lemma. Ha , j= A(x) es x 62 Fv(,); akkor , j= 8xA(x):
A levezethet}oseg A predikatumkalkulusban a formula-fa es magassaganak induktv de ncioja: minden A formula 1 magassagu formula-fa, melyben A also formula, es nincs nala feljebb lev}o formula; ha D m es D m magassagu olyan formulafak, melyben az also formulak A es A B alakuak, akkor a 1
1
2
2
D
1
B
D
2
alakzat is formula-fa, melyben B also formula, melynel D es D minden formulaja feljebb van, es a formula-fa magassaga max fm ; m g + 1; ha D m magassagu olyan formula-fa, amelyben az also formula A, akkor a 1
2
1
D 8xA
2
alakzat is formula-fa, melyben 8xA also formula, melynel D minden formulaja feljebb van, es a formula-fa magassaga m + 1.
A formulafaban azon formulak, melyeknel nincs feljebb lev}o: alapformulak, hipotezisek, vagy nylt premisszak. Pelda.
Q(x) P 8x(Q(x) P )
9xQ(x) P
8x(Q(x) P ) (9xQ(x) P )
3 magassagu formulafa also formula: 9xQ(x) P alapformula: 8x(Q(x) P ) (9xQ(x) P ) hipotezis: Q(x) P
Levezetes-fa egy formula-fa, melyben ha A-bol az altalanostas szabalyaval akarjuk a 8xA-t nyerni, akkor x nem parameter egyetlen a 8xA-nal feljebb lev}o hipotezisben sem.
A , veges formulahalmazbol a B formula levezethet}o, ha keszthet}o olyan levezetes-fa, melyben B also formula, es a hipotesisek mind elemei ,-nak. Jelolese: , ` B (szekvencia) Tetel. A predikatumkalkulus adekvat logikai kalkulus.
A termeszetes levezetes
Az azonossag torvenye ,; A ` A Strukturalis szabalyok b}ovtes
sz}uktes
,`A ,; B ` A
,; B; B; ` A ,; B; ` A
felcsereles
vagas
,; B; C; ` A ,; C; B; ` A
, ` A ; A ` B ,; ` B
Logikai szabalyok BEVEZETE S
ELTA VOLITA S
implikacio ,; A ` B ,`AB
,`A ,`AB ,`B
konjunkcio ,`A ,`B ,`A^B
,; A; B ` C ,; A ^ B ` C
diszjunkcio ,`A ,`A_B
,; A ` C ,; B ` C ,; A _ B ` C
,`B
,`A_B negacio ,; A ` B ,; A ` :B , ` :A ekvivalencia ,; A ` B ,; B ` A ,`AB
, ` ::A ,`A ,`A ,`AB ,`B ,`B ,`AB ,`A
BEVEZETE S
ELTA VOLITA S
univerzalis kvantor , ` A(x) (x 62 Fv(,)) , ` 8xA(x)
, ` 8xA(x) , ` A(x)xt
egzisztencialis kvantor , ` A(x)xt , ` 9xA(x)
,; A(x) ` B (x 62 Fv(,)) ,; 9xA(x) ` B
Dedukcio-tetel. Ha ,; A ` B; akkor , ` A B: Tovabbi szabalyok Ha A B; akkor ` A B: ,`A [,] ` [A]
Kvantoros formulak prenex alakja Egy Q x Q x : : : QnxnA (n 0) alaku formulat, ahol a A kvantormentes formula, prenex alaku formulanak nevezunk. 1
1
2
2
Lemma. Az nyelv tetsz}oleges formulajahoz konstrualhato vele logikailag ekvivalens prenex alaku formula. A konstrukcio lepesei: 1. valtozo-tiszta alakra hozzuk a formulat; 2. alkalmazzuk De Morgan kvantoros es az egyoldali kvantorkiemelesre vonatkozo logikai torvenyeket. Pelda. 8xP (x) :9xQ(x) # valtozo-tiszta alakra hozas 8xP (x) :9yQ(y) # egyoldali kvantorkiemeles 8xP (x) 8y:Q(y) 9x(P (x) 8y:Q(y)) 9x8y(P (x) :Q(y))
Kvantormentes formulak normalformai Egy atomi formulat vagy negaltjat literalnak fogjuk nevezni. Legyenek L ; L ; : : : ; Ln (n 1) literalok. 1
2
L ^ L ^ : : : ^ Ln elemi konjunkcio L _ L _ : : : _ Ln elemi diszjunkcio Legyenek D ; D ; : : : ; Dm elemi diszjunkciok, K ; K ; : : : ; Km elemi konjunkciok (m 1). D ^ D ^ : : : ^ Dm konjunktv-, K _ K _ : : : _ Km diszjunktv normalforma. 1
2
1
2
1
1
1
1
2
2
2
2
Lemma. Az nyelv minden kvantormentes formulajahoz konstrualhato vele logikailag ekvivalens konjunktv es diszjunktv normalforma. A konstrukcio lepesei: 1. a logikai jelek kozotti osszefuggesek alapjan az implikaciokat eltavoltjuk; 2. De Morgan torvenyeivel elerjuk, hogy negacio csak atomokra vonatkozzon; 3. a disztributivitast felhasznalva elerjuk, hogy a konjunkciok es diszjunkciok megfelel}o sorrendben kovessek egymast; 4. esetleg egyszer}ustunk.
Pelda.
(A B ) _ :(:B A _ :C ) # implikacio-eltavoltas (:A _ B ) _ (:B ^ :(A _ :C )) # negacio atomokra vonatkozik (:A _ B ) _ (:B ^ :A ^ C ) # konjunkciok diszjunkcioja (:A _ B _ :B ) ^ (:A _ B _ :A) ^ (:A _ B _ C ) # egyszer}ustes (:A _ B ) ^ (:A _ B _ C ) # egyszer}ustes
:A _ B
1 Irodalomjegyzek
1. Dragalin Albert, Buzasi Szvetlana, Bevezetes a matematikai logikaba, Egyetemi jegyzet (KLTE), 4. kiadas, Kossuth Egyetemi Kiado, Debrecen, 1996. 2. Pasztorne Varga Katalin, Logikai alapozas alkalmazasokhoz, Egyetemi jegyzet, ELTE, Budapest, 1992. 3. Szendrei A gnes, Diszkret matematika, Polygon, Szeged, 1994. 4. Urban Janos, Matematikai logika (Peldatar), 2. kiadas, M}uszaki Konyvkiado, Budapest, 1987.
