Verplicht in fase
Optioneel in fase
Eerste semester
Tweede semester
Beide semesters
Niet ingericht
Dit jaar
Volgend jaar
Wisselende jaren
Extern
Voorwaarden
Docenten
Onderwijstaal
Duur
Identieke opleidingsonderdelenLogica voor informatici (B-KUL-G0T42D)
Uitgesloten voor examencontractDoelstellingen
Zich precies kunnen uitdrukken, correct kunnen redeneren, in het abstracte kunnen redeneren zijn essentiele vaardigheden. Ze zijn niet van toepassing, niet alleen in de wiskunde of formele wetenschappen, maar overal waar informatie aanwezig is, waar taken en problemen opgelost moeten worden met die informatie, en waar dus geredeneerd moet worden over de informatie om deze problemen op te lossen. Dat is zeer specifiek het geval in de Informatica. Logica is bij uitstek de wetenschappelijke discipline waarin precieze taal en correct en abstract redeneren bestudeerd wordt. Dit is de motivatie voor deze basiscursus over logica en de rol ervan in de informatica.
De doelstellingen van deze cursus betreffen enerzijds het aanleren van deze basisvaardigheden, zowel op het informele niveau, gebruikmakend van precieze informele taal zoals in wiskunde en formele wetenschappen, als op een formeel niveau, gebruikmakend van een formele taal; anderzijds het aanleren van basiskennis over logica die verderop in de opleiding van nut is.
Vaardigheden:
- informatie op een precieze manier uitdrukken, zowel in informele precieze taal als in formele taal;
- inzicht in precieze taal, bv. equivalente manieren om eigenschappen te formuleren, vermijden van ambiguiteiten, correct formuleren van definities en eigenschappen;
- correct redeneren, zowel in informele wiskundige taal als in de context van formele taal: bewijzen van wiskundige eigenschappen in de context van logica, gebruik van definities in bewijzen, formele bewijstheorie, berekenen van waarheidswaarde, van consistentie, van logische gevolgen in formele taal. Vaardigheid in correct redeneren zoals bewijzen van eigenschappen is een weg naar diep inzicht;
- analyseren van computationele problemen in relatie tot de beschikbare informatie. In een informatica-context is dit de analyse van hoe informaticaproblemen op te lossen door middel van verschillende modi van inferentie op logische theorieen.
- abstractievermogen: logisch redeneren is bij uitstek redeneren in het abstracte.
Kennis:
- Kennis van propositie- en predicatenlogica, bewijsheorie, onderwerpen die in verschillende cursussen in de verdere opleiding terugkeren zowel impliciet als expliciet (bv. databanken, declaratieve talen, modellering van complexe systemen, formele methodes, artificiele intelligentie).
Begintermen
Een degelijk niveau wiskunde (niveau 6 uur wiskunde in het middelbaar onderwijs)
Volgtijdelijkheidsvoorwaarden
Dit opleidingsonderdeel is een voorwaarde voor het opnemen van volgende opleidingsonderdelen:
G0V47B : Objectgericht programmeren
G0U41A : Bewijzen en redeneren voor informatici
Plaats in het onderwijsaanbod
Onderwijsleeractiviteiten
2.5 sp. Logica voor informatici (B-KUL-G0T42a)
Inhoud
I Predikatenlogica- De predikatenlogicataal; vrije en gebonden variabelen.
- Structuren en interpretaties, semantiek.
- Predikatenlogica met functiesymbolen.
- Uitgebreide oefeningen over het interpreteren van logische formules in concrete situaties. Vertalen uit het Nederlands naar de predikatenlogica. Gebruik van didactische software (bijvoorbeeld LogicPalet met o.a. Tarski’s World en DecaWorld) om deze aspecten in te oefenen (zelfstudie).
- Logisch ware formules, logische gevolgen van een verzameling formules, modellen van een verzameling formules, satisfieerbaarheid, inconsistentie.
- Lijst van de belangrijkste logisch ware formules: negatie van kwantoren, doorschuiven en verwisselen van kwantoren, naamverandering van kwantoren, prenex normaalvorm.
- Maken van oefeningen over ’al dan niet logisch waar’ en over ’al dan niet logisch gevolg’: methode van het gezonde verstand. Oefeningen met de hierboven vermelde software.
- Bewijzen van logische gevolgen, door middel van formele methoden: Formele bewijsmethode door middel van waarheidsbomen (tableaux), ondersteund door didactische software. Toepassing: automatisch redeneren.
- Formulering van de volledigheidsstelling van Goedel.
- Toepassing van logica in kennisrepresentatie.
-- onvolledige kennis in logica
-- de "gesloten domeinaanname" en de "unieke naamaxioma’s"
-- definities en predikatevervollediging
-- toepassing van predikatenlogica voor een concreet probleem (b.v. het modelleren van een scheduling probleem)
II Onbeslisbaarheid en de onvolledigheidsstelling van Goedel
- Een computermodel en de onbeslisbaarheid van het stopprobleem.
- Onbeslisbaarheid van de natuurlijke getallen en van de predikatenlogica (zonder bewijzen).
- Formulering van de onvolledigheidsstelling van Goedel.
III De rol van Logica in de Informatica
A. Gegegevensbanken
- Predikatenlogica als query-taal voor databases: ja-nee queries, queries van verzamelingen
- Predikatenlogica als taal voor integriteitsbeperkingen
- null-values door middel van Predikatenlogica
- logische equivalentie van queries en het princiepe van queryoptimalisatie
- het recursieve query algoritme voor "veilige" queries
B. Redeneren over software
- beschrijven van programmafragmenten in logica
- transacties, precondities, postcondities, toestandsafhankelijke predikaten, invarianten, invarianten als logisch gevolg van pre- en post-condities
- gebruik van automatisch redeneren voor het verifieren van de geldigheid van invarianten
2.5 sp. Logica voor informatici: oefenzittingen (B-KUL-G0T43a)
Inhoud
Zie hoorcollege
Toelichting werkvorm
De studenten maken pen-en-papier oefeningen of oefeningen op een software tool die hun beschikbaar gesteld wordt, en dit op alle aspecten die in de doelstellingen van het OPO worden verwoord, met uitzonderingen van de theoretische grondslagen.
Het practicum is een verplichte gekwoteerde oefenzitting met een aantal oefeningen in LogicPalet.
Er zijn twee verplichte bewijsoefeningen. Studenten krijgen een stelling en moeten deze bewijzen. Het doel is om het analytisch denken en de taal van bewijsvoering te oefenen. Ze werken samen in groepjes van 2 en krijgen persoonlijke feedback.
Evaluatieactiviteiten
Evaluatie: Logica voor informatici (B-KUL-G2T42d)
Toelichting
- 1 examen voor theorie en oefeningen samen.
- Volledig schriftelijk en gesloten boek.
- Geen studiemateriaal behalve een (onbeschreven) formularium.
- Duurt maximaal 4 uren.
- Meenemen naar het examen: studentenkaart, (onbeschreven) formularium, schrijfgerief ( geen pennenzak, geen ander papier dan het formularium), eten en drinken.
Het examen bevat een theoriegedeelte en een oefeningengedeelte. Het oefeningengedeelte staat op iets meer dan de helft van de punten. Het theoriegedeelte bestaat uit een aantal vragen over definities, stellingen en bewijzen, en uit vragen hoe bepaalde informaticaproblemen kunnen geformuleerd en opgelost worden met methodes uit de logica.
De Toledo-pagina van de cursus bevat informatie over zowel de theoretische vragen als de oefeningenvragen.