11 11

Logika és számításelmélet. 2011/11 11 (Logika rész) 1. előadás 1. Bevezető rész Logika (és a matematikai logika) tárgya Logika (és a matematikai logika) tárgya az emberi gondolkodás vizsgálata. A gondolkodás fontos része a mindennapi életnek. A gondolkodás fontos része bármely (humán- vagy természet-) tudománynak A logika célkitűzése. Gondolkodási folyamatok vizsgálata során A helyes következtetés törvényeinek feltárása. Újabb helyes következtetési módszerek kidolgozása. KÖVETKEZTETÉS - (ekvivalens megfogalmazások) Adott ismeretek  új ismeret premisszák  konklúzió feltételek  következmény állítások  állítás A  jel a gondolkodási folyamatot jelöli, amelynek eredménye a következmény. Definíció: Gondolkodásforma vagy következtetésforma egy F = {A1, A2,…,An} állításhalmaz és egy A állításból álló (F,A) pár. Megjegyzés: Az állítás adott körülmények között lehet igaz (i) vagy hamis (h). Ezt az értéket az állítás igazságértékének nevezzük. Definíció: Helyes következtetésforma egy(F,A) pár, ha minden olyan esetben, amikor az F-ben minden állítás igaz, a következmény állítás is igaz, Logika (és a matematikai logika) feladata, helyes gondolkodásformák kiválasztása és új következtetési formák keresése. A legfontosabb matematikai eszköztár: A) Halmaz, leképezés/függvény, értelmezési tartomány D, értékkészlet R. Legyenek D és R (nem feltétlenül különböző) halmazok. Legyen U egy halmaz, UxU direktszorzathalmaz az U elemeiből képezhető összes rendezett párok halmaza. Un-nel jelöljük U-nak önmagával vett n-szeres direktszorzatát, ami az U elemeiből képezhető összes n elemű sorozatok halmaza. Függvénynek nevezünk egy DR leképezést, (D a leképezés értelmezési tartománya, R az értékkészlete. Leképezések minősítése: Ha D=U (individuum)halmaz, akkor a leképezés egyváltozós

1

Ha D= Un , akkor a leképezés n-változós R (az értékkészlet) adja meg a leképezés fajtáját. Ha R=, akkor egész(értékű), ha R={i,h} vagy {0,1}, akkor logikai vagy kétértékű leképezésről beszélünk. Függvényosztályozás, 1. logikai függvény – reláció, D tetszőleges U vagy Un , R={h,i} vagy {i,h}, tehát Un →{i,h} a leképezés 2. matematikai függvény – művelet. Olyan DR leképezés, ahol D=Rn., n=1, 2,..., k véges érték. tehát Un →U a leképezés általános alakja. Logikai értékek – {i,h} vagy {0,1} n-változós logikai műveletek: {h,i}n{h,i} leképezések A lehetséges kétváltozós logikai műveletek közös igazságtáblája. 1 2 3 4 5 6 7 8 9 10 11 12 13 X Y XY XY XY XY      XY X Y X i i i i i i h h h h h i h h i i h h i h h i i h i h i h i i h i h i i h i i h h i h i h h h h h h i i h i i h h i i i h A táblázat tartalmazza a 16 db. 2-változós műveletet (köztük található a 4.db.1- és a 2.db. 0-változós művelet). Ezekből a logika tárgyalásánál a {,,,} műveleteket használjuk csak.

X 1 1 0 0

1 2 3 4 5 Y XY XY XY XY  1 1 1 1 1 0 0 0 1 0 0 1 1 0 1 1 0 1 0 0 0 1 1 0

6  0 1 1 1

7  0 0 0 1

8  0 1 0 0

9  0 0 1 0

10 XY

1 1 0 1

11 X 0 0 1 1

12 Y 0 1 0 1

13 X 1 1 0 0

14 Y i h i h

15 i i i i i

16 h h h h h

14 Y 1 0 1 0

15 i 1 1 1 1

16 h 0 0 0 0

2

B) Nyelv – leíró nyelv=ábécé+szintaxis+szemantika C) Rekurzív definíció Olyan definíció, ahol a definiálandó fogalmat (mondat, szó, formula,...) egy adathalmaz (ábécé) felett két lépésben definiálunk. 1. (alaplépés)ben, az adathalmaz bizonyos elemeivel azonosítjuk a definiálandó objektumot. 2. (rekurziós lépésben, ) a már definiált objektumokból és az ábécé elemeiből, megadott szabályok szerint állítjuk elő az objektumokat. Például az aritmetikai kifejezés definíciója. 1. Egy x változó vagy egy aritmetikai konstans term. 2. Ha t1, t2 termek, akkor (t1+ t2), és (t1 t2) is termek 3. Az összes term az 1. és 2. szabályok véges sokszori alkalmazásával áll elő.

Itéletlogika vagy állításlogika Tárgya az egyszerű állítások és a belőlük logikai műveletekkel kapott összetett állítások vizsgálata (könyv 19 és 28-33 oldalak). Definíció: Egyszerű állítás egy olyan kijelentés, amelynek tartalmáról eldönthető, hogy igaze vagy nem. Egy állításhoz hozzárendeljük az igazságértékét: az i vagy h értéket. Definíció: Összetett állítás egy egyszerű állításokból álló összetett mondat, amelynek az igazságértéke csak az egyszerű állítások igazságértékeitől függ. Ezért az összetett állítások csak olyan nyelvtani összekötőszavakat tartalmazhatnak amelyek logikai műveleteknek feleltethetők meg. Az ítéletlogika leíró nyelve ábécé= a teljes ábécé V0 ítéletváltozók X, Y, Xi,... együttesen Vv-vel jelöljük unér és binér logikai műveleti jelek ,,, elválasztójelek () Szintaxis (könyv. 46.old. 4.1.2.def) (L0 ítéletlogika) 1. (alaplépés) minden ítéletváltozó ítéletlogikai formula. (prímformula) 2. (rekurziós lépés) Ha A ítéletlogikai formula, akkor A is az. Ha A és B ítéletlogikai formulák, akkor (AB) is ítéletlogikai formula „” a három binér művelet bármelyike. 3. Minden ítéletlogikai formula az 1, 2 szabályok véges sokszori alkalmazásával áll elő. Formulaelnevezések: A negációs (AB) konjunkciós (AB) diszjunkciós (AB) implikációs 3

Definíció: Ha X ítéletváltozó, akkor az X és a X formulákat literálnak nevezzük. Az ítéletváltozó a literál alapja. X és X azonos alapú literálok. Definíció: (könyv. 48.old. 4.1.6.def) Közvetlen részformula 1. prímformulának nincs közvetlen részformulája. 2. A közvetlen részformulája, az A formula 3. Az (AB) közvetlen részformulái az A (baloldali) és a B (jobboldali) Például a ((ZX) Y) formula baloldali és jobboldali részformulái a (ZX) és Y. Szerkezeti fa felrajzolás (könyv 49. oldal)

Teljesen zárójelezett formulák esetén a formula szerkezetének megállapítása egyértelmű. (((XY)(YZ))(XZ)) Annak érdekében, hogy a formulákat kevesebb zárójellel írhassuk fel bevezetjük a műveletek prioritását csökkenő sorrendben: , , ,  Zárójelelhagyás (könyv 52. old) célja egy formulából a legtöbb zárójel elhagyása a formula szerkezetének megtartása mellett . 1. a formula külső zárójel párjának elhagyása (ha még van ilyen) 2. egy binér logikai összekötő hatáskörébe eső részformulák külső zárójelei akkor hagyhatók el, ha a részformula fő logikai összekötőjele nagyobb prioritású nála. Példa: (((XY)(YZ))(XZ)) a zárójelelhagyás után (XY) (YZ)XZ Láncformulák. Literál egy ítéletváltozó X, vagy egy negált ítéletváltozó X. Elemi konjunkció: különböző literálok konjunkciója. Elemi diszjunkció: különböző literálok diszjunkciója (klóz). Literál egy ítéletváltozó vagy Implikációs láncformula default zárójelezése jobbról balra. Formula logikai összetettsége l(A) (szerkezeti rekurzióval való definíció) (könyv. 50.old. 4.1.12.def) 1. Ha A ítéletváltozó, akkor l(A)=0 2. l(A)= l(A)+1 3. l(AB)= l(A)+ l(B)+1 Definíció: (könyv. 52.old. 4.1.17.def) A logikai műveletek hatásköre a formula részformulái közül az a legkisebb logikai összetettségű, amelyben az adott logikai összekötőjel előfordul. Pl. (XY)(YZ)XZ formula  műveletet tartalmazó részformulái: 1. l[(XY)(YZ)XZ]= 6 2. l[( (XY)(YZ)X]=5

4

3. l[( (XY)(YZ]=3 Ezek közül a 3. formula az  hatásköre. Egy művelet hatáskörébe eső formula(’k) egyben közvetlen komponensek is. Definíció: (könyv. 52.old. 4.1.18.def) Egy formula fő logikai összekötőjele az az összekötőjel, amelynek a hatásköre maga a formula.

5

2. előadás Láncformulák. (emlékeztető) Literál egy ítéletváltozó X, vagy egy negált ítéletváltozó X. Elemi konjunkció: különböző literálok konjunkciója. Elemi diszjunkció: különböző literálok diszjunkciója (klóz). Literál egy ítéletváltozó vagy Implikációs láncformula default zárójelezése jobbról balra. Szemantika. (könyv. 57.-68. old.) a) A nyelv ábécéjének értelmezése (interpretációja - modellezése). Az ítéletlogika ábécéjében csak az ítéletváltozókat kell interpretálni. Az ítéletváltozók befutják az állítások halmazát. Ha megmondjuk melyik ítéletváltozó melyik állítást jelenti, akkor a változó igazságértékét megadtuk. Ennek rögzítését interpretációnak nevezzük: Interpretáció: I: Vv {i,h} I(X) jelöli az X változó értékét az I interpretációban. Az I interpretáció tehát változókiértékelés, amit igazságkiértékelésnek is hívnak. Egy formula véges sok ítéletváltozót tartalmaz és így a formula vizsgálatához csak ezeknek az interpretációja szükséges. Szerepeljenek egy formulában az {X,Y,Z} ítéletváltozók. E változók egy sorrendjét bázisnak nevezzük. Legyen most a bázis X,Y,Z. Ekkor az összes interpretációt megadhatjuk a

X i i i i h h h h

Y i i h h i i h h

Z i h i h i h i h

táblázattal, vagy adott bázis esetén az összes interpretáció megadható, szemantikus fával. Definíció. Egy n-változós szemantikus fa egy n-szintű bináris fa, ahol a szintek a bázisbeli változóknak vannak megfeleltetve. Egy X változó szintjén a csúcsokból kiinduló élpárokhoz X, X. cimkéket rendelünk. X jelentése X igaz, X jelentése X hamis, így egy n-szintű szemantikus fa ágain az összes (2n ) lehetséges igazságkiértékelés (I interpretációigazságkiértékelés) megjelenik. Szemantikus fa az X, Y, Z logikai változókra, mint bázisra.

6

X

X Y

Y Z iii

Z iih

Z ihi

Y

Z ihh

Z hii

Z hih

Y Z hhi

Z hhh

b) Az interpretációk alapján a formulák logikai jelentésének meghatározása. BI a formulákon értelmezett függvény. BI(C) a C formulához hozzárendeli annak helyettesítési értékét az adott I interpretációban. BI(C)-definíciója szerkezeti rekurzióval: 1. A C formula ítéletváltozó. BI(C)= I(C). 2. A C formula negációs BI(A)=  BI(A) A C formula (AB) alakú BI(AB)= BI(A) BI(B) Definíció: Egy n-változós formula igazságtáblája egy olyan n+1 oszlopból és 2n+1 sorból álló táblázat, ahol a fejlécben a bázis (a formula változói rögzített sorrendben) és a formula szerepel. A sorokban a változók alatt az interpretációk (a változók igazságkiértékelései), a formula alatt a formula helyettesítési értékei találhatók.

X i i i i h h h h

Y i i h h i i h h

Z i h i h i h i h

((ZX) Y) i i i h i i h h

(ZX) Y) és a a leképezést írják le.

A ((ZX) Y) formula igazságtáblája

Egy n-változós formula az igazságtáblájával megadott {i,h}n{i,h} leképezést ír le. Egy formula igazhalmaza azon I interpretációk halmaz amelyekre a formula helyettesítési értéke igaz. Egy formula hamishalmaza azon I interpretációk halmaza amelyekre a formula helyettesítési értéke hamis.

(XYZ)(XYZ)(XYZ) formulák is ugyanezt

Egy formula igazhalmaza/hamishalmaza előállítható rekurzív módon is. Ennek eszköze a formulákon értelmezett A igazságértékelés függvény (= i vagy h), amely a különböző formulák esetén az igazságtábla felírása nélkül megadja a formula közvetlen részformuláin keresztül azokat az interpretációkra vonatkozó Ai és a Ah feltételeket, amelyeket teljesítő interpretációkban a formula értéke i vagy h lesz.

7

A -igazságértékelés szabályai (könyv 62-64 old.)

1. ha A primformula (ítéletváltozó): akkor a Ai feltételt pontosan azok az interpretációk teljesítik amelyekben I(A)=i, a Ah feltételt pedig azok amelyekben I(A)=h. 2. a  (A) i feltételek pontosan akkor teljesülnek, ha teljesülnek a Ah feltételek. 3. a  (AB) i feltételek pontosan akkor teljesülnek, ha teljesülnek mind a Ai mind a Bi feltételek. 4. a  (AB) i feltételek pontosan akkor teljesülnek, ha teljesülnek a Ai vagy a Bi feltételek. 5. a  (AB) i feltételek pontosan akkor teljesülnek, ha teljesülnek a Ah vagy a Bi feltételek. A  (A) h a  (AB) h , a  (AB) h , és a  (AB) h feltételek értelemszerűen adódnak. Példa.  (XYZX) i, ha Xh (YZX) i, ha 1.értékadás konjunkciós formula  (YZ) i, Yi Zi 2. értékadás 1. ág XYZ h~ ~

2. ág XYZ ~ i i

implikációs formula diszjunkciós formula  (X) i, negációs formula Xh 3. értékadás 3. ág XYZ h~ ~

Az igaz halmaz X Y Z i i i h i i h i h h h i h h h

8

A hamis halmazt, az igaz halmazban nem szereplő interpretációk alkotják. A hamis halmazt a formula hamissá válás feltételeinek megkeresésével rekurzív módon is megkapjuk.  (XYZX) h, ha 1. értékadás

Xi (YZX) h, ha

 implikációs formula diszjunkciós formula

(X) h  (YZ)h, ha Xi

2. értékadás

Y h

3a. értékadás

bal ág XYZ i h ~

 Z h 3b. értékadás jobb. ág XYZ i ~ h

A hamis halmaz X Y Z i i h i h i i h h Formulák és formulahalmazok szemantikus tulajdonságai. Definíció: Azt mondjuk, hogy az ítéletlogikában egy I interpretáció kielégít egy B formulát (I=0B). ha a formula helyettesítési értéke i az I interpretációban. Definíció: Azt mondjuk, hogy egy B formula kielégíthető, ha legalább egy interpretáció kielégíti. Definíció: Azt mondjuk, hogy egy B formula kielégíthetetlen, ha egyetlen interpretáció sem elégíti ki. Definíció: Azt mondjuk, hogy egy B formula tautologia (=0B), ha minden interpretáció kielégíti. A tautologiát ítéletlogikai törvénynek is nevezik. Legyen F = {A1, A2,…,An} formulahalmaz Definíció: Azt mondjuk, hogy az ítéletlogikában egy I interpretáció kielégít egy F formulahalmazt (I=0F). ha a formulahalmaz minden formulájának helyettesítési értéke i az I interpretációban. Definíció: Azt mondjuk, hogy egy F formulahalmaz kielégíthető, ha legalább egy interpretáció kielégíti. Definíció: Azt mondjuk, hogy egy F formulahalmaz kielégíthetetlen, ha bármely interpretációban legalább egy formulája h (nincs olyan interpretáció, ami kielégítené). Definíció: Két vagy több formula igazságtáblája lehet azonos, ekkor azt mondjuk, hogy a formulák tautologikusan ekvivalensek. Ennek jelölésére a ~0 szimbólumot használjuk.

9

:

Példák XY~0 XY, X~0 X, és néhány fontos azonosság: De Morgan szabályok: 1. ¬(XY) ~0 XY, 2. (XY) ~0 X¬Y Egyszerűsítési szabályok: 1. (Xd)(Xd) ~0 d, 2. (Xk) (Xk) ~0 k, ahol d elemi diszjunkció és k elemi konjunkció. Ítéletlogikai törvények (könyv. 71. és 74. old. ) például: =0 A(BA) =0 (ABC)(AB)AC =0 ABAB stb.

Szemantikus következményfogalom az itéletlogikában. (könyv 76. old.) -Egy G formula szemantikus vagy tautologikus következménye az F={F1, F2, ..., Fn} formulahalmaznak, ha minden olyan I interpretációra amelyre I=0{F1, F2, ..., Fn} fennáll, I=0G is fennáll. Jelölés: (F=){F1, F2, ..., Fn}=0G -Egy G formula bármely F feltételhalmaznak következménye - G tautologia (=0G). Tétel: F-nek következménye G, akkor és csak akkor, ha az F  {G} kielégíthetetlen. Visszakövetkeztetés alapjául szolgáló egyik eldöntésprobléma azaz F1F2...FnG kielégíthetetlen. Tétel: Ha F-nek következménye G1 (F=0G1) és S-nek következménye G2 (S=0G2), valamint, {G1, G2}-nek következménye A ({G1, G2}=0A), akkor az F  S-nek következménye A (F  S=0A). Megjegyzés: Ha F és S ugyanaz a formulahalmaz, akkor a tétel a következő: Ha F-nek következménye G1 (F=0G1) és F-nek következménye G2 (F=0G2), valamint, {G1, G2}nek következménye A ({G1, G2}=0A), akkor az F -nek következménye A (F =0A). Definíció: Az A és a B formulák tautologikusan ekvivalensek., ha A=0B és B=0A. Ekkor =0 (AB)(BA) Tétel:(dedukciós)(könyv 80.old 4.4.7.tétel) Az {F1, F2, ..., Fn}=0G akkor és csak akkor, ha {F1, F2, ..., Fn-1}=0 (FnG). Tétel:(eldöntésprobléma)(könyv 80.old 4.4.8.tétel) Az {F1, F2, ..., Fn}=0G akkor és csak akkor, ha =0F1(F2(...( Fn-1(FnG))...). tautologia. Ez a másik eldöntésprobléma az ítéletlogikában.

10

3. előadás Előre- és visszakövetkeztetés Legszűkebb következmény (közös igazságtáblával)(könyv 84.old. 4.4.14.def) – Legyen a feltételhalmazban szereplő változók száma n. Ekkor a legszűkebb következmény az az {h,i}n{h,i} leképezés, amely pontosan azokhoz az interpretációkhoz rendel i értéket amelyek kielégítik a feltételhalmazt. Előrekövetkeztetés: ismert az F feltételhalmaz és keressük F lehetséges következményeit. Megkeressük F legszűkebb következményét R-t. Következmény minden olyan G formula, amelyre RG tautologia (1. rendben logikailag igaz) azaz R igazhalmaza része G igazhalmazának. Példa. F={ZMP, Z, P } P M Z Z ZMP

P

h

i

i

i

i

i

következmény h vagy i i h vagy i

Csak egy igazságkiértékelésre kielégíthető a feltételhalmaz Visszakövetkeztetés: Az F feltételhalmaz és a B következményformula ismeretében eldöntjük, hogy B valóban következménye-e F-nek. Mivel F=0B pontosan akkor, ha az {F{B}} formulahalmaz kielégíthetetlen. Más szóval B pontosan akkor következménye Fnek, ha minden olyan interpretációban, ahol B hamis az F kielégíthetetlen. A probléma megoldása legfeljebb az ítéletlogikában átlátható. Példa. F={ZMP, Z, P } és be kell látni, hogy M következmény. Be kell látni, hogy , ha M igaz, akkor {ZMP, Z, P } nem lesz kielégíthető. Hogy minden feltételformula i legyen Z=i, P=h. Viszont ha M hamis, akkor ZMP=h lehet csak. Tehát M következménye F-nek. Formalizálás az ítéletlogikában (könyv. 54. – 55. old.) Tegyük fel, hogy adott valamilyen köznapi vagy matematikai probléma. Ennek természetes nyelvű egyszerű vagy összetett kijelentő mondatokkal való leírását ismerjük. Az egyszerű kijelentő mondatok formalizálására bevezetünk egy azonosítót (állításjel, ítéletváltozó). Az összetett mondatot analizáljuk, átalakítjuk azonos értelmű de egyszerű kijelentő mondatokból olyan nyelvtani összekötőkkel felírt mondattá, ahol a nyelvtani összekötők egyben logikai összekötők (logikai műveletek). Betörtek egy áruházba(könyv. 54.old). A nyomozási jegyzőkönyv a következőket tartalmazza: Ha férfi a tettes, akkor kistermetű. Ha kistermetű, akkor az ablakon mászott be. A tettes férfi vagy legalábbis férfiruhát hordott.

11

Ha férfiruhát hordott és feltéve, hogy a szemtanú vallomása hiteles akkor az ablakon mászott be. A helyszíni szemle megállapította, hogy az ablakon senki sem mászott be. A nyomozók az sejtik, hogy a tettes nem férfi. Ezt a táblánál formalizáljuk. Az elsőrendű logika Az ítéletlogikában nem foglalkoztunk az állítások minősítésével és az állítások leírásával. Az állítás definíciója szerint az állítást egy kijelentő mondattal ki lehet fejezni. Ha a kijelentő mondat alanya egy konkrét egyed, akkor az állítást nulladrendű állításnak hívjuk. Az ilyen állítások formális leírására egy relációt (logikai függvényt) definiálunk. Pl.:E(x)=i, ha x egészszám, P(x)=i, ha x prímszám, L(x,y,z)=i, ha z az x és az y legnagyobb közös osztója. Az állítás konkrét egyedekkel behelyettesített reláció. Pl.: E(9)=i, E(0.8)=h vagy L(9,6,3)=i, L(9,6,7)=h állítások, de L(9,6,z) nem állítás (paraméteres állítás). Itt az egyedek/indivíduumok halmaza lehet például a racionális számok halmaza. Ha a kijelentő mondat alanya bizonyos egyedek egy halmaza, akkor, az állítást elsőrendű állításnak hívjuk. Ebben az esetben az állítás az elemek halmazára vonatkozik és az összes elemre egyidejűleg fennálló megállapítást/általánosítást vagy a halmaz bizonyos elemeire (nem feltétlenül mindre) fennálló megállapítást/létezést fogalmaz meg. Ennek leírására vezetjük be a  (univerzális) és a  (egzisztenciális) kvantorokat. Pl. a „Vannak prímszámok” kijelentés - xP(x) alakban írható le, ha feltételezzük, hogy a vizsgált elemhalmaz/ vagy indivíduumhalmaz/univerzum az egészszámok halmaza. Amennyiben az univerzum a valós számok halmaza, akkor ugyanezt az állítást x(E(x)P(x)) alakban írhatjuk fel. Vagy a „Minden háromszög szögösszege 180 fok” kijelentést – felírhatjuk x(H(x)S(x,f(y1,y2,y3)) alakban, ahol H(x)=i, ha x háromszög és S(x,f(y1,y2,y3))=i, ha y1,y2,y3 az x szögei és f(y1,y2,y3)=y1+y2+y3=180 fok. Megjegyzés: Itt az univerzum elemei a síkidomok, a szögek, ahol a szögek mérőszáma lehet fok vagy radián. Az S nevű kétváltozós reláció első argumentuma háromszög, a második argumentuma fok lehet és az f nevű háromváltozós matematikai függvény/művelet argumentumai és a függvényérték is fokok. A matematikai függvények (műveletek) és a logikai függvények (relációk) az elsőrendű logika eszközei az állítások belső szerkezetének leírására. Az univerzális és az egzisztenciális kvantorok pedig az elsőrendű állítások megfogalmazásának eszközei. Esetünkben a háromszögekre vonatkozó leíró nyelv ábécéjének speciális része: A relációk nevei: S,H nevei A műveletek nevei: f A nyelv ábécéjének logikai része: Az egyszerű nulladrendű állítások megfogalmazásához bevezetjük az univerzum elemeinek kezelésére – az indivíduumváltozót x, y, …. Az összetett állítások leírására az ábécét kiegészítjük még Logikai összekötők neveivel ,,, A kvantorokkal ,  és az elválasztójelekkel (),

12

Az 1800-as évek végén és az 1900-as évek elején a matematikai struktúrák (halmazelmélet és az aritmetika (számelmélet)) logikai vizsgálatához meg kellett teremteni az illető matematikai struktúrában mind a nulladrendű mind az elsőrendű állítások leírására szolgáló eszközöket. Más szóval szükségessé vált egy a matematikai struktúrákat leíró nyelv definiálása.

13

4. előadás Alapfogalmak Matematikai struktúra = együttes, ahol U – nem üres halmaz, a struktúra értelmezési tartománya (amennyiben U egyfajtájú elemekből áll) R – az U-n értelmezett n-változós (n=1,2, ...k) logikai függvények (alaprelációk) halmaza M - az U-n értelmezett n-változós (n=1,2, ...k) matematikai függvények (alapműveletek) halmaza K – az U megjelölt elemeinek egy (esetleg üres) részhalmaza A struktúra szignatúrája megadja az alaprelációk és az alapműveletek aritását valamint K elemszámát. Egy matematikai struktúra leíró nyelvének ábécéje áll - az indivíduumváltozókból, amelyek az U univerzum elemeit futják be. - az R halmazbeli alaprelációk neveiből - az M halmazbeli alapműveletek neveiből - a K halmazbeli elemek neveiből. Ezekkel a nevekkel már lehet egyszerű (nulladrendű és paraméteres) állításokat leírni. Az R, M, K-beli nevek a leíró nyelv logikán kívüli részét képezik (csak a struktúrára jellemző megnevezések, mivel a matematikai struktúra alkotóelemeit nevezik meg). Az összetett állítások és az elsőrendű állítások leírására kibővítjük az ábécét a logikai szimbólumokkal (az ábécé logikai része): - indivíduumváltozók - unér és binér logikai műveleti jelek ,,, - kvantorok ,  - elválasztójelek (), Ez együtt a matematikai struktúra logikai leíró nyelvének az ábécéje. Elemi aritmetika (könyv 36-37 old.) mint példa: együttes, ahol N0 - a természetes számok halmaza = - az {(x,x)} igazhalmazú alapreláció neve s - az egyváltozós rákövetkezés függvény neve + és x - rendre az összeadás és a szorzás műveletek nevei 0 - a megjelölt univerzumelem neve. (az az elem, amely nem tartozik a rákövetkezés függvény értékkészletébe) A struktúra szignatúrája alatt az alaprelációk és az alapműveletek aritásait valamint a konstansok számát megadó v1, v2, v3 egész értékű függvényeket értjük. Esetünkben: v1(=)=2, v2(s)=1, v2(+)=2, v2(x)=2, v3=1. Felsorolással megadva: =; s, +, x; 0 2; 1, 2, 2; 1 Az elemi aritmetika leíró nyelvének ábécéjében az N0 kezelésére a változók (x,y,...) szolgálnak (individuumváltozók) az {=, s, +, x; 0} jelek a megfelelő leképezések azonosítói. A leíró nyelv szignatúrája ugyanaz, mint struktúráé.

14

Az alaprelációkkal (itt csak az = relációval) lehet állításokat leírni. Pl. 2=3, 5=5. De nem állítás pl. y=5 vagy z=w (paraméteres állítások). Egyéb ismert egyszerű állításokat pl. a kisebb egyenlő () relációt ezen a nyelven csak összetett állítás formájában lehet felírni (formalizálni). Ehhez a nyelv ábécéjét logikai résszel bővítjük ki. Ezek: Logikai összekötőjelek , , ,  Kvantorok ,  Elválasztójelek – (), Definiáljuk (formalizáljuk) az aritmetika logikai leíró nyelvén a  relációt: xy =def z((x+z)=y) (további definíciós formalizálás könyv 37. és 38. oldal) Megjegyzés: Az aritmetika univerzuma egyfajtájú elemekből, a természetes számokból állt. Egy matematikai struktúra univerzuma többfajtájú elemekből is állhat. Például a térgeometriában pontok, egyenesek és síkok alkotják az értelmezési tartományt. Ekkor a leíró nyelv ábécéjében a fajták elnevezésére is bevezetünk jeleket. Esetünkben például p, e, s. Így az értelmezési tartomány Up Ue Us lesz, a struktúra pedig az < Up Ue Us, R, M, K> együttes. Az elsőrendű logika leíró nyelve L Olyan ábécével kell hogy rendelkezzen, melynek a logikán kívüli szimbólumai és azok szignatúrája bármely adott matematikai struktúra szignatúrájával megfeleltethető legyen és ennélfogva a szimbólumok lehessenek a struktúra relációinak, műveleteinek és megjelölt elemeinek a nevei. Más szóval a nyelv alkalmas kell hogy legyen tetszőleges szignatúrájú matematikai struktúrák leírására. Például struktúra leíró nyelve lehet a következő. Az L nyelv ábécéje: < Srt, Pr, Fn, Cnst > (könyv 110-116) Srt, nemüres halmaz melynek πj elemei fajtákat szimbolizálnak Pr, predikátumszimbólumok halmaza. υ1, P Pr –re megadja P aritását (k) és, hogy milyen fajtájúak az egyes argumentumok (π1 , π2 , πk ) Fn, függvényszimbólumok halmaza. υ2, megadja f aritását (k) és, hogy milyen fajtájúak az egyes argumentumok valamint a függvény értéke (π1 , π2 , ..., πk; πf ). Cnst, konstansszimbólumok halmaza, υ3 megadja konstansok számát és minden konstanshoz annak fajtáját. Szignatúra (υ1, υ2, υ3) A < Srt, Pr, Fn, Cnst > képezi a logikai nyelv logikán kívüli részét. logikai jelek. Különböző fajtájú individuum változók minden fajtához megszámlálható végtelen sok x, y, yk, ... unér és binér logikai műveleti jelek ,,, kvantorok ,  elválasztójelek (),

15

Az L nyelv ábécéjére V[Vv]-vel hivatkozunk, ahol Vv adja meg a (υ1, υ2, υ3) szignatúrájú <Srt, Pr, Fn, Cnst > halmaznégyest. A nyelv kifejezései informálisan. termek (matematikai leképezéseket szimbolizálják) és a formulák (logikai leképezéseket szimbolizálják) Szintaxis (könyv 112 old.) Termek: Lt(Vv) 1. (alaplépés) minden πSrt fajtájú individuum változó és konstans szimbólum, π fajtájú term. 2. (rekurzív lépés)Ha az f Fn (π1 , π2 , πk; πf ) fajtájú függvényszimbólum és t1 , t2 , tk rendre π1 , π2 , πk fajtájú termek, akkor f(t1 , t2 , tk) πf fajtájú term. 3. minden term az 1., 2. szabályok véges sokszori alkalmazásával áll elő. Formulák: Lf(Vv) 1. (alaplépés) Ha a P Pr (π1 , π2 , πk ) fajtájú predikátumszimbólum és t1 , t2 , tk rendre π1, π2, ,πk fajtájú termek, akkor P(t1 , t2 , tk) formula. Atomi formula. 2. (rekurzív lépés) Ha A formula, akkor A is az. Ha A és B formulák, akkor (AB) is formula () a három binér művelet bármelyike. 3. Ha A formula, akkor xA és xA is az. 4. Minden ítéletlogikai formula az 1, 2, 3 szabályok véges sokszori alkalmazásával áll elő. Egyfajtájú esetben a szintaxis szabályai: Termek: Lt(Vv) 1. (alaplépés) minden individuum változó és konstans szimbólum term. 2. (rekurzív lépés) Ha az f Fn k-változós függvényszimbólum és t1 , t2 , tk termek, akkor f(t1 , t2 , tk) is term. 3. minden term az 1., 2. szabályok véges sokszori alkalmazásával áll elő. Formulák: Lf(Vv) 1. (alaplépés) Ha a P Pr k-változós predikátumszimbólum és t1 , t2 , tk termek, akkor P(t1 , t2 , tk) formula. Atomi formula. 2. (rekurzív lépés) Ha A formula, akkor A is az. Ha A és B formulák, akkor (AB) is formula () a három binér művelet bármelyike. 3. Ha A formula, akkor xA és xA is az.

4. Minden ítéletlogikai formula az 1, 2, 3 szabályok véges sokszori alkalmazásával áll elő. Elsőrendű logikai nyelv: L(Vv)= Lt(Vv) Lf(Vv) Formulaelnevezések: A negációs (AB) konjunkciós (AB) diszjunkciós (AB) implikációs 16

xA xA

univerzálisan kvantált egzisztenciálisan kvantált

Vezessük be a , , , , ,  prioritási sorrendet, ekkor az ítéletlogikához hasonlóan definiáljuk a - zárójelelhagyásokat, - műveletek és a kvantorok hatáskörét, a komponens és prímkomponens fogalmakat - egy formula fő műveleti jelét Az ítéletlogikában minden formulát fel lehet írni a prímformulák (azaz ítéletváltozók) és a műveletek segítségével. Az elsőrendű nyelvben is vannak ilyen formulák. Prímformulák az elsőrendű nyelvben az atomi formulák és a kvantált formulák (könyv 113 old.). Közvetlen részterm és közvetlen részformula az elsőrendű nyelvben (könyv 115 old.). Termek: 1. kostansnak és individuumváltozónak nincs közvetlen résztermje. 2. az f(t1 , t2 , tk) term közvetlen résztermjei a t1 , t2 , tk termek. Formulák: 1 .egy atomi formulának nincs közvetlen részformulája 2. A közvetlen részformulája, az A formula 3. Az (AB) közvetlen részformulái az A (baloldali) és a B (jobboldali) 4. A QxA közvetlen részformulája, az A formula. Egy formulában egy logikai művelet hatáskörében lévő részformulá(ka)t komponens formuláknak nevezzük. 1 .egy atomi formulának nincs közvetlen komponense -prímformula 2. A közvetlen komponense, az A formula 3. Az (AB) közvetlen komponensei az A (baloldali) és a B (jobboldali) 4. A QxAnak nincs közvetlen komponense. - prímformula Megjegyzés: Prímkomponensnek nevezünk azokat a prímformulákat, amelyekből a formula kizárólag a ,,, műveletek segítségével épül fel. Ennek megfelelően a prímformulák: 1. Egy atomi formula prímformula. 2. Egy QxA formula prímformula. Term szerkezeti fája Formula szerkezeti fája (könyv 116-117 old.), melynek levelei a formula prímkomponensei Logikai összetettség: Formula logikai összetettsége l(A) (rekurzív definíció) (könyv. 118.old. 5.1.15. def.) 1. Ha A atomi formula, akkor l(A)=0 2. l(A)= l(A)+1 3. l(AB)= l(A)+ l(B)+1 4. l(QxA)= l(A)+1 A zárójelelhagyáshoz a prioritási sorrend: (,,),,, Szabad és kötött változók (könyv 119-123 ol. 5.1.1. fejezet) Elsőrendű formulák vizsgálata. Definíciók. Egy formulában egy x változó egy előfordulása 17

szabad, ha nem esik x-re vonatkozó kvantor hatáskörébe kötött, ha x-re vonatkozó kvantor hatáskörébe esik. Definíciók: Egy x változó egy formulában - kötött változó ha x minden előfordulása kötött, - szabad változó ha x minden előfordulása szabad, - vegyes változó ha x -nek van szabad és kötött előfordulása is. Megjegyzés: Ha egy formulában egy változó kötött, akkor átnevezve ezt a változó a formulában elő nem forduló változónévvel a formula ekvivalens marad az eredetivel. Ily módon minden formula átírható változóátnevezésekkel vegyes változót már nem tartalmazó formulává. A formula xP(x)yQ(w,y)P(v)zQ(w,z) A primkomponensek: xP(x), y(Q(w,y), P(v), zQ(w,z)). A szabad indivíduum változók v, w. Egy formula zárt, ha minden változója kötött. Egy formula nyitott, ha legalább egy individuum változónak van legalább egy szabad előfordulása. Egy formula kvantormentes, ha nem tartalmaz kvantort. 1. rendű állításokat szimbolizálnak az L nyelven a zárt formulák vagy mondatok. Definíció: Alapkifejezés a változót nem tartalmazó L kifejezés (alapformula, alapterm). Ezeket alappéldányoknak is nevezik. Az atomi formulák alappéldányait két csoportba soroljuk. a)Egy atomi formula alapatom, ha argumentumai konstans szimbólumok vagy egy megadott univerzum elemei P(c) b)Egy atomi formulát az atomi formula alappéldányának nevezzük, ha argumentumai alaptermek Q(f(a,b),a) Egy atomi formulát (nem alappéldány) egyébként paraméteres állításnak is neveznek. Termhelyettesítés.(könyv 123 old.) =(x1 , x2 , xk ||t1 , t2 , tk) Feladatok (könyv 129-132 old.)

18

5. előadás Szemantika (L=< Srt, Pr, Fn, Cnst >) Egy elsőrendű logikai nyelv L(Vv) interpretációja egy az L nyelvvel azonos szignatúrájú matematikai struktúra és az I interpretáció működése: I= függvénynégyes, ahol ISrt: U Ha Srt egyelemű, akkor az interpretáció univerzuma egyfajtájú elemekből áll. IPr: P PI IFn: ffI ICns: ccI Változókiértékelés. : VU. |x|I, az U univerzumbeli (x) individuum. Informális definíció. A formula valamely L(P1, P2,..., Pn; f1, f2,..., fk ) formalizált nyelven íródott, (ahol ( r1, r2, ..., rn; s1, s2, ..., sk) az L nyelv típusa/szignatúrája (υ1, υ2, υ3)). 1. lépés. Választunk egy S= U(R1, R2,..., Rn; o1, o2,..., ok) matematikai struktúrát, amelynek a típusa/szignatúrája ( r1, r2, ..., rn; s1, s2, ..., sk)/ (υ1, υ2, υ3) megegyezik a nyelvével és a logikán kívüli szimbólumokat a megfelelő relációknak illetve műveleteknek feleltetjük meg: Pi= PiI , fk=fkI , (ha az interpretáló struktúrának nincs leíró nyelve, vagy nem akarjuk azt használni. Ha felhasználjuk az interpretáló struktúra leíró nyelvét, akkor PiI =Ri és fkI = ok. Ez a nyelv szimbólumainak interpretációja, ahol Ri és ok jelentése egyértelmű.) 2. lépés. A nem kötött individuum változók kiértékelése ( |x|I,) és a kifejezések helyettesítési értékeinek kiszámítása. Formális definíció. - Termek: 1. xs individuumváltozó, |xs| I, a (x)U ( egy változókiértékelés) c konstansszimbólum |c| I, az U-beli cI elem. 2. |f(t1, t2, ..., tn)| I, = fI (|t1| I, , |t2| I, , ..., |tn| I, ) - Formulák: 1. |P(t1, t2, ..., tn)) | I, =i, ha (|t1| I, , |t2| I, , ..., |tn| I, )PI , a PI jelöli a PI reláció igazhalmazát. 2. |A| I, =|A| I, |AB| I, = |A| I,  |B| I, |AB| I, = |A| I,  |B| I, |AB| I, = |A| I,  |B| I, 3. |xA| I, =i, ha |A| I,* =i  minden * x variánsára |xA| I, =i, ha |A| I,* =i  legalább egy * x variánsára (A a formula törzse/mátrixa) A továbbiakban egyfajtájú struktúrákkal és egyfajtájú L nyelvvel (Srt egyelemű halmaz) foglalkozunk az elsőrendű logika tárgyalása során. Példa: L nyelv L= (=, P1, P2 ; a, b, f1, f2) (2, 2, 2 ; 0, 0, 2, 2 )

struktúra leíró nyelve S= N(=, <, > ; 0, 1, +, * ) (2, 2, 2 ; 0, 0, 2, 2 )

19

Egy term interpretációja (a struktúrának van leíró nyelve): |t| I, = |f1(x, f2(x,y))) | I, = |f1| I, (|x| I, , |f2(x,y)| I, ) =

1 2 3

x 1 2 0

y 1 3 4

+ ( x, * (x ,y)) = x+ x*y x+ x*y 2 8 0

Egy formula interpretációja (a struktúrának van leíró nyelve): |P1(t, f1(y, f2(x,y)))) | I, = |P1| I, (|t| I, , |(f1(y, f2(x,y))) | I, )= |P1| I, (|t| I, , |f1| I, (|y| I,, |f2| I, (|x| I,,|y| I,))) = < (+ (x,* (x,y)),+(y,*(x,y)) = <( x+ x*y, y+ x*y) = (x+ x*y)<( y+ x*y) Egy kvantormentes formula kiértékelése A formula minden alap előfordulását generáljuk és így minden állítás előáll az I-ban

x

y

(x+ x*y)<( y+ x*y)

1

1

(1+ 1*1)<( 1+ 1*1)=i

2

3

(2+ 2*3)<( 3+ 2*3)=h

Egzisztenciális formula interpretálása |x P1(a, f1(x,x))) | I, =i, ha |P1(a, f1(x,x))) | I,* =i  legalább egy * x variánsára ebben az interpretációban, ha 0<(x+x) =i legalább egy uN

Nézzük meg az értéktábláját

x 0 1

0<(x+x) h i

Mivel az x=1-re a formula törzse i, ezért a x(0<(x+x)) formula is i. univerzális formula interpretálása. Legyen s(x)=def f1(b,x). |x P1(a, f1(s(a),x))) | I, = i, ha |P1(a, f1(s(a),x))) | I,* =i  minden * x variánsára Nézzük meg az értéktábláját x 0<(1+x) 0 i 1 i Mivel minden egészre a formula törzse i, ezért a x(0<(1+x)) formula értéke i. Formulakifejtés véges U felett: U={a, b, c} xA(x)) =A(a)  A(b)  A(c) xA(x)) =A(a)  A(b)  A(c)

20

Lehetséges interpretáló struktúrák száma adott U és adott szignatúra mellett Legyen az L nyelv típusa ( r1, r2, ..., rn; s1, s2, ..., sk). Legyen U az univerzum, ahol U=M. hány különböző (r1, r2, ..., rn; s1, s2, ..., sk) típusú struktúra létezik U felett j=1n 2Mrj* t=1 kMMst Elsőrendű szemantikus fa, mint a lehetséges adott univerzum feletti ( r1, r2, ..., rn; s1, s2, ..., sk) típusú struktúrák megadásának eszköze. Az univerzum elemeinek felhasználásával előállítjuk az összes alapatomot, rögzítjük sorrendjüket (ez a bázis), a szemantikus fa szintjeihez ebben a sorrendben rendeljük hozzá az alapatomokat. Egy interpretáció a szemantikus fa egy ágán áll elő (könyv 254. és 261. o.). Példa: Legyen a formulahalmaz: K= {xP(x), yz(Q(y,z) P(z)), uv Q(u,v)} és az U={a,b,c} a B bázis:P(a),Q(a,a),P(b),Q(a,b), …, Q(c,c) alapatomsorozat I intpr.  P(a),Q(a,a),P(b),Q(a,b), …, Q(c,c) A szemantikus fa B bázis alapján. P(a)  Q(a,a)

Q(a,a) P(b) A

P(b) P(b)

P(a) Q(a,a)

P(b) P(b)

Q(a,a)

P(b) P(b)

P(b)

-val jelölt út jelzi a fenti I interpretációt reprezentáló ágat.

A formula értéktáblája Egy formula igazságtáblája és értéktáblája. Egy 1. rendű formula primformulái az atomi formulák (ezek paraméteres állítások az interpretációkban) és a kvantált formulák (ezek állítások ha zártak). Egy 1. rendű formula primkomponensei a formula azon primformulái, amelyekből a formula logikai összekötőjelek segítségével épül fel. Az igazságtáblában (ítéletlogika) az első sorba az állításváltozók (ezek a formula prímkomponensei) és a formula kerülnek. A változók alá igazságértékeiket (interpretáció) írjuk. A formula alatt a megfelelő helyettesítési értékek találhatók. X i i i

Y i i h

Z i h i

(ZXYZ) i i i és így tovább

Egy 1. rendű formula értéktáblájában az első sorba a formula szabad változói, a primkomponensek és a formula kerülnek. (Mivel a primformulák több esetben paraméteres

21

állítások, ezért az interpretációban az individuum változók kiértékelése után válnak állításokká.) A individuum változók alá a lehetséges változókiértékelések, a primformulák alá a megfelelő helyettesítési értékek kerülnek. A formula alatt a formulának a prímformulák értékei alapján kiszámított helyettesítési értékei találhatók.

Példa. A formula xP(x)yQ(w,y)P(v)zQ(w,z) A primkomponensek: xP(x), yQ(w,y), P(v), zQ(w,z). A szabad individuum változók v, w. Legyen az interpretáló struktúra: U={1, 2, 3}, |P| I ={1,3}, |Q| I ={(1,2),(1,3), (2,1), (2,2), (2,3)}, Ekkor |xP(x)) | I = h, a többiek paraméteres állítások. Az értéktábla: v 1

w 1

|xP(x)| I |yQ(w,y)| I

h

|yQ(1,y)| =i

1 1 2 3 2 2 3 3

2 3 1 1 2 3 3 2

h h h h h h h h

|yQ(2,y)|I, =i |yQ(3,y)|I, =h |yQ(1,y)|I, =i |yQ(1,y)|I, =i |yQ(2,y)|I, =i |yQ(3,y)|I, =h |yQ(3,y)|I, =h ...

I,

|P(v)| I

|zQ(w,z)| I |P| (1)=i zQ(1,z)=h

|xP(x)yQ(w,y)P(v)zQ(w,z)|I

|P| I (1)=i zQ(2,z)=i |P| I (1)=i zQ(3,z)=h |P| I (2)=h ... |P| I (3)=i |P| I (2)=h |P| I (2)=h |P| I (3)=i

i i i i i i i i

I

i

mivel a feltételrész hamis minden kiértékelésre

Formulák és formulahalmazok szemantikus tulajdonságai. Az L egy I interpretációja kielégít egy 1. rendű A formulát (I=A) , ha a formula |A| I értéke i. Ha az A formula mondat és I=A, akkor azt mondjuk, hogy az S struktúra elégíti ki A-t, így S=A . Más szóval S modellje A-nak. Ha L egy I interpretációjára az F={F1, F2, ..., Fn} formulahalmazban |Fk| I értéke i, minden 1kn-re, akkor I kielégíti F-et. Jelölés: I= F. Azt mondjuk, hogy F formulahalmaz kielégíthető ha L-nek legalább egy I interpretációja kielégíti, azaz I= F. Azt mondjuk, hogy egy G formula kielégíthető ha L-hez van legalább egy I interpretáció, hogy I= G. Azt mondjuk, hogy egy G formula logikailag igaz, ha G igaz minden lehetséges I interpretációra. Ez azt jelenti, hogy G igaz minden lehetséges interpretáló struktúrában. Jelölés: = G. Logikailag igaz és a tautologia kérdése. Azt mondjuk, hogy egy G formula tautologia, ha G értéktáblájában a prímkomponensekhez rendelhető összes lehetséges igazságérték hozzárendelés esetén a formula helyettesítési értéke i. Kielégíthetetlenség. Azt mondjuk, hogy G illetve F kielégíthetetlen (nem kielégíthető) ha L-hez nincs olyan I interpretáció, hogy I= G illetve, hogy I= F. Más szóval egy G formula kielégíthetetlen ha minden interpretációban a G értéktáblájának minden sorában G helyettesítési értéke h(amis). Az F formulahalmaz kielégíthetetlen, ha az F közös értéktáblájában minden sorban van legalább egy eleme F-nek, amelynek a helyettesítési értéke h(amis).

22

A következményfogalom az 1 rendű logikában. Szemantikus következményfogalom, eldöntésprobléma, előre- és visszakövetkeztetés 1. rendű logika: Logikai vagy szemantikus következmény. Azt mondjuk, hogy a G formula logikai (szemantikus) következménye az F formulahalmaznak, ha minden olyan I interpretációra amelyre I= F a I= G is fennáll. Jelölés: F= G. Más szóval F= G ha minden olyan interpretáló struktúrában, ahol az F, G közös értéktáblájában minden olyan sorban, ahol az F elemeinek helyettesítési értéke i(gaz), a G helyettesítési értéke is i(gaz). Jelölés: F= G vagy {F1, F2, ..., Fn}= G. -Egy G formula bármely F feltételhalmaznak következménye - G logikailag igaz. Az ítéletlogikában bebízonyított tételek itt is igazak. Tétel: F-nek szemantikus következménye G, akkor és csak akkor, ha az F  {G} kielégíthetetlen (egyik eldöntésprobléma). Visszakövetkeztetés Tétel: Ha F-nek következménye G1 és S-nek következménye G2, valamint, {G1, G2}-nek következménye A, akkor az F  S-nek következménye A. A következményfogalom alapján, annak eldöntése, hogy F= G elméletileg megoldható az interpretáló struktúrákban az F1, F2, ..., Fn és G-re kapott közös értéktábla alapján. Ha minden olyan interpretáló struktúrában, ahol ennek a közös értéktáblának minden olyan sorában, ahol F1, F2, ..., Fn igaz a G szintén igaz akkor F=G (G logikai következménye F-nek). Ha G kizárólag azokban sorokban igaz ahol F1, F2, ..., Fn igazak, akkor G a legszűkebb következménye F-nek. - Az A és B elsőrendű formulák logikailag ekvivalensek ha A=B és B=A. Tétel . G elsőrendű formula. Ha =0 G, akkor = G. (Ha G tautologia, akkor G logikailag igaz) Biz. Ha =0 G, akkor G igaz a prímkomponenseinek minden igazságkiértékelésére. Tekintsük a G egy I interpretációját, az individuum változók egy  kiértékelése mellett. Ekkor a prímkomponensek igazságértéke, és ezután a G helyettesítési értéke kiszámítható és i mivel=0 G. Tétel. Ha F=0 G, akkor F= G. Biz. Az F prímkomponenseinek minden az F-et kielégítő I interpretációjára (I=0 F) I kielégíti G-t is. Ha az I interpretáció kielégíti F-et, akkor kielégíti G-t is mivel az egyidejűleg igazságkiértékelés. Tétel. Ha A és B tautologikusan ekvivalens, akkor A és B logikailag ekvivalens. Tétel. (Dedukciós tétel) {F1, F2, ..., Fn}=G  {F1, F2, ..., Fn-1}=FnG Biz. (ugyanaz, mint a 0. rendű logikában) Tétel (Eldöntésprobléma a predikátumlogikában) {F1, F2, ..., Fn}=G  = F1(F2(...( Fn-1(FnG))...)). [Vagyis F1(F2(...( Fn-1(FnG))...)) logikailag igaz]. Biz.  Ha {F1, F2, ..., Fn}=G, akkor =F1(F2(...( Fn-1(FnG))...)). A (Ded.) tétel nszeres alkalmazása az  irányba  Ha =F1(F2(...( Fn-1(FnG))...)), akkor {F1, F2, ..., Fn}=G. A (Ded.) tétel nszeres alkalmazása az  irányba.

23

Helyes következtetési formák. Egy F, B pár helyes következtetési forma, ha B szemantikus következménye F-nek. Általános érvényű ítéletlogikabeli következtetésformák (könyv 165 old.) Például {AB,A}=0B, modus ponens {AB,A}=0B, modus ponens más alakban {AB,B}=0A, modus tollens vagy kontrapozíció. stb. Általános érvényű 1. rendű következtetésformák xA(x)=A(t), t tetszőleges jft. Előrekövetkeztetés és visszakövetkeztetés mint az ítéletlogikában. A 0 és 1 rendű eldöntésprobléma megoldása szemantikai eszközökkel. Egy n-változós ítéletlogikai B formula tautologia, ha - hamis halmaza üres. Ez azt jelenti, hogy B kielégíthetetlen. - az ítéletváltozók minden kiértékelésére (minden interpretációban) a helyettesítési érték i. 1. rendű n változós B formula logikailag igaz, - ha minden U univerzumon, a változók minden behelyettesítése mellett kapott B’ alapformulák igazak minden, a nyelvnek megfelelő struktúrában. - ha B kielégíthetetlen. Egyetlen interpretációban sem igaz. Ezek a problémák szemantikailag világosak, de megoldásuk a teljes kipróbálást tételezi fel. Algoritmusokra van szükség a megoldáshoz.

Gödel bebizonyította, hogy „Az eldöntésprobléma algoritmikusan nem oldható meg – nem létezik univerzális eldöntési algoritmus” Kutatások „eldönthető formulaosztályok” keresésére.

24

Formulák logikailag ekvivalens átalakításai Előkészítő definíciók: literál, azonos alapú literál, különböző literál, elemi konjunkció, -diszjunkció, teljes elemi konjunkció, -diszjunkció, konjunktív és diszjunktív normálforma (KNF, DNF), kitüntetett konjunktív és diszjunktív normálforma (KKNF, KDNF felírásának algoritmusa) (könyv 93-96 és 99-100 old.). Egyszerűsítési szabályok: 1. (Xd)(Xd)= d, 2. . (Xk) (Xk)=k, ahol d elemi diszjunkció és k elemi konjunkció. KKNF és KDNF, valamint KNF és DNF egyszerűsítése. Tetszőleges formulák átírása DNF-be és KNF-be. Döntési algoritmus, levezető eljárás egy olyan algoritmus, amely adott input adatokkal dolgozik, azokat a megfelelő szabályok szerint használja fel és a levezetési szabály szerint alakítja át és akkor áll meg amikor a kitűzött célt (az algoritmus megállási feltétele) elérte. A megállással egy kétesélyes döntés egyik kimenetét igazolja. Azonban, ha az algoritmus nem éri el a kitűzött célt az nem feltétlenül jelenti azt, hogy meghozta a másik eshetőségre a döntést. Az egyik eldöntésprobléma megoldására: egy formula kielégíthetetlenségének eldöntésére több döntési algoritmus ismert. Ezekről bebizonyítható, hogy ha a formula felhasználásával az algoritmus eléri a megállási feltételt, akkor a formula kielégíthetetlen (vagyis, ha a formula a F1F2...FnG akkor bebizonyítottuk, hogy {F1, F2, ..., Fn}=0G.) Azt is mondjuk, hogy az ilyen algoritmusok automatikus tételbizonyító algoritmusok. 6. és 7. előadás. Itéletlogika. Ha az {F1, F2, ..., Fn}=0G, akkor és csak akkor {F1,F2,..., Fn-1,Fn,G} következésképen F1F2...FnG kielégíthetetlen. Átírva KNFF1KNFF2...KNFFn-1KNFFn KNFG kielégíthetetlen ezért {KNFF1,KNFF2,...,KNFFn-1,KNFFn, KNFG} kielégíthetetlen Más szóval a belőle kapott S klózhalmaz kielégíthetelen Példa: (XY)  (XZ)  (XZ)  (YZ)  Z, A kapott klózhalamaz: {XY, XZ, XZ, YZ, Z} Elnevezések: n-változós klóz 1-változós klóz 0-változós klóz

n-argumentumos klóz egységklóz üres klóz 

S klózhalmaz és a szemantikus fa Egy k klóz akkor hamis egy interpretációban, ha minden literálja hamis. Egy L literál hamis abban az interpretációban, ahol a szemantikus fában a literálnak megfelelő címke L. Egy

25

klóz illesztése a szemantikus fára az olyan ágak kiválasztása amelyeken a klóz minden literálja negálva szerepel. Ezekben az interpretációkban ez a klóz hamis. Cáfoló csúcsnak nevezzük a szemantikus fa azon csúcsát, amelyiket elérve egy klóz (amely azt megelőzően még nem volt hamis) hamissá válik. Levezető csúcsnak nevezzük a szemantikus fa azon csúcsát, amelyiket két cáfoló csúcs követ. A szemantikus fa egy ága zárt, ha cáfoló csúcsban végződik. A szemantikus fa zárt, ha minden ága zárt. Tétel: Minden zárt T szemantikus fának van legalább egy levezető csúcsa. Bizonyítás: Tegyük fel, hogy T zárt, de nincs levezető csúcsa. T szintszáma n. Más szóval T egyetlen szintjén sincs levezető csúcs. Tehát minden szinten van legalább egy csúcs, amelyet követő két csúcs közül legalább az egyik nem cáfoló csúcs. Igy van ez az n-dik szinten is, ami azt jelenti, hogy T-nek van legalább egy nyitott ága ellentétben azzal, hogy egy zárt T-ből indultunk ki. Példa: {XY, XZ, XZ, YZ, Z} khtlen. Klózok illesztése szemantikus fára. Fa ágának lezárása. Cáfoló csúcs (), levezető csúcs () (könyv 225-227 old).

X

X 

Y XY

Y

Z Z Z, XZ YZ Zárt szemantikus fa

Y Y   Z Z Z Z Z XZ Z XZ YZ

Példa {XY, XZ, YZ, Z} khető X

X Y Z Z Z,  YZ

Y XY

Y 

Y

 Z Z Z Z Z XZ Z XZ YZ

Nem zárt szemantikus fa cáfoló csúcs, levezetõ csúcs, zárt ág, zárt fa.

26

Elsőrendű logika Az F1F2...FnG elsőrendű formulát logikailag ekvivalens módon át kell írni elsőrendű klózok konjunkciójává. Elsőrendű klóz: xy(P(x)Q(x,f(y)). Elsőrendű logika formuláinak logikailag ekvivalens átalakításai. Def: prenex forma. Jelöle Q bármely kvantort. A Qx1 Qx2 ... QxnB formula egy prenex formula. Qx1 Qx2 ... Qxn a prefixum és B a formula törzse, mátrixa. B kvantormentes formula. Minden 1. rendű formula átírható prenex formába. Átírási szabályok xA=xA,

xA=xA

általános De Morgan szabályok

A kvantorkiemelési szabályok 1. xA[x]B=x(A[x]B) “  “= “  “ 2. xA[x]B= x(A[x]B) “  “= “ “ 3. xA[x]xB[x]= x(A[x] B[x]) , de  -re nem 4. xA[x] xB[x] = x(A[x] B[x]), de  -re nem. 5. Q1xA[x] Q2xB[x]=Q1xQ2z(A[x]B[x/z]) 6. Q1xA[x] Q2xB[x]= Q1xQ2z(A[x] B[x/z]). A prenex formába való átírás algoritmusa. 1. A logikai összekötőjelek átírása , , -ra. 2. A De Morgan szabályok alkalmazása addig amíg a  hatásköre atomi formula nem lesz. 3. A kvantorkiemelési szabályok alkalmazása addig amíg minden kvantor a formula elejére nem kerül (a formula törzse kvantormentes formula). Példa. x (yP(x,y)y (Q(y)P(x,a))) xy(P(x,y)R(x,y)) 1. lépés x (yP(x,y)y(Q(y)P(x,a))) xy(P(x,y)R(x,y)) 2. lépés. x(yP(x,y)y(Q(y)P(x,a)))xy(P(x,y)R(x,y)) x(yP(x,y) y(Q(y)P(x,a))) xy(P(x,y)R(x,y)) x(yP(x,y) y (Q(y)P(x,a))) xy(P(x,y)  R(x,y)) x(yP(x,y) y (Q(y)P(x,a))) xy(P(x,y)  R(x,y)) 3. lépés. kvantorkiemelési szabályok x-re x(yP(x,y) y (Q(y)P(x,a))  y(P(x,y)  R(x,y))) y-ra először végrehajtjuk az y/y1 helyettesítést a y-al kezdődő első részformulában és az y/y2 helyettesítést ay al kezdődő második részformulában x(yP(x,y) y1 (Q(y1)P(x,a))  y2 (P(x,y2)  R(x,y2))) xy(P(x,y) y1 (Q(y1)P(x,a))  y2 (P(x,y2)  R(x,y2))) és végül xyy1 y2 (P(x,y) (Q(y1)P(x,a))  (P(x,y2)  R(x,y2))) Megkaptuk a prenex formulát.

27

Ha a prenex formula törzse KNF-ben vagy DNF-ben van, akkor a formula normálforma: prenex konjunktív / prenex diszjunktív formula. A másik speciális formula egy 1. rendű formula Skolem formája. A x1, x2, ..., xnA formulát , ahol a prefixumban csak univerzális kvantorok vannak Skolem formulának, ha az A formula alakja KNF, akkor Skolem normál formulának nevezzük. (A Skolem formulák eldönthető formulaosztályt alkotnak) Minden 1. rendű formula átírható Skolem formába. Először átírjuk a formulát prenex formába. Azután bevezetjük a Skolem függvényeket és elimináljuk az egzisztenciális kvantorokat. Tekintsük az első egzisztenciális kvantort a prefixumban, legyen ez xj. Ha a formula igaz, akkor az x1, x2, ..., xj-1 változók minden értékkombinációjához létezik legalább egy értéke az xj változónak amelyre a formula értéke i. Ezt a tényt az f(x1, x2, ..., xj-1 ) =xj függvénnyel fejezzük ki. Ez a függvény rendeli az xj -hez a megfelelő értéket. Ezt a lépést végrehajtjuk a soronkövetkező egzisztenciális kvantorra addig amíg, minden egzisztenciális kvantort nem elimináltunk. Pl. xyP(x,y) Skolem alak: xP(x,f(x)) Megkonstruáljuk az előbbi formula Skolem formuláját, amelyben a törzs KNF alakú. A kvantorok bevitelével átírjuk elsőrendű klózok konjunkciójaként a formulát. Majd változóátnevezést alkalmazunk. Legyen a Skolem formula: xy[(P(x)Q(x,f(y))) (P(g(x))P(y)) Q(g(x),x)] A mag konjunkciós formula. Alkalmazzuk a kvantorkiemelési szabályt. A kapott formula: xy(P(x)Q(x,f(y)))  xyP(g(x))P(y)  xy Q(g(x),x). A változóátnevezések után a változóidegen klózhalmaz: xyP(x)Q(x,f(y)), zvP(g(z))P(v), uQ(g(u),u) A szemantikus eldöntésprobléma új alakja a Skolem formula elsőrendű klózai S halmazának kielégíthetetlensége. Herbrand eredménye, hogy a kielégíthetetlenséget egyetlen univerzum (Herbrand univerzum) feletti összes interpretációban kell csak vizsgálni. Ez az univerzum a leíró nyelv összes alaptermjeinek halmaza. (könyv 258-259 old.) A nyelvbex f(x), g(x) függvényszimbólumok, a konstansszimbólum alaptermek: a f(a),g(a),f(f(a)),f(g(a)),… A feladat tehát Az F1F2...FnG elsőrendű formulát logikailag ekvivalens módon át kell írni elsőrendű klózok konjunkciójává. Elsőrendű klóz: xy(P(x)Q(x,f(y)). Az eldöntésprobléma megoldásának egy szintaktikus eszköze a Rezolúciós elv. Ítéletlogikában a {F1,F2,..., Fn-1,Fn,G}-ből kapott klózhalmaz az input. Elsőrendű logikában a {F1,F2,..., Fn-1,Fn,G}-ből kapott elsőrendű klózhalmaz az input. vagy az az elsőrendű klózhalmaz Herbrand univerzumon való kifejtésének eredményeként az {F1,F2,..., Fn-1,Fn,G}-ből kapott elsőrendű klózhalmaz klózainak alappéldányait tartalmazó alapklózhalmaz az input.

28

Megjegyzés: Egy ítéletlogikai klózokból álló klózhalmaz és egy univerzum feletti alapklózokból álló klózhalmaz kielégíthetetlensége ugyanúgy kezelhető. Azaz ha klózhalmazban szereplő literálok (ítéletváltozók - alapatomok) minden I interpretációjában a klózhalmaz legalább egy klóza hamis, akkor a klózhalmaz kielégíthetetlen. Az alapatomok interpretációi a hozzájuk rendelt i, h értékek ugyanúgy, mint az ítéletlogikában az ítéletváltozókhoz rendelt i, h értékek. Ezért a továbbiakban számunkra a literál alapja ítéletváltozó vagy alapatom. Így az ítéletlogikai rezolúciós kalkulust, valamint az alapklózhalmazon definiált alaprezolúciós kalkulust egyszerre lehet definiálni. Rezolvens fogalma, legyenek C1, C2 olyan klózok, amelyek pontosan egy komplemens literálpárt tartalmaznak: C1= C’1 L1 és C2= C’2 L2 és L1= L2 ,ekkor létezik rezolvensük res(C1, C2) = C klóz, ami C= C’1 C’2. Tétel: { C1, C2}=0 C (könyv 227-228 old.) Def. K klózhalmazból való rezolúciós levezetés egy olyan (könyv 229 old.) véges k1, k2, ..., kn klózsorozat, ahol minden j=1, 2, ..., n-re 1. vagy kj K 2. vagy van olyan 1s,tj, hogy kj a ks, kt klózpár rezolvense. Levezetés célja üres klóz levezetése / megállási feltétel. Példa K ={AB, AC, AC, BC, C}-ből rezolúciós levezetés: 1.C, K 2.AC, K 3.A, res(1,2) 4.AC, K 5.C, res(3,4) 6. res(1,5) K klózhalmazból való rezolúciós levezetés mint döntési eljárás. Eldöntésproblémája : levezethető-e egy K klózhalmazból az üres klóz? Rezolúciós cáfolat. Tétel: (Helyesség) Ha a K klózhalmazból levezethető az üres klóz, akkor a K klózhalmaz kielégíthetetlen. (könyv 230 old.) Biz. a { C1, C2}=0 C felhasználásával Tétel: (Teljesség) Ha a K klózhalmaz kielégíthetetlen, akkor a K klózhalmaznak van rezolúciós cáfolata. (könyv 230-231 old.) Biz. Zárt szemantikus fával Előrekövetkeztetés és visszakövetkeztetés rezolúciós kalkulussal. (könyv 233-234 old.) Def. Levezetési fa. (Egy rezolúciós levezetés szerkezetét mutatja) (könyv 235-236 old.) Rezolúciós stratégiák. Lineáris rezolúció (teljes), lineáris input-, egység rezolúció (nem teljes) (könyv 236-238 old)

29

Lineáris rezolúciós levezetés egy S klózhalmazból egy olyan q1, p1, q2, p2, ...qn, pn, klózsorozat, ahol q1, p1S a qi (i=2, 3,...,n) esetben a pi a pi-1,qi-1 rezolvense, ahol qi-1S, vagy egy korábban megkapott centrális klóz (rezolvense valamely ps, qs (s
q1

p2

q2

p3 . . . p(i-1) pi

lineáris reprezentáció p1 q1 p2 q2 p3 .

q(i-1)

.

. p(i-1) q(i-1) pi

Lineáris input rezolúciós levezetés egy S klózhalmazból egy olyan q1, p1, q2, p2, ...qn, pn, klózsorozat, ahol q1, p1S a qi (i=2, 3,...,n) esetben qiS és a pi pedig a p(i-1),q(i-1) rezolvense. Horn klózok. Horn logika. Def. Egy klózt Horn klóznak nevezünk, ha legfeljebb egy literálja nem negált. Def. Horn logika az összes, csak Horn klózokat tartalmazó KNF alakú formulák halmaza. Pl. S={BC, AC, AB, AC, C} Horn klózok halmaza lineáris input levezetés egységrezolúciós levezetés 1. BC S 1. BC S 2. AB S 2. C S 3. AC rez(1,2) 3. B rez(1,2) 4. AC S 4. AB S 5. C rez(3,4) 5. A rez(3,4) 6. C S 6. AC S 7.  rez(5,6) 7. C rez(5,6) 8.  rez(2,7) Tétel: Ha az levezethető lineáris input rezolúcióval egy K klózhalmazból, akkor K-ban van legalább egy egységklóz. Biz. Az -t mint rezolvenst egy centrális egységklózból és egy klózhalmazbeli klózból kapjuk, Ez utóbbi csak egységklóz lehet. Tétel:Kielégíthetetlen Horn klózhalmazban van legalább egy egységklóz. {AB, AB, AB, AB} nincs lineáris input cáfolat. {BC, AC, AB, AC, C} van lineáris input cáfolat.

30

Teljes levezetési fa adott klózzal kezdődő összes lineáris levezetés megadására. C BC

AC

B

A

AB

AB

AC

A +

B

C

AC

BC

BC AC

C

C

C

AC

C



A +



A nem ad újat

B AC A +

AB A

+ folyt. mint +-nál

Példa alaprezolúcióra Előállítjuk az első rendű klózok magjainak összes alappéldányát és az alapklózok halmazán ítéletlogikai rezolúcióval levezetjük az üres klózt. Az elsőrendű klózhalmaz:

{xyP(x)Q(x,f(y)), zvP(g(z))P(v), uQ(g(u),u)} H univerzum: a, g(a), f(a), g(f(a)), g(g(a)), (A klózhalmaz leíró nyelvének összes alaptermje) Alapklózok: x y z v u P(x)Q(x,f(y))

f(f(a)), f(g(a)), … P(g(z))P(v)

Q(g(u),u)

a

a

a

a

a

P(a)Q(a,f(a))

P(g(a))P(a)

Q(g(a),a)

g(a)

a

a

g(a)

a

P(g(a))Q(g(a),f(a))

P(g(a))P(g(a))

Q(g(a),a)

g(a)

a

a

g(a)

f(a) P(g(a))Q(g(a),f(a))

P(g(a))P(g(a))

Q(g(f(a)), f(a))

g(f(a))

a

f(a) g(f(a))

f(a) P(g(f(a))) P(g(f(a)))P(g(f(a))) Q(g(f(a)),f(a))

alaprezolúció 1. Q(g(f(a)), f(a)) u/f(a) 2. P(g(f(a)))Q(g(f(a)),f(a)) x/g(f(a)), y/a 3. P(g(f(a))) 4. P(g(f(a))) z/f(a), v/ g(f(a)) 5. 

Q(g(f(a)), f(a))

1. X 2. YX 3. Y 4. Y 5. 

31

Legyen a bázis első két eleme P(g(f(a))), Q(g(f(a)), f(a)), … Illesszük szemantikus fára az alapklózhalmazt.

P(g(f(a)))

P(g(f(a)))

P(g(f(a))) Q(g(f(a)),f(a)) P(g(f(a)))Q(g(f(a)),f(a))

Q(g(f(a)),f(a)) Q(g(f(a)), f(a))

Ezekkel az alapklózokkal lezártuk a szemantikus fát. Az elsőrendű rezolúciós kalkulushoz definiálni kell két elsőrendű klóz elsőrendű rezolvensét. Az elsőrendű rezolúciós levezetés definíciója ezután ugyanaz mint az ítéletlogikában. Az elsőrendű lineáris input rezolúciós stratégia a háttere a Prolog programozási nyelvnek. A Prolog elsőrendű lineáris inputrezolúcióval dolgozza fel az elsőrendű klózhalmazt, felépíti a teljes levezetési fát és ilymódon az összes megoldást előállítja. (további részletek könyv 349-374. o.) Irodalom Pásztorné Varga Katalin, Várterész Magda: A matematikai logika alkalmazásszemléletű tárgyalása. PANEM kiadó, 2003 (jegyzetboltban kapható)

32

Tételek: 1. Mit értünk egy formulának adott I interpretációban való Boole értékelésén (igazságkiértékelésén)? Milyen eleme az igazságkiértékelés az ítéletlogikának? Mit ad meg egy igazságtábla? Mi az igazságértékelés függvény (Ai, Ah)? Hogyan kapcsolódik egymáshoz az igazságértékelés, az igazságtábla, az igazságkiértékelés és az interpretáció? 2. Ismertesse az ítéletlogikat leíró nyelvet (ABC, szintaxis, szemantika). Mi a jólformált formula definíciója az ítéletlogikában? Mit ír le egy ilyen formula? Hány leképezést lehet definiálni n ítéletváltozó felett? Milyen eleme a jólformált formula fogalma az ítéletlogika leíró nyelvének? 3. Mi egy formula igazságtáblája és igaz halmaza? Milyen speciális tulajdonságú formulákat ismer az általuk leírt leképezést tekintve? Lehet-e több formula igazhalmaza ugyanaz? Ha igen, akkor mi ennek a feltétele? Megkapható-e tetszőleges F1 ,F2 formulára az (F1 F2) igazhalmaza az F1 ,F2 igazhalmazából? 4. Mit jelent az, hogy egy adott igazságkiértékelés kielégít egy F formulahalmazt? Mi az igazságkiértékelés? Definiálja a tautológia, a kielégíthető formula, a kielégíthetetlen formula fogalmakat és a szemantikus következmény fogalmát. 5. Mit értünk helyes következtetésforma alatt? Hogyan lehet igazságtáblával ellenőrizni, hogy F=oA fennáll-e? Hogyan lehet igazságtáblával megadni a legszűkebb következményt. Definiálja a tautológikus ekvivalencia fogalmat. 6. Ha {F1,F2,...,Fn}=oA, akkor milyen tulajdonsága van a {F1,F2,...,Fn,A} formulahalmaznak és miért? Mondja ki és bizonyítsa be a dedukciós tételt. 7. Bizonyítsa be, hogy {F1,F2,...,Fn}=oA akkor és csak akkor, ha {F1,F2,...,Fn-1}=o FnA. Melyik tétel ez? Milyen fontos logikai eredményt lehet a tétel felhasználásával belátni? 8. Melyek az ítéletlogika eldöntésproblémái? Mi köztük és az automatikus tételbizonyítás közötti kapcsolat? Mely tételek adják ezt meg? Ismertesse e tételek bizonyításának elvét. Van-e elsőrendben is hasonló eredmény? 9. Mi a rezolúciós elv eldöntésproblémája az ítéletlogikában? Melyek a rezolúciós elv alapfogalmai? Definiálja a rezolúciós levezetést. Lássa be, hogy a rezolúciós kalkulus helyes. 10. Milyen kapcsolat van a C rezolvens klóz és ősei, C1 ,C2 között az ítéletlogikában és az 1.-rendű logikában.? Bizonyítsa be az erre vonatkozó tételt az ítéletlogikában. Mit biztosít ez a kapcsolat a rezolúciós elvre, mint kalkulusra nézve? 11. Hogyan kell előkészíteni egy 0-ad illetve egy 1. rendű tételbizonyítási feladatot a rezolúciós elvvel való megoldásra? Mi a rezolvens? Mikor létezik rezolvens? Lássa be, hogy az üres klóz kielégíthetetlen. 12. Ismertesse a predikátumlogikát leíró nyelvet. Mi a nyelv szintaxisa és szemantikája? A nyelv típusa (szignatúrája) alapján határozza meg a lehetséges interpretáló struktúrák számát adott számosságú univerzumon (szemantikus fával vagy kombinatórikus úton). 13. Mit ír le egy jólformált formula a predikátumlogikában? Mit értünk formalizálás alatt elsőrendben? Hogyan lehet megadni egy elsőrendű formula által leírt leképezést? Mit jelent az, hogy egy elsőrendű formula logikailag igaz. Lehet-e egy elsőrendű formula tautológia? 14. Mit fejez ki a F=A jelsorozat? Mi a predikátumlogika következményfogalma és melyek eldöntésproblémái. Megoldható-e ez kiértékeléssel? Mi a formula kifejtése? Rezolúciós kalkulussal való döntéshez hogyan kell átalakítani a feltételhalmazt és a tételformulát? 15. Mi a logikai összekötőjelek és a kvantor hatásköre? Definiálja a szabad, a kötött és a vegyes előfordulású változó, a nyitott formula és a mondat fogalmát. A különböző formulák egy vagy több állítást fejeznek ki? Melyik az a formulafajta, amely egyetlen állítást jelent?

33

Fontosabb definíciók: Definíció: Gondolkodásforma vagy következtetésforma egy F = {A1, A2,…,An} állítás (formula)halmaz és egy A állításból/formulából álló (F,A) pár. Definíció: Helyes következtetésforma egy(F,A) pár, ha minden olyan esetben/interpretációban, amikor az F-ben minden állítás/formula igaz, a következmény állítás/formula (az A) is igaz, Definíció: Függvénynek nevezünk egy DR leképezést, (D a leképezés értelmezési tartománya, R az értékkészlete. Függvényosztályozás, definíciók: 1. logikai függvény – reláció, D tetszőleges, R= {i,h} 2. matematikai függvény – művelet. olyan DR leképezés, ahol D=Rn., vagyis tetszőleges R-re: Rn R. Definíció: (ítéletlogika, könyv. 48.old. 4.1.6.def) Közvetlen részformula 1. prímformulának nincs közvetlen részformulája. 2. A közvetlen részformulája, az A formula 3. Az (AB) közvetlen részformulái az A (baloldali) és a B (jobboldali) Definíció: (ítéletlogika,könyv. 52.old. 4.1.17.def) : A logikai műveletek hatásköre a formula részformulái közül az a legkisebb logikai összetettségű, amelyben az adott logikai összekötőjel előfordul. Definíció: (könyv. 52.old. 4.1.18.def) Fő logikai összekötőjel. Egy formula fő logikai összekötőjele az az összekötőjel, amelynek a hatásköre maga a formula. Definíció (ítéletlogika). Egy n-változós szemantikus fa egy n-szintű bináris fa, ahol a szintek a bázisbeli változóknak vannak megfeleltetve. Egy X változó szintjén a csúcsokból kiinduló élpárokhoz X, X. cimkéket rendelünk. X jelentése X igaz, X jelentése X hamis, így egy n-szintű szemantikus fa ágain az összes (2n ) lehetséges igazságkiértékelés (I interpretáció) megjelenik. Definíció: Egy n-változós formula igazságtáblája egy olyan n+1 oszlopból és 2n+1 sorból álló táblázat, ahol a fejlécben a bázis (a formula változói rögzített sorrendben) és a formula szerepel. A sorokban a változók alatt az interpretációk (a változók igazságkiértékelései), a formula alatt a formula helyettesítési értékei találhatók. Definíció: Egy formula igazhalmaza azon I interpretációk halmaz amelyekre a formula helyettesítési értéke igaz Egy formula hamishalmaza azon I interpretációk halmaz amelyekre a formula helyettesítési értéke hamis Definíció: Azt mondjuk, hogy az ítéletlogikában egy I interpretáció kielégít egy B formulát (I=0B). ha a formula helyettesítési értéke i az I interpretációban. Definíció: Azt mondjuk, hogy egy B formula kielégíthető, ha legalább egy interpretáció kielégíti. Definíció: Azt mondjuk, hogy egy B formula kielégíthetetlen, ha egyetlen interpretáció sem elégíti ki. Definíció: Azt mondjuk, hogy egy B formula tautologia (=0B), ha minden interpretáció kielégíti. A tautologiát ítéletlogikai törvénynek is nevezik.(71. old.) Legyen F = {A1, A2,…,An} formulahalmaz Definíció: Azt mondjuk, hogy az ítéletlogikában egy I interpretáció kielégít egy F formulahalmazt (I=0F). ha a formulahalmaz minden formulájának helyettesítési értéke i az I interpretációban. Definíció: Azt mondjuk, hogy egy F formulahalmaz kielégíthető, ha legalább egy interpretáció kielégíti. Definíció: Azt mondjuk, hogy F formulahalmaz kielégíthetetlen, ha bármely interpretációban legalább egy formulájának helyettesítési értéke h (nincs olyan interpretáció, ami kielégítené). Definíció: Két vagy több formula igazságtáblája lehet azonos, ekkor azt mondjuk, hogy a formulák tautologikusan ekvivalensek. Ennek jelölésére a ~0 szimbólumot használjuk. Példák: XY~0 XY, X~0 X, és néhány fontos azonosság. Definíció: -Egy G formula az F={F1, F2, ..., Fn} formulahalmaznak tautologikus következménye, ha minden olyan I interpretációra amelyre I=0{F1, F2, ..., Fn} fennáll, I=0G is fennáll. Jelölés: (F=){F1, F2, ..., Fn}=0G -Ha egy G formula bármely F feltételhalmaznak következménye, akkor G tautologia. Definíció: Alapkifejezés a változót nem tartalmazó L kifejezés (alapformula, alapterm). Ezeket az indivíduumváltozók konstansszimbólumokkal, vagy rögzített U univerzum esetén univerzumelemekkel való behelyettesítésével kapjuk. Szokás alappéldányoknak is nevezni az alapkifejezéseket. Az atomi formulák alappéldányait két csoportba soroljuk.

34

a)Egy atomi formula neve alapatom, ha argumentumai konstans szimbólumok vagy univerzumelemek b)Egy atomi formulát az atomi formula alappéldányának nevezzük, ha argumentumai alaptermek Egy atomi formulát (nem alapatom) egyébként paraméteres állításnak is neveznek. Definíció: Döntési algoritmus, levezető eljárás egy olyan algoritmus, amely adott input adatokkal dolgozik, azokat a megfelelő szabályok szerint használja fel, a levezetési szabály szerint alakítja át és akkor áll meg amikor a kitűzött célt (az algoritmus megállási feltétele) elérte. A megállással egy kétesélyes döntés egyik kimenetét igazolja. Azonban, ha az algoritmus nem éri el a kitűzött célt az nem feltétlenül jelenti azt, hogy meghozta a másik eshetőségre a döntést. Rezolvens fogalma, legyenek C1, C2 olyan klózok, amelyek pontosan egy komplemens literálpárt tartalmaznak: C1= C’1 L1 és C2= C’2 L2 és L1= L2 ,ekkor létezik rezolvensük res(C1, C2) = C klóz, ami C= C’1 C’2. Definíció. K klózhalmazból való rezolúciós levezetés egy olyan (könyv 229 old.) véges k1, k2, ..., kn klózsorozat, ahol minden j=1, 2, ..., n-re 1. vagy kj K 2. vagy van olyan 1s,tj, hogy kj a ks, kt klózpár rezolvense. Def. Egy klózt Horn klóznak nevezünk, ha legfeljebb egy literálja nem negált. Def. Horn logika az összes, csak Horn klózokat tartalmazó KNF alakú formulák halmaza. Definíció: Lineáris rezolúciós levezetés egy S klózhalmazból egy olyan q1, p1, q2, p2, ...qn, pn, klózsorozat, ahol q1, p1S a qi (i=2, 3,...,n) esetben a pi a pi-1,qi-1 rezolvense, ahol qi-1S, vagy egy korábban megkapott centrális klóz (rezolvense valamely ps, qs (s
35

A továbbiak már nem tartoznak az anyaghoz. Példa: F(PQR)(PQ) ( PR) igazságértékelés fája: F(PQR)(PQ) ( PR) és F (PQ) ( PR)

T(PQR) vagy TP

vagy T QR

F PQ

és TQ

F PR

és TR

FP

és FQ

FP

FR

FFF. ábra A hamissá váláshoz négy feltételcsoportot kaptunk Ezek egyike sem teljesíthető TP, FP, FQ TP, FP, FR TQ, TR, FP, FQ TQ, TR, FP, FR A feltételek egyike sem teljesíthető, tehát a formula tautológia.

1. előadás 1. oldal Bevezető rész – logika tárgya és feladata A legfontosabb matematikai eszköztár A nyelv fogalma Ítéletlogika. Egyszerű és összetett állítás fogalma. Ítéletlogika leíró nyelvének - ábécéje - szintaxisa - szemantikája. 2. előadás 5. oldal Formulák és formulahalmazok szemantikus tulajdonságai. Szemantikus/tautologikus ekvivalencia, átírási és egyszerűsítési szabályok. Ítéletlogikai törvények Szemantikus következményfogalom az itéletlogikában. Eldöntésproblémák Dedukciós tétel 3. előadás 10. oldal Előre- és visszakövetkeztetés

36

Legszűkebb következmény Problémamegoldás, formalizálás ítéletlogikában. Elsőrendű logika. Elsőrendű és nulladrendű állítások. Szintaxis. Formulavizsgálatok. 4. előadás 12. oldal elsőrendű logika alapfogalmak Matematikai struktúra leíró nyelve, szignatúrája Az elsőrendű logika leíró nyelve, szignatúrája Egy és többfajtájú logika Szintaxis. Termhelyettesítés. Alapkifejezések. 5. előadás 17. oldal Elsőrendű logika. Szemantika. Lehetséges interpretáló struktúrák száma adott U és adott típus mellett Egy formula igazságtáblája és értéktáblája Következményfogalom és eldöntésprobléma az 1 rendű logikában 6. és 7. előadás 22. oldal. Formulák logikailag ekvivalens átalakításai Döntési algoritmus, levezető eljárás S klózhalmaz és a szemantikus fa Elsőrendű logika formuláinak logikailag ekvivalens átalakításai. Prenex és Skolem formula Rezolúciós elv. Rezolúciós stratégiák Horn klózok. Horn logika. Teljes levezetési fa Alaprezolúció

37