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

26 contacturen Hoorcollege
26 contacturen Werkcolleges, practica en oefeningen
120 contacturen Zelfstudie en externe werkvormen

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.

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 georganiseerd die over het gedeelte propositielogica handelt. Deelname aan deze tussentijdse evaluatie is verplicht voor generatie studenten.

In de zittijd na het eerste semester is er een verplicht schriftelijk examen. Wanneer de student 14 of meer behaalt op de tussentijdse evaluatie kan de student de voorkeur geven om het gedeelte propositielogica (deel 1) niet te hernemen. In dit geval wordt de score van het schriftelijk examen bepaald op basis van predikaatlogica (deel 2 ) en Lambda-calculus (deel 3). In de 2de zittijd (aug-sept) worden steeds de 3 delen geexamineerd.

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