Behörighetskrav

Algebra DV1.

Syfte

Kursen ska ge färdighet i att formulera

matematiska och vardagliga påståenden i exakta

logiska termer, genomföra stringenta matematiska

bevis och resonera med modeller. Särskild vikt ska

läggas vid den logiska behandlingen av grafer,

relationer och induktiva datastrukturer.

Innehåll

Informell logik: konnektiv och kvantorer. Formalisering

och precisering av naturliga språk. Boolesk algebra.

Diskreta strukturer: grafer, partiella ordningar,

välordningar och induktiva datastrukturer.

Lambdakalkyl och typer.

Satslogik och predikatlogik. Disjunktiv och

konjunktiv normalform. Prenex normalform. Modell

och motmodell. Axiomatik: konsistens och oberoende.

Begreppen sundhet och fullständighet.

Naturlig deduktion. Direkt och indirekt bevis:

klassisk logik och något om intuitionistisk logik.

Indirekta definitioner. Samband mellan rekursion

och induktion.

Orientering om Gödels ofullständighetssats,

automatisk bevissökning.

Undervisning

Föreläsningar, lektioner, räkneövningar och

laborationer.

Examination

Ett skriftligt och eventuellt ett muntligt prov

ges vid kursens slut. Obligatoriska uppgifter kan

förekomma i samband med undervisningen. För

studerande som underkänts i prov anordnas extra

provtillfällen i augusti och vid höstterminens

eller vårterminens slut.