Název:

Matematická logika

Zkratka:

MLD

Ak.rok:

2010/2011

Semestr:

letní

Studijní plán:

Program	Obor	Ročník	Povinnost
VTI-DR-4	DVI4	-	volitelný

Vyučovací jazyk:

čeština

Ukončení:

zkouška (kombinovaná)

Výuka:

hod./sem	přednáška	sem./cvičení	lab. cvičení	poč. cvičení	jiná
Rozsah:	26	0	0	0	0
	zkouška	testy	cvičení	laboratoře	ostatní
Body:	100	0	0	0	0

Garant:

Šlapal Josef, prof. RNDr., CSc., ÚM OADM

Přednášející:

Šlapal Josef, prof. RNDr., CSc., ÚM OADM

Cvičící:

Pavlík Jan, Mgr., Ph.D., ÚM 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 osvojit obecné principy predikátové logiky a získat tak schopnost přesného matematického uvažování a vyjadřování. Také by se měli naučit pracovat s některými dalšími důležitými formálními teoriemi využívanými v informatice.

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. Pozornost bude také věnována nerozhodnutelnosti teorií 1. řádu vyplývající ze známých Gödelových vět o neúplnosti. Závěrem předmětu bude pojednáno o některých dalších významných logikách, které nacházejí uplatnění v informatice.

Požadované prerekvizitní znalosti a dovednosti:

Předpokládají se znalosti získané v předmětech Diskrétní matematika v bakalářském stupni studia a Matematické struktury v informatice v magisterském stupni studia.

Získané dovednosti, znalosti a kompetence z předmětu:

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ů).

Dovednosti, znalosti a kompetence obecné:

Osnova přednášek:

Základy teorie množin a kardinální aritmetiky
Jazyk, formule a sémantika výrokové logiky
Formální systém výrokové logiky
Dokazatelnost ve výrokové logice, věta o úplnosti
Jazyk predikátové logiky, termy a formule
Sémantika predikátové logiky
Formální systém predikátové logiky 1. řádu
Dokazatelnost v predikátové logice
Věta o úplnosti a o kompaktnosti, prenexní tvar formulí
Teorie 1. řádu a jejich modely
Nerozhodnutelnost teorií prvního řádu, Gödelovy věty o neúplnosti
Teorie 2. řádu (monadická logika, SkS a WSkS)
Některé další logiky (intuicionistická, modální a temporální logika, Presburgerova aritmetika)

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

Nacházíte se v sekcích

Matematická logika