Název:

Logika

Zkratka:LOG
Ak.rok:2012/2013
Semestr:letní
Studijní plán:
ProgramObor/
specializace
RočníkPovinnost
IT-MGR-2MBI-volitelný
IT-MGR-2MBS-volitelný
IT-MGR-2MGM-volitelný
IT-MGR-2MIN-volitelný
IT-MGR-2MIS-volitelný
IT-MGR-2MMI-volitelný
IT-MGR-2MMM-povinný
IT-MGR-2MPV-volitelný
IT-MGR-2MSK1.povinně volitelný - skupina M
Vyučovací jazyk:čeština
Kredity:5 kreditů
Ukončení:zápočet+zkouška
Výuka:
hod./sempřednáškasem./cvič.lab. cvič.poč. cvič.jiná
Rozsah:2626000
 zkouškatestycvičenílaboratořeostatní
Body:60202000
Garant:Šlapal Josef, prof. RNDr., CSc. (UM OADM)
Přednášející:Šlapal Josef, prof. RNDr., CSc. (UM OADM)
Fakulta:Fakulta strojního inženýrství VUT
Pracoviště:Ústav matematiky - odbor algebry a diskrétní matematiky FSI VUT
 
Cíle předmětu:
  Cílem předmětu je seznámit studenty se základními metodami uvažování v matematice. Studenti by si měli zopakovat základy výrokové logiky a seznámit se s axiomatickým přístupem k výrokové logice. Především by si však měli osvojit obecné principy predikátové logiky a získat tak schopnost přesného matematického uvažování a vyjadřování. Závěrem kurzu budou studenti seznámeni s problematikou neúplnosti predikátové logiky včetně slevných Gödelovách vět o neúplnosti.
Anotace:
  V předmětu budou systematicky vyloženy základy výrokové a zejména predikátové logiky. Nejprve budou studenti seznámeni se syntaxí a sémantikou těchto logik, pak budou logiky studovány jako formální teorie s důrazem na problematiku dokazování formulí. Prodiskutovány budou také klasické věty o korektnosti,  úplnosti a kompaktnosti. Po probrání převodu formulí na prenexní tvar budou uvedeny některé vlastnosti a modely teorií 1. řádu.  Závěrem předmětu bude pojednáno o nerozhodnutelnosti teorií 1. řádu vyplývající ze známých Gödelových vět o neúplnosti.
Požadované prerekvizitní znalosti a dovednosti:
  Předpokládají se znalosti získané v předmětu Diskrétní matematika z bakalářského stupně studia.
Získané dovednosti, znalosti a kompetence z předmětu:
  Po absolvování předmětu získají studenti schopnost chápání principů axiomatických matematických teorií i schopnost přesného (formálního) matematického vyjadřování. Naučí se také formálně odvozovat nové formule a dokazovat formule dané. Uvědomí si efektivitu formálního uvažování, ale také jeho hranice.
Dovednosti, znalosti a kompetence obecné:
  Studenti se naučí exaktnímu formálnímu myšlení, které jim umožní provádět korektní a efektivní algoritmizaci řešení zadaných problémů. Také získají schopnost ověřovat správnost již vytvořených algoritmizací (verifikace programů).
Osnova přednášek:
 
  1. Základy teorie množin a kardinální aritmetiky
  2. Jazyk a formule výrokové logiky
  3. Sémantika výrokové logiky 
  4. Formální systém výrokové logiky
  5. Dokazatelnost ve výrokové logice, věta o úplnosti
  6. Jazyk predikátové logiky, termy a formule
  7. Sémantika predikátové logiky
  8. Formální systém predikátové logiky 1. řádu
  9. Dokazatelnost v predikátové logice
  10. Prenexní tvar formulí
  11. Teorie 1. řádu a jejich modely
  12. Věta o úplnosti a o kompaktnosti 
  13. Nerozhodnutelnost teorií prvního řádu, Gödelovy věty o neúplnosti
Osnova numerických cvičení:
 
  1. Relační systémy a univerzální algebry
  2. Množiny, kardinální čísla a kardinální aritmetika
  3. Výroky, výrokové spojky a jejich nezávislost
  4. Pravdivostní tabulky, tautologie a kontradikce
  5. Axiomy a odvozovací pravidlo výrokové logiky
  6. Věta o dedukci a dokazování formulí výrokové logiky
  7. Termy a formule predikátové logiky
  8. Realozace, splnitelnost a pravdivost
  9. Axiomy a odvozovací pravidla predikátové logiky
  10. Věta o dedukci a dokazování formulí v predikátové logice
  11. Převody formulí na prenexní tvar
  12. Teorie 1. řádu a jejich modely
  13. Úplnost a kompaktnost predikátové logiky

 

Literatura referenční:
 
  • E. Mendelson, Introduction to Mathematical Logic, Chapman&Hall, 2001
  • A. Nerode, R.A. Shore, Logic for Applications, Springer-Verlag 1993
  • D.M. Gabbay, C.J. Hogger, J.A. Robinson, Handbook of Logic for Artificial Intelligence and Logic Programming, Oxford Univ. Press 1993
  • G. Metakides, A. Nerode, Principles of logic and logic programming, Elsevier, 1996
  • Melvin Fitting, First order logic and automated theorem proving, Springer, 1996
  • Sally Popkorn, First steps in modal logic, Cambridge Univ. Press, 1994
Literatura studijní:
 
  • E. Mendelson, Introduction to Mathematical Logic, Chapman&Hall, 2001
  • A. Nerode, R.A. Shore, Logic for Applications, Springer-Verlag 1993
  • D.M. Gabbay, C.J. Hogger, J.A. Robinson, Handbook of Logic for Artificial Intellogence and Logic Programming, Oxford Univ. Press 1993
  • G. Metakides, A. Nerode, Principles of logic and logic programming, Elsevier, 1996
  • Melvin Fitting, First order logic and automated theorem proving, Springer, 1996
  • Sally Popkorn, First steps in modal logic, Cambridge Univ. Press, 1994
  • A. Sochor, Klasická matematická logika, Karolinum, 2001
  • V. Švejnar, Logika, neúplnost a složitost, Academia, 2002
Průběžná kontrola studia:
  Kontrolní testy v polovině a na konci semestru.
Podmínky zápočtu:
  Pravidelná docházka na cvičení a úspěšné složení obou kontrolních testů
 

Vaše IPv4 adresa: 184.72.212.254