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 4. Az ítéletlogika

Chapter 4. Az ítéletlogika

Ebben a fejezetben a legegyszerűbb eszköztárral rendelkező formális logikát, az ítéletlogikát tanulmányozzuk. Az ítéletlogika nyelvében egyszerű és konkrét állítások között (tetszőlegesen bonyolult) logikai kapcsolatokat akarunk leírni. Az előző fejezetben az egyszerű állítások azonosítására állításjeleket használtunk. Szót ejtettünk az ítéletváltozókról is, melyek az egyszerű állítások halmazát futják be és ezzel lehetővé teszik tetszőleges egyszerű állítás elérését. Ezután megvizsgáltuk a formula intuitív fogalmát. Formulát nyertünk, amikor egy formalizált állításban az állításjeleket ítéletváltozókra cseréltük ki. Egy formulából tehát, ha az ítéletváltozók helyébe egyszerű állításokat, illetve azokat azonosító állításjeleket helyettesítünk, állítások lesznek. Ezért tehát az ítéletlogikában a formulákat fogjuk tanulmányozni. Természetesen foglalkozunk azokkal az ítéletlogikai lehetőségekkel is, hogyan szimbolizálhatók az előzmény és következmény kapcsolatok, és hogyan igazolható egy következtetés helyessége. Az ítéletlogikában tehát

  • eszközt adunk egyszerű állítások közötti logikai kapcsolatok leírására,

  • az állítások igazságértékének meghatározására,

  • definiáljuk ezekkel az eszközökkel a helyes következtetés fogalmát, és

  • módszert adunk, amellyel el lehet dönteni, hogy az előző pont értelmében helyesen következtettünk-e.

Az ítéletlogika nyelve – szintaxis

Az ítéletlogika nyelve egy speciális nulladrendű nyelv, melynek ábécéje csak logikai szimbólumokból áll: ítéletváltozókat, logikai összekötőjeleket és elválasztójeleket tartalmaz. Megállapodhatunk abban, hogy az ítéletváltozók jelölésére általában az X,Y,Z, betűket – esetleg ezeket a betűket indexelve – fogjuk használni, az ítéletváltozók halmazát pedig jelölje Vv. Alkalmazhatók a ¬ unér és a , , binér logikai összekötőjelek, továbbá két elválasztójel, a nyitó és a záró zárójel. Hivatkozzunk a továbbiakban röviden az ítéletlogika nyelvének ábécéjére V0-lal.

4.1.1. DEFINÍCIÓ. Az ítéletlogika nyelve a V0 ábécé feletti legszűkebb olyan tulajdonságú szóhalmaz, amelynek

  1. V v minden betűje egyúttal szava is,

  2. ha S eleme a szóhalmaznak, akkor ¬S is eleme és

  3. ha S és T elemei a szóhalmaznak és binér logikai összekötőjel, akkor (ST) is eleme a szóhalmaznak.

Egyszerű belátni, hogy a definícióban hivatkozott szóhalmaz egyértelműen létezik. Egyrészt van olyan szóhalmaz – a V0 ábécé feletti összes szónak a halmaza –, aminek eleme minden a definícióban megkívánt szó is. Másrészt az 1–3. tulajdonságú szóhalmazok metszete is 1–3. tulajdonságú. A legszűkebb olyan szóhalmaz pedig, mely ilyen tulajdonságú, az összes 1–3. tulajdonságú szóhalmaz metszete. Jelöljük ezt a halmazt 0-lal. 0-t tehát az ítéletlogika nyelvének nevezzük.

Ezek után könnyű megadni az ítéletlogika nyelvének szintaxisát, vagyis azokat a szabályokat, amelyek alapján elő lehet állítani a V0-beli jelekből 0 szavait. Ezeknek a szabályoknak megfelelően előállított szavakat nevezzük ítéletlogikai formuláknak (néha hangsúlyozottan: jólformált formuláknak). A szintaktikai szabályok alapján azt is el lehet majd dönteni, hogy egy V0 feletti szó formula-e. A formulákat a továbbiakban általában az A,B,C, betűkkel, vagy indexelt változataikkal jelöljük.

4.1.2. DEFINÍCIÓ. (0 SZINTAXISA.)

  1. Minden ítéletváltozó ítéletlogikai formula, ezeket a formulákat (atomi vagy) prímformuláknak is nevezzük.

  2. Ha A ítéletlogikai formula, akkor ¬A is az.

  3. Ha A és B ítéletlogikai formulák és binér logikai összekötőjel, akkor (AB) is ítéletlogikai formula.

  4. Minden ítéletlogikai formula az 1–3. szabályok véges sokszori alkalmazásával áll elő.

Világos, hogy 0 minden szava ítéletlogikai formula, hisz a szintaktikai szabályok segítségével előállított szavak a 4.1.1. definíció szerinti 1–3. tulajdonságú szóhalmazt alkotnak, és 0 a legszűkebb ilyen halmaz.

4.1.3. PÉLDA. A V0 ábécé feletti Z, ¬X, (Z¬X), (¬(Z¬X)Y) szavak ítéletlogikai formulák, de a Z¬X, (Z), ¬Z¬XY szavak nem formulák.

Ha egy formula ¬A alakú, negációs, ha (AB) alakú, konjunkciós, ha (AB) alakú, diszjunkciós, ha pedig (AB) alakú, implikációs formulának nevezzük. A negációs, konjunkciós, diszjunkciós és implikációs formulák összetett formulák.

4.1.4. TÉTEL. (A SZERKEZETI INDUKCIÓ ELVE.)

0 minden formulája T tulajdonságú,

(alaplépés:) ha minden prímformula T tulajdonságú és

(indukciós lépések:)

(i1) ha A0T tulajdonságú, akkor ¬A is T tulajdonságú

(i2) ha A,B0T tulajdonságúak és binér logikai összekötőjel, akkor (AB) is T tulajdonságú.

BIZONYÍTÁS. Tegyük fel, hogy teljesülnek az alaplépésben és az indukciós lépésekben megfogalmazott feltételek. Legyen továbbá Γ a T tulajdonságú formulák halmaza. Világos, hogy Γ a 4.1.1. definícióban szereplő 1–3. tulajdonságú halmaz rendre egyrészt az alaplépésben, másrészt az (i1) és (i2) indukciós lépésekben megadott feltételek teljesülése miatt. Mivel 0 a legszűkebb ilyen tulajdonságú halmaz, 0Γ. Így tehát 0 minden formulája is T tulajdonságú.

A szerkezeti indukció elve segítségével 0 formuláinak sok hasznos tulajdonságát lehet könnyen igazolni. Ennek az elvnek a felhasználásával bizonyítható a következő fontos állítás is.

4.1.5. TÉTEL. (AZ EGYÉRTELMŰ ELEMZÉS TÉTELE.)

0 minden formulájára a következő állítások közül pontosan egy igaz.

  1. A formula prímformula.

  2. A formula egy egyértelműen meghatározható 0-beli formula negáltja.

  3. A formula az egyértelműen meghatározható 0-beli A,B formulák és binér logikai összekötőjel felhasználásával előállított (AB) alakú formula.

BIZONYÍTÁS. Az állítást nem nehéz igazolni, de hosszadalmas. Ezért csak a bizonyítás vázlatát közöljük, részletes kidolgozását az olvasóra bízzuk.

  1. Foglalkozzunk először a negációjelet nem tartalmazó formulákkal. A szerkezeti indukció elve segítségével könnyű belátni, hogy egy ilyen formula minden valódi kezdőszelete több nyitó, mint záró zárójelet tartalmaz. Mivel minden formula ugyanannyi nyitó, és záró zárójelet tartalmaz, ezért

(*) egy negációjelet nem tartalmazó formulának egyetlen valódi kezdőszelete sem formula.

Vizsgáljuk most 0 egy tetszőleges, negációjelet nem tartalmazó formuláját. Ha ennek a formulának nincs valódi kezdőszelete, akkor prímformula. Ha pedig van kezdőszelete, csak binér logikai összekötőjelekkel generálhattuk. Tegyük fel, hogy ez a formula (AB) és (AB) alakú egyszerre, ahol és binér logikai összekötőjelek. Ekkor A és A azonos formulák, ellenkező esetben ugyanis a (A és a (A kezdőszeletek közül az egyik valódi kezdőszelete lenne a másiknak, továbbá ez a helyzet nem változik a nyitó zárójel elhagyásával sem, tehát (*) miatt vagy A, vagy A nem lehetne formula. De így rendre a és a binér logikai összekötőjelek, továbbá a B és a B formulák is azonosak.

  1. A továbbiakban azt kellene belátni, hogy egy – most már tetszőleges – formula valódi kezdőszelete

    • vagy csupa negációjelből álló betűsorozat – és ez nem formula –,

    • vagy több nyitó, mint záró zárójelet tartalmaz,

tehát egyetlen formulának sem lehet olyan valódi kezdőszelete, mely maga is formula. Innen már pontosan az előbbihez hasonló gondolatmenettel folytatható a bizonyítás.

Ezzel az egyértelmű elemzés tételét bizonyítottnak tekintjük.

Gyakran fogjuk használni a részformula és a közvetlen részformula fogalmát. Egy ítéletlogikai formula részformulája a formulában előforduló minden olyan összefüggő betűsorozat, mely maga is ítéletlogikai formula. A közvetlen részformula fogalmának korrekt definíciója az egyértelmű elemzés tételén alapszik.

4.1.6. DEFINÍCIÓ. 0 -ban

  1. egyetlen prímformulának sincs közvetlen részformulája,

  2. a ¬A egyetlen közvetlen részformulája az A formula,

  3. az (AB) formula közvetlen részformulái az A és a B formulák. A az (AB) formula bal oldali, B a jobb oldali közvetlen részformulája.

4.1.7. DEFINÍCIÓ. Legyen A0. Az A formula részformuláinak halmaza a legszűkebb olyan halmaz, melynek

  1. eleme A, és

  2. ha a C formula eleme, akkor C közvetlen részformulái is elemei.

Egyszerű most is belátni, hogy a definícióban megadott tulajdonságokkal rendelkező formulahalmaz egyértelmű. Nyilván 0-nak eleme minden a definícióban megkívánt formula is, tehát van ilyen tulajdonságú formulahalmaz, továbbá az 1–2. tulajdonságú formulahalmazok metszete is 1–2. tulajdonságú. A legszűkebb ezek közül pedig az összes ilyen tulajdonságú halmaz metszete. Szerkezeti indukcióval az is könnyen belátható, hogy minden formulának véges sok részformulája van.

4.1.8. PÉLDA. A (¬(Z¬X)Y) formula bal oldali közvetlen részformulája ¬(Z¬X), jobb oldali közvetlen részformulája Y, részformuláinak halmaza pedig

{ ( ¬ ( Z ¬ X ) Y ) , ¬ ( Z ¬ X ) , ( Z ¬ X ) , Z , ¬ X , X , Y } .

Gyakran hasznos fával szemléltetni egy formula szerkezetét.

4.1.9. DEFINÍCIÓ. Egy C formula szerkezeti fája egy olyan véges rendezett fa, melynek csúcsai formulák,

  1. gyökere C,

  2. a ¬A csúcsának pontosan egy gyermeke van, az A formula,

  3. az (AB) csúcsának pontosan két gyermeke van, rendre az A és a B formulák,

  4. levelei prímformulák.

4.1.10. PÉLDA.

Figure 4.1. Ítéletlogikai formula szerkezetének fája

Ítéletlogikai formula szerkezetének fája

Most megmutatjuk, hogy a formulákhoz – azok szerkezete szerinti rekurzióval – egyértelműen rendelhetünk különböző dolgokat.

4.1.11. TÉTEL. (A SZERKEZETI REKURZIÓ ELVE.)

Pontosan egy olyan 0-on értelmezett függvény van, melynek

(alaplépés:) értékeit rögzítjük 0 prímformuláin és megmondjuk, hogy

(indukciós lépések:)

(r1) ¬A-n felvett értéke az A-n felvett értékéből, illetve

(r2) (AB)-n felvett értéke (ahol binér logikai összekötőjel) az A-n és a B-n felvett értékekből hogyan származtatható.

BIZONYÍTÁS. Tegyük fel, hogy és olyan függvények, melyek 0 prímformuláihoz azonos értékeket rendelnek, és azonosan határozzák meg, hogy a ¬A-n felvett értéküket az A-n felvett értékekből, és az (AB)-n felvett értéküket az A-n és B-n felvett értékeikből hogyan kell származtatni. Nevezzük a bizonyítás során jónak 0 egy A formuláját, ha (A)=(A). A szerkezeti indukció elve segítségével igazolni fogjuk, hogy minden 0-beli formula jó. Mutassuk meg tehát, hogy a szerkezeti indukció alaplépésében és indukciós lépéseiben megfogalmazott feltételek teljesülnek:

(alaplépés:) és a prímformulákhoz azonos értékeket rendelnek, tehát 0 minden prímformulája jó.

(indukciós lépések:) Ha feltesszük, hogy egy A0 jó, azaz (A)=(A), akkor mivel ¬A-n az értéküket és függvények az A-n felvett értékből egyformán határozzák meg, (¬A)=(¬A) is teljesül, azaz ¬A is jó. Az (i1) indukciós feltétel teljesül. Hasonlóan ehhez ha feltesszük azt, hogy A,B0 jók, azaz (A)=(A) és (B)=(B), akkor mivel AB-n az értéküket a függvények az A-n és a B-n felvett értékekből szintén egyformán határozzák meg, így (AB)=(AB) teljesül, azaz (AB) is jó. Az (i2) indukciós feltétel is teljesül.

Az alaplépésben és az indukciós lépésekben megfogalmazott feltételek teljesülnek, tehát a szerkezeti indukció elve szerint minden 0-beli formula jó, a tételt bebizonyítottuk. Tehát egy, a formulákon értelmezett függvényt egyértelműen definiálunk, ha definiáljuk a prímformulákon, és rekurzióval megadjuk, hogy kell kiszámítani értékét egy összetett formulán, ha ismerjük az értékeit a közvetlen részformulákon.

Egy formulában a számunkra igazán fontos betűk a logikai összekötőjelek. Ezek számát a formula logikai összetettségének nevezzük. A szerkezeti rekurzió elvének a felhasználásával is definiálhatjuk a logikai összetettséget. Ehhez az alaplépésben megadjuk az összetettséget a prímformulákon, majd az indukciós lépések során meghatározzuk, hogyan kell kiszámolni egy formula összetettségét akkor, ha ismerjük a közvetlen részformuláinak az összetettségét. A szerkezeti rekurzió elve szerint ekkor minden formulára egyértelműen meghatároztuk a logikai összetettséget.

4.1.12. DEFINÍCIÓ. Definiáljuk a :0N0 függvényt a következőképpen:

  1. ha A prímformula, (A) legyen 0,

  2. ( ¬ A ) legyen (A)+1,

  3. ( A B ) pedig legyen (A)+(B)+1.

Ekkor egy A0 formulához rendelt (A) függvényértéket a formula logikai összetettségének nevezzük.

4.1.13. PÉLDA. Az X és a Z prímformulák logikai összetettsége egyaránt 0, tehát ¬X összetettsége 1, (Z¬X) összetettsége pedig 2.

Gyakran érdekes számunkra, hogy egy formulában előfordul-e egy ítéletváltozó. Ezt a fogalmat is rekurzióval definiálhatjuk, ugyanis elképzelhetünk egy olyan 0{van,nincs} függvényt, ami ha az A-hoz a van elemet rendeli, az azt jelenti, hogy az X ítéletváltozó előfordul az A formulában, ha a nincs elemet, akkor pedig az X ítéletváltozó nem fordul elő az A formulában. Mivel egy ilyen függvényt rekurzióval egyértelműen definiálhatunk, magát a fogalmat is közvetlenül – a fenti függvény explicit megadása nélkül – egyértelműen definiálhatjuk rekurzióval.

4.1.14. DEFINÍCIÓ. Azt mondjuk, hogy az X ítéletváltozó

  1. a prímformulák közül egyedül az X-ben fordul elő,

  2. a ¬A formulában pontosan akkor fordul elő, ha előfordul A-ban,

  3. ( A B ) -ben pedig akkor fordul elő, ha előfordul vagy A-ban, vagy B-ben.

Ha fel akarjuk tüntetni, hogy egy A formulában éppen az X1,X2,,Xn ítéletváltozók fordulnak elő, akkor A helyett A[X1,X2,,Xn]-et írunk, és A-ra n-(ítélet)változós formulaként hivatkozunk. Legyenek most B1,B2,,Bn tetszőleges formulák, és írjuk be egyidejűleg A-ban Xi minden előfordulása helyére a Bi formulát (i=1,2,,n). Világos, hogy ezzel az eljárással, amit formulahelyettesítésnek nevezünk, ismét formulát kapunk, amit jelöljünk A(X1,X2,,XnB1,B2,,Bn)-nel.

4.1.15. DEFINÍCIÓ. Egy formulában az X1,X2,,Xn ítéletváltozókat rendre a B1,B2,,Bn formulákkal helyettesítve a következő formulát kapjuk:

  1. Minden 1in-re Xi(X1,X2,,XnB1,B2,,Bn) épp Bi. Ha viszont X{X1,X2,,Xn} ugyan, de X prímformula, akkor az X(X1,X2,,XnB1,B2,,Bn) változatlanul X.

  2. A ¬A(X1,X2,,XnB1,B2,,Bn) formula definíció szerint legyen ¬(A(X1,X2,,XnB1,B2,,Bn)).

  3. Az (AB)(X1,X2,,XnB1,B2,,Bn) formula pedig legyen az (A(X1,X2,,XnB1,B2,,Bn)B(X1,X2,,XnB1,B2,,Bn))formula ( tetszőleges binér összekötőjel).

4.1.16. PÉLDA. Az ((XY)¬X) formula kétváltozós, az X és az Y ítéletváltozók fordulnak elő benne. Ha a formulában elvégezzük az (X,Z(XZ),¬X) formulahelyettesítést, az (((XZ)Y)¬(XZ)) formulát nyerjük.

Egy formula áttekinthetőbbé válhatna, ha megteremtenénk a lehetőséget arra, hogy kevesebb zárójel felhasználásával adjuk meg. Vezessünk be először is a logikai összekötőjelek között egy erősorrendet, úgynevezett prioritást, ami csökkenő sorrendben:

¬ , , , .

Definiáljuk továbbá a formulákban egy logikai összekötőjel hatáskörét és a fő logikai összekötőjel fogalmát.

4.1.17. DEFINÍCIÓ. Egy formulában egy logikai összekötőjel hatásköre a formulának azon részformulái közül a legkisebb logikai összetettségű, amelyekben az adott logikai összekötőjel is előfordul.

4.1.18. DEFINÍCIÓ. Egy formula fő logikai összekötőjele az az összekötőjel, melynek hatásköre maga a formula.

A definíciók alapján egyértelmű, hogy egy teljesen zárójelezett formulában mi egy logikai összekötőjel hatásköre és mi a fő logikai összekötőjel. Most megmutatjuk, hogy egy formulából milyen esetekben és mely részformulákat határoló zárójelpárok hagyhatók el úgy, hogy a logikai összekötőjelek hatásköre ne változzon. Vegyük észre, hogy a részformulák közül a prímformuláknak és negációs formuláknak nincs külső zárójelpárja, tehát csak az (AB) alakú részformulákról kell eldöntenünk, hogy írható-e helyette AB. A külső zárójelpárok elhagyhatóságáról egyesével, a következő sorrendben döntünk. A zárójelek elhagyását mindig a formula külső zárójelpárjának – ha van egyáltalán ilyen – az elhagyásával kezdjük. Majd ha a formulánk egy részformulájában már megvizsgáltuk a külső zárójelelhagyás kérdését, utána ezen részformula közvetlen részformulájának (részformuláinak) külső zárójeleivel foglalkozunk. Két eset lehetséges:

  1. A részformula egy negációs formula, amelyben az (AB) alakú közvetlen részformula külső zárójelei nem hagyhatók el.

  2. A részformula egy (AB), vagy AB alakú formula, melynek A és B közvetlen részformuláiban kell dönteni a külső zárójelek sorsáról. Ha az A formula (A1A2) alakú, A külső zárójelpárja akkor hagyható el, ha nagyobb prioritású, mint . Ha a B közvetlen részformula (B1B2) alakú, B külső zárójelpárja akkor hagyható el, ha nagyobb vagy egyenlő prioritású, mint .

4.1.19. PÉLDA. Az ((XY)Z), illetve az ((XY)Z) formulákban, csak a külső zárójelpár hagyható el, ugyanakkor az ((XY)Z) és az (X(YZ)) formulákban mindkét zárójelpár elhagyható, tehát egyszerűen írhatjuk, hogy XYZ és XYZ.

Egy olyan formulába, melyből elhagytunk bizonyos zárójelpárokat, ezek mindig egyértelműen vissza is írhatók. A zárójelek visszaírásának eredményeképp újból megkapjuk a teljesen zárójelezett formulát. Ehhez meg kell keresni a formula részformuláit és bennük a fő logikai összekötőjeleket. Először számoljuk meg rendre, hogy a formula egy-egy logikai összekötőjele hány zárójelpár belsejébe esik. Ezt a számot a logikai összekötőjel formulabeli szintszámának nevezzük. Egy részformula fő logikai összekötőjele a benne legkisebb prioritású minimális szintű összekötőjel, ha ilyen több is van, akkor ezek közül balról az első. Eltekintve attól az esettől, hogy a vizsgált részformula prímformula, két eset lehetséges:

  1. Ha a negációjel a részformula fő összekötőjele, közvetlen részformulája a negációjelet követő jelsorozat. Itt nem kell zárójel-visszaírással foglalkozni.

  2. Ha egy binér összekötőjel a részformula fő összekötőjele és külső zárójelei hiányoznak, akkor visszaírjuk azokat. A nyitó zárójel és a fő összekötőjel között található a részformula bal oldali, a fő összekötőjel és a záró zárójel között pedig a jobb oldali közvetlen részformulája, esetleg külső zárójelek nélkül.

Először mindig a formula fő logikai összekötőjelét keressük meg. Utána a fő logikai összekötőjel hatáskörébe eső közvetlen részformulákat dolgozzuk fel. Egy ily módon nyert részformula feldolgozása során hasonlóan járunk el újabb részformulákat vizsgálva. Ezt az eljárást addig folytatjuk, amíg a közvetlen részformulák prímformulák nem lesznek.

4.1.20. PÉLDA. Az XZYZ formula fő logikai összekötőjele az implikációjel, közvetlen részformulái XZ és YZ. A teljesen zárójelezett formula ((XZ)(YZ)).

Bizonyos formulákból gyakran még további zárójeleket is elhagynak, feladva a zárójelek eredeti helyre történő visszaírhatóságának a lehetőségét. Később a szemantika tárgyalása során látni fogjuk, hogy – bár a visszaírás során máshova kerülhetnek ilyenkor bizonyos zárójelek – az eredeti formula és a zárójelek elhagyása, majd visszaírása során nyert formula szoros kapcsolatban vannak egymással, ugyanazt jelentik. Az újabb zárójeleket a következő, a 3. eset során hagyhatjuk el.

  1. Egy (AB) vagy AB alakú formula valamely közvetlen részformulája szintén konjunkció, illetve egy (AB), vagy AB alakú formula valamely közvetlen részformulája szintén diszjunkció, az ilyen közvetlen részformulákból a külső zárójelpár elhagyható.

A zárójelek elhagyására vonatkozó megállapodásokat figyelembe véve úgynevezett konjunkciós, diszjunkciós, illetve implikációs formulaláncokat is nyerhetünk. Ezek alakja A1A2An1An, A1A2An1An, illetve A1A2An1An, amelyekben A1, A2, …, An1, An, (n2) tetszőleges ítéletlogikai formulák. Ezeknek a láncformuláknak a fő logikai összekötőjelét a következő zárójelezési megállapodással fogjuk meghatározni: (A1(A2(An1An))), (A1(A2(An1An))), illetve (A1(A2(An1An))).

Formalizálás az ítéletlogikában

Tegyük fel, hogy adott egy köznapi vagy egy matematikai probléma, amelyben csak individuumokra vonatkozó állítások (ítéletlogikai állítások) szerepelnek. Tekintsük át az ilyen problémák ítéletlogikai formulákkal való leírásának folyamatát. A problémát általában természetes nyelven leírt egyszerű vagy összetett kijelentő mondatokkal adják meg. Minden állítást kifejező egyszerű mondat helyett bevezetünk egy-egy állításjelet. Egy összetett mondatot, amennyiben nem mellérendelt egyszerű mondatok kapcsolata, analizálunk, és átalakítjuk az eredeti mondattal azonos értelmű, de egyszerű mondatokból olyan nyelvtani összekötőkkel felépített mondattá, ahol a nyelvtani összekötők egyben logikai összekötők is. Ezután az állításjeleket a logikai összekötőknek megfelelő jelekkel összekapcsolva kapjuk a problémát vagy megállapítást leíró összetett ítéletlogikai állítást. Ebben kicserélve az állításjeleket ítéletváltozókkal nyerjük az ítéletlogikai formulát. Nézzünk néhány példát az ítéletlogikában való formalizálásra.

4.1.21. PÉLDA.

  1. ,,Panni, Robi és Sanyi készülnek a vizsgára.” Ez a kijelentő mondat három állítás – x készül a vizsgára (ahol x lehet Panni, Robi és Sanyi valamelyike) – együttes bekövetkezését jelenti. Jelölje P,R,S rendre a következő egyszerű mondatokat ,,Panni készül a vizsgára”, ,,Robi készül a vizsgára”, ,,Sanyi készül a vizsgára”. A formalizált mondat PRS és a megfelelő ítéletlogikai formula: XYZ. Az eredmény egy konjunkciós formula(lánc).

  2. A formalizálandó állítás: ,,Tetszőleges háromszögben az oldalak hosszának egymásközti viszonya öröklődik a szemközti szögek nagyságának egymásközti viszonyára.” Legyen a és b a háromszög két oldala, α és β rendre a velük szemben fekvő szögek. Jelölje A azt, hogy ab, B, hogy a=b, C, hogy ab. A két oldal viszonyát ki tudjuk fejezni A-val, B-vel vagy C-vel. További jelölések: D jelölje, hogy αβ, E, hogy α=β, F, hogy αβ. Ekkor az oldalak és a szögek egymáshoz való viszonya (AD)(BE)(CF). A formalizált állításból az (X1Y1)(X2Y2)(X3Y3) ítéletlogikai formulát nyertük.

  3. Egy szinte ,,klasszikus” feladat [69]: ,,Betörtek egy áruházba. A nyomozás a következő adatokat állapította meg: Ha férfi a tettes, akkor kistermetű. Ha kistermetű, akkor az ablakon mászott be. Férfi a tettes, vagy legalábbis férfiruhát hordott. Ha férfiruhát hordott, akkor – feltéve, hogy hiteles a szemtanú vallomása – az ablakon mászott be. A helyszíni szemle kiderítette, hogy a tettes nem az ablakon mászott be. A nyomozók azt sejtik, hogy a tettes nem férfi.” Formalizáláshoz a jelölések: F – a tettes férfi, K – a tettes kistermetű, A – a tettes az ablakon mászott be, R – a tettes férfiruhát hordott, H – a szemtanú vallomása hiteles. A formalizált mondatok sorban: FK, KA, FR, RHA, ¬A, ¬F. A megfelelő ítéletlogikai formulák pedig: XY, YZ, XU, UVZ, ¬Z, ¬X.

  4. A programozási nyelvekben feltételes utasításoknak (kapcsolóknak) nevezzük az

IF f e l t é t e l THEN u t a s í t á s ( o k )

és az

IF f e l t é t e l THEN u t a s í t á s ( o k ) ELSE u t a s í t á s ( o k )

szerkezetű utasításokat. A program írásakor feltétel helyére egy F ítéletlogikai formula kerül, amelyben az ítéletváltozók igazságértéke az utasítás végrehajtásakor adott. Az utasítás(ok) helyére a programozó konkrét p,p1,p2 végrehajtandó programutasítás(oka)t ír (ezek tehát nem állítások). Vezessük be a

V ( x ) { i ha az x programutasítások végrehajtódnak , h egyébként

relációt. Ekkor a két feltételes utasítás értelmezése: „IF F THEN V(p)” és az „IF F THEN V(p1) ELSE V(p2)”. Formalizáljuk a két utasítás működését, azaz adjunk meg olyan formulákat, amelyek pontosan leírják az utasítások működését.

Az „IF F THEN V(p)” működését az

( F V ( p ) ) ( ¬ F ¬ V ( p ) )

formula és az ,,IF F THEN V(p1) ELSE V(p2)” működését az

( F V ( p 1 ) ¬ V ( p 2 ) ) ( ¬ F ¬ V ( p 1 ) V ( p 2 ) )

formula írja le.

Feladatok

4.1.1. FELADAT. Döntsük el, hogy a V0 ábécé feletti alábbi szavak ítéletlogikai formulák-e.

  1. ( ( X Y ) ¬ Z )

  2. ( X ( Y ) Z )

  3. ( ( Z X ) ¬ X )

4.1.2. FELADAT. Legyenek A,B,C ítéletlogikai formulák. Döntsük el, hogy az alábbi szavak szintén formulák-e.

  1. ( ( A B ) B )

  2. ¬ ( A ( B ¬ ¬ C ) )

  3. ¬ A B

4.1.3. FELADAT. Legyenek A,B,C formulák. Hányféleképpen lehet zárójelekkel ellátni az alábbi jelsorozatokat úgy, hogy formulákat kapjunk?

  1. A ¬ B B C

  2. A B C ¬ A ¬ B

4.1.4. FELADAT. Soroljuk fel a formulák közvetlen részformuláit és adjuk meg a részformuláik halmazát, majd állapítsuk meg a formulák logikai összetettségét.

  1. ( ( ( X Y ) ( Y Z ) ) ( ¬ X Z ) )

  2. ( ( X Y ) ( ( X ¬ Y ) ¬ Y ) )

4.1.5. FELADAT. Szemléltessük a formulákat szerkezeti fával.

  1. ( ( X ¬ Y ) ¬ ( X ( Z Y ) ) )

  2. ¬ ( ( X Y ) ¬ ( ¬ X Z ) )

4.1.6. FELADAT. Legyen az A formula logikai összetettsége n. Hány részformulája lehet maximum A-nak?

4.1.7. FELADAT. Írjuk fel az összes egyváltozós 2 logikai összetettségű implikációs ítéletlogikai formulát. Az ítéletváltozó legyen X.

4.1.8. FELADAT. Hagyjuk el a lehető legtöbb zárójelpárt a formulákból.

  1. ( ( ( X Y ) ( Y Z ) ) ( X Z ) )

  2. ( ( X Y ) ( X ( Y Z ) ) )

4.1.9. FELADAT. Írjuk vissza az elhagyott zárójeleket a formulákba.

  1. X Y Z ¬ X

  2. X Y Z Y

4.1.10. FELADAT. Formalizáljuk az ítéletlogika nyelvén a következő mondatokat.

  1. Arnold és Bálint vagy egyidősek, vagy Arnold idősebb Bálintnál. Ha Arnold és Bálint egyidősek, akkor Bálint nem lehet Csabával egyidős. Ha Arnold idősebb Bálintnál, akkor Bálint idősebb Dénesnél.

  2. Ha a szemtanú megbízható, és az írásszakértő véleménye helytálló, úgy a bűncselekményt akkor és csak akkor követték el előre megfontolt szándékkal, ha a talált ujjlenyomatok a tettestől vagy esetleges bűntársától származnak.