Logika szeminárium – 4,5 Molnár Attila 2008. október 9. A vastag betű új fogalmat, a dőlt betű pedig hangsúlyt jelez.
1. Analitikus fák 1.1. Bevezető példa Ez történt velem a reggel: 1. Kakaót ittam vagy nem ettem zabpelyhet. 2. Zabpelyhet ettem vagy nem ettem joghurtot. 3. Nem ettem zabpelyhet vagy nem ettem kakaót. Ettem-e vagy ittam-e valamit a reggel? Ha valamiért nem triviális ez a nagyon egyszerű mondathalmaz, az azért van, mert ezek ’vagy’-gyal összekapcsolt (diszjunktív) állítások; próbáljuk akkor szétválasztani az eseteket, amik megtörténhettek! Először persze formalizálunk: (1) p ∨ ∼ q (2) q ∨ ∼ r (3) ∼ q ∨ ∼ p Nos, abból a formulából, hogy ’p ∨ ∼ q’, leszűrhetjük azt a tanulságot, hogy p történt meg, vagy ∼ q történt meg.1 Szabatosan fogalmazva: p igaz, vagy ∼ q igaz, azaz q hamis. Ezt a következőképp fogjuk jelölni: (1) p ∨ ∼ q p
∼q
Igazság szerint jobb lenne, ha nem mászna rá az ’(1)’ jel a formulára, de egyelőre LATEX-hel ennyit bírok egyelőre megoldani. A lényeg, hogy az (1) jelölje azt, hogy most abban a sorban azt a mondatot honnan is vettük. Mindjárt felsejlik, miért lesz erre szükség.
A két eseten továbbmenve ábrázolhatjuk a (2)-es és (3)-as eseteket is. Csak azért se menjünk sorrendben; vegyük előbb a (3)-ast: (1) p ∨ ∼ q p ∼q (3) ∼ q ∨ ∼ p ∼ q ∨ ∼ p Ezt megintcsak mindkét ágon szét tudjuk választani: (1) p ∨ ∼ q p (3) ∼ q ∨ ∼ p ∼q
∼p
∼q ∼ q∨ ∼ p ∼q
∼p
1 Ezt a „vagy”-ot nehogy kizáró értelemben vegyük! mindkét szétválasztott esetben még előfordulhat az, hogy a másik eset még fennáll – pusztán csak amellett köteleztük el magunkat, hogy legalább az egyik eset fennáll.
1
Itt most álljunk meg egy kicsit! A baloldalon azt találhatjuk, hogy az esetek részletezésben felsoroltunk egy ellentmondást is! Láthatjuk, hogy miközben p esetén indultunk el a bal oldalon, továbbmenve előfordult ∼ p esete is. Ez bizony ellentmondás, és arra mutat rá, hogy ez az eset valójában nem is eset: ide rakunk egy ’?’-ot, és azt mondjuk, hogy ez az ág lezárult. Tehát a ’?’-gal így nézünk most ki: (1) p ∨ ∼ q p(3) ∼ q ∨ ∼ p ∼q
∼q ∼ q∨ ∼ p
∼p ∼q ∼p ? Ezt a módszert továbbfolytatva a következő analitikus fát kapjuk (Oda, ahova nem kerül ’?’, ’◦’-t teszünk: (1) p ∨ ∼ q ∼q ∼ q∨ ∼ p
p (3) ∼ q ∨ ∼ p ∼q (2) q ∨ ∼ r
∼p ?
∼q q∨ ∼ r
∼p q∨ ∼ r
q ∼r q ∼r q ∼r ? ◦ ? ◦ ? ◦ Nos, ez szép, de mi derül ki ebből? Az derül ki, hogy ott, ahol ’◦’-t találunk, olyan eseteket találunk, amik lehetségesek; Ha balról jobbra nézzük, és a különféle ágakon szigorúan felfelé megmásszuk az analitikus fánk ágait, felsorolhatjuk, milyen atomi mondatok nem mondanak egymásnak ellent, ha igazak. Tegyük is meg ezt: • ∼ r, ∼ q, p • ∼ r, ∼ q • ∼ r, ∼ p, ∼ q Élesebb szeműek észrevehetik, hogy e három mondat együttese arról árulkodik, hogy a p igazsága vagy hamissága teljesen irreleváns annak szempontjából, hogy van-e ellentmondás a kijelentések közt. Milyen kapcsolatban is állnak ezek egymással? Például a ∼ r, ∼ p, ∼ q itt az utolsó sorban? Ez bizony konjunkció! Lám, vegyük akkor észre, ha ágakon szigorúan felfele haladunk, akkor konjunktív kapcsolatokat találunk. Ha diszjunktív kapcsolattal találkozunk, akkor pedig szétágaztatunk. Ebből egy triviális harmadik hozzátételével mindjárt adódnak is ún. származtatási szabályok.
1.2. Származtatási szabályok ∼∼ A A
A∨B A
A&B
B
A B Ennek pedig örülünk, mert már láttuk, hogy a ”∼, & , ∨ ” igazságfüggvényekre vissza lehet már vezetni a többit. A biztonság kedvéért nézzük azonban még is meg, hogyan is állunk az összes lehetséges származtatási szabállyal. Javallott mindegyiket egyszer az életben alaposan átgondolni – és ez jó, ha még a házifeladatok leadása előtt megtörténik. Standard hibák forrása pl. a De Morgan-szabályok okozta felbontások elnézése. Még a legjobbaknál is. A fentiek tagadása a De Morganból így jön ki: ∼ (A ∨ B) ∼ (A & B) ∼A ∼B ∼A ∼B A kondicionális és tagadása szintén különböznek az elágazás tekintetében. Pont mint az előbb. 2
A ⊃ B ∼A
∼ (A ⊃ B)
B
A ∼B A bikondicionális és tagadása, a ’kizáró-vagy’ közti kapcsolat most talán még szebben látszik: ∼ (A ≡ B) A ≡ B A ∼A ∼A A B ∼B B ∼B Nos, egy mondathalmaz analitikus fáját a következőképpen fogjuk megadni: Fölírjuk a mondatokat egymás alá – lévén őket konjunkció köti össze. Pont, mint a származtatási szabálynál. Majd ezek után elkezdjük mindegyiket szétszedni úgy, hogy ami következik, azt minden nyitott ág végére (nyitott, ami nem lezárt) beillesztjük, és ott bontjuk tovább. Itt látszik, miért érdemes folyton keresni az ellentmondásokat, a lezárt ágakat; így nem dolgozunk feleslegesen. A kezdeti példa tehát így felírva: (1) p ∨ ∼ q (2) q ∨ ∼ r (3) ∼ q ∨ ∼ p (1) p ∨ ∼ q ∼q ∼ q∨ ∼ p
p (3) ∼ q ∨ ∼ p ∼q (2) q ∨ ∼ r q ?
∼p ?
∼r ◦
∼q q∨ ∼ r q ?
∼r ◦
∼p q∨ ∼ r q ?
∼r ◦
1.3. Kisebb nagyobb megjegyzések • Láttuk, hogy ha csak fölfele sétálunk a formulákon, akkor ’és’-sel kell összekapcsolnunk a mondatokat. Akkor is, ha csak egymás fölött van két formula, és akkor is, ha egy vonallal vannak összekötve. A szisztéma, amit a rajzok követnek, a következő: Ha valamit származtatási szabállyal bontottunk szét, akkor oda vonalat húzunk (akkor is, ha csak egy vonalat kell behúznunk), ha pedig egy ideiglenesen félretett fentebb előfordult formulát hozunk újra le, hogy szétbontsuk, akkor (mivel nem használtunk származtatási szabályt) nem húzunk vonalat. Ennek én sem tudok néha megfelelni, mert ennek a szedése elég komplikált, de azért igyekszem. Szóljatok, ha hibát találnátok! • Elképzelhető, hogy ha máshol olvastok erről a témáról, analitikus táblázatokat találtok. Az ugyanez. Azt hiszem, ez átláthatóbb, de mindenesetre könnyebben taníthatóbb, ugyanakkor nekem is tartott egy ideig, míg megszereztem azt a TEX csomagot, amivel ilyen fákat lehet rajzolni. A szedés miatt tehát általában analitikus táblázat néven találkozhattok ilyesmivel. Bár ne ijedjetek meg, ha a standard könyvekben néztek utána: ott ezen táblázatok már nem nulladrendben, hanem elsőrendben működnek. Akit érdekel tehát, hogy mit tudnak még ezek az analitikus fák/táblázatok, annak javaslom Ruzsa Imre: Bevezetés a modern logikába című könyvét. Ezzel úgyis fogtok még találkozni egypárszor.
1.4. Néhány kis feladat 1) Az eredeti mondathalmazhoz milyen állítást hozzátéve juthatunk egyből ellentmondásos mondathalmazhoz? 2) Elentmondásos mondathalmazhoz jutunk-e, ha az eredeti mondathalmazhoz a q ∨ r, a p ∨ r, netán a p ∨ q mondatokat csatoljuk? 3) Egy csendes napon békésen dolgozol egy analitikus fán, amikor is a következő formulával hoz össze a sors: A ∨ B ∨ C∨ ∼B ∨ D 3
Mit kezdenél egy ilyen formulával? Hogyan illesztenéd be az analitikus fádba? És hogyan tennéd ugyanezt, ha a számítógép barátod szintaxerror villogtatása közepette sipitozná, hogy „a ” ∨ ” egy kétoperandusos művelet!” ?
1.5. Egy komolyabb példa Az előző órai vázlatban vizsgáltuk, hogy vajon van-e ellentmondás az alábbi mondathalmazban: 1. Az nem úgy van, hogy ha az Etnához elmegyek, akkor már nem megyek a Balatonra. 2. Tévhit, hogy ha elmegyek a Balatonhoz, akkor már fürdőruhát is viszek – már amennyiben ha elmegyek az Etnához, akkor a bazaltorgonákhoz is elmegyek. 3. Nem igaz, hogy az Etnához megyek és van nálam fürdőruha. 4. Ha elmegyek a Balatonra, akkor elmegyek a bazaltorgonákhoz is. Amit a következőképp formalizáltunk: 1. ∼ (p ⊃ ∼ q) 2. (p ⊃ s) ⊃ ∼ (q ⊃ r) 3. ∼ (p & r) 4. q ⊃ s Most, mivel más igazságfüggvények felbontásával még nem próbálkoztunk, megvizsgáljuk ezt a mondathalmazt az analitikus fák módszerével. Ez, az igazságtáblázattal ellentétben nem tart sokáig.2 Sajnálatos módon nem tudom balra igazítani a formulákat. A példa végiggondolásához két hozzáállás javallott: Vagy nézzük folyamatosan a származtatási szabályokat, amik az előbb szerepeltek, vagy pedig gondolatban bontsuk fel ”∼”-re, ” & ”-re, ” ∨ ”-ra a mondatokat, és úgy ábrázoljuk őket. Előbbit a kezdőknek, utóbbit a haladóknak javasoljuk. (1) ∼ (p ⊃ ∼ q) (2) (p ⊃ s) ⊃ ∼ (q ⊃ r) (3) ∼ (p & r) (4) q ⊃ s (1) ∼ (p ⊃ ∼ q) p ∼∼ q q (2) (p ⊃ s) ⊃ ∼ (q ⊃ r) ∼ (p ⊃ s)
∼ (q ⊃ r)
p ∼s (4) q ⊃ s
q ∼r q ⊃ s
∼q ?
s ?
∼q ?
s (3) ∼ (p & r)
∼p ∼r ? ◦ Nos tartozom egy vallomással: Fifikás módon választottam meg, hogy melyik mondatot bontom fel először. Észrevehetjük ugyanis, hogy egy mondathalmaznak ilyetén módon több lehetséges felbontása is van, és sokszor nem mindegy a sorrend. Törekedjünk jegenyékre: Érdemes az olyan mondatokat megválasztani, amik nem nagyon akarnak elágazni. Érdemes továbbá azon mondatokat választani, ahol sanszos, hogy ellentmondások várnak ránk. 2 Ennek az az oka, hogy a mondatok különbözősége önmagában koránt sem befolyásolja olyan mértékben a algoritmust, mint ahogy azt igazságtáblázatok esetében teszi.
4
De nézzük a példát: Egy nyílt ágat találtunk. Milyen atomi mondatokat is találunk szigorúan felfelemenet ezen a nyílt ágon? Azaz máshogy fogalmazva: Milyen atomi mondatok igazsága esetén nem ütközünk ellentmondásba? Talán nem meglepő módon: p, q, ∼ r, s
1.6. Néhány kisebb szorgalmi feladat 4) Mire utal az, ha még azelőtt zárul le minden ág, mint hogy sorra került az összes mondat a mondathalmazból? 5) Szóba került az órán, hogy a 2. mondatot érthetnénk másképpen is: 1. ∼ (p ⊃ ∼ s) 2. ∼ [(p ⊃ q) ⊃ (s ⊃ r)] 3. ∼ (s & r) 4. s ⊃ q Vizsgáljuk meg az analitikus fák módszerével, majd gondolkozzunk el azon, hogy a fából, amit kaptunk, milyen következtetéseket vonhatunk le ehhez a mondathalmazhoz kapcsolódóan? Hát a két alternatív mondathalmaz között milyen kapcsolat lehet?
1.7. Centrális logikai fogalmaink az analitikus fák tükrében Centrális logikai fogalmaink: • Kielégíthetőség. • Helyes következtetés. • Logikai igazság. Felmerül a kérdés, hogy az analitikus fák módszerét hogyan használhatnánk fel ez utóbbiak vizsgálatára. Egyszerűbben fogalmazva: Egy mondathalmaz analitikus fáján miről ismerszik meg a kielégíthetőség, helyes következtetés és logikai igazság? 1.7.1. Kielégíthetőség A kielégíthetőséget tekintve van a legkönnyebb dolgunk, ezt tulajdonképpen már ki is használtuk. Kielégíthető egy mondathalmaz akkor és csak akkor, ha az analitikus fák módszerével találunk egy olyan ágat, ami nyílt(◦). Az ellentmondás ez alapján úgy ismerszik meg, ha ilyen ágat nem találunk; minden ág bezárul (?). 1.7.2. Helyes következtetés Kicsit bonyolultabb csak az az eset, amikor nem egy átlagos mondathalmazzal, hanem egy következtetéssel állunk szemben. Ámde felidézhetjük azt, mikor is helyes egy következtetés. Pár átfogalmazás után oda jutottunk, hogy helyesnek nevezünk egy következtetést akkor, ha a mondathalmaz, amiben a premisszák és a konklúzió tagadása szerepel, ellentmondásos. Helyben is vagyunk: Analitikus fákkal tudunk tehát következtetéseket vizsgálni, mivel mondathalmazok közti ellentmondást is képesek vagyunk keresni. Vegyük például a következő példát: Az nem megy, hogy apa is ott legyen a diplomaosztómon, meg anya is. Az sem megy, hogy se apa ne legyen ott, se anya. Tehát anya lesz ott, de apa nem, vagy apa lesz ott, de anya nem.
∼ (p & q) ∼ (∼ p & ∼ q) (q & ∼ p) ∨ (p & ∼ q)
Tegyük akkor, amit tennünk kell: Képezzük a premisszákból és a konklúzió tagadásából álló mondathalmazt: 1) ∼ (p & q) 2) ∼ (∼ p & ∼ q) 3) ∼ (q & ∼ p) ∨ (p & ∼ q) 5
Rászabadítva a fantasztikus módszerünket: 1) ∼ (p & q) 2) ∼ (∼ p & ∼ q) 3) ∼ (q & ∼ p) ∨ (p & ∼ q) ∼ (q & ∼ p) ∼ (p & ∼ q)
∼q ∼ (p & ∼ q)
∼∼ p p ∼ (p & ∼ q)
∼p 2) ∼ (∼ p & ∼ q) ∼∼ p
∼∼ q
p ?
q ?
∼∼ q q ?
∼p ?
∼∼ q q 2) ∼ (∼ p & ∼ q) ∼∼ p
∼∼ q
p 1) ∼ (p & q)
q 1) ∼ (p & q)
∼p ∼q ∼p ∼q ? ? ? ? Látjuk, hogy minden ág zárt. Ez arról árulkodik, hogy a három mondat ellentmondást rejt, azaz ellentmondásos a premisszák igazsága mellett tagadni a konklúziót. Ezzel a következtetés helyességét beláttuk. Talán a szemünkre hányhatnák, hogy ez a fa elég hatalmas lett, noha mindössze két mondat, p és q szerepel benne. Ez igazságtáblázatban mindössze négy sor. Erre azt válaszolhatjuk, hogy ez egy bevezető példa; egyrészt kiírtunk minden, később triviálisnak gondolható származtatást, mint a kétszeres tagadást, másrészt újraírtuk azon formulákat, amelyeket ’fent hagytunk’. Ezeket lehagyva kb. a felére csökkenhet a fa. De döntő érvnek az analitikus fák használata mellett én mégis a következőt szánom: Analitikus fát sokkal jobb érzés kibontani. 1.7.3. Logikai igazság No és hogyan ismerszik meg egy logikai igazság? Vegyük a standard klasszikus logikai igazság analitikus fáját: A∨ ∼ A A ∼A ◦ ◦ Látjuk, hogy minden ága nyílt. Vajon ez lenne a logikai igazságok ismertetőjele? Cáfoló ellenpélda: A∨ ∼ B A ∼B ◦ ◦ Hoppá. De nem lepődünk meg. Mit is jelent a sok kör? Hogy a logikai szerkezetükből adódóan nem bukkanunk ellentmondásra. A logikai igazság ebben ugye ott tér el, hogy ott nem is bukkanhatunk, akármilyen formulát is helyettesítünk be ’A’ helyére. Érdemes tehát abból kiindulni, hogy ez a fa-módszer alapvetően ellentmondások keresésére jó: Tagadjuk a két formulát, mindjárt meglátjuk, mi sül ki belőlük:
6
∼ A∨ ∼ A
∼ A∨ ∼ B
∼A ∼∼ A
∼A ∼∼ B
A ?
B ◦
No ez már különbség: Logikai igazságot tagadni ellentmondásos. Tanulság: Egy formuláról úgy bizonyítjuk, hogy logikai igazság, hogy tagadjuk, és ellentmondást mutatunk ki benne. 6) Kis szorgalmi feladat: Hogyan lehet egy következtetés premisszáinak analitikus fájából ’látni’, hogy mik következnek belőlük?
1.8. Megjegyzések • Talán feltűnt már, hogy nem szerepelnek ebben a módszerben I és H betűk. Ez ennek a módszernek elméleti szépsége is: Az igazságértékekre való folytonos támaszkodás nélkül, pusztán előzetesen felállított rajzolgatási szisztémáink betartásával is képesek vagyunk ellentmondásokat kimutatni, és így következtetéseket ellenőrizni, logikai igazságokat igazolni. • Ajánljuk a kijelentéslogika tananyagot további olvasgatásra és gyakorlásra:3 fin
3 Figyelem,
ott táblázatokban van elregélve ugyanez. Apróbb ábrázolási különbségről van azonban csak szó.
7
