Logica en formele systemen

6 ECTS credits
180 u studietijd

Aanbieding 2 met studiegidsnummer 1000447ANR voor alle studenten in het 1e semester met een inleidend bachelor niveau.

Semester

1e semester

Inschrijving onder examencontract

Niet mogelijk

Beoordelingsvoet

Beoordeling (0 tot 20)

2e zittijd mogelijk

Onderwijstaal

Nederlands

Faculteit

Faculteit Wetenschappen en Bio-ingenieurswetensch.

Verantwoordelijke vakgroep

Computerwetenschappen

Onderwijsteam

Ann Nowe (titularis)

Onderdelen en contacturen

0 contacturen Exam
26 contacturen Lecture
26 contacturen Practical exercises
120 contacturen Self study

Inhoud

Dit opleidingsonderdeel bestaat uit drie delen:

Een eerste deel van de cursus herhaalt kort de belangrijkste wiskundige bewijstechnieken die later in de cursus gebruikt zullen worden: bewijs door contrapositie, bewijs uit het ongerijmde, bewijs per inductie.

Het tweede deel van deze cursus bestaat uit een inleiding tot de formele logica, waarbij ook de nadruk gelegd wordt op de aspecten die relevant zijn voor de informatica.

De volgende onderwerpen komen daarbij aan bod:

- Motivatie: logica en informatica.

- Propositielogica: syntaxis en semantiek, logisch gevolg en semantische tableaus, afleidingen (natuurlijke deductie, axiomatisch afleiden), adequaatheid en volledigheid.

- Predicaatlogica: syntaxis en semantiek, logisch gevolg en semantische tableaus, afleidingen (natuurlijke deductie, axiomatisch afleiden), adequaatheid en volledigheid theorieën en normaalvormen.

Het derde gedeelte is een inleiding tot de lambda-calculus. Hier ligt de nadruk op het verband met de functionele programmeertaal Scheme (die gebruikt wordt als inleidende programmeertaal in de bachelor opleiding Computerwetenschappen): oorsprong, lambda-expressies, currying, vrije en gebonden variabelen, substitutie, reductie, Church-getallen, lambda-defineerbaarheid, fixpunten en recursieve definities, lambda-calculus als een programmeertaal.

Studiemateriaal

Digitaal cursusmateriaal (Vereist) : Logica voor informatica, J.F.A.K. van Benthem, H.P. van Ditmarsch, J. Ketting, J.S. Lodder & W.P.M Meyer-Viol, 3de, http://resources.illc.uva.nl/lvi/, 2003

Bijkomende info

Bijkomende informatie (uurrooster, assistenten, contactinformatie, inleverdata, opdrachten, oefeningen, ...) kan gevonden worden via het leerplatform.

De cursus (behalve het gedeelte over Lambda calculus) is gebaseerd op het volgende boek:
J.F.A.K. van Benthem, H.P. van Ditmarsch, J. Ketting J.S. Lodder & W.P.M. Meyer-Viol (2003) Logica voor Informatica, 3de editie, Addison-Wesley.
De behandelde hoofdstukken zijn 1 -12. Het boek is niet meer verkrijgbaar in de handel, maar een on-line versie is beschikbaar via http://resources.illc.uva.nl/lvi/

Het materiaal (transparanten) dat tijdens de hoorcolleges gebruikt wordt om de theorie toe te lichten, een beschrijving van Lambda Calculus en een oefeningenbundel zijn verkrijgbaar in dictaatvorm

Opnamen van de lessen (voor o.a. werkstudenten) zijn beschikbaar via het leerplatform.

Een educatief spel is beschikbaar voor het inoefenen van de logisch tabellen (info via het leerplatform).

Al het bovenvermelde studiemateriaal is in het Nederlands

Aanvullend studiemateriaal (in Engels):
R.P. Grimaldi (2017) Discrete and Combinatorial Mathematics , An applied introduction, third edition, Addison-Wesley.

D.R. Hofstadter (1979) Goedel, Escher, Bach, The Harvester
Press, US.

G. Révész (1988) Lambda-Calculus, Combinatorics, and Functional Programming, Cambridge University Press, UK.

Leerresultaten

Algemene competenties

De leerresultaten zijn:
De studenten hebben een basiskennis van logica, meer bepaald propositie- en predicaatlogica.
Zij kunnen deze kennis aanwenden voor het formuleren en oplossen van problemen en gebruiken om andere soorten logica zelfstandig te leren.
De studenten kennen het verband tussen formele systemen, zoals lambda calculus, en programmeren.

De hieraan gekoppelde specifieke leerresultaten zijn:
Op het vlak van:

Kennis en het inzicht:
Syntax en semantiek van de propositielogica en de predicaatlogica kennen en verstaan.
Het concept logisch gevolg en de daaraan gerelateerde concepten kennen en verstaan, voor zowel de propositielogica als de predicaatlogica.
De bewijstechniek semantisch tableaus kennen en verstaan, voor zowel de propositielogica als de predicaatlogica.
Het systeem van natuurlijke deductie kennen en verstaan, voor zowel de propositielogica als de predicaatlogica.
De adequaatheidsstelling, voor zowel de propositielogica als de predicaatlogica kennen, verstaan en kunnen bewijzen (enkel voor propositielogica).
De volledigheidsstelling, voor zowel de propositielogica als de predicaatlogica kennen, verstaan en kunnen bewijzen (enkel voor propositielogica).
Het verschil kennen en verstaan tussen de propositielogica en de predicaatlogica.
De basisbegrippen van de lambda calculus kennen en verstaan.
Het verband tussen lambda calculus en de programmeertaal Scheme kennen en verstaan.

Toepassing van de kennis en het inzicht:
Over de hierboven vermelde onderwerpen oefeningen kunnen oplossen; eenvoudige situaties en problemen kunnen uitdrukken in termen van de propositie- of predicaatlogica en kunnen oplossen.
Lambda expressies kunnen uitwerken.

Oordeelvorming:
Keuze kunnen maken over het te gebruiken formalisme voor eenvoudige oefeningen en problemen.

Communicatie:
Zich duidelijk schriftelijk kunnen uitdrukken over de hierboven opgesomde onderwerpen.

Leervaardigheden:
Vertrekkend van de opgedane basiskennis, andere logische systemen kunnen leren.

Beoordelingsinformatie

De beoordeling bestaat uit volgende opdrachtcategorieën:
Examen Schriftelijk bepaalt 95% van het eindcijfer

ZELF Praktijkopdracht bepaalt 5% van het eindcijfer

Binnen de categorie Examen Schriftelijk dient men volgende opdrachten af te werken:

exm schriftelijk met een wegingsfactor 95 en aldus 95% van het totale eindcijfer.

Toelichting: Dit is een gesloten boek examen en omvat per onderdeel (propositielogica, predicaatlogica en lambda calculus) ten minste een theorievraag en een oefening. De theorievragen toetsen kennis en inzicht, de oefeningen toetsen het kunnen toepassen van de kennis.

Binnen de categorie ZELF Praktijkopdracht dient men volgende opdrachten af te werken:

taak predicaatlogica met een wegingsfactor 5 en aldus 5% van het totale eindcijfer.

Aanvullende info mbt evaluatie

In de loop van het semester moet een huistaak ingediend worden.

In week 6 of 7 wordt een tussentijdse evaluatie (proefexamen) georganiseerd die over het gedeelte propositielogica handelt. Deelname aan deze tussentijdse evaluatie is verplicht.

In de zittijd na het eerste semester is er een verplicht schriftelijk examen. Wanneer de student 14 of meer haalt op de tussentijdse evaluatie kan de student een vrijstelling opnemen bij dit examen voor het gedeelte propositielogica (opnemen van de vrijstelling is niet verplicht). De vrijstelling geldt niet voor de 2de zittijd (aug-sept).

Het schriftelijk examen is een gesloten boek examen en omvat per onderdeel (propositielogica, predicaatlogica en lambda calculus) ten minste een theorievraag en een oefening. De theorievragen toetsen kennis en inzicht, de oefeningen toetsen het kunnen toepassen van de kennis.

Toegestane onvoldoende

Kijk in het aanvullend OER van je faculteit na of een toegestane onvoldoende mogelijk is voor dit opleidingsonderdeel.

Academische context