2004-12-09
1. félév

Témák 1. Félév
- Paraméteres , elsőrendű nyelv.
- Kalkulusok (Helyesség, teljesség): 
        bizonyításelmélet (Hilbert rendszer)
	        Gentzen szekvent kalkulus
	        Tablókalkulus paraméteres és klasszikus nyelv esetén.
	        Rezolúciós kalkulus (0. és 1. rendű)
- Konzisztencia, inkonzisztencia, mint a logika eltérõ tárgyalásmódjainak ekvivalenciáját megmutathatóvá tevõ fogalom (0. és 1. rend). 
- Különbözõ kalkulusok konzisztencia inkonzisztencia fogalmai.
- -konzisztencia (inkonzisztencia) (véges jelleg),
-  bizonyíthatóság definíciója, maximális -konzisztens formulahalmaz  - maximális konzisztens formulahalmaz  - 0. és  1. rendű Hintikka halmaz
A kompaktsági tétel. A kompaktsági tétel belátása 0-adrendben a Kõnig tétel és az analitikus tabló felhasználásával, Hintikka halmazzá való kiterjesztéssel.
Tukey lemma . Bizonyítás: Lindenbaum konstrukció. Szerepe a logikában.
- 1. rendû logika alaptétele. Boole értékelés   -  1. rendû értékelés definíciója. "Helyes" formulahalmaz def.
Reguláris formulák - def
Reguláris sorozat - def.
Reguláris halmaz - def. , kielégíthetõsége, helyessége.
Kvázi reguláris halmaz.
- A logika alaptétele  R^X tautológia
S asszociáltja, X asszociáltja
"S-nek van asszociáltja"  -inkonzisztencia tulajdonság, 
"S-nek nincs asszociáltja"  -inkonzisztencia tulajdonság
- A logika alaptétele  R^X tautológia esetén megmutatni hogy QQ(a)-ban Q az X gyenge részformulája. 
- Tablókonstrukcióval megmutatni ezt. (indokolni)

Ebben a félévben nem kerültek sorra

. (Hogyan kapcsolódnak egymáshoz a Hintikka és a Henkin halmazok.) 1. rendû bizonyításelmélet teljessége.
(- Mágikus halmazok)
Elsőrendű logikai nyelvek  formai eltérései. Milyen célokra alkalmas a paraméteres nyelv.

Vizsgakérdések
1. Melyek egy logikai nyelvvel szemben támasztott követelmények? Milyen elsörendű nyelveket ismer? Vannak-e köztük lényegesen eltérők? Ha igen, akkor ennek mi az oka?

2. Hogyan segít az analitikus tabló módszer a különböző tételbizonyító eljárások teljességének egységes bizonyításában?

3. Definiálja a maximális konzisztens formulahalmazt és ismertesse tulajdonságait. Hasonlítsa össze a -konzisztens formulahalmazokkal.

4. Mondja ki és bizonyítsa a Tukey lemmát. Miért alkalmas ez annak igazolására, hogy tetszőleges konzisztens, -konzisztens formulahalmaz kiterjeszthető maximális konzisztenssé.
Mit jelent az, hogy egy tulajdonság véges jellegű?

5. Ismertesse a tabló módszereket. (, , ,  formulaosztályozás)

6. Ismertesse a logika szintaktikus tárgyalását (bizonyításelmélet). Mi a bizonyításelmélet kapcsolata a Gentzen típusú kalkulusokkal?

7. Reguláris halmaz, - A logika alaptétele  R^X tautológia esetén megmutatni hogy QQ(a)-ban Q az X gyenge részformulája. 
- Tablókonstrukcióval megmutatni ezt. (indokolni)

8. Hintikka halmaz és az U-formulák, tiszta formulák. Milyen konzisztenciafogalom esetén tudná bebizonyítani, a kompaktsági tételt.

9. Definíciók: Hintikka halmaz, igazhalmaz, lefele zárt halmaz, felfele zárt halmaz, konzisztens halmaz,maximális konzisztens halmaz. Milyen kapcsolatok vannak e halmazok között?

10. Milyen kalkulusokat ismer? Ismertesse ezek közül (beleértve a helyesség és teljesség kérdését is) a
a)	bizonyításelméleti tárgyalást
b)	Gentzen féle kalkulusokat
c)	Tablókalkulust
d)	Rezolúciós kalkulus

11. Igazolja tablóval, hogy ha egy formula kielégíthetetlen, akkor ellentmondásos is.

12. Adja meg a -konzisztencia definícióját. Miben különbözik ez a Hintikka halmaz definíciójától?
Milyen megoldásokat ismer annak megmutatására, hogy egy -konzisztens formulahalmaz kielégíthető?

13. Mondja ki a kompaktsági tételt és bizonyítsa be tabló módszerrel. Kell-e ehhez még valamilyen más eredmény is?

14. Adja meg a reguláris halmaz definícióját. Mit fed itt és mit fed a tablóépítésnél a liberalizált paramétertechnika? 
Egy R reguláris halmaz kielégíthetősége milyen értelemben jelent többet, mint a szokásos kielégíthetőség?

15. Mondja ki a logika alaptételét R (reguláris halmaz) és X-re. Definiálja az asszociált fogalmát. Mutassa meg, hogy milyen konzisztencia tulajdonságot lehet ezzel a fogalommal megadni.

16. Mi a szisztematikus- és mi a teljes tabló? Igazolja, hogy a teljes, szisztematikus tabló nyitott ágán Hintikka halmaz áll elő. Hogy lehet eldönteni, hogy egy formula hamis-e valamilyen interpretáció(k)ban? Kapható-e információ az interpretáció univerzumának számosságáról?

17. Milyen módon kell lezárni egy formula tablóját, hogy a formula Boole értelemben való kielégíthetetlenségét igazoljuk. Ha X egy logikailag igaz formula, akkor mi az a formula, ami biztosan Boole értelemben Kielégíthetetlen?
11. Ismertesse a tablóépítési szabályokat. Mi a kritikus paraméter és mi a kritikus változó? Mitől függ, hogy melyikkel dolgozunk?

18. Ismertesse a rezolúciós elvet. Ismertesse a fontosabb stratégiákat.(lineáris, szemantikus) Mit tud mondani helyességről, teljességről. Be is tudja bizonyítani?

19. Ismertesse a Davis Putnam módszert. Mit tud mondani helyességről, teljességről. 

20. Ismertesse az illesztő helyettesítés algoritmusát. Bizonyítsa be, hogy a legáltalánosabb illesztő helyettesítést kapjuk.

21. Mondja ki a lifting tételt. Bizonyítsa. Milyen tétel bizonyításához van szükség a lifting tételre?

22. Definiálja az elsőrendű rezolvens fogalmát. Mutassa meg, hogy az elsőrendű rezolvens logikai következménye az ősöknek.

23. Az illesztő helyettesítésnek mi a szerepe? Miért szabad kötött változókba helyettesíteni vagy itt nem is erről van szó? Mi a faktorizálás?