Shrnutí na Formális és predikátumlogika

Formális és Predikátumlogika: Átfogó Útmutató Hallgatók Számára

SummaryKnowledge testFlashcardsPodcastMindmap

Bevezetés

A formális logika olyan módszerek és jelölések összessége, amelyekkel pontosan kifejezhetők az objektumokról, relációkról és bizonyításokról szóló állítások. Ennek az anyagnak a célja, hogy áttekinthető összefoglalót nyújtson az alapvető témákról, eljárásokról és hasznos trükkökről, amelyek a formális logika feladataiban előfordulnak (pl. nyelv megfogalmazása, skolemizáció, PNF, rezolúció, modus ponens, elméletek modelljei). Az anyag önálló tanulásra készült, és célja, hogy megkönnyítse a tájékozódást és a felkészülést gyakorlatokra vagy vizsgára.

Alapvető részek és eljárások

Az alábbiakban gyakran ismétlődő feladatokat bontunk kisebb lépésekre, definíciókkal, példákkal és gyakorlati tippekkel kiegészítve.

1) Nyelvi megfogalmazás (állítás: hogyan írjuk át a feladatot FOL-ba)

  • Cél: olyan elsőrendű predikátumlogikai formula létrehozása, amely pontosan leírja a feladat szövegét.
  • Eljárás:
    1. Azonosítsa a kvantorokat: „minden”, „összes” típusú szöveg → $ orall$, „létezik” típusú szöveg → $\exists$.
    2. Határozza meg a predikátumokat/függvényszimbólumokat: pl. $even(x)$, $odd(x)$, $dir(x)$.
    3. Adja hozzá a feltételeket (összetéve $\land$, $\lor$, $\to$, negáció $\neg$ segítségével) pontosan úgy, ahogy a feladat megadja.
    4. Ellenőrzés: a formula hangos felolvasása gyakran felfedi a hibákat.

Definíció: A nyelvi megfogalmazás egy olyan predikátumlogikai formula, amely kvantorok és predikátumok segítségével pontosan rögzíti a természetes nyelven megfogalmazott állítást.

Gyakorlati példa: „Bármely két különböző páros szám között létezik páratlan szám.”

    1. lépés: két változó → $ orall x\forall y$.
    1. lépés: mindkettő páros: $even(x)\land even(y)$.
    1. lépés: különböző és rendezés: $x<y$ (vagy $x\neq y$ a feladat szerint).
    1. lépés: páratlan szám létezése közöttük: $\exists z,(odd(z)\land x<z\land z<y)$.
  • Eredő formula: $$\forall x\forall y,\bigl((even(x)\land even(y)\land x<y)\to \exists z,(odd(z)\land x<z\land z<y)\bigr)$$

Tipp: A legtöbb mondatban érvényes, hogy a $\forall$ részek előfeltételeket és az $(P\to Q)$ implikáció alakját adják meg, ahol $P$ a változókra vonatkozó feltételeket, $Q$ pedig a létezést vagy más záró feltételt jelenti.

Érdekesség: A gyakorlatban néha nem lehet automatikusan új predikátumokat hozzáadni a szignatúrához; ha a feladatban csak $dir(x)$ (könyvtár) szerepel, de „fájlra” van szükség, akkor azt $\neg dir(x)$ formában lehet modellezni, amennyiben ez a kontextusban ésszerű.

2) Prenex normálforma (PNF) és szkolemizáció

  • A PNF célja: az összes kvantor áthelyezése a formula elé, anélkül, hogy a jelentés megváltozna (a szabad változókon kívül).
  • Szkolemizáció: az egzisztenciális kvantorok eltávolítása szkolem-függvények bevezetésével, hogy egy rezolúcióra alkalmas ekvivalens formula jöjjön létre.

A PNF alapvető eljárása:

  1. A logikai ekvivalenciák és implikációk eliminálása.
  2. A negációk befelé mozgatása De Morgan-törvények és a kettős negáció szabálya segítségével.
  3. Annak biztosítása, hogy a kvantorok ne vonatkozzanak egymással ütköző változókra (változók átnevezése).
  4. A kvantorok kiemelése a formula elé.

Szkolemizáció (egyszerű eljárás):

  1. Legyen egy formula PNF-ben: $\forall x\exists y,P(x,y)$. Az $\exists y$ eltávolításához bevezetünk egy $f(x)$ szkolem-függvényt, és $y$-t $f(x)$-szel helyettesítjük.
  2. A szkolemizáció után a következőket kapjuk: $\forall x,P(x,f(x))$, és elimináljuk az $\exists$-t (a függvény rögzített, tehát már nem létezik kvantor $y$-ra).

Példa (röviden): $$\forall x\exists y,R(x,y)$$ Szkolemizáció → $$\forall x,R(x,f(x))$$

3) KNF és DNF (átalakítás közöttük)

  • DNF (diszjunktív normálforma): literálok konjunkcióinak diszjunkciója; akkor alkalmas, ha közvetlenül akarjuk leolvasni az igazságtábla igaz sorait.
  • KNF (konjunktív normálforma): literálok diszjunkcióinak konjunkciója; rezolúciós bizonyításokhoz alkalmas.

Átalakítás igazságtáblából:

  • DNF: vegye azokat a sorokat, ahol az eredmé
Sign up for the full summary
FlashcardsKnowledge testSummaryPodcastMindmap
Start for free

Already have an account? Sign in

Formális logika – áttekintés

Klíčové pojmy: Formulace jazyka: identifikujte kvantifikátory a predikáty, Při překladu do FOL napište podmínky do antecedentu a existence/něco do konsekventu: $\\forall...((P)\\to \\exists...)$, PNF: vytáhněte kvantifikátory před formuli po eliminaci implikací a přesunech negací, Skolemizace: $\\exists y$ nahraďte Skolemovou funkcí $f(\cdot)$ závislou na univerzálních proměnných, DNF z řádků s hodnotou 1: konjunkce literálů spojte disjunkcí, CNF z řádků s hodnotou 0: disjunkce literálů spojte konjunkcí, Rezoluce: z $(A\\lor l)$ a $(B\\lor\\neg l)$ odvodíme $(A\\lor B)$, Modus Ponens: z $A$ a $(A\\to B)$ odvodíme $B$, Model: interpretace $(D,\\alpha)$ musí splňovat všechny axiomy, Relace: uspořádání = reflexivní+tranzitivní+antisymetrické; ekvivalence = reflexivní+symetrická+tranzitivní

## Bevezetés A formális logika olyan módszerek és jelölések összessége, amelyekkel pontosan kifejezhetők az objektumokról, relációkról és bizonyításokról szóló állítások. Ennek az anyagnak a célja, hogy áttekinthető összefoglalót nyújtson az alapvető témákról, eljárásokról és hasznos trükkökről, amelyek a formális logika feladataiban előfordulnak (pl. nyelv megfogalmazása, skolemizáció, PNF, rezolúció, modus ponens, elméletek modelljei). Az anyag önálló tanulásra készült, és célja, hogy megkönnyítse a tájékozódást és a felkészülést gyakorlatokra vagy vizsgára. ## Alapvető részek és eljárások Az alábbiakban gyakran ismétlődő feladatokat bontunk kisebb lépésekre, definíciókkal, példákkal és gyakorlati tippekkel kiegészítve. ### 1) Nyelvi megfogalmazás (állítás: hogyan írjuk át a feladatot FOL-ba) - Cél: olyan elsőrendű predikátumlogikai formula létrehozása, amely pontosan leírja a feladat szövegét. - Eljárás: 1. Azonosítsa a kvantorokat: „minden”, „összes” típusú szöveg → $ orall$, „létezik” típusú szöveg → $\\exists$. 2. Határozza meg a predikátumokat/függvényszimbólumokat: pl. $even(x)$, $odd(x)$, $dir(x)$. 3. Adja hozzá a feltételeket (összetéve $\\land$, $\\lor$, $\\to$, negáció $\\neg$ segítségével) pontosan úgy, ahogy a feladat megadja. 4. Ellenőrzés: a formula hangos felolvasása gyakran felfedi a hibákat. > Definíció: A nyelvi megfogalmazás egy olyan predikátumlogikai formula, amely kvantorok és predikátumok segítségével pontosan rögzíti a természetes nyelven megfogalmazott állítást. Gyakorlati példa: „Bármely két különböző páros szám között létezik páratlan szám.” - 1. lépés: két változó → $ orall x\\forall y$. - 2. lépés: mindkettő páros: $even(x)\\land even(y)$. - 3. lépés: különböző és rendezés: $x<y$ (vagy $x\neq y$ a feladat szerint). - 4. lépés: páratlan szám létezése közöttük: $\\exists z\,(odd(z)\\land x<z\\land z<y)$. - Eredő formula: $$\\forall x\\forall y\,\bigl((even(x)\\land even(y)\\land x<y)\\to \\exists z\,(odd(z)\\land x<z\\land z<y)\bigr)$$ Tipp: A legtöbb mondatban érvényes, hogy a $\\forall$ részek előfeltételeket és az $(P\\to Q)$ implikáció alakját adják meg, ahol $P$ a változókra vonatkozó feltételeket, $Q$ pedig a létezést vagy más záró feltételt jelenti. Érdekesség: A gyakorlatban néha nem lehet automatikusan új predikátumokat hozzáadni a szignatúrához; ha a feladatban csak $dir(x)$ (könyvtár) szerepel, de „fájlra” van szükség, akkor azt $\\neg dir(x)$ formában lehet modellezni, amennyiben ez a kontextusban ésszerű. ### 2) Prenex normálforma (PNF) és szkolemizáció - A PNF célja: az összes kvantor áthelyezése a formula elé, anélkül, hogy a jelentés megváltozna (a szabad változókon kívül). - Szkolemizáció: az egzisztenciális kvantorok eltávolítása szkolem-függvények bevezetésével, hogy egy rezolúcióra alkalmas ekvivalens formula jöjjön létre. A PNF alapvető eljárása: 1. A logikai ekvivalenciák és implikációk eliminálása. 2. A negációk befelé mozgatása De Morgan-törvények és a kettős negáció szabálya segítségével. 3. Annak biztosítása, hogy a kvantorok ne vonatkozzanak egymással ütköző változókra (változók átnevezése). 4. A kvantorok kiemelése a formula elé. Szkolemizáció (egyszerű eljárás): 1. Legyen egy formula PNF-ben: $\\forall x\\exists y\,P(x,y)$. Az $\\exists y$ eltávolításához bevezetünk egy $f(x)$ szkolem-függvényt, és $y$-t $f(x)$-szel helyettesítjük. 2. A szkolemizáció után a következőket kapjuk: $\\forall x\,P(x,f(x))$, és elimináljuk az $\\exists$-t (a függvény rögzített, tehát már nem létezik kvantor $y$-ra). Példa (röviden): $$\\forall x\\exists y\,R(x,y)$$ Szkolemizáció → $$\\forall x\,R(x,f(x))$$ ### 3) KNF és DNF (átalakítás közöttük) - DNF (diszjunktív normálforma): literálok konjunkcióinak diszjunkciója; akkor alkalmas, ha közvetlenül akarjuk leolvasni az igazságtábla igaz sorait. - KNF (konjunktív normálforma): literálok diszjunkcióinak konjunkciója; rezolúciós bizonyításokhoz alkalmas. Átalakítás igazságtáblából: - DNF: vegye azokat a sorokat, ahol az eredmé