Logika a számtástudományban

Tematika:

• Az ítéletkaluklus alapfogalmai: formula, hozzárendelés, kielégíthetőség, érvényesség, normálformák, logikai következmény. Horn formulák kielégíthetősége. Hilbert és Gentzen típusú következtetési (dedukciós) rendszerek, helyesség, teljesség, konzisztencia. A kompaktsági tétel. A rezolúciós következtetés és teljessége. Bonyolultsági kérdések.
  
• A predikátumkalkulus alapfogalmai: formula, struktúra, interpretáció, kielégíthetőség, érvényesség. Prenex normálformák, Skolemizáció. A kielégíthetőség eldönthetetlensége. Axiomatizálhatóság, Gödel nemteljességi tétele. Teljes következtetési rendszerek. Herbrand struktúra és tétel. A Löweinhem-Skolem tétel. Unifikáció, elsőrendű rezolúció. Korlátozott rezolúciós módszerek: lineáris, egység és SLD rezolúció teljessége.
  
• Alkalmazások: Logikai áramkörök és Boole függvények kapcsolata. Horn formulák kifejező ereje, logika mint programozási nyelv. Adatbázis lekérdezés (SQL).
  

Ajánlott irodalom:

• Fülöp Zoltán: Logika a számítástudományban, kézirat, fejlesztés alatt.
• Uwe Schönig: Logic for Computer Scientists, Birkhauser, 1989.
• M. Ben-Ari, Mathematical Logic for Computer Sciece, Prentice Hall, 1993.
• Nerode, R. A. Shore: Logic for Applications, Springer, 1997.
• R. Socher--Ambrosiusm P, Johann: Deduction Systems, Springer, 1997.
• J. H. Gallier, Logic for Compuer Science - Foundations for Automatic Theorem Proving, John Wiley & Sons, 1987.