INFORMATIKAI KAR DOKTORI PROGRAM
SZIGORLATI TEMATIKA

Matematikai logika



Logikai nyelvek (0., 1., 2. és magasabb rendû) változatai.
Következményfogalom (szemantikus, szintaktikus). Dedukciós tétel. Eldöntésprobléma. Tautológia, érvényesség, levezethetõség, bizonyíthatóság.
Szintaktikus következményfogalomra épülõ kalkulusok (0. és 1. rend)
Bizonyításelmélet természetes levezetés Gentzen szekvent módszerek
Szemantikus következményfogalomra épülõ szintaktikus kalkulusok (0. és 1. rend)
Megvalósítás lehetõségei. Stratégiák.
Dualitás szerepe a formulaátalakításban. Általánosított normálformák.

Rezolúciós kalkulus.
Herbrand univerzum - bázis - interpretáció.
Rezolúciós levezetés, lifting lemma. Megvalósítás lehetõségei. Stratégiák.

Tabló módszer.
Jelölt - jelöletlen - szisztematikus tabló. Megvalósítás lehetõségei. Stratégiák.

A logika egységes tárgyalásmódja - Teljesség egységes bizonyítása.
Boole értékelés és az 1. rendû értékelés. Reguláris formulák - sorozat - halmaz. Kielégíthetõsége, "jó"sága.

 


Irodalom:


R. Smullyan: First order Logic. Springer, 1968
Pásztoné Varga Katalin, Várterész Magda: Matematikai logika alkalmazásszemléletû tárgyalása. PANEM 2003.
C.L. Chang, R.C.T. Lee: Symbolic Logic and Mechanical Theorem Proving. Academic Press. 1973.
Bell, M. Machover: A Course is Mathematical Logic. North Holland, 1977.
A. Leitch: The Resolution Calculus. Springer. 1997.
M. Fitting:First Order Logic and Automated Theorem Proving. Springer. 1994.