LOGIKA. Magyarok: Bereczki Ilona, Kalmár László, Neumann, Péter Rózsa, Pásztorné Varga Katalin, Urbán János, Lovász László

PPKE

Diszkrét matematika LOGIKA

M ATEMATIKAI L O GIKA A gondolkodás tudománya Diszkrét matematika Arisztotelész(i.e. 384-311) Boole, De Morgan, Gödel, Cantor, Church, Herbrand, Hilbert, Kleene, Lukesiewicz, Löwenheim, Ackermann, McKinsey, Tarski, Ramsey, Russel, Robinson, Skolem, Turing, Zermelo, Post, , Quine Magyarok: Bereczki Ilona, Kalmár László, Neumann, Péter Rózsa, Pásztorné Varga Katalin, Urbán János, Lovász László Mesterséges Intelligencia (MI) és matematikai logika: MI matematikai alátámasztása Tudás manipuláció: • Állítások • Újabb állítások • Bizonyítások Következtetések Problémák: Emberi következtetés – nem a logika szabályai szerint történik Túl „szigorú” ⇒ rugalmatlan

A logika egyik feladata: helyes következtetési sémák kialakítása Logikai alapok

Automatikus tételbizonyítás

Programozási nyelvek

PROLOG

MPROLOG (moduláris Prolog): Szeredi Péter, Futó Iván

© Bércesné Novák Ágnes

1

PPKE


Nulladrendű logika (ítéletkalkulus) Formalizált nyelv: szintaxis és szematika Szintaxis: • •

Jelkészlet Formulaképzés szabályai

•

A helyes szintaxisú formulák jelentése

Szemantika:

Szintaxis Jelkészlet: 1. Betűk 2. ¬, ∧, ∨, →

Atomok

3. I, H 4. Zárójelek

Formula: Minden atom formula Ha α, β formula akkor ¬α, α∧β, α∨β, α→β is formulák a fenti két szabály véges sokszori alkalmazásával kapjuk a formulákat A magyar betűkkel az atomi formulákat, a görög betűkkel az összetett formulákat jelöljük.


2

PPKE


Szemantika A jelkészlet elemeit értelmezzük. A betűk az ún. ítéletváltozók. Nevüket az indokolja, hogy a köznapi nyelv kijelentő mondatainak, kijelentéseinek felelnek meg. A klasszikus logikában csak olyan kijelentésekre gondolunk, amelyek igaz vagy hamis volta egyértelműen eldönthető. Ezáltal egyfajta ítéletet képviselnek e mondatok. Változók pedig azért, mert az eredeti kijelentés tartalmától függetlenül, csakis annak igazságértékeit vehetik fel: az igaz, vagy a hamis értékek valamelyikét. Az igazságértékek tehát az ítéletváltozók lehetséges értékei, jelöljük ezek a halmazát I-vel. I csak a klasszikus logikában kételemű halmaz. Azt a függvényt, amely a betűkkel jelölt változókhoz hozzárendeli a lehetséges igazságértékek valamelyikét, interpretációnak hívjuk. (Az interpretációk az igazságtábla atomokat tartalmazó oszlopaiban találhatók, ezen oszlopok minden egyes sora egy interpretáció.) Praktikus, ha az I és H betűt kiemeljük a betűk közül, és rögzítjük igazságértéküket - ezáltal e betűk nem ítéletváltozók, hanem ítéletkonstansok lesznek. Az I betű igazságértéke minden interpretációban legyen igaz, a H betű igazságértéke minden interpretációban legyen hamis. A többi ítéletváltozó esetében az igazságérték az interpretációtól függ. A zárójelek értelmezése és használata a matematikában szokásos módon történik: lényegében a műveletek kiértékelési sorrendjét tudjuk általuk neghatározni. A ∧ , ∨ , → jelek az igazságértékeken értelmezett műveleteknek felelnek meg. E műveletek közül csak az egy-, és kétváltozós műveletek közül néhánynak van gyakorlati jelentősége. A műveletek definícióját szokás kiértékelésnek, kiértékelési szabálynak is nevezni. A kiértékelés az igazságtábla eredménynek megfelelő oszlopában van.

Egyváltozós művelet Negáció (tagadás): Igazságtáblázat: Ítéletváltozó A Igaz Hamis

Ítéletváltozó tagadása ¬A Hamis Igaz

A 4 egyváltozós művelet közül csak a negáció lényeges, a többi a gyakorlatban alig fordul elő.


3

PPKE


Kétváltozós műveletek Általában infix jelölést használunk.

Konjunkció A∧B: informális jelentése: és. Példa: Esik az eső és süt a nap. Ezt a mondatot az A∧B sémával lehet jellemezni. Mikor gondoljuk igaznak ezt a két kijelentés összetételével kapott mondatot? A konjunkció akkor és csak akkor igaz, ha mindkét változó igazságértéke igaz. Igazságtáblázat: Művelet A∧B I H H H

kiértékelések

interpretációk

Ítéletváltozók A B I I I H H I H H

Diszjunkció A∨B: informális jelentése: vagy . Példa: Esik az eső vagy süt a nap. Ezt a mondatot az A∨B sémával lehet jellemezni. Mikor gondoljuk igaznak ezt a két kijelentés összetételével kapott mondatot? A diszjunkció akkor és csak akkor hamis, ha mindkét változó igazságértéke hamis. Igazságtáblázat: Ítéletváltozók B I H I H

Művelet A∨B I I I H

kiértékelések

interpretációk

A I I H H

Implikáció A→B : informális jelentése: ha A, akkor B. Példa: Ha az iskolai tanulmányai alatt a tanuló/hallgató minden félévben lagalább jeles átlageredményt ért el, akkor az állam egy aranygyűrűt ad ajándékba a diploma kiosztásakor. (Valójában ehhez még az is feltétel, hogy ne legyen hármasnál rosszabb jegye). Ezt a mondatot az A→B sémával lehet jellemezni. Mikor gondoljuk igaznak ezt a két kijelentés összetételével kapott mondatot? Az implikáció akkor és csak akkor hamis, ha az előtagja igaz, az utótagja hamis. Igazságtáblázat: Ítéletváltozók B I H I H

Művelet A→B I H I I

kiértékelések

interpretációk

A I I H H

Kérdés: Hány kétváltozós művelet van?


4

PPKE


Mitől függ az interpretációk száma? Példák kiértékelésre: 1. Adja meg az ((A∨B) ∧C) → (A∧¬B) formula kiértékelését minden interpretációban! A I I I I H H H H

B I I H H I I H H

C I H I H I H I H

((A

∨ I I I I I I H H

B)

∧ I H I H I H H H

→ H I I I H I I I

C)

(A

∧ H H I I H H H H

¬B) H H I I H H I I

2. Adja meg az (A →B) ∧ (A∧¬B) formula kiértékelését minden interpretációban! Megoldás: A I I H H

B I H I H

(A → B) ∧ (A ∧ I I I H I H I H H H I I H I I H H H H I H H H H

¬B) H I H I

3. Adja meg az (A →B) ∨ (A∧¬B) formula kiértékelését minden interpretációban! A I I H H

B A→B A∧¬B (A→B)∨(A∧¬B) I I H I H H I I I I H I H I H I

Def.: Tautológia (azonosan igaz formula, érvényes formula): Az a formula, amely minden interpretációban igaz (például a 3. formula). Def.: Kontradikció (ellentmondás, azonosan hamis, kielégíthetlen):Az a formula, amely minden interpretációban hamis (például a 2. formula). A kétértékű logikában érvényes az ún. harmadik (érték) kizárásának elve, amelyet például az alábbi formulákkal is megfogalmazhatunk: A∧¬A=H (kontradikció) – ez azt jelenti, hogy az A ítéletváltozó az igaz, hamis értékek közül pontosan egyet vehet fel (kétértékű logika). A v ¬A=I (tautológia) – ez informálisan azt jelenti, hogy az A ítéletváltozó az igaz, hamis értékek közül legalább az egyiket felveszi. Def.: Modell: modellnek nevezzük azt az interpretációt, amelyben a formula igaz.


5

PPKE


Kérdések: Mi a tautológia tagadása? Mi a kontradikció tagadása? Hány modellje van az 1., 2., 3 példákban szereplő formuláknak?

kielégíthető formulák van modellje Formula:

tautológia nincs modellje – kontradikció, ellentmondás

Def.: Ekvivalens két formula, α és β, ha minden interpretációban ugyanaz az igazságértékük. (A két formula közös igazságtáblájában a kiértékelésnek megfelelő oszlopok azonosak) Jelölés: α ≡β Példák fontos ekvivalens formulákra: 1. A konjunktív normálformára hozáshoz nélkülözhetetlen: α→β≡¬α∨β α β α→β ¬α∨β I I I I I H H H H I I I H H I I 2. De Morgan azonosság 1. ¬(A∨B)≡¬A∧¬B A B A∨B ¬A∧¬B I I H H I H H H H I I I H H I I 3. De Morgan azonosság 2. ¬(A∧B)≡¬A∨¬B A B ¬(A∧B) ¬A∨¬B I I H H I H I I H I I I H H I I


6

PPKE

Diszkrét matematika LOGIKA A konjunkció és diszjunkció tulajdonságai

1.a. A∨B≡B∨A 2.a. (A∨B)∨C≡A∨(B∨C) 3.a. A∨(A∧B)≡A 4.a. I∨A≡I 5.a. A∨(B∧C)≡(A∨B)∧(A∨C) 6.a. A∨¬A≡I

1.b. A∧B≡B∧A 2.b. (A∧B)∧C≡A∧(B∧C) 3.b. A∧(A∨B)≡A 4.b. H∧A≡H 5.b. A∧(B∨C)≡(A∧B)∨(A∧C) 6.b. A∧¬A≡H

Feladat: Igazolja igazságtáblázattal, hogy a fenti formulák valóban ekvivalensek!

Halmazelméletben is hasonló azonosságok igazak: 1.a. A∪B=B∪A 2. a. (A∪B)∪C=A∪(B∪C) 3. a. A∪(A∩B)=A 4. a. U ∪ A=U 5. a. A∪(B∩C)= (A∪B) ∩ (A∪C) 6. a. A∪ A = U

1.b. A∩B=B∩A 2.b. (A∩B)∩C=A∩(B∩C) 3.b. A∩(A∪B)=A 4.b. ∅∩A=∅ 5.b. A∩(B∪C)= (A∩B) ∪(A∩C) 6.b. A∩ A =∅

Az olyan struktúrákat, amelyekben két művelet van definiálva, és van két kitüntett elem, amelyekre a fenti azonosságok igazak, BOOLE ALGEBRÁnak nevezzük. További példa: a valószínűségszámításban Boole algebrát alkotnak az események.


7

PPKE


További kétváltozós művelet Ekvivalencia Az ekvivalencia szót a logikában egy kétváltozós műveletre is használjuk. Az ekvivalencia, mint művelet az implikációból és a konjunkcióból származtatható: Def.: α↔β:= (α→β)∧(β→α) Az ekvivalencia akkor és csak akkor igaz, ha α és β igazságértéke egyforma. Az ekvivalencia igazságtáblázata: α I I H H

β α→β β→α (α→β)∧(β→α) I I I I H H I H I I H H H I I I

Kérdés: Ha α és β ekvivalens formulák, mit tudunk mondani az α↔β formuláról? Megjegyzés: Noha az alapjelkészletben nem szerepelt a ↔ jel, ezt használhatjuk a definícióban megadott formula rövidítéseként. Lemma: Minden (eddig felírt) igazságtábla igaz úgy is, ha az atomok helyett formulákat írunk. Lemma: α és β akkor és csak akkor ekvivalens, ha α↔β tautológia. Biz.: a. α ekvivalens β ⇒ α↔β tautológia. Ha α és β igazságértéke megegyezik, akkor az ekvivalencia definíciója miatt csak igaz lehet⇒tautológia. b. ha α↔β tautológia → csak igaz lehet, de ez pontosan akkor van, ha α és β igazságértéke ugyanaz, vagyis α ekvivalens β. Tétel: Ha α tautológia, akkor az ítéletváltozók helyébe formulákat írva tautológiát kapunk. Tétel: Ha α tautológia, akkor bármely részformula helyett azzal ekvivalens formulát írva tautológiát kapunk. Tétel: Az ekvivalens nulladrendű formulák az összes formulák partícióját adják. ↔ ha α≡β

α≡α reflexív α≡β és β≡α szimmetrikus α≡β és β≡γ ⇒ α≡γ tranzitív


Ekvivalencia reláció

8

PPKE


A logikai következmény A logika egyik feladata: helyes következtetési sémák kialakítása. Példa következtetésekre régebbi jelölésekkel: Az első példát nem tudjuk nulladrendű formulákkal jól modellezni: Minden veréb madár. Minden madár gerinces. Minden veréb gerinces.

Feltétel1 Feltétel2 Következmény

Az alábbi példa nulladrendben is jól modellezhető: Ha elfogy a benzin, az autó leáll. Elfogyott a benzin. Az autó leáll.

Feltétel1 Feltétel2 Következmény

A= Elfogy a benzin, B=az autó leáll. A megfelelő séma: A A→B _____________ B Újabb jelöléssel: {A, A→B} =0 B

Latin szavakkal: 1. feltétel 2. feltétel. Következmény

1. Premissza 2. Premissza Konklúzió

Mikor helyes egy következtetési séma? Ahhoz, hogy e kérdésre válaszolni tudjunk, értelmeznünk kell a következmény fogalmát. Def.: Modellelméleti vagy szemantikus következményfogalom: Azt mondjuk, hogy az {α1, α2, …,αn} formulahalmaz következménye a β formula, ha minden olyan interpretációban, amelyben az α1 , α2, …αn formulák igazak, β is igaz. Más szavakkal: {α1, α2, …,αn} formulahalmaz következménye a β formula, ha β legalább akkor igaz, amikor az αi-k igazak.

Jelölés: {α1, α2, …,αn} =0 β Megjegyzés: Mivel az elsőrendű logika következményfogalma nem teljesen azonos a nulladrendűével, ezért az indexben szokás azt is jelölni, hogy melyik nyelvről van szó: =0 © Bércesné Novák Ágnes

9

PPKE


Az elsőrendű logikában a következményfogalom jele: =1 Ha β tautológia, akkor minden interpretációban igaz, tehát abban is, amelyekben az αi –k. Ezért a tautológia bármely formulahalmaz következménye. Ez indokolja a tautológia jelölését: =0 β. A következményfogalom definíciójának egyszerű következményei:) - αi-k közös modellje β-nak is modellje (fordítva az állítás nem igaz) - tautológia következménye csak tautológia lehet: tautológia =0 tautológia - a tautológia bármely α formula következménye: α=0 tautológia, - kontradikciónak bármi lehet a következménye ( spec. A is és az A tagadása is) : Kontradikció =0 α - kontradikció csak kontradikciónak lehet következménye (hiszen más formula esetén igaznak kellene lennie ott, ahol a formula igaz): kontradikció =0 kontradikció Most már válaszolni tudunk a fejezet elején feltett kérdésre, melyek a helyes következtetési sémák. Def.: Azokat a következtetési sémákat tekintjük helyesnek, amelyekben a következmény valóban a feltételek (szemantikai) következménye.

Példák helyes következtetési sémákra (szabályokra) 1.

Modus ponens (leválasztási szabály): {α, α→β }=0 β

Azt kell vizsgálnunk, ahol α és α→β igaz, ott a β igaz-e. Ha igen, akkor helyes, ha nem, akkor helytelen a következtetési séma. Csak az első interpretációban teljesül, hogy α és α→β igaz. Ebben a interpretációban β is igaz, tehát valóban {α, α→β }=0 β. Ítéletváltozók α I I H H

β I H I H A A→B A

α→β I H I I

MODUS PONENS

Feladat: Bizonyítsa be, hogy az alábbi következtetési sémák helyesek! - Modus tollens (elvető mód, kontrapozíció): {α→β, ¬β } =0 ¬α - Hipotetikus szillogizmus (feltételes szillogizmus, láncszabály): {α→β, β→γ} =0 γ - Modus tollendo ponens / diszjunktív szillogizmus (elvéve helyező mód): {α∨β, ¬β} =0 α - Indirekt: {¬α→¬β, β } =0 α


10

PPKE


Tétel: α1, α2, …,αn=0 β akkor és csak akkor, α1∧α2∧ …∧αn=0 β Biz.: α1, α2, …,αn együttesen akkor és csak akkor igaz, ha α1∧α2∧ …∧αn igaz. E tétel miatt a =0 jel bal oldalát a továbbiakban egyszerűen α-val jelöljük, ahol α-n mindig α=α1∧α2∧ …∧αn formulát értjük. Tétel: α=0 β akkor és csak akkor, ha α→β tautológia. Biz.: a.) ha α=0 β akkor α→β tautológia: a jelölt sor ez esetben nem lehet az igazságtáblában, ugyanis akkor α=0 β nem teljesülne, hiszen ekkor β-nak legalább akkor kell igaznak lennie, amikor α igaz. A maradék sorokra pedig valóban az I az igazságérték. α β α→β I I I I H H H I I H H I b.) ha α→β tautológia, akkor α=0β: Ha α→β tautológia, akkor a fenti igazságtáblában jelölt sor nem szerepelhet, hanem csak a jelöletlen, I sorok. Ezekben a sorokban viszont valóban a β legalább ott igaz, ahol az α. Példa: Modus ponens: {α, α→β }=0 β helyes: Ítéletváltozók α I I H H

β I H I H

Formulák α→β (α∧(α→β)) → β I I I H H I I H I I H I

Feladat: A fenti módszerrel bizonyítsa be, hogyaz alábbi következtetési szabályk helyesek! - Modus tollens: {α→β, ¬β } =0 ¬α - Hipotetikus szillogizmus: {α→β, β→γ} =0 γ - Modus tollendo ponens / diszjunktív szillogizmus (elvéve helyező mód) {α∨β, ¬β} = α - Indirekt: {¬α→¬β, β } =0 α Tétel: α=0β akkor és csak akkor, ha α∧¬β azonosan hamis. Biz: α=0β akkor és csak akkor, ha α→β tautológia, vagyis hamis): ¬(α→β)=¬(¬α∨β)≡¬¬α∧¬β≡α∧¬β


¬(α→β) kontradikció (azonosan

11

PPKE


Példa: Modus ponens {α, α→β }=0β helyes: Ítéletváltozók α I I H H

β I H I H

Formulák α→β (α∧(α→β)) ∧¬β I I H H H H I H H I H H

Feladat: A fenti módszerrel bizonyítsa be, hogyaz alábbi következtetési szabályok helyesek! - Modus tollens:

{α→β, ¬β } =0 ¬α

- Hipotetikus szillogizmus: {α→β, β→γ} =0 γ - Modus tollendo ponens / diszjunktív szillogizmus (elvéve helyező mód) {α∨β, ¬β} =0 α - Indirekt: {¬α→¬β, β } =0 α Tétel (rezolúció alapelvéhez): {α∨β, γ∨¬β} =0 α∨γ (diszjunktív szillogizmus általánosabban). Megjegyzés: Az α∨β és γ∨¬β formulák ún. klózok. E két klóz rezolvense α∨γ. Biz.: igazságtáblával, a következők alapján többféleképpen lehet: a.) def. alapján (házi feladat) b.) α=0 β akkor és csak akkor, ha α→β tautológia (házi feladat) c.) α=0 β akkor és csak akkor, ha α∧¬β azonosan hamis (előadáson) Alkalmazás: automatikus tételbizonyítás, rezolúció (PROLOG nyelv ) alapelve: A következményfogalom eldöntésére bizonyított tételekben az összes interpretációt meg kell vizsgálni. Ez exponenciális nagyságrendű feladat. Ezért volt forradalmi jelentőségű a rezolúció felfedezése (Robinson, 1965). Feladat: Hány interpretáció van, ha az ítéletváltozók száma n?

Def.: Konjunktív NormálForma, KNF: Ki klózok konjunkciója, klóz: literálok diszjunkciója, literál: atom, vagy annak tagadása.


12

PPKE


KNF: Klózok (diszjunkciók) konjunkciója K1∧K2∧…∧Kn Ki= A1∨A2∨…∨An Pozitív, ha A Literál Negatív, ha ¬A Tétel: Minden formulához létezik vele ekvivalens konjunktív normálforma. Biz.: 1. α→β≡¬α∨β 2. De Morgan ¬(α∧β)≡¬ α∨¬β ¬(α∨β)≡¬ α∧¬β 3. α∨(β∧γ)≡( α∨β)∧( α∨γ) α∧(β∨γ)≡( α∧β)∨( α∧γ) Def.: DNF (diszjunktív normálforma): konjunkciók diszjunkciója Megjegyzés: A KNF és DNF duális: ua. mindkettő, csak ∧ helyett ∨, ∨ helyett ∧. Következmény: (Funkcionálisan) teljes rendszerek Fentiekből szerint, minden formula kifejezhető a ∧, ∨, ¬ műveletekkel. Ezért azt mondjuk, hogy e három művelet teljes rendszert alkot. A De Morgan azonosságokból azonnal adódik, hogy ¬(α∨β)≡¬ α∧¬β, így ∧, ¬, és hasonlóképpen bizonyíthatóan a ∨, ¬ is funkcionálisan teljes halmaz. A ∧, ∨ műveletekkel viszont nem lehet a ¬-t kifejezni, így a konjunkció és diszjunkció együttesen NEM alkot teljes rendszert. Feladat: Bizonyítsa be, hogy a → és ¬ teljes rendszert alkot! (Melyik implikáció ekvivalens α∨β-val?) Példa: Hozza konjunktív normálformára az alábbi formulát! ¬[(A→B)→((C∨A)→(C∨B))]≡¬[(¬A∨B)→(¬(C∨A)∨(C∨B))]≡¬[¬(¬A∨B)∨(¬(C∨A)∨(C∨B))]≡ ≡¬[¬(¬A∨B)∨((¬C∧¬A)∨(C∨B))]≡¬[(A∧¬B)∨(¬C∧¬A)∨(C∨B)]≡ ≡¬(A∧¬B)∧¬(¬C∧¬A)∧¬(C∨B)]≡(¬A∨B)∧(C∨A)∧(¬C)∧¬B A klózok: K1=(¬A∨B) K2=(C∨A) K3=(¬C) K4=¬B


13

PPKE


Tétel volt: α =0 W akkor és csak akkor, ha α∧¬W kontradikció, vagyis α=α1∧α2∧ …∧αn miatt α1∧α2∧ …∧αn∧¬W kontradikció. Adott az {α1,α2, …,αn }formulahalmaz. E tétel alapján el szeretnénk dönteni, hogy {α1,α2, …,αn }=0 W?

A rezolúció alapelve informálisan: W-t is, és a feltételhalmaz formuláit is konjunktív normálformára hozzuk. Mikor igaz egy KNF? Ha minden benne szereplő klóz igaz. A klózokban viszont lehetnek negált és negálatlan, azonos atomok. Ezek együttesen nem lehetnek igazak az egész formulában, ezért ezeket a klózpárokból, amelyekben szerepelnek, elhagyjuk, és a „maradékból” egy klózt képezünk, ez a rezolvens. Az így kapott klózzal bővítjük a formulát. Ezen új formula modelljét (amely interpretációban igaz a formula) keressük. A fentiek alkalmazása: Adott az {α1,α2, …,αn }formulahalmaz. El szeretnénk dönteni, hogy {α1,α2, …,αn }=0 W? W-t is, és a feltételhalmaz formuláit is konjunktív normálformára hozzuk. Ekkor világos, hogy az α1∧α2∧ …∧αn∧¬W formula is KNF-ben van. Azt kell tehát megnézni, hogy van-e modellje. A fenti megjegyzés értelmében olyan klózokat keresünk, amelyekben azonos atom pozitív és negatív literálja szerepel. Ezekből a fent leírt módon konstruáljuk az új klózt, a rezolvenst. Az eljárás akkor ér véget, ha egy negált és egy negálatlan literál önmaga alkot egy-egy klózt. Ezek rezolvense az üres klóz, az azonosan hamis klóz (NIL-nek is nevezik). Jele:


14

PPKE


Példa: Adott {P1, P1→Q1, Q1→ Q2}=AB (adatbázis) Kérdés: Q2 következmény-e? Megoldás: {P1, P1→Q1, Q1→ Q2 } a feltételek halmaza, mindegyiket KNF-re kell hozni:

AB={ P1, ¬P1∨Q1, ¬Q1∨ Q2}

W= Q2 , tagadása: ¬ Q2 (tagadás ⇒ indirekt feltevés) Fentiek értelmében azt kell belátni, hogy az AB∪{¬ Q2 }formulahalmaz elemeinek nincsen modellje, nincsen olyan interpretáció, amelyben igaz lehetne. Informálisan: Ha például P1 igaz ⇒ ¬P1 nem lehet igaz a 2. klózban, ezért mivel minden klóznak igaznak kell lennie, a Q1 literálnak igaznak kell lennie ⇒¬Q1 ekkor hamis a 3. klózban, ami szerint tehát Q2 igaz, de ekkor már ellentmondásra jutottunk, hiszen Q2 és ¬ Q2 egyszerre nem lehet igaz. (Azért kellene nekik egyszerre igaznak lenni, mert különböző klózokban szerepelnek, és az egész formula igazságát az összes klóz igaz értéke garantálja. Igy azonban nagyon nehéz bizonyítani, hiszen minden lehetséges értékadásra végig kellene nézni. Ezt oldja meg a rezolúció. Rezolúciós levezetés: P1 Q1 ¬P1∨Q1 ¬Q1∨Q2 ¬Q2

Eredeti Klózhalmaz

P1 ¬P1∨Q1 ¬Q1∨ Q2 ¬Q2 Q1

=0

Q2

P1 ¬P1∨Q1 ¬Q1∨Q ¬Q2 Q1 Q2

Rezolvenssel bővített klózhalmaz

- Üres klóz, ellentett literálpárból jön létre Rezolvense ⇒ kielégíthetetlen P1 ¬P1∨Q1 ¬Q1∨Q ¬Q2 Q1 Q2

Ennek a klózhalmaznak nincsen modellje a miatt.


15

PPKE


Példa: Igazoljuk, hogy az alábbi ϕ formula tautológia! ϕ=[(A→B)→[(C∨A)→(C∨B)]] Megoldás: ϕ akkor és csak akkor tautológia, ha ¬ϕ kielégíthetetlen⇒ ¬ϕ-t KNF-re írjuk át. ¬ϕ=¬[(A→B)→[(C∨A)→(C∨B)]]≡…≡(¬A∨B)∧(C∨A)∧(¬C)∧(¬B) ¬A∨B C∨A ¬C ¬B

A

B Tehát az eredeti formula tautológia (hiszen tagadása kielégíthetetlen)

Példa: Részlet egy nyomozás jegyzőkönyvéből (Pásztorné Varga Katalin: Matematikai logika és alkalmazásai, ELTE, 1991.) : 1. Ha férfi a tettes (F), akkor kistermetű(KT). (F→KT≡¬F∨KT) 2. Ha kistermetű a tettes(KT), akkor az ablakon keresztül mászott be(AM). (KT→AM≡¬KT∨AM) 3. A tettes férfi(F), vagy férfiruhát hordott(FR). (F∨FR) 4. Ha a tettes férfiruhát hordott(FR) – és a szemtanú hiteles(H) – akkor az ablakon keresztül mászott be.(AM) (H∧FR→AM≡¬(H∧FR)∨AM≡¬H∨¬FR∨AM) 5. Helyszíni szemle: a tettes nem az ablakon mászott be. (¬AM). Kérdés: férfi , F, vagy nő, ¬F, a tettes? Adott {¬F∨KT, ¬KT∨AM, F∨FR, ¬H∨¬FR∨AM, ¬AM} klózhalmaz. 1. Tegyük fel, hogy nő a tettes: ¬F. A klózhalmazhoz hozzávesszük ¬F tagadását: F 2. Rezolúcióval eldöntjük a klózhalmaz kielégíthetetlenségét. ¬F∨KT ¬KT∨AM F∨FR H∨¬FR∨AM ¬AM F

¬F ¬KT

→ tautológia ⇒ ¬F (tehát nem férfi a tettes)


16

LOGIKA. Magyarok: Bereczki Ilona, Kalmár László, Neumann, Péter Rózsa, Pásztorné Varga Katalin, Urbán János, Lovász László

Recommend Documents