Ugrás a tartalomhoz

A matematikai logika alkalmazásszemléletű tárgyalása

Pásztorné Varga Katalin, Várterész Magda, Sági Gábor

Panem Kft.

Chapter 3. A logikai nyelvekről

Chapter 3. A logikai nyelvekről

Általános tudnivalók – megjegyzések

A logika tárgyalásához ugyanúgy mint bármely más tudományág esetén, szükség van egy megfelelő leíró nyelvre. Ennek a nyelvnek alkalmasnak kell lennie az állítások pontos leírására és az állítások közötti logikai kapcsolatok megfogalmazására. Az e feltételeknek eleget tevő nyelveket logikai nyelveknek nevezzük. A logikai nyelv első feladata az egyszerű állítások leírása. Az egyszerű állításokat kijelentő mondatokkal fogalmazhatjuk meg, amelyekben mindig valami(k)ről, valaki(k)ről, más szóval bizonyos individuum(ok)ról állítunk valamit. Vizsgáljunk meg egy állítást kifejező kijelentő mondatot mint a logikai nyelv elemét. Egy ilyen mondat alkotóelemei nem logikai jellegűek. A logikai nyelvekben két nem logikai alapkategóriát állapítunk meg. Ezek a kijelentő mondat, röviden mondat és az individuumnév, röviden név. A név valamely individuum azonosítására szolgál. Nevek a tulajdonnevek, az egyes számú névmások (én, te, ő, ez), valamint az individuumleírások (,,Panni férje”, ,,Géza sógora”, ,,Jancsi és Juliska első gyermeke”). Az individuumleírásokkal szemben követelmény, hogy a leírás az individuumokat egyértelműen határozza meg, és hogy létezzen a leírt individuum. Például a ,,Géza sógora” meghatározás akkor individuumleírás, ha Gézának pontosan egy sógora van, nem egyértelmű a leírás, ha Gézának több sógora is van, és nem létezik a leírt individuum, ha Gézának nincs sógora. Megjegyezzük, hogy az individuumleírás matematikai értelemben egy többváltozós függvény. Például a ,,Jancsi és Juliska első gyermeke” egy kétváltozós függvény, amelynek értéke Jancsi és Juliska behelyettesítésre az első gyermekük. A mondat alkotóelemei a nevek és a mondat többi része, amely valamilyen önmagában is értelmes kifejezés vagy egy kifejezésszerkezet. Ebben a kifejezésszerkezetben a nevek helyei ki vannak jelölve. Az alábbi példákban vastag betűkkel szedtük a kifejezésszerkezeteket.

  1. Panni kirándulni ment. … kirándulni ment.

  2. Mari alacsonyabb, mint Géza. … alacsonyabb, mint …

  3. Kati látta, hogy Jancsi találkozott Juliskával. … látta, hogy … találkozott …

Ezt a szerkezetet predikátumnak is nevezzük. A predikátum megadható mint a megfelelő szerkezet, vagy pedig egy a predikátumot jelölő szöveg, amelyet – zárójelbe téve – az eredeti mondatban szereplő nevek megfelelő sorrendben való felsorolása követ. Egyrészt a predikátum egy vagy több névből mondatot képez, vagyis nyelvi szempontból nézve ez egy funktor (,,predikátum funktor” [57]). Másrészt a predikátum egy olyan függvénnyel modellezhető, ahol a változószám a mondatban szereplő nevek száma. Ez a függvény a mondathoz igaz vagy hamis értéket rendel. Tehát a predikátum jelentése matematikai értelemben logikai függvény vagy reláció.

Írjuk fel a fenti példákat mint predikátumos kifejezéseket:

1.

Kirándulni ment (Panni)

vagy

Km(Panni)

2.

Alacsonyabb, mint (Mari, Géza)

vagy

Am(Mari, Géza)

3.

Látta, hogy találkozott (Kati, Jancsi, Juliska)

vagy

Lt(Kati, Jancsi, Juliska)

Azokat az állításokat, amelyek meghatározott individuumokról mondanak valamit nulladrendű állításoknak nevezzük. Ilyen állítások leírására definiálni kell az individuumok halmazán a megfelelő relációt. Vezessük be az individuumváltozó fogalmát. Az individuumváltozó az individuumok halmazát futja be, tehát bármelyik individuum lehet az értéke.

  1. Legyen az individuumhalmaz N0; x,y,z individuumváltozók és a reláció:

R ( x , y , z ) { i ( g a z ) ha z az x és az y legkisebb közös többszöröse , h ( a m i s ) egyébként .

Ennek megfelelően R(2,3,6) egy igaz állítás.

  1. Legyen az individuumhalmaz a ,,mesehősök” halmaza, x,y individuumváltozók, a reláció definíciója pedig:

T ( x , y ) { i ( g a z ) ha x és y testvérek , h ( a m i s ) egyébként .

Ekkor T(Jancsi,Juliska) és T(Jancsi,t(Jancsi)) igaz állítások, feltéve hogy a t(x) függvény értéke egy u mesehős esetén u testvére, ha u-nak egy testvére van, és nemdefiniált egyébként.

Egy logikai nyelvben meg kell oldani tetszőlegesen összetett állítások felírását is. Ehhez az állítások közötti logikai kapcsolatokat kifejező logikai összekötőkre (logikai szavakra [56]) van szükség. A logikai nyelv második feladata tehát a logikai összekötők meghatározása. A logikai összekötők logikai jellegűek, hiszen egy logikai nyelv elemeit (az állításokat) kapcsolják össze. A logikai összekötőktől megköveteljük, hogy az alkalmazásuk során kapott állítás igazságértéke csak a velük összekötött állítások igazságértékétől függjön. Ez azt jelenti, hogy egy n állítást összekapcsoló logikai összekötő az igazságértékek bármely a1,a2,,an sorozatához egyértelműen rendel hozzá egy igazságértéket, tehát jelentése egy n-változós logikai művelet (igazságfüggvény). Ezzel érjük el azt a célt, hogy az összetett állítás igazságértéke objektív, és hogy a kétértékűség valamint az ellentmondás elve sem sérül. Az egyszerű állítások leírása így elveszíti jelentőségét, tehát elegendő hozzájuk egy-egy azonosítót rendelni. Ezeket az azonosítókat állításjeleknek, vagy propozicionális betűknek szokták nevezni és nagybetűvel kezdődő jelsorozatokat fogunk azonosításukra használni. Jelölhetjük például Th-val azt az egyszerű állítást, hogy ,,tegnap havazott”.

A logikában egy- és kétváltozós logikai összekötőket használnak, amelyek jelentése nyilván egy-, illetve kétváltozós logikai művelet. Most művelettáblájuk (igazságtáblájuk) felhasználásával áttekintjük a lehetséges egy- és kétváltozós logikai műveleteket és kiválasztjuk azokat, amelyek egy-egy logikai összekötő értelmezésével megegyeznek, vagy legalábbis közel állnak ahhoz. A logikai összekötők egy nyelv szavai. E szavak alapjelentéséből kiindulva egy ilyen szónak az a logikai műveletet lehet a jelentése, amelynek a művelettáblája lényegében fedi az összekötő mint szó nyelvbeli jelentését.

Table 3.1. Az egyváltozós logikai műveletek

1.

2.

3.

4.

X

¬ X

X

i

h

i

h

i

i

h

h

i

h

i

h


A fenti egyváltozós logikai műveletek közül csak az első és a második valódi egyváltozós művelet. A harmadik és a negyedik, a konstans i és h, nullváltozós műveletek. Logikai összekötőnek csak az első műveletet feleltetjük meg. Ezzel fejezzük ki egy állítás tagadását, hiszen ha az állítás igaz (i), akkor a művelet eredménye hamis (h) és ha az állítás hamis (h), akkor a művelet eredménye igaz (i). A művelet jele ¬, a neve műveletként negáció, logikai összekötőként pedig nem igaz, hogy …. Jelöljön P egy tetszőleges állítást, akkor a ¬P igazságértéke akkor és csak akkor igaz, ha P hamis és ¬¬P igazságértéke megegyezik P igazságértékével.

Table 3.2. A kétváltozós logikai műveletek

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

15.

16.

X

Y

|

¬

¬

X

¬ X

Y

¬ Y

i

h

i

i

i

i

i

i

h

h

h

h

i

h

i

h

i

h

i

h

i

h

h

i

h

h

i

i

h

i

i

h

i

h

h

i

i

h

h

i

h

i

i

h

i

i

h

h

h

i

h

i

i

h

i

h

h

h

h

h

i

i

h

i

i

h

i

h

h

i

h

i

i

h


E műveletek között az első tíz a valódi kétváltozós művelet. A 11–14. műveletek egy-, a 15. és 16. műveletek nullváltozósak. Hagyományosan az első négyet (az 1–4. sorszámúakat) feleltetik meg logikai összekötőknek. Egyes esetekben már a negyedik művelet sem szerepel a kiválasztottak között. (A kiválasztott logikai műveletek száma még tovább csökkenthető az összetett állítások felírásának korlátozása nélkül, ezt azonban egy későbbi fejezetben fogjuk vizsgálni.) Most az 5–7. sorszámú műveleteket is megfeleltetjük logikai összekötőknek, bár ilyen szerepkörben nem fogjuk használjuk őket.

Jelöljenek a következőkben P és Q tetszőleges állításokat.

  • Az 1. művelet jele , a neve műveletként konjunkció, logikai összekötőként … és …. A ,,P és Q” állítás jelölése: PQ, jelentése: PQ akkor és csak akkor igaz, ha P is és Q is igaz, illetve akkor és csak akkor hamis, ha P és Q közül legalább az egyik hamis.

  • A 2. művelet jele , a neve műveletként diszjunkció, logikai összekötőként … vagy …. A ,,P vagy Q” állítás jelölése PQ. Jelentése: PQ akkor és csak akkor igaz, ha P és Q közül legalább az egyik igaz, illetve akkor és csak akkor hamis, ha P is és Q is hamis. Ebből az értelmezésből látható, hogy ez a művelet a ,,megengedő vagy”, bár az elnevezés (diszjunkció) a ,,kizáró vagy”-ra utal.

  • A 3. művelet jele , a neve műveletként implikáció (bizonyos szerzőknél kondicionális), logikai összekötőként ha …, akkor …. A ,,ha P, akkor Q” (feltételes) állítás jelölése PQ. P-t szokás feltételrésznek (előtagnak) és Q-t következményrésznek (utótagnak) nevezni. Jelentése: PQ akkor és csak akkor igaz, ha P hamis vagy Q igaz, illetve akkor és csak akkor hamis, ha P igaz és Q hamis. Ez utóbbi feltétel tulajdonképpen természetes: egy következtetést akkor tekintünk hamisnak, ha a kiindulási állítás igaz, de a következményként előírt állítás nem. Az implikáció műveletnek és a ,,ha …, akkor …” logikai összekötőnek a megfeleltetése mégis magyarázatra szorul. A művelet kifejezi, hogy igaz feltételből csak igaz állítás következhet. A művelet kifejezi azt is, hogy ha a következmény hamis, akkor a feltétel sem lehet igaz. Mint láttuk, az implikáció művelet akkor és csak akkor hamis, ha P¬Q értéke hamis. Ezért ¬(P¬Q) jelentése ugyanaz mint PQ jelentése. Példán illusztrálva: A ,,ha minden kérdésre tudok válaszolni, akkor átmegyek a vizsgán” állítás ugyanazt fejezi ki, mint a ,,nem igaz, hogy minden kérdésre tudok válaszolni és nem megyek át a vizsgán” állítás.

  • A 4. művelet jele , a neve műveletként ekvivalencia (bizonyos szerzőknél bikondicionális), logikai összekötőként … akkor és csak akkor, ha …. A ,,P akkor és csak akkor, ha Q” állítás jelölése PQ. Jelentése: PQ akkor és csak akkor igaz, ha P és Q igazságértéke egyforma. Könnyű belátni, hogy PQ jelentése megegyezik (PQ)(QP) jelentésével.

  • Az 5. művelet jele , a neve műveletként kizáró vagy, logikai összekötőként vagy …, vagy …. A ,,vagy P, vagy Q” állítás jelölése PQ. Jelentése: PQ akkor és csak akkor igaz, ha P és Q közül pontosan az egyik igaz.

  • A 6. művelet jele |, a neve műveletként Sheffer-vonás, logikai összekötőként … és … közül legalább az egyik nem. A ,,P és a Q közül legalább az egyik nem” állítás jelölése P|Q. Jelentése: P|Q akkor és csak akkor igaz, ha P és Q közül legalább az egyik hamis, illetve akkor és csak akkor hamis, ha P is és Q is igaz.

  • A 7. művelet jele: , a neve műveletként Peirce-vonás, logikai összekötőként sem …, sem …. A ,,sem P, sem Q” állítás jelölése PQ. Jelentése: PQ akkor és csak akkor igaz, ha sem P sem Q nem igaz, illetve akkor és csak akkor hamis, ha P és Q közül legalább az egyik igaz.

Table 3.3. A logikai műveletek mint logikai összekötők

jel

logikai művelet

logikai összekötő

¬

negáció

nem igaz, hogy …

konjunkció

… és …

diszjunkció

… vagy …

implikáció

ha …, akkor …

ekvivalencia

… akkor és csak akkor, ha …

kizáró vagy

vagy …, vagy …

|

Sheffer-vonás

… és … közül legalább az egyik nem

Peirce-vonás

sem …, sem …


Összetett állítás tehát egy egyszerű állításokból logikai összekötőkkel összekapcsolt kifejezés. Például ha Pa a ,,Péter alszik”, Ko a ,,Kati olvas” egyszerű állításokat jelöli, ¬Pa a ,,Péter nem alszik”,PaKo a ,,Péter alszik és Kati olvas”, PaKo a ,,ha Péter alszik, akkor Kati olvas” összetett állításokat adja.

Vezessünk be az állítások halmazát befutó változókat, melyeket ítélet-, vagy állításváltozóknak nevezünk. Miután ezeknek a változóknak az értékei, az állítás definíciója miatt, végül is logikai igazságértékek lesznek, az ítéletváltozókat logikai változóknak is hívhatjuk. Formulának nevezünk egy olyan kifejezést, amelyet összetett állításból kapunk úgy, hogy benne az egyszerű állításokat ítéletváltozókra cseréljük.

Egy logikai nyelv kifejezőerején a nyelven leírható egyszerű és összetett állítások minőségét értjük. Az eddigi eszközökkel csak az egyes individuumokra vonatkozó állítások fogalmazhatók meg. Ezeket a nyelveket nulladrendű nyelveknek nevezzük. Már láttuk, hogy az egyszerű állítások leírására fel kellett használjuk az állításban szereplő individuumokat és valamilyen logikai függvényt (relációt). Legyen U egy individuumhalmaz, x,y,z individuumváltozók. Definiáljuk például az R relációt U-n a következőképpen:

R ( x , y , z ) { i ha legalább két argumentum értéke megegyezik , h egyébként .

Ekkor R(ui,uj,uk) egy egyszerű állítás, ahol ui,uj,ukU. Ez az eszköz az egyes individuumokra vonatkozó egyszerű nulladrendű állítások megfogalmazására alkalmas. Az R(x,uj,uk) kifejezés nem állítás, hisz x nem individuum. Az ilyen kifejezéseket paraméteres állításoknak nevezzük, mivel lényegében úgy viselkednek, mint az ítéletváltozók. Formulákat nyerhetünk tehát úgy is, hogy egy összetett állításban az egyszerű állításokat paraméteres állításokra cseréljük. Az R(x,uj,uk) paraméteres állítás azonban nem az összes állítások halmazát futja be, hanem csak azon állításokét, amelyeket a R(x,uj,uk)-ből az x individuumváltozónak az uU individuummal való helyettesítése eredményeképp kapunk.

A nyelv kifejezőerejének növelését jelenti, ha az egyes individuumokra megfogalmazott állítások mellett az individuumok halmazára vonatkozó állítások leírására is lehetőséget teremtünk. Erre eszközök a kvantorok, amelyek esetünkben az individuumváltozókra vonatkoznak. Az univerzális kvantor jele , az egzisztenciális kvantoré . A x javasolt kiolvasása: ,,minden x-re”, illetve a x javasolt kiolvasása pedig: ,,van olyan x, hogy”. Jelöljön A egy formulát. A xA pontosan akkor igaz, ha A minden individuumhalmazbeli elemnek x-be való behelyettesítésére igaz, és a xA pedig pontosan akkor igaz, ha A az individuumhalmaz legalább egy elemének x-be való behelyettesítésére igaz. Azt mondjuk, hogy egy xA, illetve egy xA formulában a kvantor ,,leköti” az x változót. Mint látható, egy formula igazságértéke nem függ a kvantorral lekötött változójától. A x, illetve az x jelekkel kezdődő formulákat univerzálisan, illetve egzisztenciálisan kvantált formuláknak nevezzük. A kvantorokat tartalmazó nyelvek az elsőrendű logikai nyelvek, a kvantoros formulák pedig az elsőrendű formulák.

Az előzőekben vázolt, valamely konkrét helyzetet leíró logikai nyelvről elmondhatjuk, hogy a nyelv ábécéjének elemei a leírásban előforduló individuumok neveinek összessége (vagy néhány kitüntetett individuum neve), az individuumváltozók, az állítások leírásához szükséges predikátumok, a logikai összekötők jelei és a kvantorok. A szintaxis a predikátumok és a műveletek formai jegyeinek, a szemantika pedig ezek tartalmának meghatározását írja le. Tehát azt mondhatjuk, hogy

nyelv = ábécé + szintaxis + szemantika.

(A szintaxis és a szemantika fogalmának pontos definiálására a későbbiekben kerül sor.)

Egy logikai nyelvben az egyszerű állítások leírásához az individuumhalmazon kívül individuumleírásra és relációkra van szükség. Ezek alkotják a nyelv nem logikai (logikán kívüli) részét. A logikai nyelvek logikai része tartalmazza a logikai összekötőjeleket, a kvantorokat és az individuumváltozókat. A logikai nyelvek logikai részei csak abban különbözhetnek, hogy melyek a nyelv ábécéjéhez tartozó logikai összekötőjelek és kvantorok.

Feladatok

3.1.1. FELADAT. Az alábbi mondatok közül melyek fejeznek ki állítást?

  1. 2002. augusztus 20-án Debrecenben virágkarneváli felvonulás volt.

  2. Véges sok prímszám van.

  3. Azt mondom, hogy hazudok.

  4. Ki vette el a könyvemet?

  5. Vedd tudomásul, hogy nekem van igazam!

  6. Ki korán kel, aranyat lel.

  7. Holnap kánikula lesz.

  8. Elég jól megtanultam a leckét.

3.1.2. FELADAT. Vannak-e az alábbi mondatok között olyanok, amelyek ugyanazt az állítást fejezik ki?

  1. Senki sem vizsgázott sikeresen, aki nem járt előadásra.

  2. Aki nem járt előadásra, az nem vizsgázott sikeresen.

  3. Aki sikeresen vizsgázott, az járt előadásra.

  4. Ha időben nem kezded el a tanulást, nem fejezed be időre.

  5. Ha időre befejezed a tanulást, akkor időben elkezdted.

  6. Ha nem fejezted be időre a tanulást, akkor el sem kezdted időben.

  7. Elkezded a tanulást, vagy nem fejezed be időre.

  8. Nem igaz, hogy időben nem kezded el a tanulást, mégis befejezed időre.

3.1.3. FELADAT. A következő mondatokban helyezzük el a megfelelő logikai összekötőket, ahol ezek köznyelvi formában szerepelnek.

  1. Anna nem ment el az iskolába.

  2. Nem igaz, hogy Anna nem ment el az iskolába.

  3. Esik az hó, de nincs hideg, és a szél sem fúj.

  4. Lóránt vagy moziba ment, vagy színházba, de nincs otthon.

  5. Ha ismerem a szabályt, és tudom, hogyan kell alkalmazni, jó eredményt kapok, feltéve, hogy nem vétek hibát.

  6. Csak akkor veszem meg az almát, ha érett, és nem kukacos.

  7. Egy természetes szám akkor és csak akkor páros, ha kettővel osztható.

3.1.4.FELADAT. Jelöljük ki az alábbi mondatokban szereplő predikátumokat.

  1. Zoltán okos.

  2. Péter és Pál testvérek.

  3. Veronika képeslapot küldött Lublinból Sándornak.