A matematikai logika alkalmazásszemléletű tárgyalása

Pásztorné Varga Katalin

Várterész Magda

Ez a könyv az Oktatási Minisztérium támogatásával, a Felsőoktatási Pályázatok Irodája által lebonyolított felsőoktatási tankönyvtámogatási program keretében jelent meg.

Új Széchenyi Terv logó.

A kiadásért felel a Panem Kft. ügyvezetője, Budapest, 2003

A tananyag a TÁMOP-4.1.2-08/1/A-2009-0046 számú Kelet-magyarországi Informatika Tananyag Tárház projekt keretében készült. A tananyagfejlesztés az Európai Unió támogatásával és az Európai Szociális Alap társfinanszírozásával valósult meg.

Nemzeti Fejlesztési Ügynökség 06 40 638-638

Minden jog fenntartva. Jelen könyvet, illetve annak részeit tilos reprodukálni, adatrögzítő rendszerben tárolni, bármilyen formában vagy eszközzel - elektronikus úton vagy más módon - közölni a kiadók engedélye nélkül

2003


Tartalom

1. Matematikai alapfogalmak
2. A logikáról általában
A logika meghatározásáról
Rövid történeti áttekintés
3. A logikai nyelvekről
Általános tudnivalók – megjegyzések
Néhány matematikai diszciplína logikai nyelve
A matematikai logika leíró nyelve
4. Az ítéletlogika
Az ítéletlogika nyelve – szintaxis
Az ítéletlogika nyelve – szemantika
Ítéletlogikai törvények
Szemantikus következményfogalom
Az ítéletlogika strukturális tulajdonságairól
Hálók és Boole-algebrák
Az ítéletlogika műveleteinek tulajdonságairól
A Boole-függvények funkcionális teljességéről általában
5. Az elsőrendű logika
Elsőrendű logikai nyelvek – szintaxis
Szabad és kötött változók
Termhelyettesítés
Feladatok
Elsőrendű logikai nyelvek – szemantika
Feladatok
Elsőrendű logikai törvények
Feladatok
Szemantikus következményfogalom
Feladatok
6. A logika szintaktikus tárgyalása
Bizonyításelmélet
Az ítéletkalkulus
A predikátumkalkulus
Gentzen-stílusú kalkulusok
A természetes levezetés technikája
Szekventkalkulusok
Rezolúciós elv – rezolúciós kalkulus
Konjunktív normálformák és nulladrendű klózhalmazok
A rezolúciós kalkulus az ítéletlogikában
Rezolúciós stratégiák
Skolem-normálforma és az elsőrendű klózhalmaz
Az alaprezolúció
A Herbrand-univerzum és az elsőrendű klózhalmazok
Davis és Putnam módszere
A rezolúciós kalkulus az elsőrendű logikában
Rezolúciós levezetési stratégiák
A tablók módszere – tablókalkulus
Előkészítő fogalmak, ítéletlogika
Analitikus és jelölt tabló az ítéletlogikában
A tablók módszerének alkalmazásai
Előkészítő fogalmak, elsőrendű logika
Az elsőrendű analitikus tabló
7. Alkalmazások
Formalizálás – problémamegoldás
A formális axiomatikus elméletekről
A formalizálás kérdései
A logikai programozásról
A Prolog nyelv
A Prolog szemantikája

Az ábrák listája

4.1. Ítéletlogikai formula szerkezetének fája
4.4. Az (YZ)(Z¬X) formula igazságértékelés-fája
4.12. Hasse-diagramok
4.13. Komplementumos háló Hasse-diagramja
5.1. Term szerkezeti fája
5.2. Elsőrendű formula szerkezeti fája
5.3. [ V ν ] -beli formulák besorolása
5.4. Logikailag és tautologikusan igaz elsőrendű formulák
6.13. Az interpretációhoz tartozó zárt szemantikus fák
6.14. A zárt szemantikus fa
6.16. φ ((X(YZ))(XY)(XZ)) h igazságértékelés-fája
6.17. F(X(YZ))(XY)(XZ) igazságértékelés-fája
6.18. ¬((X(YZ))(XY)(XZ)) igazságértékelés-fája
6.20. Közvetlen tablók ,,jelöletlen” és α -, β -formulákra
6.21. Közvetlen tablók jelölt formulákra
06.22. ¬((X(YZ))(XY)(XZ)) analitikus tablója
6.23. F(X(YZ))(XY)(XZ) jelölt tablója
6.24. A jelölt formulák feldolgozása a tablóba kerülés sorrendjében
6.25. A jelölt formulák feldolgozása ,, α -típus előbb” stratégiával
6.26. Közvetlen tablók α -, β -, γ - és δ - formulákra
6.27. Közvetlen tablók ,,jelöletlen” formulákra
6.28. Közvetlen tablók jelölt formulákra
7.1. Véges SLD fa
7.2. Végtelen SLD fa

A táblázatok listája

3.1. Az egyváltozós logikai műveletek
3.2. A kétváltozós logikai műveletek
3.3. A logikai műveletek mint logikai összekötők
3.4. Logikán kívüli rész a struktúrák és leíró nyelvük ábécéjében
3.5. A formalizált nyelv ábécéje és jellemzőik
4.2. A logikai műveletek közös igazságtáblája
4.3. Az (YZ)(Z¬X) formula igazságtáblája
4.5. Kiterjesztett igazságtábla
4.6. Kiterjesztett igazságtábla egyszerűen
4.7. Kiterjesztett igazságtábla lusta módszerrel
4.8. Kiterjesztett igazságtábla lusta módszerrel egyszerűen
4.9. Az X¬X formula igazságtáblája
4.10. Az XY és a ¬XY formulák közös igazságtáblája
4.11. Az {X,XY,¬Y} formulahalmaz kielégíthetetlen
4.14. A h( X i ¬ C 3 , X j ¬ C 2 ) függvény komponensei behelyettesítve
6.1. Az ítéletkalkulus axiómasémái
6.2. Az ítéletkalkulus levezetési szabálya
6.3. Levezetés generálása adott levezetésből
6.4. A predikátumkalkulus axiómasémái
6.5. A predikátumkalkulus levezetési szabálya
6.6. A természetes levezetés technikájának strukturális szabályai
6.7. A természetes levezetés technikájának logikai szabályai
6.8. A természetes levezetés technikájának kvantoros szabályai
6.9. A G-kalkulus
6.10. A C-kalkulus
6.11. A G-kalkulus kvantoros levezetési szabályai
6.12. A C-kalkulus kvantoros levezetési szabályai
6.15. Jelölt és ,,jelöletlen” formulapárok igazságtáblája
6.19. Az α - és β -formulák közvetlen részformulái