Modale Logica & Kennisrepresentatie 99-00

college stof

Iedere week zijn er twee hoorcolleges en een werkcollege Modale Logica & Kennisrepresentatie. Op dinsdagen is er een hoorcollege van 15:00 tot 17:00. Op vrijdagen is er eerst een hoorcollege van 13:00 tot 15:00 gevolgd door een werkcollege van 15:00 tot 17:00.

Het collegemateriaal bestaat uit een syllabus die verkrijgbaar is bij de onderwijsadministratie (dezelfde als vorig jaar, met enige kleine correcties), aangevuld met handouts over volledigheid van afleidingssystemen voor propositielogica en modale logica's.

De tentamenstof beslaat alle behandelde stof. Tentamensommen over de stof uit de syllabus zullen van vergelijkbare moeilijkheidsgraad zijn als de sommen in de syllabus. Tentamens van voorgaande jaren (met name die van vorig jaar) geven natuurlijk ook een goede indicatie. Het tentamencijfer is tevens het eindcijfer. Door het volgen van `alle' (zeg, 5 van de 6) werkcolleges en het voldoende maken van een literatuuropdracht, kan vrijstelling van 1 (op het tentamen aangegeven) som ter waarde van een 1/4 van het totaal aantal punten verkregen worden. Dwz als aan beide voorwaarden voldaan is, krijgt de student automatisch alle punten voor die opgave toegewezen. Het tentamen vindt plaats op maandag 22 oktober in een nader bekend te maken zaal. De vrijdag ervoor, 19 oktober, is er op collegetijd een vragenuur in een nader bekend te maken zaal.

Vragen en opmerkingen kunnen altijd gericht worden aan:

Docent (hoorcolleges)

Vincent van Oostrom (ma,di,vr: BG 441a, 030-2532761)

Studentassistent (werkcolleges)

Jeroen van der Ham, vdham@phil.uu.nl

Modale Logica & Kennisrepresentatie

literatuur: syllabus
hoorcollege dinsdag 7 september, syllabus blz. 1 tot en met 9
- syntax: modale formules, noodzakelijk (box), mogelijk (diamond)
- semantiek: Kripke (mogelijke werelden) semantiek, frames, toestand, toegankelijkheidsrelatie, toekenning (valuatie), model
- waarheid van een modale formule in een model in een toestand, waarheid in een model, geldigheid in een frame
- (een beetje) karakterisering van frames dmv formules
hoorcollege vrijdag 10 september, reader blz. 9 tot en met 15
- karakteriseerbaarheid van klassen van frames (vervolg)
- karakteriseerbaarheid transitiviteit met bewijs
- bisimulatie
- preservatie van waarheid onder bisimulatie (met bewijs)
- temporele logica
- temporeel frame (tijdsstructuur): irreflexief en transitief frame
werkgroep vrijdag 10 september, syllabus blz. 1 tot en met 9
- opgaven: 1.1, 1.2, 1.3, 1.4
hoorcollege dinsdag 14 september, reader blz 15 tot 19
- intuitieve interpretaties: [] = voortaan, <> = ooit
- lineaire vs vertakkende tijd
- karakterisering van lineaire tijd
- niet karakteriseerbaarheid van vertakkende tijd
hoorcollege vrijdag 17 september, reader blz 19 tot 26
- operator: toekomst (Future,<>F) en verleden (Past, <>P)
- logica met <>F en <>P is expressiever dan logica met alleen <>F
- computationele temporele logica: tijdsstructuur N
- operator: until (U)
- logica met U is expressiever dan logica met alleen <>
werkgroep vrijdag 17 september, reader blz. 9 tot 19
- opgaven: 1.4, 1.5, 1.6, 1.7, 1.8, 1.9, 2.1, 2.2, 2.3
hoorcollege dinsdag 21 september, reader blz 32 tot 34
- operator: kenner i weet phi (Ki phi)
- informele afleiding van cheating husbands/muddy children redenering
- epistemische logica: afleidingssysteem K^n voor epistemische formules
  klassieke tautologie, distributie, universele generalisatie, modus ponens, substitutie
- formele afleiding in K^n van een stap in de muddy children redenering
werkgroep vrijdag 24 september, reader blz. 21 tot 34
- opgaven 2.4 tot en met 2.10 en evt. 3.1
hoorcollege dinsdag 28 september, reader blz 34 tot 42
- afgeleide regels : regels van klassieke natuurlijke deductie (introductie, eliminatie regels voor intersectie), als phi -> psi en psi -> chi, dan psi -> chi
- axiomatiek: waarheidsaxioma (A1,T), positieve introspectie (A2,S4), negatieve introspectie (A3,S5)
- platslaan van K's en negaties in S5
- semantiek van epistemische logica: Kripke semantiek waarbij K `is' een box en iedere agent (i) heeft z'n eigen bereikbaarheidsrelatie (R_i)
- correctheid en volledigheid van afleidingssystemen tov van verzamelingen frames (alleen correctheid bewezen)
  (A1 <=> reflexief, A2 <=> transitief, A3 <=> euclidisch)
hoorcollege vrijdag 1 oktober, reader blz 42 tot eind
- uitgebreide epistemische taal voor algemene en gemeenschappelijke kennis
- E(very body) en C(ommon knowledge)
- constructies van bereikbaarheidsrelaties (semantiek) voor E en C uit die voor de K_i (vereniging, en transitieve afsluiting)
- correctheid en volledigheid stellingen voor uitgebreide epistemische logica's
werkgroep vrijdag 1 oktober, reader blz 30 tot eind
- opgaven 3.1 tot en met 3.13 (alleen 3.1 tot en met 3.3 behandeld)
werkgroep dinsdag 5 oktober reader blz 42 tot eind
- restant opgaven uit reader
hoorcollege vrijdag 8 oktober, Secties 1.4 en 1.5 uit `Logic and Structure', Dirk van Dalen, Third Edition, Universitext, Springer-Verlag, ISBN 3-540-57839-0.
- recapitulatie natuurlijke deduktie voor en semantiek van propositielogica
- tweetraps bewijs van volledigheidsstelling: Gamma |-/- phi => Gamma u { neg phi } consistent => Gamma |=/= phi
- consistentie van een verzameling formules
- voorbeelden van consistente verzamelingen: verzameling formules die vervulbaar is
- bewijs eerste implicatie van volledigheidsbewijs mbv de reductie ad absurdum bewijsregel
- maximaal consistente verzameling
- bestaan van maximaal consistente verzamelingen (mcs)
- eenvoudige eigenschappen van mcs Gamma: gesloten onder afleidbaarheid, neg phi in Gamma <=> phi niet in Gamma, phi /\ psi in Gamma <=> phi in Gamma en psi in Gamma.
werkgroep vrijdag 8 oktober, reader blz 42 tot eind
- dedukties
hoorcollege dinsdag 12 oktober, Secties 1.4 en 1.5 uit `Logic and Structure', Dirk van Dalen, Third Edition, Universitext, Springer-Verlag, ISBN 3-540-57839-0. en Hoofdstuk 4, Completeness, uit een boek in wording Modal Logic, Patrick Blackburn, Maarten de Rijke, en Yde Venema.
- `truth-as-membership' valuatie en `truth-as-membership' model (inductie naar opbouw van formules).
- bewijs tweede implicatie mbv constructie van het truth-as-membership model van een mcs-uitbreiding van Gamma u { neg phi }
- uitleg van bekende begrippen zoals: modale logica, consistentie, geldigheid, normale modale logica zoals gedefinieerd in de handout
- verschil tussen natuurlijke deductie en hilbert-style afleidingssysteem
- bewijs van de eerste implicatie van volledigheid voor modale logica's mbv modus ponens en neg neg p <-> p.
hoorcollege vrijdag 15 oktober, Hoofdstuk 4, Completeness, uit een boek in wording Modal Logic, Patrick Blackburn, Maarten de Rijke, en Yde Venema.
- Herhaling van bewijs van de tweede implicatie in volledigheidsbewijs voor propositielogica, nu voor normale modale logica's.
  - consistentie van een verzameling formules
  - voorbeelden van consistentie behoudende constructies: doorsnede.
  - maximaal consistente verzameling
  - bestaan van maximaal consistente verzamelingen (mcs) (Lindenbaum's Lemma)
  - eenvoudige eigenschappen van mcs Gamma: gesloten onder afleidbaarheid, neg phi in Gamma <=> phi niet in Gamma, phi /\ psi in Gamma <=> phi in Gamma en psi in Gamma.
- constructie canonical model: wereld = mcs, wereld w bereikbaar vanuit v als voor alle phi []phi in v => phi in w, truth-as-membership valuatie.
- bewijs van truth lemma (`truth-as-membership')
- bewijs tweede implicatie mbv constructie van het truth-as-membership model van een mcs-uitbreiding van Gamma u { neg phi }
- toepassing van volledigheidsbewijs op enige normale modale logica's: K, T, S4, S5.
werkgroep vrijdag 15 oktober
- bespreking tentamen en hertentamen van vorig jaar