Podcast on Formális és predikátumlogika

Přepis

Anna: Szóval a kvantorok lényegében csak egy szuper menő módja annak, hogy azt mondjuk: „mindenki” vagy „valaki”? Ez zseniális!

Lukáš: Pontosan! A formális logika ijesztően hangzik, de valójában csak egy eszköz arra, hogy szuper pontosak legyünk. És a vizsgákon a pontosság kulcsfontosságú.

Anna: Oké, ezt szét kell szednünk. A Studyfi Podcastot hallgatjátok. Ma szakértőnkkel, Lukáccsal, elmerülünk a formális logika világában.

Lukáš: Szia Anna, sziasztok mindannyian. Ne féljetek, nem lesz olyan szörnyű, mint amilyennek hangzik. Tulajdonképpen egész szórakoztató, ha tudjátok, hogyan kell csinálni.

Anna: Rendben, akkor térjünk is rá egy példára. Van egy mondatunk: „Bármely két különböző páros szám között van egy páratlan szám.” Hogyan a fenébe fordítsam ezt le a ti szimbólumaitokra?

Lukáš: Remek kérdés! Szedjük szét darabokra. A „bármely két” azt mondja nekünk, hogy minden lehetséges párról fogunk beszélni. Szóval szükségünk van két univerzális kvantorra. Ezt ∀-val jelöljük. Tehát ∀x ∀y-nal kezdünk.

Anna: Oké, mintha „minden x-re” és „minden y-ra”. Értem. Mi következik?

Lukáš: Most azt kell mondanunk, hogy az x és az y párosak. Szóval hozzáadunk egy feltételt: (even(x) ∧ even(y)). Ez a kalap alakú szimbólum, a ∧, azt jelenti, hogy „és egyben”.

Anna: Szóval: minden x-re és minden y-ra igaz, hogy x páros és egyben y is páros. Eddig van értelme. De a mondat *különböző* számokról beszél.

Lukáš: Pontosan! Pontosítanunk kell. Hozzáadunk egy másik feltételt: x < y. Az egész most így néz ki: ∀x ∀y((even(x) ∧ even(y) ∧ x < y) ... és most jön a mondat második része.

Anna: Az a rész, ahol azt mondja, hogy „köztük van egy páratlan szám”.

Lukáš: Igen. A „van” vagy „létezik” azt sugallja, hogy egzisztenciális kvantort, ∃-t fogunk használni. Szóval a formulánk egy nyíllal, ami implikációt jelöl, és utána ∃z-vel folytatódik.

Anna: Szóval ha igaz az első rész a két különböző páros számról, AKKOR létezik valamilyen 'z'?

Lukáš: Tökéletesen mondtad. És most már csak definiáljuk, mi az a 'z'. Páratlannak kell lennie, tehát (odd(z)).

Anna: És *x* és *y* között kell lennie.

Lukáš: Így van. Tehát x < z és egyben z < y. Ha mindezt összekötjük, megkapjuk a végső formulát.

Anna: Szóval: ∀x ∀y((even(x) ∧ even(y) ∧ x < y) → ∃z(odd(z) ∧ x < z ∧ z < y)). Hú. Ha az ember így látja szétszedve, akkor hirtelen már nem is olyan nagy mágia.

Lukáš: Egyáltalán nem. Olyan, mint egy kirakós. Minden szónak megvan a maga szimbóluma és a maga helye.

Anna: Említettél egy kis tippet, ami jól jöhet. Valamit arról, hogy a kvantorok hogyan barátkoznak a kötőszavakkal.

Lukáš: Ja, ez egy jó segédeszköz. Az univerzális kvantor ∀, azaz „mindenre”, leggyakrabban az implikációval, tehát azzal a nyíllal →, párosul. Ezzel azt mondjuk: „MINDEN elemre igaz, hogy HA teljesítik az A feltételt, AKKOR teljesítik a B feltételt is.”

Anna: Világos, mint a mi példánkban. HA x és y két különböző páros szám, AKKOR köztük van egy páratlan.

Lukáš: Pontosan. És fordítva, az egzisztenciális kvantor ∃, azaz „létezik”, többnyire a konjunkcióval ∧, azaz „és egyben” párosul.

Anna: Mert azt mondjuk: „LÉTEZIK olyan elem, amelynek A tulajdonsága ÉS EGYBEN B tulajdonsága is van.”

Lukáš: Telitalálat. Mint a mi példánkban a z: LÉTEZIK z, ami páratlan ÉS EGYBEN nagyobb, mint x ÉS EGYBEN kisebb, mint y. Ez tényleg egy hasznos mankó.

Anna: De mi van, ha a feladatban nincsenek meg az összes szükséges szimbólumok? Például itt van az even és az odd, de mi van, ha csak a párosat definiáltuk?

Lukáš: Kiváló észrevétel. Ez gyakran előfordul. Tudnunk kell boldogulni azzal, amink van. Ha csak az even(x) predikátumunk lenne, akkor a páratlan számot egyszerűen a negációjaként írnánk le: ¬even(x).

Anna: Aha! Szóval „nem páros”. Ez okos. Ez olyan, mint a programozásban, amikor valamit negációval definiálsz.

Lukáš: Pontosan. Vagy képzeld el, hogy a feladatban csak könyvtárak halmaza van megadva, dir(x). De a feladat azt kéri tőled, hogy fájlokkal dolgozz. Hogyan írnád le, hogy 'x' egy fájl?

Anna: Hát... egyszerűen azt mondanám, hogy nem könyvtár? Szóval ¬dir(x)?

Lukáš: Bingo! A logika erről szól. Dolgozni azzal, ami definiálva van, és a többit okosan levezetni. Nem mindig van minden ezüsttálcán tálalva.

Anna: Oké, a gyakorlat megvan. De a vizsgákon elméleti kérdések is vannak. És némelyik hangzik… hát, elég ijesztően. Például: Fogalmazza meg Gödel első nemteljességi tételét.

Lukáš: Ó, Gödel. A nagy mumus. De mi nem fogunk félni tőle. Próbáljuk meg egyszerűen. Az első tétel lényegében azt mondja, hogy bármely kellően erős és ellentmondásmentes matematikai rendszer – mint például az aritmetika, amit az iskolából ismerünk – mindig tartalmazni fog olyan állításokat, amelyek igazak, de a rendszeren belül nem bizonyíthatók.

Anna: Várj, várj. Szóval léteznek olyan matematikai igazságok, amiket egyszerűen nem tudunk bizonyítani az általunk használt matematikával?

Lukáš: Pontosan! Ez egy teljesen lenyűgöző gondolat. Mindig lesznek határai annak, amit bizonyítani tudunk. Egy rendszer soha nem lehet egyszerre kellően erős, ellentmondásmentes és teljes.

Anna: Ez… kicsit aggasztó. És mi van a második tétellel?

Lukáš: Az erre épül. Gödel második tétele azt mondja, hogy egyetlen ilyen rendszer sem tudja bizonyítani a saját ellentmondásmentességét. Más szóval, a matematika nem tudja bizonyítani, hogy önmagában nincsenek ellentmondások.

Anna: Szóval egyszerűen hinnünk kell abban, hogy 2+2=4, és hogy az egész rendszerünk nem omlik össze valahol?

Lukáš: Lényegében igen. Fel kell tételeznünk, hogy ellentmondásmentes, mert belülről nem bizonyítható. Ez a matematika filozófiai túlnyúlása, ami már majdnem száz éve lenyűgözi az embereket.

Anna: Oké, Gödel filozófia. De mi van a szárazabb definíciókkal? Például: „Definiálja az elsőrendű predikátumlogika nyelvének interpretációja fogalmát.”

Lukáš: Bonyolultan hangzik, de képzeld el, mint egy szótárt. Az interpretáció egy (D, α) pár. A 'D' a doménum – ez az a világ, amiről beszélünk. Például az összes ember vagy az összes szám halmaza.

Anna: És az 'α'?

Lukáš: Az 'α' az a leképezés, az a fordító. Megmondja nekünk, hogy az egyes szimbólumok mit jelentenek a 'D' világunkban. Minden változóhoz hozzárendel egy konkrét elemet a doménumból, minden predikátumszimbólumhoz hozzárendel valamilyen relációt, és minden függvényszimbólumhoz valamilyen függvényt.

Anna: Szóval az interpretáció lényegében a kulcs ahhoz, hogyan olvassuk a formulánkat a valós világban? Nélküle csak üres szimbólumok.

Lukáš: Pontosan. És ehhez kapcsolódik egy másik fogalom is: a term. Mi az a term?

Anna: Ez úgy hangzik, mint valami a Terminátorból.

Lukáš: Majdnem. A term lényegében bármi, ami egy objektumot jelölhet a doménumunkban. A legegyszerűbb term egy változó. És aztán, ha van egy 't' függvényszimbólumunk és 't1'-től 'tn'-ig termjeink, akkor a 't(t1, ..., tn)' ismét egy term.

Anna: Szóval például az 'x' egy term. És ha van egy 'apa(x)' függvényünk, akkor az 'apa(x)' is term? Mert egy konkrét személyt jelöl – az x személy apját.

Lukáš: Pontosan! A termek az objektumok nevei. A formulák pedig teljes állítások ezekről az objektumokról.

Anna: Menjünk a következőre. Egy formula bizonyítása az ítéletlogikában, az úgynevezett Hilbert-féle bizonyítás.

Lukáš: Ez egyszerű. Ez egy formulák sorozata, ami azzal a formulával végződik, amit bizonyítani akarunk. És most jön a fontos rész: a sorozatban minden formulának vagy axiómának kell lennie – tehát valamilyen alapvető, adott igazságnak – vagy le kell vezetni az előző formulákból valamilyen levezetési szabály segítségével, tipikusan a Modus Ponens-szel.

Anna: Szóval ez olyan, mint falat építeni. Minden téglának (formulának) vagy szilárd alapon (axióma) kell állnia, vagy más, már lerakott téglákkal (levezetés) kell megtámasztani.

Lukáš: Tökéletes analógia! És ehhez kapcsolódik két kulcsfontosságú fogalom: a rendszer korrektsége és teljessége.

Anna: Ez fontosnak hangzik.

Lukáš: Ezek a legfontosabb tulajdonságok. Egy rendszer *korrekt*, ha minden, amit benne bizonyítunk, valóban igaz. Más szóval, a rendszerünk nem termel hazugságokat. A bizonyítható implikálja az érvényeset.

Anna: És a teljesség?

Lukáš: A *teljesség* az érme másik oldala. Egy rendszer teljes, ha minden igazság, ami benne érvényes, egyben bizonyítható is benne. Tehát, hogy egyetlen igazság sem szökik meg tőlünk, hogy mindenre rájöhetünk.

Anna: Aha! Szóval a korrektség azt jelenti, hogy „nem bizonyítunk hülyeségeket”, és a teljesség azt jelenti, hogy „minden igazságot bizonyítani tudunk”.

Lukáš: Pontosan. Az ideális logikai rendszer korrekt és teljes. De ahogy Gödel megmutatta nekünk, bonyolultabb rendszerek, mint az aritmetika esetében, ezt a teljességet soha nem érjük el.

Anna: Hú. A formális logika végül sokkal mélyebb, mint amilyennek tűnik. Nem csak a szimbólumokról szól, hanem a tudásunk hatáiról is.

Lukáš: Pontosan. És ezeknek az alapoknak a megértése óriási előnyt ad nektek, nemcsak a vizsgán, hanem általában a kritikus gondolkodásban is. És erről többet fogunk mesélni egy rövid szünet után.

Anna: Szóval ha már van egy formulánk valamilyen alapformában, az még nem a vége, ugye? Például belefutottam a disztributivitás törvényébe, ami úgy nézett ki... hát, elég vadul.

Lukáš: Ja, az tud kínozni, de az elv valójában egyszerű. Hasonló ahhoz, mint amikor az általános iskolában szorzod a zárójeleket a matematikában.

Anna: Szorzod? Ez ismerősen hangzik.

Lukáš: Pontosan. Képzeld el, hogy van egy kifejezésed: A vagy (B és C). A disztributivitás törvénye lehetővé teszi, hogy a „vagy”-ot eloszd a zárójelbe. Így azt kapod, hogy (A vagy B) és (A vagy C).

Anna: Aha! Szóval ez érvényes arra a bonyolultabb példára is, amit láttam? Valami olyasmi volt, hogy nem-X vagy (Y és (nem-Z vagy nem-W)).

Lukáš: Pontosan! Fogod a nem-X-et, és lényegében „hozzáadod” a nagy zárójelben lévő minden taghoz. Az eredmény (nem-X vagy Y) és egyben (nem-X vagy nem-Z vagy nem-W). Ezzel a lépéssel jutunk el az úgynevezett konjunktív normálformához, azaz a CNF-hez.

Anna: Szuper, ez sokkal világosabb. De mi van, ha egy ilyen átalakítás után valamilyen káosz keletkezik a zárójelben?

Lukáš: Jó kérdés. Minden lépés után kulcsfontosságú a kifejezés egyszerűsítése. Ez szinte a legfontosabb rész.

Anna: Szóval egyfajta logikai takarítás?

Lukáš: Pontosan. Ha például a zárójelben (Y és Y és Z) van, az feleslegesen hosszú. Rövidítheted csak (Y és Z)-re.

Anna: Ez van értelme. És mi van egy bonyolultabb esettel?

Lukáš: Na mi van például az (Y és nem-Z és nem-Y)-nal? Itt történik valami érdekes. Van ott Y és egyben a negációja, a nem-Y.

Anna: Ez a két dolog nem lehet egyszerre igaz.

Lukáš: Bingo! Ez egy ellentmondás. Az egész zárójel tehát hamis, logikai nulla. És ha valamit nullával kötsz össze, az gyakran egyszerűsíti az egész kifejezést. Szóval a káoszból hirtelen... semmi.

Anna: Eltűnik, mint a kámfor. Remek. Most viszont letérek valamire, ami úgy hangzik, mint egy titkos kód... MGU. Mi a fenébe ez?

Lukáš: MGU, azaz Most General Unifier. Magyarul a legáltalánosabb unifikátor. A cél az, hogy vegyünk több különböző kifejezést, és a változók helyettesítésével egyetlen, teljesen azonos kifejezést hozzunk létre belőlük.

Anna: Szóval kifejezések egyesítése. Hogyan működik ez a gyakorlatban?

Lukáš: Mutassuk meg egy példán. Van három predikátumunk: P(x, g(v), v), aztán P(w, z, a) és végül P(h(u), u, y). Kezdjük az első kettővel.

Anna: Rendben, készen állok.

Lukáš: Balról jobbra haladunk. Összehasonlítjuk az első pozíciókat: x és w. Egyszerű, x-et w-re cseréljük. Most van P(w, g(v), v) és P(w, z, a).

Anna: Szuper, az első rész egyezik. Mi következik?

Lukáš: Második pozíciók: g(v) és z. Szóval a z változót lecseréljük az egész g(v) kifejezésre. És az utolsó pozíciók: v és az 'a' konstans. Tehát v-t a-ra cseréljük. És figyelem, mindenhol le kell cserélnünk, tehát a g(v) belsejében is, amiből g(a) lesz.

Anna: Szóval az első fázis után mindkét kifejezésből egy ugyanazt kapjuk: P(w, g(a), a)?

Lukáš: Pontosan! És most ezt az új kifejezést összehasonlítjuk a harmadikkal, P(h(u), u, y). És újra balról haladunk.

Anna: Szóval w-t h(u)-ra cserélem. Aztán van g(a) és u, tehát u-t g(a)-ra cserélem. És végül a és y, tehát y-t az 'a' konstansra cserélem.

Lukáš: Tökéletes! Egyből megoldottad. És mindazok a helyettesítések, amiket csináltunk, együtt alkotják a keresett legáltalánosabb unifikátort. Ez tulajdonképpen egyfajta recept arra, hogyan egyesítsük ezeket a kifejezéseket.

Anna: Értem. Ez egyfajta fokozatos puzzle-összerakás. És mire jó ez pontosan a gyakorlatban? Ezt talán majd legközelebbre hagyjuk, mi?

Anna: Szóval az unifikáció segít nekünk megtalálni a közös nyelvet a különböző kifejezések között. De mire vezet ez valójában? Mi a következő lépés?

Lukáš: Remek kérdés! A következő lépés egy szuper erős módszer, amit rezolúciónak hívnak. Ez tulajdonképpen egyfajta logikai detektív.

Anna: Logikai detektív? Ez érdekesen hangzik. Mit vizsgál pontosan?

Lukáš: Ellentmondásokat keres! A lényeg az, hogy találjunk két azonos kifejezést, ahol az egyik negált. Például P(f(x)) és egyben ¬P(f(x)). Mivel mindkettő egyszerre igaznak lenni nonszensz, kölcsönösen kioltják egymást.

Anna: Világos, mint plusz öt és mínusz öt. És mi van, ha a kifejezések nem teljesen azonosak?

Lukáš: Hát pontosan ott jön be a mi unifikációnk! Helyettesítést használunk, hogy egyesítsük őket, és aztán kiolthatjuk őket. De figyelem, ugyanarról a predikátumról kell szólnia! Nem olthatsz ki P(valamit) és ¬S(valamit). Ez olyan lenne, mintha almákat és negált körtéket adnál össze.

Anna: Rendben, almát körtével nem. Mutass egy példát.

Lukáš: Például van két sorunk: az egyikben ¬P(f(x,y)) ∨ Q(y) van, a másikban pedig ¬Q(z). Látsz ott valamit, amit meg lehetne piszkálni?

Anna: Hát, Q(y) és ¬Q(z) gyanúsan néznek ki. Ha 'z' helyére 'y'-t helyettesítenénk...

Lukáš: Pontosan! z helyettesítése y-nal, és hirtelen van Q(y) és ¬Q(y). Ezek kioltják egymást, és csak ¬P(f(x,y)) marad. Egyszerű, ugye?

Anna: Ez van értelme. De mi van, ha ott zavarnak minket a kvantorok, az a 'mindenre' és 'létezik'?

Lukáš: Kiváló észrevétel. Mielőtt belevágunk a bonyolultabb rezolúciókba, rendet kell raknunk a képletekben. És erre van a Prenex normálforma, röviden PNF.

Anna: Még egy rövidítés! Mit jelent?

Lukáš: A cél az, hogy az összes kvantort teljesen a formula elejére tegyük. Egyszerűen mindet kitoljuk a zárójelek elé.

Anna: És ez csak úgy megy? Büntetlenül áthelyezni őket?

Lukáš: Majdnem. Többnyire igen, de egy dologra figyelned kell. Ha egy kvantort, például ∃z-t, áthelyezel egy olyan formula részen keresztül, ahol már van valamilyen 'z', akkor át kell nevezned. Például 'v'-re. Különben zűrzavar lenne.

Anna: Szóval egyszerűen biztosítom, hogy minden változónév egyedi legyen az adott kontextusban. Logikus.

Lukáš: Pontosan. És amint az összes kvantor szépen sorban van az elején, jön az utolsó tisztítási lépés: a Skolemizáció.

Anna: Ez majdnem úgy hangzik, mint valami varázslat.

Lukáš: Kicsit. A Skolemizációval megszabadulunk az összes egzisztenciális kvantortól, tehát azoktól az '∃'-től. Egyszerűen kitöröljük őket.

Anna: Várj, csak úgy kitöröljük őket? Ez megváltoztatja a jelentést, nem?

Lukáš: Megváltoztatja, de ellenőrzötten! Az ott lévő változó helyére, például 'z' helyére, egy úgynevezett Skolem-függvényt helyettesítünk. Jelöljük például fz-vel. És a függvény zárójelébe beírjuk az összes változót az '∀' kvantorokból, amelyek az '∃z' előtt álltak.

Anna: Aha! Szóval ha az elején ∀x ∀y ∃z volt, akkor 'z' helyett most fz(x,y)-t írunk?

Lukáš: Bingo! Teljesen pontosan. És ha véletlenül egyetlen '∀' sem lenne az '∃' előtt, akkor konstans lesz belőle. Ez egy elegáns módja annak, hogy megszabaduljunk az egzisztenciától és előkészítsük a terepet magának a rezolúciónak. És pontosan ehhez térünk most vissza bonyolultabb példáknál.

Anna: ...pontosan. És ez remekül elvezet minket a következő témához, ami a tanulmányi jegyzetek. Úgy érzem, sok diák csak passzívan jegyzetel, amit hall.

Lukáš: Ez hatalmas hiba! A passzív jegyzetek szinte semmire sem jók. Olyan, mintha zenét hallgatnál, de nem hallanád a dallamot.

Anna: Rendben, akkor hogyan kell „aktívan” csinálni? Mit jelent ez pontosan a gyakorlatban?

Lukáš: Azt jelenti, hogy gondolkodj azon, amit írsz. Ahelyett, hogy szó szerint lemásolnád a prezentációról, próbáld meg a fő gondolatokat a saját szavaiddal átfogalmazni. Ez óriási különbség.

Anna: Szóval a jegyzeteim, amik a középiskolában inkább absztrakt művészetnek tűntek, tele nyilakkal és saját rövidítésekkel, tulajdonképpen helyesek voltak?

Lukáš: Pontosan! Ha segített neked megjegyezni, akkor zseniális volt. A cél nem az, hogy szép füzeted legyen Instagramra, hanem hogy funkcionális jegyzeteid legyenek az agyadnak.

Anna: És mi van az olyan sötétbe kiáltott felkiáltásokkal, mint a „utálom ezt a tárgyat”, ami az egész oldalon át van írva? Az valószínűleg nem sokat segít, ugye?

Lukáš: Az tényleg nem. Az csak a frusztráció levezetése, nem hatékony tanulás. Kulcsfontosságú az érzelmeket elválasztani a tényektől, és megpróbálni strukturálni azokat az információkat is, amik éppen nem érdekelnek.

Anna: Értem. Szóval összefoglalva: gondolkodni, átfogalmazni és nem rajzolni mérges szmájlikat a füzetbe. Nézzük meg most a konkrét módszereket...

Anna: Na és a végére egy utolsó gyors kérdés. Egyfajta felismerő játék. Készen állsz?

Lukáš: Igen! Remélem, nem bukok el.

Anna: Rendben. Ki az a tipikus kocka kerek szemüveggel, akinek egyetlen fotón sincs szakálla?

Lukáš: Az biztos Kurt Gödel lesz. Egyértelmű eset.

Anna: Pontosan! És mi van azzal, aki kicsit úgy néz ki, mint Mike a Breaking Badből? Kopasz, szintén kerek szemüveggel...

Lukáš: Ez a leírás tökéletesen illik David Hilbert-re. Ez egy remek asszociáció!

Anna: Ugye? Rendben, ki az, akit gyakran látni pipával, többnyire mint egy idősebb, ősz hajú urat?

Lukáš: Az Bertrand Russell. Klasszikus. A pipás fotói ikonikusak.

Anna: Tökéletes. És az utolsó... mind közül neki van a leghosszabb szakálla. És ez talán az egyetlen fotó, ahol van haja.

Lukáš: Gottlob Frege! Az a szakálla felejthetetlen.

Anna: Szuper, egyből megoldottad! És ezzel a mai rész végére értünk.

Lukáš: Pontosan. Tényleg sok mindent átvettünk, az ítéletlogika alapjaitól egészen a híres logikusokig és a szakállukig...

Anna: Pontosan. Reméljük, jól éreztétek magatokat és tanultatok valami újat. Köszönjük a hallgatást!

Lukáš: Érezzétek jól magatokat, és a Studyfi Podcast következő részében újra találkozunk.