Leírás

1. Bevezetés a logikába. Az állításlogika nyelve, nulladrendű formulák. Alapvető fogalmak a nyelv szintaxisában: összetettség, (közvetlen) részformula, szerkezeti fa, fő logikai összekötőjel, hatókör, zárójelhasználat.

2. Nulladrendű nyelv interpretációja, szemantikai szabályok. Igazságtáblázat, formulák igazságértékének meghatározása egy adott interpretában. Centrális logikai (szemantikai) fogalmak: modell, kielégíthetőség, kielégíthetetlenség, következmény, érvényesség, logikai ekvivalencia.

3. A logikai műveletek fontosabb tulajdonságai. Alapvető tételek.

4. Konjunktív- és diszjunktív normálformák. Formula kielégíthetőségének vizsgálata.

5. A klasszikus elsőrendű nyelv (függvényparaméterek nélkül). A névparaméterek, predikátumparaméterek, változók, kvantorok a formulákban. Szintaxis: összetettség, részformula, hatókör, zárójelhasználat.

6. Az elsőrendű nyelv interpretációja, az értékelés fogalma. Szemantikai szabályok. Formulák igazságértéke adott interpretáció és értékelés szerint. Centrális logkikai (szemantikai) fogalmak: modell, kielégíthetőség, kielégíthetetlenség, következmény, érvényesség, logikai ekvivalencia.

7. Alapvető tételek. Változók kötött és szabad előfordulása. Kvantorokra vonatkozó logikai ekvivalenciák.

8. Behelyettesíthetőség. Kötött változók átnevezése. Kongruencia. Változótiszta alak. Prenex alak.

9. Nevezetes elsőrendű következtetések.

Kompetenciák

Megismerkedve az alapvető logikai műveletekkel és a logikailag helyes következtetésekkel a hallgatók elsajátítják a szabatos gondolkodás elméleti alapjait. Képessé válnak a logikailag helyes és helytelen következtetések megkülönböztetésére, az ellentmondástalanság bizonyítására, az ellentmondásos állításhalmazok felismerésére.

Oktatók

Dr. Mihálydeák Tamás Sándor

Heti beosztás

1. A formális nyelvek alapfogalmai. Műveletek nyelvekkel. Reguláris kifejezések, reguláris nyelvek.

2. A véges automata fogalma, determinisztikus és nemdeterminisztikus automaták.

3. A véges automaták által felismert nyelvek és a reguláris nyelvek ekvivalenciája. Az algoritmus fogalmának formális megalapozása (például Markov algoritmus)

4. Bevezetés a logikába. Az állításlogika nyelve, nulladrendű formulák. Alapvető fogalmak a nyelv szintaxisában: összetettség, (közvetlen) részformula, szerkezeti fa, fő logikai összekötőjel, hatókör, zárójelhasználat.

5. Nulladrendű nyelv interpretációja, szemantikai szabályok. Igazságtáblázat, formulák igazságértékének meghatározása egy adott interpretában. Centrális logikai (szemantikai) fogalmak: modell, kielégíthetőség, kielégíthetetlenség, következmény, érvényesség, logikai ekvivalencia.

6. A logikai műveletek fontosabb tulajdonságai. Alapvető tételek.

7. Konjunktív- és diszjunktív normálformák. Formula kielégíthetőségének vizsgálata.

8. Bináris döntési diagramok.

9. A klasszikus elsőrendű nyelv (függvényparaméterek nélkül). A névparaméterek, predikátumparaméterek, változók, kvantorok a formulákban. Szintaxis: összetettség, részformula, hatókör, zárójelhasználat.

10. Az elsőrendű nyelv interpretációja, az értékelés fogalma. Szemantikai szabályok. Formulák igazságértéke adott interpretáció és értékelés szerint. Centrális logkikai (szemantikai) fogalmak: modell, kielégíthetőség, kielégíthetetlenség, következmény, érvényesség, logikai ekvivalencia.

11. Alapvető tételek. Változók kötött és szabad előfordulása. Kvantorokra vonatkozó logikai ekvivalenciák.

12. Behelyettesíthetőség. Kötött változók átnevezése. Kongruencia. Változótiszta alak. Prenex alak.

13. Nevezetes elsőrendű következtetések.

14. Az elsőrendű logikai nyelv és a programozási nyelvek: párhuzamok, alkalmazások, kitekintés.

Követelmények

RÉSZVÉTEL 
A hallgatónak részt kell vennie az előadásokon. 
Hiányzások maximális száma: 3 

IRODALOM 
Formális nyelvek és autómaták ( https://gyires.inf.unideb.hu/KMITT/b24/ ) 
Michael Sipser: Introduction to the Theory of Computation, 3rd ed., Cengage Learning, 2012. 
Mihálydeák Tamás: Az informatika logikai alapjai 
( https://arato.inf.unideb.hu/mihalydeak.tamas/Logika_my_twt-treeview.html ) 
Aszalós László, Mihálydeák Tamás: Logika kiskáté 
( https://arato.inf.unideb.hu/mihalydeak.tamas/kiskate.pdf ) 
Mordechai Ben-Ari: Mathematical Logic for Computer Science, 3rd ed., Springer, 2012. Dragálin Albert, Búzási Szvetlana: Bevezetés a matematikai logikába, Kossuth Egyetemi Kiadó, 1986. 
Pásztorné Varga Katalin, Várterész Magda: A matematikai logika alkalmazásszemléletű tárgyalása, Panem, 2003. 
Kádek Tamás, Robu Judit, Várterész Magda: Matematikai logika példatár, Kolozsvári Egyetemi Kiadó, 2010.

Vizsga/számonkérés

Vizsgát az a hallgató tehet, aki a tárgy gyakorlatán megszerezte az gyakorlat teljesítését igazoló aláírást. A vizsgák a NEPTUN-ban meghirdetett időben és helyen lesznek.

Konzultációk

A tárgy előadójának és a gyakorlatok vezetőinek a fogadóóráin.

Kötelező irodalom

1. Mihálydeák Tamás: Az informatika logikai alapjai 
   ( https://arato.inf.unideb.hu/mihalydeak.tamas/Logika_my_twt-treeview.html )

2. Aszalós László, Mihálydeák Tamás: Logika kiskáté 
   ( https://arato.inf.unideb.hu/mihalydeak.tamas/kiskate.pdf )

3. Mordechai Ben-Ari: Mathematical Logic for Computer Science, 3rd ed., Springer, 2012.

Ajánlott irodalom

1. Mendelson, E.: Introduction to Mathematical Logic, Chapman & Hall, London, 1997.

2. Dragálin Albert, Búzási Szvetlana: Bevezetés a matematikai logikába, Kossuth Egyetemi Kiadó, 1986.

3. Pásztorné Varga Katalin, Várterész Magda: A matematikai logika alkalmazásszemléletű tárgyalása, Panem, 2003.

4. Kádek Tamás, Robu Judit, Várterész Magda: Matematikai logika példatár, Kolozsvári Egyetemi Kiadó, 2010.

5. Gabbay, D. M., Abramsky, S., Maibaum, T. S. E.: Handbook of Logic in Computer Science, Oxford University Press, Oxford, 2000.

Etikai elvárások

A hallgatókkal kapcsolatos etikai normákra A DEBRECENI EGYETEM ETIKAI KÓDEXE az irányadó. Az etikai normákat megsértők automatikusan elégtelent kapnak a vizsga során.