David Stanovský    //

MATEMATICKÁ LOGIKA 2016/17

Program: Výroková logika - syntax a semantika, úplnost, kompaktnost Predikátová logika - syntax a semantika, úplnost, kompaktnost, Löwenheim-Skolemovy věty, Vaughtův test, nestandardní modely Nerozhodnutelnost a neúplnost - vyčíslitelné funkce, Turingův stroj, halting problem, Gödelova a Churchova věta o neúplnosti a nerozhodnutelnosti aritmetiky Požadavky ke zkoušce

	program přednášky	doporučená četba	domácí práce
6.10.	Motivace, historie. Výroková logika - krátký úvod.	vdDries 1.1, 2.1 Logicomix	projděte vdDries 1.2, doučte se co nevíte příležitostně si nastudujte axiom výběru
13.10.	Výroková logika - semantika vs. syntax, formulace věty o úplnosti.	vdDries 2.1, 2.2
20.10.	Výroková logika - důkaz věty o úplnosti.	vdDries 2.2	DOMÁCÍ ÚKOL, odevzdat 3.11.
27.10.	Výroková logika - věta o kompaktnosti. Predikátová logika - jazyk, struktura v jazyce.	vdDries 2.2, 2.3
3.11.	Predikátová logika - struktury, termy, formule, semantický důsledek.	vdDries 2.3-2.6
10.11.	Predikátová logika - syntaktický důsledek, dvě formulace věty o úplnosti.	vdDries 2.7, 3.1	DOMÁCÍ ÚKOL, odevzdat 24.11.
24.11.	Důkaz věty o úplnosti - silná a slabá forma, konstrukce modelu.	vdDries 3.1, 3.2
1.12.	Důkaz věty o úplnosti - kdy model funguje, zúplnění, svědci.	vdDries 3.1, 3.2.	DOMÁCÍ ÚKOL, odevzdat 8.12.
8.12.	Dokončení věty o úplnosti. Löwenheim-Skolemova věta.	vdDries 3.2, 4.1
15.12.	Vaughtův test. Věta o kompaktnosti.	vdDries 2.7, 4.1	DOMÁCÍ ÚKOL, odevzdat 5.1.
22.12.	Úvod do nerozhodnutelnosti a neúplnosti. Rekurzivní funkce. Turingův stroj.	vdDries 5.1, 5.2
5.1.	Halting problem. Reprezezentovatelnost rekurzivních funkcí.	wikipedia, vdDries 5.4	DOMÁCÍ ÚKOL, odevzdat 27.1.
12.1.	Gödelova věta o neúplnosti a Churchova věta o nerozhodnutelnosti aritmetiky.	vdDries 5.5, 5.6

V průběhu semestru budou zadávány domácí úkoly. Bude 5 sérií, počítají se 4 nejlepší. Zadání a jejich termíny se budou objevovat průběžně zde.
Z celkových 100 bodů ke zkoušce je možné získat 20 za domácí úkoly a 80 za závěrečný test (standardní termíny během zkouškového období). Stupnice: 75-100 výborně, 65-75 velmi dobře, 55-65 dobře.

Výsledky domácích úkolů

Literature:

• Lou van den Dries, Lecture notes on mathematical logic - podle těchto skript půjde přednáška
• Logicomix - motivace a historické pohnutky ke vzniku formální logiky
• zdroje v češtine:
  • V. Švejdar, Logika: neúplnost, složitost a nutnost, Academia, Praha, 2002.
  • A. Sochor, Klasická matematická logika, Karolinum, Praha, 2001.
  • B. Balcar a P. Štěpánek, Teorie množin, Academia, Praha, 1986.
• více o nerozhodnutelnosti a neúplnosti (nedokazatelnosti):
  • J.R. Shoenfield: Mathematical logic - klasická učebnice
  • E. Mendelson: Introduction to Mathematical Logic
  • H.D. Ebinghaus, J. Flum, W. Thomas: Mathematical Logic, Springer-Verlag 1984
• P. Pudlák, Logical Foundations of Mathematics and Computational Complexity, Springer, 2013 - alternativní přístup ke kurzu základů matematiky