Várterész Magda - Az informatika logikai alapjai

Országok listájaHungaryDebreceni EgyetemInformatikai KarProgramtervező informatikusAz Informatika Logikai AlapjaiJegyzetekVárterész Magda - Az informatika logikai alapjai

VÁRTERÉSZ MAGDA

Az informatika logikai alapjai eladások

2006/07-es tanév 1. félév

Tartalomjegyzék
1. Bevezetés 2. Az ítéletlogika 2.1. Az ítéletlogika nyelve ­ szintaxis . . 2.2. Az ítéletlogika nyelve ­ szemantika 2.3. Ítéletlogikai törvények . . . . . . . 2.3.1. Formulák normálformái . . . 2.4. Szemantikus következményfogalom . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 18 18 26 31 39 44 51 51 81 100 118 120 127 131

3. Az elsrend logika 3.1. Elsrend logikai nyelvek ­ szintaxis . 3.2. Elsrend logikai nyelvek ­ szemantika 3.3. Elsrend logikai törvények . . . . . . 3.3.1. Formulák prenex alakja . . . . . 3.4. Szemantikus következményfogalom . . 4. A szekventkalkulus Irodalomjegyzék

1

1. fejezet

Bevezetés A logika szó · hétköznapi jelentése: rendszeresség, következetesség ­ Ez logikus beszéd volt. ­ Nincs benne logika. ­ Más logika szerint gondolkodik. · egy tudományszak neve: f feladata a helyes következtetés ­ fogalmának szabatos meghatározása, ­ törvényszerségeinek feltárása.
2

3

A következtetés gondolati eljárás kiinduló információk állítások premisszák = nyelvi megnyilvánulás kinyert információ állítás konklúzió

A logika feladata: a premisszák és a konklúzió közötti összefüggés tanulmányozása.

4

1.

Bevezetés

Egy kijelent mondat állítás, ha egyértelm információt hordoz és igazságértékkel bír. állítás 2004. szeptember 1-én esett az es Budapesten. 5<3 A francia király 1788-ban Rómába látogatott. nem állítás Esett.

x<3 A francia király ma Rómába látogatott.

Iskolánk igazgatója 50 éves. Iskolánk tanára 50 éves.

5

Egy állítás igaz, ha az információtartalma a valóságnak megfelel, egyébként hamis, függetlenül tudásunktól. Arisztotelész alapelvei · az ellentmondástalanság elve: Egyetlen állítás sem lehet igaz is és hamis is. · a kizárt harmadik elve: Nincs olyan állítás, amely sem nem igaz, sem nem hamis.

6

1.

Bevezetés

Köznapi értelemben vett következtetés: (P1) Erika Sándornak a felesége. (P2) Katalin Sándornak az édesanyja. (K) Katalin Erikának az anyósa. A logika nem fogja vizsgálni a (magyar) nyelv szavainak jelentését!! pótpremissza: (P3) Azt mondjuk, hogy z x-nek az anyósa, ha z az édesanyja annak, akinek x a felesége.

7

Valamely tudományterületen végrehajtott következtetés: (P1) A vizsgált háromszög egyik oldalhosszának négyzete egyenl a másik két oldalhossz négyzetének összegével. (K) A vizsgált háromszög derékszög. A logika nem tartalmaz egyetlen más szaktudományt sem, így nem ismerheti ezek eredményeit!! pótpremissza (Pitagorasz tétele): (P2) Ha egy háromszög egyik oldalhosszának négyzete egyenl a másik két oldalhossz négyzetének összegével, akkor a háromszög derékszög.

8

1.

Bevezetés

Következtetések ,,sémái" (P1) Ha esik az es, sáros az út. (P2) Esik az es. (K) Sáros az út. (P1) Ha az tanszék nyer a pályázaton, nyomtatót vásárol. (P2) A tanszék nyert a pályázaton. (K) A tanszék nyomtatót vásárol. (P1) Ha három lábon gyábokorsz, a Kálán Púgra nem tudsz menni. (P2) Három lábon gyábokorsz. (K) A Kálán Púgra nem tudsz menni.1

1

Lázár Ervin, A hétfej tündér c. könyvébl

9

Mi volt közös az elbbi következtetésekben? (P1) Ha ..............., akkor ______. (P2) ................ (K) ______. Egyforma jelölés helyén ugyanaz az állítás volt. Használjunk, mint a matematikában, (állítás)változókat! (P1) Ha X, akkor Y. (P2) X. (K) Y.

10

1.

Bevezetés

(P1) Ha 10 másodperc alatt futom a 100 métert, akkor kiküldenek az olimpiára. (P2) De nem futom 10 másodperc alatt a 100 métert. (K) Tehát nem küldenek ki az olimpiára. (P1) Ha a benzin elfogyott, az autó megáll. (P2) Nem fogyott el a benzin. (K) Az autó nem áll meg. Ezen okoskodások közös sémája: (P1) Ha X, akkor Y. (P2) Nem X. (K) Nem Y.

11

A következtetési sémák helyessége · Helyes a következtetési séma, ha igaz premisszák esetén a konklúzió csak igaz lehet. · Helytelen a következtetési séma, ha igaz premisszák esetén is megtörténhet, hogy a konklúzió hamis. Egy következtetés helyes, ha helyes következtetési séma alapján hajtjuk végre. Tehát a következtetés helyessége független a benne szerepl állítások természetes nyelvi jelentésétl, csupán az ún. logikai szavak jelentésétl, és logikai szavak meghatározta szerkezettl függ.

12

1.

Bevezetés

Logikai szavak és jelentésük A negáció: logikai szó, mely igaz állításból hamisat, hamisból igazat készít. Alfréd diák. Alfréd nem diák. DE: A társaság néhány tagja diák. A társaság néhány tagja nem diák. Nem igaz, hogy a társaság néhány tagja diák.

13

A konjunkció: mely két igaz állításból igaz, egyébként hamis állítást készít. Amália és Bella kertészek. ,,Lement a nap. De csillagok nem jöttenek." (Petfi) Juli is, Mari is táncol. Kevésre vitte, noha becsületesen dolgozott. DE: Amália és Bella testvérek.

14

1.

Bevezetés

A diszjunkció: mely két hamis állításból hamis, egyébként igaz állítást készít. Esik az es, vagy fúj a szél. DE: Vagy busszal jött, vagy taxival.

Az implikáció: mely ha az eltag állítás igaz és az utótag állítás hamis, akkor hamis, egyébként igaz állítást készít. Ha megtanulom a leckét, akkor ötösre felelek. Csak akkor felelek ötösre, ha megtanulom a leckét. Akkor és csak akkor felelek ötösre, ha megtanulom a leckét.

15

Gyakran az egyszer állítások szerkezetét is fel kell tárnunk. Dezs postás. Amália és Bella testvérek. Az Erzsébet híd összeköti Budát Pesttel. predikátum + objektumnevek Az egzisztenciális kvantor: Amáliának van testvére. Az univerzális kvantor: Amália mindegyik testvére lány.

16

1.

Bevezetés

LOGIKAI NYELV · A logikai szavak helyett logikai jeleket írunk: nem ¬ negáció és konjunkció vagy diszjunkció ha . . . akkor implikáció minden univerzális kvantor van egzisztenciális kvantor · Az állítások természetes nyelvi jelentése közömbös, helyettük az állítás szerkezetét hordozó formulákat írunk.

17

Miért van szüksége a logikának saját nyelvre? · Nem tartozhat egyetlen nemzeti nyelvhez sem; · a természetes nyelvek nyelvtani rendszerei különbözek és bonyolultak; · a logika saját nyelvében minden (ábécé, nyelvtani szabályok, kategóriák) a logika feladatának ellátását szolgálhatja.

2. fejezet

Az ítéletlogika
2.1. Az ítéletlogika nyelve ­ szintaxis

Az ítéletlogika nyelvének ábécéje az alábbi szimbólumokat tartalmazza: · logikai összekötjelek: ¬, , , · elválasztójelek: a nyitó- és a záró-zárójel · ítéletváltozók: X, Y, Z, . . . betk, esetleg indexelve

18

2.1.

Az ítéletlogika nyelve ­ szintaxis

19

2.1. definíció. (Ítéletlogikai formula.) 1. Minden ítéletváltozó ítéletlogikai formula, ezeket a formulákat atomi vagy prímformuláknakis nevezzük. 2. Ha A ítéletlogikai formula, akkor ¬A (negált A) is az. 3. Ha A és B ítéletlogikai formulák, akkor · (A B) (A konjunkció B), · (A B) (A diszjunkció B) és · (A B) (A implikáció B) is ítéletlogikai formulák. 4. Minden ítéletlogikai formula az 1­3. szabályok véges sokszori alkalmazásával áll el. Az ítéletlogikai formulák halmaza az ítéletlogika nyelve. Jelölése: L0.

20

2.

Az ítéletlogika

2.2. tétel. (A szerkezeti indukció elve.) Minden ítéletlogikai formula T tulajdonságú, (alaplépés:) ha minden atomi formula T tulajdonságú továbbá (indukciós lépések:) (i1) ha az A ítéletlogikai formula T tulajdonságú, akkor ¬A is T tulajdonságú és (i2) ha az A és a B ítéletlogikai formulák T tulajdonságúak, akkor (A B), (A B) és (A B) is T tulajdonságúak.

2.1.

Az ítéletlogika nyelve ­ szintaxis

21

2.3. tétel. (Az egyértelm elemzés tétele.) Minden ítéletlogikai formulára a következ állítások közül pontosan egy igaz. 1. A formula atomi formula. 2. A formula egy egyértelmen meghatározható ítéletlogikai formula negáltja. 3. A formula egyértelmen meghatározható ítéletlogikai formulák konjunkciója. 4. A formula egyértelmen meghatározható ítéletlogikai formulák diszjunkciója. 5. A formula egyértelmen meghatározható ítéletlogikai formulák implikációja.

22

2.

Az ítéletlogika

2.4. definíció. Az ítéletlogika nyelvében 1. egyetlen atomi formulának sincs közvetlen részformulája, 2. a ¬A egyetlen közvetlen részformulája az A formula, 3. az (A B) formula (ahol {, , }) közvetlen részformulái az A és a B formulák. A az (A B) formula bal oldali, B a jobb oldali közvetlen részformulája. 2.5. definíció. Legyen A ítéletlogikai formula. Az A formula részformuláinak halmaza a legszkebb olyan halmaz, melynek 1. eleme A, és 2. ha a C formula eleme, akkor C közvetlen részformulái is elemei.

2.1.

Az ítéletlogika nyelve ­ szintaxis

23

A formulákhoz ­ azok szerkezete szerinti rekurzióval ­ egyértelmen rendelhetünk különböz dolgokat. 2.6. tétel. (A szerkezeti rekurzió elve.) Egy az ítéletlogikai nyelvén értelmezett F függvényt egyértelmen adtunk meg, ha (alaplépés:) értékeit rögzítjük a nyelv atomi formuláin és megmondjuk, hogy F (indukciós lépések:) (r1) ¬A-n felvett értéke az A-n felvett értékébl, illetve (r2) (A B)-n felvett értéke (ahol {, , }) az A-n és a B-n felvett értékekbl hogyan származtatható.

24

2.

Az ítéletlogika

2.7. definíció. Definiáljuk az : L0 N0 függvényt a következképpen: 1. ha A atomi formula, (A) legyen 0, 2. (¬A) legyen (A) + 1, 3. (A B) pedig legyen (A) + (B) + 1. Ekkor egy A L0 formulához rendelt (A) függvényértéket a formula logikai összetettségének nevezzük. 2.8. definíció. Egy formulában egy logikai összekötjel hatásköre a formulának azon részformulái közül a legkisebb logikai összetettség, amelyekben az adott logikai összekötjel is elfordul. 2.9. definíció. Egy formula f logikai összekötjele az az öszszekötjel, melynek hatásköre maga a formula.

2.1.

Az ítéletlogika nyelve ­ szintaxis

25

A formulák leírásakor szokásos rövidítések: · formula-kombinációk helyett speciális jelölések; Példa. (A B) ((A B) (B A)) · küls zárójelek elhagyása; · logikai jelek prioritása csökken sorrendben: ¬

26

2.

Az ítéletlogika

2.2.

Az ítéletlogika nyelve ­ szemantika

Az {i, h} halmazon értelmezett fontos logikai mveletek a b ¬a ab ab ab i i h i h h h i i h h i i h h h i i i h i h i i

2.2.

Az ítéletlogika nyelve ­ szemantika

27

Jelöljük most az ítéletváltozók halmazát Vv -vel. 2.10. definíció. Az L0 nyelv interpretációján egy I : Vv {i, h} függvényt értünk. 2.11. definíció. (Az ítéletlogikai formulák szemantikája.) Egy C ítéletlogikai formulához I-ben az alábbi ­ |C|I -val jelölt ­ igazságértéket rendeljük: 1. |A|I I(A), ahol A atomi formula, azaz ítéletváltozó, 2. |¬A|I ¬|A|I , 3. |A B|I |A|I |B|I , 4. |A B|I |A|I |B|I , 5. |A B|I |A|I |B|I .

28

2.

Az ítéletlogika

2.12. tétel. Legyen S ítéletváltozók egy halmaza. Ha két különböz interpretáció ugyanazokat az igazságértékeket rendeli az S-beli ítéletváltozókhoz, akkor minden olyan formulának, amelyben csak Sbeli ítéletváltozók fordulnak el, mindkét interpretációban ugyanaz lesz az igazságértéke.
X Y Z (Y Z) (Z ¬X) i i i i h h i i h i i i h i i h i h i h h i i i h

h h

h h

h h h

2.2.

Az ítéletlogika nyelve ­ szemantika

29

X Y Z Y Z ¬X Z ¬X (Y Z) (Z ¬X) i i i i i h i i i h i i i h h h h h i i i i h i h i i i i i h i h h i i i h

i h i i h h h i i h i h h h i h h h

30

2.

Az ítéletlogika

(Y Z) (Z ¬ X) i i i i i i i h i h i i i i h h h i h i h h i i i i i i i i i i h h h h i h

h i i i i

h h h h h i h i h h i i

h i

h h h h h i i

2.3.

Ítéletlogikai törvények

31

2.3.

Ítéletlogikai törvények

2.13. definíció. Egy A ítéletlogikai formula kielégíthet, ha van a nyelvnek olyan I interpretációja, hogy |A|I = i. Az ilyen interpretációkat A modelljeinek nevezzük. Ha nincs A-nak modellje, az A formula kielégíthetetlen. 2.14. példa. A (Y Z) (Z ¬X) formula kielégíthet. Az X ¬X formula kielégíthetetlen. X ¬X X ¬X i h h i h h

32

2.

Az ítéletlogika

2.15. definíció. Az A formula ítéletlogikai törvény vagy másképp tautológia, ha a nyelv minden I interpretációjára |A|I = i. Jelölése: |=0 A. A definíció alapján nyilvánvaló, hogy egy A formula pontosan akkor tautológia, ha ¬A kielégíthetetlen. 2.16. példa. A (Y Z) (Z ¬X) formula bár kielégíthet, de nem tautológia. Az alábbi igazságtábla pedig azt bizonyítja, hogy az X ¬X formula tautológia. X ¬X X ¬X i h h i i i

2.3.

Ítéletlogikai törvények

33

Az ítéletlogikai formulák szemantikai tulajdonságuk alapján az alábbi ábra szerint osztályozhatók:

kiel´g´ e ithet o

kiel´g´ e ithetetlen

tautol´gia o

34

2.

Az ítéletlogika

2.17. tétel. Ha A, B, C tetszleges ítéletlogikai formulák, a következ formulák ítéletlogikai törvények:
bvítés eltaggal implikációlánc-törvény |=0 A (B A) |=0 (A (B C)) ((A B) (A C)) |=0 A (B A B) |=0 A B A és |=0 A B B |=0 (A C) ((B C) (A B C)) |=0 A A B reductio ad absurdum a kétszeres tagadás törvénye a kizárt harmadik törvénye ellentmondás törvénye az azonosság törvénye tranzitivitás és |=0 B A B

|=0 (A B) ((A ¬B) ¬A) |=0 ¬¬A A |=0 A ¬A |=0 ¬(A ¬A) |=0 A A |=0 (A B) (B C) (A C)

ellentmondásból bármi következik |=0 A (¬A B) Peirce-törvény |=0 ((A B) A) A

2.3.

Ítéletlogikai törvények

35

2.18. definíció. Azt mondjuk, hogy az A és B ítéletlogikai formulák tautologikusan ekvivalensek, és ezt a tényt úgy jelöljük, hogy A 0 B, ha minden I interpretációban |A|I = |B|I . 2.19. példa. Az X Y formula például tautologikusan ekvivalens a ¬X Y formulával, amit mutat a közös igazságtáblájuk. X Y X Y ¬X Y i i i h i i i h i i i h h i h h

36

2.

Az ítéletlogika

Minden A, B, C ítéletlogikai formula esetén · A 0 A, · ha A 0 B, akkor B 0 A, · ha A 0 B és B 0 C, akkor A 0 C, azaz az ítéletlogikai formulák közötti binér 0 reláció ekvivalenciareláció. Ez a reláció a nyelv elemeinek egy osztályozását generálja, az egymással tautologikusan ekvivalens formulák jelentése ugyanaz. 2.20. lemma. A 0 B pontosan akkor, ha |=0 (A B) (B A).

2.3.

Ítéletlogikai törvények

37

2.21. tétel. Ha A, B, C ítéletlogikai formulák, tautológia, pedig kielégíthetetlen formula, akkor a felsorolt formulák rendre tautologikusan ekvivalensek egymással:
asszociativitás A (B C) 0 (A B) C kommutativitás A B 0 B A disztributivitás A (B C) 0 (A B) (A C) A (B C) 0 (A B) (A C) idempotencia A A 0 A elimináció (elnyelés) A (B A) 0 A De Morgan törvényei ¬(A B) 0 ¬A ¬B ¬(A B) 0 ¬A ¬B A (B A) 0 A A A 0 A A B 0 B A A (B C) 0 (A B) C

38

2.

Az ítéletlogika

kiszámítási törvények A 0 A A 0 A 0 A 0 A logikai jelek közötti összefüggések A B 0 ¬(¬A ¬B) A B 0 ¬(¬A ¬B) A B 0 ¬(A ¬B) kétszeres tagadás kontrapozíció negáció az implikációban A ¬A 0 ¬A implikációs eltagok felcserélése implikáció konjunktív eltaggal az implikáció öndisztributivitása esetelemzés ¬A A 0 A A (B C) 0 B (A C) A B C 0 A (B C) A (B C) 0 (A B) (A C) A B C 0 (A C) (B C) A B 0 ¬(A ¬B) A B 0 ¬A B A B 0 ¬A B ¬¬A 0 A A B 0 ¬B ¬A A 0 A 0 A A 0 ¬A A 0

2.3.

Ítéletlogikai törvények

39

2.3.1.

Formulák normálformái

· Egy atomi formulát vagy negáltját literálnak fogjuk nevezni. · Elemi konjunkció 1. egy literál, 2. vagy egy elemi konjunkció és egy literál konjunkciója. · Elemi diszjunkció 1. egy literál, 2. vagy egy elemi diszjunkció és egy literál diszjunkciója.

40

2.

Az ítéletlogika

· Konjunktív normálforma 1. egy elemi diszjunkció, 2. vagy egy konjunktív normálforma és egy elemi diszjunkció konjunkciója. · Diszjunktív normálforma 1. egy elemi konjunkció, 2. vagy egy diszjunktív normálforma és egy elemi konjunkció diszjunkciója. Lemma. Minden ítéletlogikai formulához konstruálható vele logikailag ekvivalens konjunktív és diszjunktív normálforma.

2.3.

Ítéletlogikai törvények

41

Jelek közötti összefüggések: (1) ¬(A B) A ¬B (2) A B ¬A B Kétszeres tagadás: De Morgan törvényei: (3) ¬¬A A (4) ¬(A B) ¬A ¬B (5) ¬(A B) ¬A ¬B Disztributivitás: (6) A (B C) (A B) (A C) (7) A (B C) (A B) (A C)

42

2.

Az ítéletlogika

A konstrukció lépései: 1. a logikai jelek közötti összefüggések alapján az implikációkat eltávolítjuk; 2. De Morgan törvényeivel elérjük, hogy negáció csak atomokra vonatkozzon; 3. a disztributivitást felhasználva elérjük, hogy a konjunkciók és diszjunkciók megfelel sorrendben kövessék egymást; 4. esetleg egyszersítünk.

2.3.

Ítéletlogikai törvények

43

Példa. (X Y ) ¬(¬Y X ¬Z) implikáció-eltávolítás (¬X Y ) (¬Y ¬(X ¬Z)) negáció atomokra vonatkozik (¬X Y ) (¬Y ¬X Z) konjunkciók diszjunkciója (¬X Y ¬Y ) (¬X Y ¬X) (¬X Y Z) egyszersítés (¬X Y ) (¬X Y Z) egyszersítés ¬X Y

44

2.

Az ítéletlogika

2.4.

Szemantikus következményfogalom

2.22. definíció. Legyen ítéletlogikai formulák tetszleges halmaza és B egy tetszleges formula. Azt mondjuk, hogy a B formula tautologikus következménye a formulahalmaznak (vagy a -beli formuláknak), ha minden olyan interpretációban, melyben a -beli formulák mindegyike igaz, ezekben a B formula is igaz. A -beli formulák a feltételformulák (premisszák), a B formula a következményformula (konklúzió). Jelölése: |=0 B.

2.4.

Szemantikus következményfogalom

45

2.23. példa. A {¬Y, X Y, X Z} formulahalmaz tautologikus következménye Z, ahogy azt közös igazságtáblájuk mutatja. X Y Z ¬Y X Y X Z i i i i i h h h i i h h i i i i i i i i h h i h i h i i i i Z i h i h i h i h

i h i i h h h i i h i h h h i h h h

46

2.

Az ítéletlogika

2.24. példa. A {¬Z, X V, X Y, Y Z, V (W Z)} formulahalmaz tautologikus következménye ¬X. Tegyük fel, hogy I olyan interpretáció, mely minden feltételformulát kielégít. 1. Mivel ¬Z feltételformula, ezért I(Z) = h lehet csak. 2. I(Z) = h mellett az Y Z feltételformula csak akkor lehet igaz, ha I(Y ) = h. 3. I(Z) = h és I(Y ) = h mellett az X Y pedig csak I(X) = h választás esetén lesz igaz. 4. Ha I(Z) = I(Y ) = I(X) = h, akkor az X V igazzá válásához I(V ) = i szükséges. 5. A rögzített I(Z) = I(Y ) = I(X) = h és I(V ) = i igazságértékek esetén a V (W Z) formula igazzá válásához az I(W ) = h kell.

2.4.

Szemantikus következményfogalom

47

A fenti lépéseket végigvihetjük a közös igazságtábla-sémán is. X Y Z V W ¬Z X V X Y Y Z V (W Z) ¬X - - h - - - h h - - h h h - - h h h i - h h h i h i i i i i i i i i i i i i i i i i i

48

2.

Az ítéletlogika

A következményfogalmat hasznos lenne egy alkalmas formula szemantikai jellemzésével leírni. Ehhez nyújtanak lehetséget a következ tételek. 2.25. tétel. Legyenek A1, A2, . . . , An, B (n 1) tetszleges ítéletlogikai formulák. {A1, A2, . . . , An} |=0 B pontosan akkor, · ha az A1 A2 . . . An ¬B formula kielégíthetetlen. · ha |=0 A1 A2 . . . An B.

2.4.

Szemantikus következményfogalom

49

2.26. definíció. Legyen {A1, A2, . . . , An} tetszleges formulahalmaz, és B egy formula. Az ({A1, A2, . . . , An}, B) párt következtetésformának nevezzük. Az ({A1, A2, . . . , An}, B) pár helyes következtetésforma, ha {A1, A2, . . . , An} |=0 B. 2.27. tétel. Legyenek A, B, C tetszleges ítéletlogikai formulák. Az alábbiakban felsorolt következtetésformák helyesek: a leválasztási szabály vagy modus ponens ({A B, A}, B) a kontrapozíció vagy modus tollens reductio ad absurdum az indirekt bizonyítás feltételes szillogizmus következtetés esetszétválasztással ({A B, ¬B}, ¬A) ({A B, A ¬B}, ¬A) ({¬A B, ¬A ¬B}, A) ({A B, B C}, A C) ({A B, A C, B C}, C)

50

2.

Az ítéletlogika

modus tollendo ponens a -ra vonatkozó következtetésformák az -re vonatkozó következtetésformák

({A B, ¬A}, B) ({A}, A B) és ({B}, A B) ({A, B}, A B) ({A B}, A) és ({A B}, B)

az -ra vonatkozó következtetésforma a ¬¬-re vonatkozó következtetésformák

({B}, A B) ({¬¬A}, A) és ({A}, ¬¬A)

3. fejezet

Az elsrend logika
3.1. Elsrend logikai nyelvek ­ szintaxis

Egy elsrend logikai nyelv ábécéje logikai és logikán kívüli szimbólumokat, továbbá elválasztójeleket tartalmaz. A logikán kívüli szimbólumhalmaz megadható Srt, Pr , Fn, Cnst alakban, ahol 1. Srt nemüres halmaz, elemei fajtákat szimbolizálnak, 2. Pr nemüres halmaz, elemei predikátumszimbólumok, 3. az Fn halmaz elemei függvényszimbólumok, 4. Cnst pedig a konstansszimbólumok halmaza.
51

52

3.

Az elsrend logika

Az Srt, Pr , Fn, Cnst ábécé szignatúrája egy (1, 2, 3) hármas, ahol 1. minden P Pr predikátumszimbólumhoz 1 a predikátumszimbólum alakját, azaz a (1, 2, . . . , k ) fajtasorozatot, 2. minden f Fn függvényszimbólumhoz 2 a függvényszimbólum alakját, azaz a (1, 2, . . . , k , ) fajtasorozatot és 3. minden c Cnst konstansszimbólumhoz 3 a konstansszimbólum fajtáját, azaz ()-t rendel (k > 0 és 1, 2, . . . , k , Srt).

3.1.

Elsrend logikai nyelvek ­ szintaxis

53

Logikai jelek · a logikai összekötjelek: ¬, , , · a kvantorok: , · a különböz fajtájú individuumváltozók. Egy elsrend nyelv ábécéjében minden Srt fajtához szimbólumoknak megszámlálhatóan végtelen
v1 , v2 , . . .

rendszere tartozik, ezek a szimbólumok a fajtájú változók. Elválasztójelek a zárójelek: () és a vessz: ,

54

3.

Az elsrend logika

3.1. példa. 1. A Geom nyelv logikán kívüli szimbólumai: Srt = {pt (ponttípus), et (egyenestípus), st (síktípus)} pt típusú változók: A, B, C, . . . et típusú változók: e, f, g, . . . st típusú változók: a, b, c,. . . P r = {P, Q, R}, F n = és Cnst = 1 P (pt, pt) Q (pt, et) R (pt, st) Megjegyzés: a geometriában a P, Q, R szimbólumok helyett rendre az =, , jeleket szokás inkább használni. 2 3

3.1.

Elsrend logikai nyelvek ­ szintaxis

55

2. Az Ar nyelv logikán kívüli szimbólumai: Srt = {szt (számtípus)} szt típusú változók: x, y, z, . . . P r = {P } F n = {f, g, h} Cnst = {nulla} 1 P (szt, szt) f 2 (szt, szt) g (szt, szt, szt) h (szt, szt, szt) Megjegyzés: az aritmetikában a g és h szimbólumok helyett a + és · jeleket, P helyett pedig az = jelet szokás használni. 3 nulla (szt)

56

3.

Az elsrend logika

3. Legyenek a logikán kívüli szimbólumaink a {1, 2}, {P, Q, R}, {f }, {c} halmaznégyessel és a következ szignatúrával megadva: 1 P (1) Q (1, 2) R (2, 2) Legyenek x, y, z, . . . 1 fajtájú és x, y , z , . . . pedig 2 fajtájú ~ ~ ~ változók. 2 3

f (1, 2, 2) c (1)

3.1.

Elsrend logikai nyelvek ­ szintaxis

57

3.2. definíció. (Az elsrend nyelv termjei és formulái) 1. Minden Srt fajtájú változó és konstans fajtájú term. 2. Ha az f Fn függvényszimbólum (1, 2, . . . , k , ) alakú és t1, t2, . . . , tk ­ rendre 1, 2, . . . , k fajtájú ­ termek, akkor az f (t1, t2, . . . , tk ) szó egy fajtájú term. 3. Minden term az 1­2. szabályok véges sokszori alkalmazásával áll el.

58

3.

Az elsrend logika

4. Ha a P Pr predikátumszimbólum (1, 2, . . . , k ) alakú és t1, t2, . . . , tk ­ rendre 1, 2, . . . , k fajtájú ­ termek, akkor a P (t1, t2, . . . , tk ) szó egy elsrend formula. Az így nyert formulákat atomi formuláknak nevezzük. 5. Ha A elsrend formula, akkor ¬A is az. 6. Ha A és B elsrend formulák, akkor az (A B), (A B) és az (A B) is elsrend formulák. 7. Ha A elsrend formula és x tetszleges változó, akkor xA és xA is elsrend formulák. Az így nyert formulákat kvantált formuláknak nevezzük. 8. Minden elsrend formula a 4­7. szabályok véges sokszori alkalmazásával áll el. Egy elsrend nyelv termjeinek halmazát Lt-vel, formuláinak halmazát Lf -fel jelölhetjük.

3.1.

Elsrend logikai nyelvek ­ szintaxis

59

3.3. példa. 1. A Geom nyelv kifejezései: · termek: A, f, b · atomi formulák: a geometriában szokásosan P (A, B) (A = B) Q(B, e) (B e) R(A, a) (A a) · formula: A(Q(A, e) Q(A, f )) A((A e) (A f ))

60

3.

Az elsrend logika

2. Az Ar nyelv kifejezései: · termek: nulla, x, f (nulla) g(x, f (nulla)) h(f (f (x)), x) · atomi formula: · formula: uP (g(x, u), y) u((x + u) = y) az arimetikában szokásosan (x + f (nulla)) (f (f (x)) · x) ((x + f (nulla)) = nulla)

P (g(x, f (nulla)), nulla)

3.1.

Elsrend logikai nyelvek ­ szintaxis

61

3. A harmadik példanyelvben - 1 fajtájú termek: c, x, y, . . . - 2 fajtájú termek: x, f (c, x), f (x, f (c, x)), . . . ~ ~ ~ - atomi formulák: P (x), Q(y, x), R(f (c, x), f (x, f (c, x))), . . . ~ ~ ~ - formulák: x¬~Q(y, x), (~Q(y, x) ~R(f (c, x), f (c, x))), . . . x ~ x ~ x ~ ~

62

3.

Az elsrend logika

3.4. tétel. (A szerkezeti indukció elve.) · Termekre: Egy elsrend logikai nyelv minden termje T tulajdonságú, (alaplépés:) ha minden változója és konstansa T tulajdonságú, továbbá (indukciós lépés:) ha a t1, t2, . . . , tk termek T tulajdonságúak, akkor az f függvényszimbólum felhasználásával elállított f (t1, t2, . . . , tk ) term is T tulajdonságú.

3.1.

Elsrend logikai nyelvek ­ szintaxis

63

· Formulákra: Egy elsrend logikai nyelv minden formulája T tulajdonságú, (alaplépés:) ha minden atomi formulája T tulajdonságú, és (indukciós lépések:) (i1) ha az A formula T tulajdonságú, akkor ¬A is T tulajdonságú, (i2) ha az A és a B formulák T tulajdonságúak, akkor az (A B), (A B) és az (A B) is T tulajdonságúak és (i3) ha az A formula T tulajdonságú és x individuumváltozó, akkor xA és xA is T tulajdonságúak.

64

3.

Az elsrend logika

3.5. tétel. (Az egyértelm elemzés tétele.) · Egy elsrend logikai nyelv minden termjére a következ állítások közül pontosan egy igaz. 1. A term a nyelv egy változója. 2. A term a nyelv egy konstansa. 3. A term a nyelv egyértelmen meghatározható t1, t2, . . . , tk termjei és az f Fn függvényszimbólum felhasználásával elállított f (t1, t2, . . . , tk ) alakú term. · Egy elsrend logikai nyelv minden formulájára a következ állítások közül pontosan egy igaz. 1. A formula a nyelv egyértelmen meghatározható t1, t2, . . . , tk termjei és P Pr predikátumszimbóluma felhasználásával elállított P (t1, t2, . . . , tk ) alakú atomi formula.

3.1.

Elsrend logikai nyelvek ­ szintaxis

65

2. A formula egy a nyelv egyértelmen meghatározható formulájának negáltja. 3. A formula a nyelv egyértelmen meghatározható formuláinak konjunkciója. 4. A formula a nyelv egyértelmen meghatározható formuláinak diszjunkciója. 5. A formula a nyelv egyértelmen meghatározható formuláinak implikációja. 6. A formula a nyelv egy egyértelmen meghatározható A formulája és x változója felhasználásával elállított xA alakú formula. 7. A formula a nyelv egy egyértelmen meghatározható A formulája és x változója felhasználásával elállított xA alakú formula.

66

3.

Az elsrend logika

3.6. definíció. Egy elsrend logikai nyelvben · 1. egyetlen konstansnak és változónak sincs közvetlen résztermje, 2. az f (t1, t2, . . . , tk ) term közvetlen résztermjei a t1, t2, . . . , tk termek, · 1. egy atomi formulának nincs közvetlen részformulája, 2. a ¬A egyetlen közvetlen részformulája az A formula, 3. az (A B), (A B), illetve az (A B) formulák közvetlen részformulái az A és a B formulák, 4. a xA, illetve xA közvetlen részformulája az A formula.

3.1.

Elsrend logikai nyelvek ­ szintaxis

67

3.7. definíció. · Egy term résztermjeinek halmaza a legszkebb olyan halmaz, melynek 1. a term eleme és 2. ha egy term eleme, akkor eleme a term összes közvetlen résztermje is. · Egy formula részformuláinak halmaza a legszkebb olyan halmaz, melynek 1. a formula eleme és 2. ha egy formula eleme, akkor eleme a formula összes közvetlen részformulája is.

68

3.

Az elsrend logika

3.8. példa. Az f (x, f (c, x)) term közvetlen résztermjei: x és f (c, x), ~ ~ résztermjeinek halmaza: {f (x, f (c, x)), x, f (c, x), c, x}. ~ ~ ~ A x¬~Q(y, x) formula egyetlen közvetlen részformulája: ¬~Q(y, x), x ~ x ~ részformuláinak halmaza: {x¬~Q(y, x), ¬~Q(y, x), ~Q(y, x), Q(y, x)}. x ~ x ~ x ~ ~

3.1.

Elsrend logikai nyelvek ­ szintaxis

69

3.9. tétel. (A szerkezeti rekurzió elve.) · Termekre: Egy elsrend logikai nyelv esetén a nyelv termjein értelmezett F függvényt egyértelmen adjuk meg, ha (alaplépés:) értékeit rögzítjük a nyelv változóin és konstansain, majd megmondjuk, hogy (indukciós lépések:) F értéke az f (t1, t2, . . . , tk ) termre az F-nek a t1, t2, . . . , tk termeken felvett értékeibl hogyan származtatható.

70

3.

Az elsrend logika

· Formulákra: Egy elsrend logikai nyelv esetén a nyelv formuláin értelmezett F függvényt egyértelmen adjuk meg, ha (alaplépés:) értékeit rögzítjük a nyelv atomi formuláin és megmondjuk, hogy F értéke (indukciós lépések:) (r1) a ¬A formulára az A-n felvett értékébl, (r2) az (A B), (A B), illetve az (A B) formulára az A-n és a B-n felvett értékeibl, illetve (r3) a xA, illetve az xA formulára az A-n felvett értékébl hogyan származtatható.

3.1.

Elsrend logikai nyelvek ­ szintaxis

71

3.10. definíció. · Definiáljuk a : Lt N0 függvényt a következképpen: 1. ha t változó vagy konstansszimbólum, (t) legyen 0, 2. (f (t1, t2, . . . , tk )) legyen (t1) + (t2) + . . . + (tk ) + 1. Ekkor a t Lt termhez rendelt (t) függvényértéket a t term funkcionális összetettségének nevezzük. · Definiáljuk a : Lf N0 függvényt a következképpen: 1. ha A atomi formula, (A) legyen 0, 2. (¬A) legyen (A) + 1, 3. (AB), (AB), illetve az (A B) legyen (A)+(B)+1, 4. (xA), illetve az (xA) pedig legyen (A) + 1. Ekkor az A Lf formulához rendelt (A) függvényértéket az A formula logikai összetettségének nevezzük.

72

3.

Az elsrend logika

3.11. példa. Az f (x, f (c, x)) term funkcionális összetettsége 2, a ~ (~Q(y, x) ~R(f (c, x), f (c, x))) x ~ x ~ ~ formula logikai összetettsége 3. Az ítéletlogikában definiáltuk a logikai összekötjel hatáskörének és a f logikai összekötjelnek a fogalmát. A fogalmak változtatás nélkül kiterjeszthetk a kvantorokra is. Egészítsük ki a logikai összekötjelek közötti ersorrendet azzal, hogy a kvantorokat is besoroljuk. A prioritás csökken sorrendben: {, , ¬}, {, }, . Azokat a zárójeleket, melyek ezt a sorrendet jelölnék ki, elhagyhatjuk.

3.1.

Elsrend logikai nyelvek ­ szintaxis

73

3.12. definíció. 1. A termek és az atomi formulák minden változójának minden elfordulása szabad. 2. A ¬A formulában egy változó-elfordulás pontosan akkor kötött, ha ez a változó-elfordulás már A-ban is kötött. 3. Az (AB), (AB), illetve az (A B) formulában egy változóelfordulás kötött, ha ez az elfordulás már kötött abban a közvetlen részformulában is, amelyben ez az elfordulás szerepel. 4. A xA, illetve a xA formulában x minden elfordulása kötött. Az A formula eltt szerepl kvantor teszi kötötté (köti) x valamely elfordulását, ha ez az elfordulás A-ban még szabad volt. Egy az x-tl különböz változó valamely elfordulása kötött, ha A-ban kötött.

74

3.

Az elsrend logika

Ha egy változónak egy kifejezésben van szabad elfordulása, akkor ezt a változó a kifejezés paramétere. Egy K kifejezés paraméterei halmazára Par(K)-val fogunk hivatkozni. 3.13. példa. - A ~(Q(x, x)Q(y, x)) formulában x elfordulásai x ~ ~ ~ az kvantor által kötöttek, az x és az y elfordulásai szabadok. Tehát a formula paraméteres, paraméterei x és y. - A ~(xQ(x, x)Q(c, x)) formulában az kvantor által kötött x x ~ ~ ~ elfordulások mellett az x elfordulásai is kötöttek egy kvantor által, más változó-elfordulás pedig nincs benne. A formula zárt formula vagy mondat. - A x(P (x) xQ(x, x)) formula szintén paraméteres, az x ~ ~ szabadon fordul el benne. Az x elfordulásai itt is kötöttek, de a P (x)-beli x elfordulást és a Q(x, x)-beli x elfordulást két ~ különböz kvantor köti.

3.1.

Elsrend logikai nyelvek ­ szintaxis

75

3.14. definíció. A xA, illetve a xA formulában az A eltt szerepl kvantor által kötött x változó átnevezésérl beszélünk, amikor 1. a x, illetve a x kvantoros eltagban x helyett egy vele megegyez fajtájú y változót nevezünk meg (y, illetve y), majd 2. A-ban az x változó minden szabad elfordulását y-ra cseréljük ki (a kapott formulát jelöljük [Ax]-nal), y és így a y[Ax], illetve a y[Ax] formulát kapjuk. y y

76

3.

Az elsrend logika

3.15. definíció. Ha a xA, illetve a xA formulában 1. y nem paraméter és 2. x egyetlen elfordulása sem esik y-t megnevez kvantor hatáskörébe, akkor szabályosan végrehajtott változó-átnevezéssel nyertük a xA, illetve a xA formulából a y[Ax], illetve a y[Ax] formulát. y y

3.1.

Elsrend logikai nyelvek ­ szintaxis

77

3.16. példa. A ~(R(~, y ) ~R(~, x)) x x ~ z z ~ formulából az kvantor által kötött x szabályosan végrehajtott át~ nevezésével nyertük a ~(R(~, y ) ~R(~, u)) u u ~ z z ~ formulát. Az kvantor által kötött változó új nevének 1. y -t nem választhatjuk, mert y a kvantor hatáskörében is elfor~ ~ duló paramétere a formulának; 2. z -t nem választhatjuk, mert x-nek van elfordulása z -t megnevez ~ ~ ~ kvantor hatáskörében.

78

3.

Az elsrend logika

Ha két formula csak kötött változóik szabályosan végrehajtott átnevezésében különbözik, akkor azt fogjuk mondani, hogy konguensek. Definiáljuk most pontosan egy elsrend nyelv formuláinak halmazán ezt a binér relációt (a reláció jele: ). 3.17. definíció. (Formulák kongruenciája.) 1. Egy atomi formula csak önmagával kongruens. 2. ¬A ¬A, ha A A. 3. (A B) (A B ), (A B) (A B ), illetve (A B) (A B ), ha A A és B B . 4. xA yA, illetve xA yA, ha [Ax] [Az ] minden olyan z z változóra, amely különbözik a kérdéses formulákban elforduló összes változótól.
y

3.1.

Elsrend logikai nyelvek ­ szintaxis

79

3.18. példa. A x (~Q(x, x) ~¬(Q(x, x) Q(y, x))) x ~ x ~ ~ formulával kongruens például a z(~Q(z, y ) ~¬(Q(z, z ) Q(y, z ))) y ~ z ~ ~ formula. Ugyanakkor nem kongruens vele a y(~Q(y, x) ~¬(Q(y, x) Q(x, x))) x ~ x ~ ~ formula, hisz az eredeti formulának y a paramétere, ez utóbbinak x. Világos, hogy minden A, B, C L formula esetén A A; ha A B, akkor B A; és ha A B és B C, akkor A C; azaz a kongruencia egy ekvivalenciareláció. Ez a reláció az elsrend nyelv formuláinak egy osztályozását generálja; az egymással kongruens formulákat a logikában nem tekintjük lényegében különböznek.

80

3.

Az elsrend logika

3.19. definíció. Egy formulát változóiban tisztának nevezünk, ha benne minden kvantoros eltagban a formula 1. paramétereitl és 2. bármely másik kvantoros eltagban megnevezett változótól különböz változó van megnevezve. 3.20. tétel. Tetszleges elsrend formulához konstruálható vele kongruens változóiban tiszta formula. 3.21. példa. A ~Q(x, x) x~¬(Q(x, x) R(~, x)) x ~ x ~ y ~ formula nem változóiban tiszta, a vele kongruens ~Q(x, z ) y~¬(Q(y, x) R(~, x)) z ~ x ~ y ~ formula viszont már az.

3.2.

Elsrend logikai nyelvek ­ szemantika

81

3.2.

Elsrend logikai nyelvek ­ szemantika

3.22. definíció. L interpretációja egy I-vel jelölt ISrt, IP r , IF n, ICnst függvénynégyes, ahol 1. az ISrt : U függvény megad minden egyes Srt fajtához egy U nemüres halmazt, a fajtájú individuumok halmazát (a különböz fajtájú individuumok halmazainak uniója az interpretáció individuumtartománya vagy univerzuma),

82

3.

Az elsrend logika

2. az IP r : P P I függvény megad minden (1, 2, . . . , k ) alakú P P r predikátumszimbólumhoz egy P I : U1 × U2 × . . . × Uk {i, h} logikai függvényt (relációt), 3. az IF n : f f I függvény hozzárendel minden (1, 2, . . . , k , ) alakú f F n függvényszimbólumhoz egy f I : U1 × U2 × . . . × Uk U matematikai függvényt (mveletet), 4. az ICnst : c cI függvény pedig minden fajtájú c Cnst konstansszimbólumhoz az U individuumtartománynak egy individuumát rendeli, azaz cI U .

3.2.

Elsrend logikai nyelvek ­ szemantika

83

Példa. 1. Az Ar nyelv természetes interpretációja ISrt(szt) = N0 ICnst(nulla) = 0 IF n(f ) = f I , ahol f I : N0 N0, és f I (n) = n + 1, ( ha n N0) IF n(g) = g I , ahol g I : N0 × N0 N0, és g I (n, m) = n + m, ( ha n, m N0) IF n(h) = hI , ahol hI : N0 × N0 N0, és hI (n, m) = n · m, ( ha n, m N0) IP r (P ) = P I , ahol P I : N0 × N0 {i, h}, és (ha n, m N0), I (n, m) = i ha n = m P h egyébként

84

3.

Az elsrend logika

2. Rögzítsük most a harmadik példanyelv egy interpretációját. U1 legyen {a, b, c}, U2 pedig legyen {1, 2}, továbbá a P I : {a, b, c} {i, h} QI : {a, b, c} × {1, 2} {i, h} RI : {1, 2} × {1, 2} {i, h} f I : {a, b, c} × {1, 2} {1, 2} függvények legyenek az alábbi táblákkal adottak: PI a b c i h i QI a b c 1 i h i 2 h i i RI 1 2 1 h i 2 i i fI a b c 1 1 2 2 2 2 2 1

Jelölje a c konstansszimbólum a c individuumot.

3.2.

Elsrend logikai nyelvek ­ szemantika

85

3.23. definíció. Legyen az L elsrend logikai nyelvnek I egy interpretációja, az interpretáció univerzuma legyen U. Jelölje V a nyelv változóinak a halmazát. Egy olyan : V U leképezést, ahol ha x fajtájú változó, akkor (x) U -beli individuum, az I interpretáció egy változókiértékelésének nevezzük. 3.24. definíció. Legyen x egy változó. A változókiértékelés a változókiértékelés x-variánsa, ha (y) = (y) minden x-tl különböz y változó esetén.

86

3.

Az elsrend logika

3.25. definíció. Legyen az L nyelvnek I egy interpretációja és egy I-beli változókiértékelés. Az L nyelv egy fajtájú t termjének értéke I-ben a változókiértékelés mellett az alábbi ­ |t|I,-val jelölt ­ U -beli individuum: 1. ha c Cnst fajtájú konstansszimbólum, akkor |c|I, az U beli cI individuum, 2. ha x fajtájú változó, akkor |x|I, az U -beli (x) individuum, 3. ha t1, t2, . . . , tk rendre 1, 2, . . . , k fajtájú termek és ezek értékei a változókiértékelés mellett I-ben rendre az U1 -beli |t1|I,, az U2 -beli |t2|I,, . . . és az Uk -beli |tk |I, individuumok, akkor egy (1, 2, . . . , k , ) alakú f F n függvényszimbólum esetén |f (t1, t2, . . . , tk )|I, az U -beli f I (|t1|I,, |t2|I,, . . . , |tk |I,) individuum.

3.2.

Elsrend logikai nyelvek ­ szemantika

87

Példa. 1. Az Ar nyelv természetes interpretációjában · bármely változókiértékelés mellett |nulla| = 0 |f (nulla)| = f I (|nulla|) = 1. · a (x) = 1, (y) = 3 változókiértékelés mellett |(f (x) + y)| = g I (|f (x)|, |y|) = g I f I (|x|), 3 = = g I f I (1), 3 = g I (2, 3) = 5

88

3.

Az elsrend logika

2. Határozzuk meg a harmadik példanyelv f (c, f (x, x)) termjének ~ az elbb megadott I interpretációbeli értékét a következ változókiértékelés mellett: legyen (x) = b, (y) = a, és minden más 1 fajtájú változóhoz a c, minden 2 fajtájú változóhoz pedig az 1 individuumot rendelje. |f (c, f (x, x))|I, = ~ = f I (|c|I,, |f (x, x)|I,) = ~ = f I (|c|I,, f I (|x|I,, |~|I,)). x Mivel |c|I, = cI = c, |x|I, = (x) = b és |~|I, = (~) = 1, x x így f I (|c|I,, f I (|x|I,, |~|I,)) = f I (c, f I (b, 1)), ami f I (b, 1) = x 2 miatt f I (c, 2), ez pedig éppen 1. Tehát |f (c, f (x, x))|I, = 1, ~ vagyis f (c, f (x, x)) I-beli értéke a változókiértékelés mellett 1. ~

3.2.

Elsrend logikai nyelvek ­ szemantika

89

3.26. lemma. Az L nyelvnek legyen I egy interpretációja, 1 és 2 pedig olyan változókiértékelések I-ben, amelyek megegyeznek individuumváltozóknak egy S halmazán. Ha egy t termben csak S-beli változók fordulnak el, akkor |t|I,1 = |t|I,2 . Példa. A harmadik példanyelv elbb vizsgált interpretációjában az f (x, f (c, x)) ~ term jelentése a termben elforduló változók kiértékeléstl függ:
(x) (~) |f (x, f (c, x))| x ~ a a b b c c 1 2 1 2 1 2 2 1 2 2 1 2

90

3.

Az elsrend logika

3.27. definíció.
Legyen az L nyelvnek I egy interpretációja és egy I-beli változókiértékelés. Egy C formulához I-ben a változókiértékelés mellett az alábbi ­ |C|I,-val jelölt ­ igazságértéket rendeljük: 1. |P (t1, t2, . . . , tk )|
I,



i ha P I (|t1|I,, |t2|I,, . . . , |tk |I,) = i, h egyébként.

2. |¬A|I, ¬|A|I,, 3. |A B|I, |A|I,|B|I,, 4. |A B|I, |A|I,|B|I,, 5. |A B|I, |A|I,|B|I,, 6. |xA|I, 7. |xA|
I,


i ha |A|I, = i minden x-variánsára, h egyébként. = i valamely x-variánsára, i ha |A| h egyébként.
I,



3.2.

Elsrend logikai nyelvek ­ szemantika

91

Példa. 1. Az Ar nyelv természetes interpretációjában a (x) = 1, (y) = 3, (z) = 4 (a többi változóra 0) változókiértékelés mellett | (f (nulla) · y) = (f (f (nulla)) + x) | = P I (|f (nulla) · y|, |f (f (nulla)) + x|) = P I hI (|f (nulla)|, |y|) , g I (|f (f (nulla)) |, |x|) = P I hI (1, 3), g I f I (|f (nulla)|), 1 P I (3, g I (2, 1)) = P I (3, 3) = i |u ((y + u) = z) | = i, mert (u) = 1 mellett = P I |y + u| , |z| = | ((y + u) = z) | PI
I (|y| , |u| ), 4 g

= P I 3, g I (f I (1), 1) =

= P I g I (3, 1), 4 = P I (4, 4) = i

92

3.

Az elsrend logika

2. · Határozzuk meg most a harmadik példanyelv Q(y, f (c, f (x, x))) ~ atomi formulájának I-beli értékét az elz példabeli változókiértékelés mellett. |Q(y, f (c, f (x, x)))|I, = QI (|y|I,, |f (c, f (x, x))|I,). ~ ~ |y|I, = (y) = a, az elz példában pedig kiszámoltuk, hogy |f (c, f (x, x))|I, = 1. ~ Tehát |Q(y, f (c, f (x, x)))|I, = QI (a, 1) = i. ~

3.2.

Elsrend logikai nyelvek ­ szemantika

93

· Ha viszont a Q(y, f (x, f (x, x))) atom I-beli értékét akarjuk ~ kiszámolni mellett, ehhez az |f (x, f (x, x))|I, értékre van ~ szükség, ami 2. Tehát |Q(y, f (x, f (x, x)))|I, = QI (a, 2) = h. ~ Továbbá a zQ(y, f (z, f (x, x))) formula I-beli értéke a vál~ tozókiértékelés mellett i, hiszen magára -ra ( egyik lehetséges z-variánsa önmaga) |Q(y, f (z, f (x, x))|I, = i. ~ A zQ(y, f (z, f (x, x))) formula I-beli értéke mellett viszont ~ h, hiszen azon z-variánsa mellett, melyre (z) = b, az adódik, hogy
I, = h. |Q(y, f (z, f (x, x)))| ~

94

3.

Az elsrend logika

3.28. lemma. Az L nyelvnek legyen I egy interpretációja, 1 és 2 pedig olyan változókiértékelések I-ben, amelyek megegyeznek individuumváltozóknak egy S halmazán. Ha az A formula olyan, hogy Par(A) S, akkor |A|I,1 = |A|I,2 . Példa. A harmadik példanyelv I interpretációjában a ~¬R(~, f (x, f (c, x)) y y ~ formula jelentése az alábbi relációtáblával írható le:
(x) (~) |~¬R(~, f (x, f (c, x))| x y y ~ a a b b c c 1 2 1 2 1 2 h i h h i h

3.2.

Elsrend logikai nyelvek ­ szemantika

95

Példa. Vizsgáljuk most a {}, {P, Q, R}, {f, g, h}, nyelvet a
1 P Q () (, ) f g 2 (, ) (, , )

R (, , ) h (, , , )

szignatúrával. Legyenek x, y, z, . . . fajtájú változók. Jelöljük ezt az elsrend nyelvet L-vel. Megadjuk most az L nyelv egy lehetséges interpretációját: I -t. Legyen a nyelv univerzuma az {a, b, c} I és a QI relációk táblával adottak: halmaz és a P
PI


a b c i i h

QI a b c



a b c i h i h i i h h h

96

3.

Az elsrend logika

I reláció pedig a következ: Az R I (x, y, z) R

i ha y = a és x és z megegyeznek, h egyébként.

I és a g I mveletek mvelettáblái: Az f
fI


a b c b c a

gI a b c



a b c a a a a b b a b c

I mvelet pedig a következ: Ah

Ezzel megadtuk az I interpretációját az L nyelvnek.

a ha x, y és z közül legalább egy a, hI (x, y, z) b ha x, y és z is b, c egyébként.

3.2.

Elsrend logikai nyelvek ­ szemantika

97

Vizsgáljuk most meg néhány L-beli formula I -beli jelentését. 1. A x(P (x) Q(x, x)) zárt formula igazságértékének megállapításához meg kell határozni egy tetszlegesen rögzített összes lehetséges x-variánsa mellett a P (x) Q(x, x) formula I -beli igazságértékét. Elég P (x) Q(x, x) paraméterénél ismerni a lehetséges x-variánsok értékét:
(x) |P (x)| a b c i i h


|Q(x, x)| i i h



|P (x) Q(x, x)| i i i



Minden x-variáns mellett igaz P (x) Q(x, x), így x(P (x) Q(x, x)) igaz I -ben.

98

3.

Az elsrend logika

2. Vizsgáljuk most a ¬P (x) R(x, y, x) formulát. A formula paraméteres, paraméterei x és y. I -ben egy-egy rögzített változókiértékelés mellett igazságértékét meghatározhatjuk.
(x) (y) |P (x)| |¬P (x)| |R(x, y, x)| |¬P (x) R(x, y, x)| a a a b b b c c c a b c a b c a b c i i i i i i h h h h h h h h h i i i i h h i h h i h h h h h h h h i h h

Ez egy {a, b, c}2 {i, h} reláció táblája, ez a reláció a ¬P (x) R(x, y, x) formula I interpretációbeli jelentése.

3.2.

Elsrend logikai nyelvek ­ szemantika

99

3. Nézzük meg azt, hogy mit jelent a y(¬P (x) R(x, y, x)) formula. Most is minden változókiértékelés mellett meg kell határozni a formula igazságértékét. De mivel a formulánk kvantált, minden esetén vizsgálni kell az y-variánsai mellett a kvantor hatáskörébe es formula igazságértékeit is. Az elz táblázatban viszont épp olyan változókiértékelések szerepelnek, melyre (x) = a, és (y) = a, (y) = b, (y) = c rendre éppen a (x) = a lehetséges y-variánsai, majd (x) = b lehetséges y-variánsai, és (x) = c lehetséges y-variánsai is megtalálhatók.
(x) |y(¬P (x) R(x, y, x))| a b c h h i

Ez egy {a, b, c} {i, h} reláció táblája, ez a reláció a y(¬P (x) R(x, y, x)) formula I interpretációbeli jelentése.

100

3.

Az elsrend logika

3.3.

Elsrend logikai törvények

3.29. definíció. Az elsrend logikai nyelv egy A formulája kielégíthet, ha van a nyelvnek olyan I interpretációja és I-ben van olyan változókiértékelés, amelyre |A|I, = i, egyébként A kielégíthetetlen. Ha az I interpretáció és a változókiértékelés olyanok, hogy |A|I, = i, azt mondjuk, hogy I a változókiértékelés mellett kielégíti A-t. Amennyiben az A formula zárt, igazságértékét egyedül az interpretáció határozza meg. Ha |A|I = i, azt mondjuk, hogy az I interpretáció kielégíti A-t vagy másképp, a I interpretáció az A formula modellje.

3.3.

Elsrend logikai törvények

101

3.30. példa. (a) A P (x) xP (x) formula kielégíthet, mert például az I interpretációban egy olyan változókiértékelés mellett, amelyben I , = h, és így (x) = c, |P (x)|
I , = |P (x)|I , |xP (x)|I , = i. |P (x) xP (x)|

(b) Ugyanakkor a xP (x)¬P (x) formula kielégíthetetlen, hiszen ha rögzítünk egy tetszleges I interpretációt és I-ben egy tetszleges változókiértékelést, akkor |xP (x)|I, 1. vagy h igazságérték, így |xP (x) ¬P (x)|I, = |xP (x)|I, |¬P (x)|I, = h, 2. vagy i igazságérték, de ekkor minden x-variánsa, tehát maga mellett is |P (x)|I, = i, így |¬P (x)|I, = h, ezek szerint most is |xP (x) ¬P (x)|I, = |xP (x)|I, |¬P (x)|I, = h.

102

3.

Az elsrend logika

3.31. definíció. Az elsrend logikai nyelv egy A formulája logikai törvény, ha a nyelv minden I interpretációjában és I minden változókiértékelése mellett |A|I, = i. Jelölése: |= A. 3.32. példa. (a) A P (x) xP (x) formula bár kielégíthet, de nem logikai törvény, mert például az I interpretációban egy olyan váltoI , = i, de zókiértékelés mellett, amelyben (x) = a, |P (x)| I , = h, mivel a (x) = c változókiértékelés mellett |xP (x)| I , = h. Ezért |P (x)|
I , = |P (x)|I , |xP (x)|I , = h. |P (x) xP (x)|

3.3.

Elsrend logikai törvények

103

(b) Alább pedig azt bizonyítjuk be, hogy a xP (x) P (x) formula viszont logikai törvény. Rögzítsünk tetszlegesen egy I interpretációt és egy változókiértékelést. Két eset lehetséges: 1. Ha I kielégíti a xP (x)-et, akkor I minden változókiértékelése mellett, tehát mellett is |P (x)|I, = i, azaz |xP (x) P (x)|I, = |xP (x)|I, |P (x)|I, = i. 2. Ha pedig I nem elégíti ki a xP (x)-et, azaz |xP (x)|I = h, akkor szintén |xP (x) P (x)|I, = |xP (x)|I, |P (x)|I, = i.

104

3.

Az elsrend logika

Hasonlóan az ítéletlogikához, egy elsrend logikai nyelv formuláit is osztályozhatjuk szemantikai tulajdonságuk alapján:

kiel´g´ e ithet o

kiel´g´ e ithetetlen

logikailag igaz

3.3.

Elsrend logikai törvények

105

Az ítéletlogikában használtuk a prímformula fogalmát. A prímformulákból a ¬, , , logikai összekötjelek segítségével minden ítéletlogikai formulát fel tudtunk építeni. Egy elsrend logikai nyelvben is vannak ilyen formulák: a nyelv atomi formulái és a kvantált formulák. Ezek a formulák az elsrend logikai nyelv prímformulái. 3.33. példa. A harmadik példanyelvben prímformulák: P (x), Q(y, x), ~Q(y, x), x¬~Q(y, x), . . . ~ x ~ x ~

106

3.

Az elsrend logika

3.34. definíció. Egy formula azon részformuláit, amelyek prímformulák és amelyekbl a formula csupán a ¬, , , logikai összekötjelek segítségével felépíthet, a formula prímkomponenseinek nevezzük. 3.35. példa. · A x¬~Q(x, x) formula egyetlen prímkomponense x ~ önmaga. · A ¬~(Q(x, x) R(~, x)) Q(x, x) prímkomponensei x ~ x ~ ~ a ~(Q(x, x) R(~, x)) és a Q(x, x) formulák. x ~ x ~ ~

3.3.

Elsrend logikai törvények

107

Legyenek az A formula prímkomponensei A1, A2, . . . , An. Ha a különböz prímkomponenseket ítéletváltozóknak tekintenénk, az így kapott ítéletlogikai formulához megadhatnánk az igazságtáblát. Az elsrend formulához így megkonstruált táblázatot Quine-féle táblázatnak hívjuk. · Ebben a táblázatban a sorokban szerepl igazságértékekrl azonban nem tudhatjuk, hogy van-e egyáltalán olyan interpretáció és az interpretációban olyan változókiértékelés, ami mellett a prímkomponensek igazságértékei rendre ezek lennének. · Az viszont nyilvánvaló, hogy minden interpretáció és minden változókiértékelés esetén a prímkomponensek igazságértékei a Quinetáblázat valamelyik sorában a prímkomponensekhez tartozó oszlopban rendre megtalálhatók.

108

3.

Az elsrend logika

3.36. példa. A ¬x¬P (x) xP (x) formula prímkomponensei x¬P (x) és xP (x). A formula Quine-féle táblázata a következ: x¬P (x) xP (x) ¬x¬P (x) xP (x) i i h h i h i h i i i h

3.3.

Elsrend logikai törvények

109

Jellemezzük most a Quine-táblázat segítségével az elsrend formulákat. 3.37. definíció. Az elsrend logikai nyelv egy A formulája tautologikusan igaz (tautológia), ha a formula Quine-táblázatában A oszlopában csupa i igazságérték található. Jelölése: |=0 A. 3.38. lemma. Ha az A elsrend formula tautologikusan igaz (tautológia), akkor elsrend logikai törvény, azaz ha |=0 A, akkor |= A. Egy formula Quine-táblázatában lehetnek olyan sorok is, melyekben szerepl igazságértékeket az egyes oszlopokhoz tartozó prímkomponensek egyszerre egyetlen interpretációban egyetlen változókiértékelés mellett sem vehetik fel. Az ilyen formula bár nem tautológia, elsrend logikai törvény még lehet.

110

3.

Az elsrend logika

3.39. példa. (a) A (xP (x) xP (x)) ¬xP (x)xP (x) formula prímkomponensei xP (x) és xP (x). A formula Quine-féle táblázata a következ: xP (x) xP (x) (xP (x) xP (x)) ¬xP (x) xP (x) i i h h i h i h i i i i

A formula oszlopában csupa i igazságérték található, tehát a formula tautologikusan igaz, azaz logikai törvény.

3.3.

Elsrend logikai törvények

111

(b) Láttuk, hogy a ¬x¬P (x) xP (x) nem tautologikusan igaz formula, pedig logikai törvény. Egy tetszlegesen rögzített I interpretációban ugyanis 1. vagy |¬x¬P (x)|I = h, így |¬x¬P (x) xP (x)|I = i, 2. vagy |¬x¬P (x)|I = i, ekkor viszont |x¬P (x)|I = h. Ez pedig azt jelenti, hogy minden változókiértékelés mellett |¬P (x)|I, = h, azaz |P (x)|I, = i, tehát |xP (x)|I = i. Így viszont ebben az esetben is |¬x¬P (x) xP (x)|I = i, tehát a ¬x¬P (x) xP (x) formula logikai törvény.

112

3.

Az elsrend logika

3.40. tétel. Legyenek A, B és C elsrend logikai formulák, ekkor a következ formulák elsrend logikai törvények:
bvítés eltaggal implikációlánc-törvény |= A (B A) |= (A (B C)) ((A B) (A C)) |= A (B A B) |= A B A és |= A B B |= (A C) ((B C) (A B C)) |= A A B reductio ad absurdum a kétszeres tagadás törvénye a kizárt harmadik törvénye ellentmondás törvénye az azonosság törvénye tranzitivitás és |= B A B

|= (A B) ((A ¬B) ¬A) |= ¬¬A A |= A ¬A |= ¬(A ¬A) |= A A |= (A B) (B C) (A C)

ellentmondásból bármi következik |= A (¬A B) Peirce-törvény |= ((A B) A) A

3.3.

Elsrend logikai törvények

113

3.41. tétel. Legyenek A és B az L nyelv tetszleges formulái. Ekkor |= xA xB x(A B) |= x(A B) xA xB |= yxA xyA

114

3.

Az elsrend logika

3.42. definíció. Legyenek A és B az L nyelv tetszleges formulái. Azt mondjuk, hogy az A és a B elsrend formulák logikailag ekvivalensek, és ezt a tényt úgy jelöljük, hogy A B, ha minden I interpretációban és változókiértékelés mellett |A|I, = |B|I,. 3.43. példa. (a) A ¬xP (x) és a x¬P (x) formulák ekvivalensek, ugyanis tetszlegesen rögzített I interpretációban és változókiértékelés mellett ha 1. |¬xP (x)|I = i, akkor |xP (x)|I = h, azaz van -nak olyan x-variánsa, hogy |P (x)|I, = h, tehát |¬P (x)|I, = i, azaz |x¬P (x)|I = i. 2. |¬xP (x)|I = h, akkor |xP (x)|I = i, azaz -nak minden I, = i, tehát |¬P (x)|I, = h, x-variánsa olyan, hogy |P (x)| azaz |x¬P (x)|I = h.

3.3.

Elsrend logikai törvények

115

(b) A xyQ(x, y) formula viszont nem ekvivalens a yxQ(x, y) formulával. Vizsgáljuk meg a formulákat az I interpretációban.
I = i, mert ,,mindhárom" x-variáns változóki1. |xyQ(x, y)|

értékeléshez van olyan y-variáns változókiértékelés, hogy mellette Q(x, y) i igazságérték. Legyen ugyanis 1 olyan, hogy 1(x) = a, 1(y) = a, 2 olyan, hogy 2(x) = b, 2(y) = b és 3 olyan, hogy 3(x) = c, 3(y) = a. Ekkor
I ,1 = |Q(x, y)|I ,2 = |Q(x, y)|I ,3 = i. |Q(x, y)| I = h, mert ,,mindhárom" y-variáns változóki2. |yxQ(x, y)|

értékeléshez van olyan x-variáns változókiértékelés, hogy mellette Q(x, y) h igazságérték. Legyen ugyanis 1 olyan, hogy 1(y) = a, 1(x) = b, 2 olyan, hogy 2(y) = b, 2(x) = a és 3 olyan, hogy 3(y) = c, 3(x) = a. Ekkor
I ,1 = |Q(x, y)|I ,2 = |Q(x, y)|I ,3 = h. |Q(x, y)|

116

3.

Az elsrend logika

Legyenek A és B elsrend formulák. 3.44. lemma. A B pontosan akkor, ha |= (A B) (B A). 3.45. tétel. Ha A B, akkor A B. 3.46. tétel. Ha A olyan formula, hogy x Par(A), akkor / xA A és xA A. 3.47. tétel. xyA yxA és xyA yxA. 3.48. tétel. (Kvantorok kétoldali kiemelése.) xA xB x(A B) és xA xB x(A B).

3.3.

Elsrend logikai törvények

117

3.49. tétel. (De Morgan kvantoros törvényei.) ¬xA x¬A és ¬xA x¬A. 3.50. tétel. (Kvantorok egyoldali kiemelése.) Ha x Par(A), akkor / A xB x(A B) A xB x(A B) A xB x(A B) xB A x(B A) A xB x(A B) A xB x(A B) A xB x(A B) xB A x(B A)

118

3.

Az elsrend logika

3.3.1.

Formulák prenex alakja

Egy Q1x1Q2x2 . . . QnxnA (n 0) alakú formulát, ahol a A kvantormentes formula, prenex alakú formulának nevezünk. Példa. A xy(P (x, y) ¬Q(x)), a xy(P (x, y) R(x, z)), a ¬P (x, x) formulák prenexformulák, viszont a xyP (x, y) ¬Q(x) formula nem prenexformula. Lemma. Egy elsrend logikai nyelv tetszleges formulájához konstruálható vele logikailag ekvivalens prenex alakú formula.

3.3.

Elsrend logikai törvények

119

A konstrukció lépései: 1. változó-tiszta alakra hozzuk a formulát; 2. alkalmazzuk De Morgan kvantoros és az egyoldali kvantorkiemelésre vonatkozó logikai törvényeket. Példa. xP (x) ¬xQ(x) változó-tiszta alakra hozás xP (x) ¬yQ(y) egyoldali kvantorkiemelés xP (x) y¬Q(y) x(P (x) y¬Q(y)) xy(P (x) ¬Q(y))

120

3.

Az elsrend logika

3.4.

Szemantikus következményfogalom

3.51. definíció. Legyen egy elsrend nyelv formuláinak halmaza és B formula. B logikai következménye a formulahalmaznak (vagy a -beli formuláknak), ha a nyelv minden olyan interpretációja és változókiértékelése, amely kielégít minden -beli formulát, az kielégíti a B formulát is. Jelölése: |= B.

3.4.

Szemantikus következményfogalom

121

3.52. példa. (a) A {P (c), x(P (x) ~Q(x, x))} formulahalmaznak logikai köx ~ vetkezménye a ~Q(c, x) formula. Ugyanis ha I egy olyan interx ~ pretáció, hogy |P (c)|I = i és |x(P (x) ~Q(x, x))|I = i, x ~ akkor bármely x-variáns mellett |P (x) ~Q(x, x)|I, = i. x ~ Legyen (x) = |c|I . De |P (x)|I, = |P (c)|I és |~Q(x, x)|I, = |~Q(c, x)|I , x ~ x ~ így világos, hogy |P (x)|I, = i miatt |~Q(x, x)|I, = i, tehát x ~ |~Q(c, x)|I = i. x ~ (b) A x~R(f (x, x), x) formulának nem logikai következménye a x ~ ~ x ~ ~ ~R(~, x) formula, hisz az I p1 interpretációban a x~R(f (x, x), x) x x ~ formula i, de a ~R(~, x) formula h igazságérték. x x ~

122

3.

Az elsrend logika

3.53. tétel. Legyenek A1, A2, . . . , An, B (n 1) az elsrend formulák. {A1, A2, . . . , An} |= B pontosan akkor, ha 1. az A1 A2 . . . An ¬B formula kielégíthetetlen. 2. az A1 A2 . . . An B formula logikai törvény.

3.4.

Szemantikus következményfogalom

123

3.54. definíció. Legyen egy elsrend nyelv formuláinak véges halmaza és B tetszleges formulája. Azt mondjuk, hogy B tautologikus következménye -nak, ha a formulahalmaz és B közös Quine-táblázatában azon sorokban, ahol minden -beli formula alatt i igazságérték található, B oszlopában is csupa i igazságérték van. Jelölése: a |=0 B. 3.55. lemma. Ha {A1, A2, . . . , An} |=0 B, akkor {A1, A2, . . . , An} |= B.

124

3.

Az elsrend logika

3.56. példa. 1. A {x~Q(x, x) xP (x), ¬xP (x)} formulahalmaznak taux ~ tologikus következménye a ¬x~Q(x, x) formula: x ~
x~Q(x, x) xP (x) x~Q(x, x) xP (x) ¬xP (x) ¬x~Q(x, x) x ~ x ~ x ~ i i h h i h i h i h i i h i h i h h i i

2. Az 3.52. (a) példájában pedig a következményformula nem tautologikus következménye a feltételformulák halmazának.

3.4.

Szemantikus következményfogalom

125

3.57. tétel. Legyenek A, B és C tetszleges elsrend logikai formulák. Az alábbiakban felsorolt elsrend következtetésformák helyesek: a leválasztási szabály vagy modus ponens ({A B, A}, B) a kontrapozíció vagy modus tollens reductio ad absurdum az indirekt bizonyítás feltételes szillogizmus következtetés esetszétválasztással modus tollendo ponens az -ra vonatkozó következtetésforma a ¬¬-re vonatkozó következtetésformák ({A B, ¬B}, ¬A) ({A B, A ¬B}, ¬A) ({¬A B, ¬A ¬B}, A) ({A B, B C}, A C) ({A B, A C, B C}, C) ({A B, ¬A}, B) ({B}, A B) ({¬¬A}, A) és ({A}, ¬¬A)

126

3.

Az elsrend logika

a -ra vonatkozó következtetésformák az -re vonatkozó következtetésformák

({A}, A B) és ({B}, A B) ({A, B}, A B) ({A B}, A) és ({A B}, B)

Természetesen vannak olyan elsrend következtetésformák is, amely következtetésformákban a formulahalmaznak logikai (de nem tautologikus) következménye a formula. az univerzális kvantor elhagyása az egzisztenciális kvantor bevezetése szillogizmusok ({x(A B), x(B C}, x(A C)) ({x(A B), x(B C)}, x(A C)) ({xA}, [A(x ({[A(x t)]) t)]}, xA)

4. fejezet

A szekventkalkulus A szekvent Legyenek A1, A2, . . . , An, B1, B2, . . . , Bm, (n, m 0) egy elsrend nyelv formulái. Ekkor a A1 A2 . . . An B1 B2 . . . Bm formulát szekventnek nevezzük. Jelölése: A1, A2, . . . , An B1, B2, . . . , Bm, vagy rövidebben: , ahol {A1, A2, . . . , An} és {B1, B2, . . . , Bm}.

127

128

4.

A szekventkalkulus

A kalkulus axiómásémái és levezetési szabályai A A

129

( )

AB (A B)

A; B ( ) (A B) AB (A B) A B (A B) A ¬A A(x||y) xA

A ; B ( ) ( ) (A B) A; B () () (A B) (¬ ) A ¬A ( ¬)

A(x||t)xA ( ) ( ) xA ( ) A(x||y) xA

A(x||t)xA ( ) xA

130

4.

A szekventkalkulus

Egy szekventet a kalkulusban levezethetnek nevezünk, ha · vagy axióma, · vagy van olyan levezetési szabály, melyben ez vonal alatti szekvent és a vonal feletti szekvent vagy szekventek pedig levezethetek. (a) A kalkulus helyes, mert ha az A1, A2, . . . , An B1, B2, . . . , Bm szekvent levezethet a kalkulusban, akkor a A1 A2 . . . An B1 B2 . . . Bm formula logikai törvény. (b) A kalkulus teljes, mert ha az A formula logikai törvény, akkor a A szekvent levezethet a kalkulusban.

Irodalomjegyzék [1] Dragálin Albert, Buzási Szvetlána: Bevezetés a matematikai logikába, Kossuth Egyetemi Kiadó, Debrecen, 1986. [2] Pásztorné Varga Katalin, Várterész Magda: A matematikai logika alkalmazás-szemlélet tárgyalása, Panem Kiadó, Budapest, 2003. [3] Szendrei Ágnes: Diszkrét matematika, Polygon Kiadó, Szeged, 1994.

131



Hasonló témájú dokumentumok

Hozzászólások

2010 állatszervezettan bce kik beadandó dns elektro elmélet eloadas elte filozófia tételek forgó mozgás fotó gén görögország hálótervezés házi doga humán információelmélet irodalomtudomány kommunikáció koncentráció konjunktúrakutatás könyvtárinformatika krúdy kultúra labor lengéstan matek ii. zh matek jegyzet metafora minta munkaerőpiac nonverbális kommunikáció öko1 önkormányzat öregedés példasor v rushdie sql stendhal szamitogep szociolingvisztika szótár toxikológia turizmus szak utazás védelem zárthelyi zh zsidó