Předmět Matematická logika pro obor alg. a geom. (KMI / PGSMA)

Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu KMI / PGSMA - Matematická logika pro obor alg. a geom., Přírodovědecká fakulta, Univerzita Palackého v Olomouci (UP).

Materiál	Typ	Datum	Počet stažení

Obsah

Důraz je kladen na věty o úplnosti těchto logik a na zvládnutí související teorie tak, aby byli studenti připraveni na studium jiných logických kalkulů, případně na jejich aplikace v informatice (analýza dat, relační databáze, a podobně). Zařazeny jsou však i pokročilejší partie z logiky.1. Úvod a výroková logikaPředmět logiky: logika v průniku řady disciplín, historický vývoj, matematická logika, význam pro informatiku.Výroková logika: jazyk výrokové logiky, formule, pravdivostní ohodnocení, pravdivostní ohodnocení formulí, sémantické vyplývání, tautologie, splnitelné formule, normální formy, tabulková metoda.Axiomatický systém VL: axiomy, odvozovací pravidla, pojem důkazu, věty o dedukci, o nahrazení, o ekvivalenci, o neutrální formuli. Teorie, bezespornost, věta o korektnosti a úplnosti (slabá a silná verze).2. Základní pojmy predikátové logikyPredikátová logika: jazyk, termy, formule a základní syntaktické pojmy; sémantika: struktury pro predikátovou logiku, ohodnocení, ohodnocení termů a formulí, tautologie, splnitelné formule, sémantické vyplývání a základní sémantické pojmy, struktura a model teorie.Axiomatický systém PL: axiomy, odvozovací pravidla, pojem důkazu, věta o dedukci, rozšíření a konzervativní rozšíření, věta o konstantách, věta o variantách, bezespornost. Jazyky s rovností.3. Úplnost predikátové logikyVěta o korektnosti. Úplnost PL: henkinovská teorie a věta o henkinovském rozšíření, úplná teorie a věta o zúplnění. Modely z konstant, věta o kanonické struktuře, věta o úplnosti. Věta o kompaktnosti. Omezení PL: vlastnosti struktur, které nelze vyjádřit teoriemi prvního řádu (např. konečnost modelů). Prenexní tvar formule, Hilbert-Ackermannova věta, Herbrandova věta.4. Vybrané negativní výsledky v logice.Neúplnost (Goedelovo číslování, aritmetizace logiky, první Goedelova věta o neúplnosti), nerozhodnutelnost (a rozhodnutelnost) vybraných problémů v logice.5. Úvod do vybraných rozšíření klasické logiky.Modální a temporální logiky, fuzzy logiky, pravděpodobnostní logiky.

Získané způsobilosti

2. PorozuměníPopsat a důkladně pochopit principy a metody matematické logiky.

Literatura

Mendelson E. Introduction to Mathematical Logic. Chapman & Hall, UK (fourth edition), 1997. ISBN 0-412-80830-7.Sochor A. Klasická matematická logika. Karolinum, Praha, 2001. ISBN 80-246-0218-0.Nerode A., Shore R. A. Logic for Applications. Springer-Verlag, New York (second edition), 1997. ISBN 0-387-94893-7.Švejdar V. Logika: neúplnost, složitost a nutnost. Academia, Praha, 2002. ISBN 80-200-1005-X.Zhongwan L. Mathematical Logic for Computer Science. World Scientific (druhé vydání), 1998. ISBN 981-02-3091-5.Ben-Ari M. Mathematical Logic for Computer Science. Springer-Verlag, London (druhé vydání), 2001. ISBN 1-85233-7.Chaitin G. J. The Limits of Mathematics. Springer-Verlag, Singapore (druhé vydání), 1998. ISBN 981-3083-59-X.

Požadavky

Aktivní účast v hodině. Plnění zadaných úkolů. Složení ústní (příp. písemné) zkoušky.

Garant

prof. RNDr. Radim Bělohlávek, Ph.D., DSc.