Logik II

10 hp

Kursplan, Grundnivå, 1MA028

Kursen är avvecklad.

Det finns en senare version av kursplanen.

Kod: 1MA028
Utbildningsnivå: Grundnivå
Huvudområde(n) med fördjupning: Datavetenskap G2F, Matematik G2F
Betygsskala: Med beröm godkänd (5), Icke utan beröm godkänd (4), Godkänd (3), Underkänd (U)
Fastställd av: Teknisk-naturvetenskapliga fakultetsnämnden, 14 december 2009
Ansvarig institution: Matematiska institutionen

Behörighetskrav

60 hp matematik/datavetenskap inklusive Algebra II, Logik och bevisteknik I

Mål

För godkänt betyg på kursen skall studenten

kunna redogöra för grundläggande begrepp inom rekursionsteori och modellteori;

ha förståelse av begreppet ofullständighet och kunna redogöra för Gödels ofullständighetssats;

kunna exemplifiera och tolka viktiga begrepp i konkreta situationer;

kunna formulera viktigare resultat och satser inom kursens område, samt beskriva huvuddragen i viktigare satsers bevis;

använda kursens teori, metoder och tekniker för problemlösning;

presentera matematiska resonemang för andra.

Innehåll

Elementär rekursionsteori: primitivt rekursiva funktioner och partiella rekursiva funktioner, egenskaper hos rekursiva och rekursivt numrerbara mängder, s-m-n-satsen, andra rekursionssatsen, något om den aritmetiska hierarkin och om relativ beräkningsbarhet.

Styrkan hos första ordningens teorier. Modeller för teorier, Tarskisemantik, fullständighetssatsen och kompakthetssatsen. Gödels ofullständighetssatser.

Modellteori: isomorfi, delstruktur, elementär ekvivalens och elementär delstruktur, Löwenheim– Skolemsatserna, Ehrenfeucht–Fraissespel, modellfullständighet, fullständiga teorier, algebraiska tillämpningar, icke-standard-modeller.

Undervisning

Föreläsningar och räkneövningar.

Examination

Skriftligt och eventuellt muntligt prov vid kursens slut eventuellt kombinerat med inlämningsuppgifter under kursen enligt anvisningar som lämnas vid kursens start.

Logik II

Behörighetskrav

Mål

Innehåll

Undervisning

Examination

Litteraturlista