Mathematics | Logic » A logikáról

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. ( ) ( ) nyelv I interpretaciojaban d ) 2[Srt D n fc~jCnst D* (c) = c~; c 2 Cnstg: Legyen az 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 formulai. 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 1 2 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