Modale Logica & Kennisrepresentatie 98-99

college stof

Iedere week zijn er twee colleges Modale Logica & Kennisrepresentatie, een op maandag en een op vrijdag. Op dinsdag (niet op donderdag!) is er een werkgroep (voor 2 colleges dus). In de derde week wordt een literatuuropdracht gegeven. Een artikel uit de recente AI literatuur dient bestudeerd te worden. Voor het tentamen dient een samenvatting ingeleverd te worden. Daarin staat in ieder geval wat voor soort modale logica in het artikel gebruikt wordt en hoe deze in de op het college besproken hierarchie (K,T,S4,S5) past (en waarom, of waarom niet).

Het hertentamen vindt plaats op dinsdag 5 januari van 14:00 tot 17:00 in zaal 311 van het Unnik Gebouw. De tentamenstof beslaat alle behandelde stof (zie de onderstaande samenvatting van het college voor details). Tentamensommen over de stof uit de reader zullen van vergelijkbare moeilijkheidsgraad zijn als de sommen in de reader. Ter indicatie van de moeilijkheidsgraad van tentamensommen over het resterende gedeelte van de stof, staan hier enige voorbeeldsommen. Ook het tentamen geeft natuurlijk een goede indicatie.

Vragen en opmerkingen kunnen gericht worden aan:

Docent

Vincent van Oostrom

Modale Logica & Kennisrepresentatie

literatuur: reader (nieuw ten opzichte van vorig jaar!)
hoorcollege maandag 31 augustus, reader 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
werkgroep dinsdag 1 september, reader blz. 1 tot en met 9
- opgaven: 1.1, 1.2, 1.3
hoorcollege vrijdag 4 september, reader blz. 9 tot en met 13
- karakteriseerbaarheid van klassen van frames (vervolg)
- karakteriseerbaarheid: reflexiviteit, symmetrie en transitiviteit (met bewijzen)
- bisimulatie
- preservatie van waarheid onder bisimulatie (met bewijs)
hoorcollege maandag 7 september, reader blz 14 tot 21
- temporele logica
- temporeel frame (tijdsstructuur): irreflexief en transitief frame
- intuitieve interpretaties: [] = voortaan, <> = ooit
- lineaire vs vertakkende tijd
- karakterisering van lineaire tijd
- dichte vs discrete tijd
- karakterisering van dichte tijd
- vb van tijdsstructuren: N, Q, R
- (een beetje) toekomst en verleden
werkgroep dinsdag 8 september, reader blz. 9 tot 21
- opgaven: 1.4, 1.5, 1.6, 1.7, 1.8, 1.9, 2.1, 2.2, 2.3, 2.4 (laatste alleen kijken)
hoorcollege vrijdag 11 september, reader blz 21 tot 32
- 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 <>
- epistemische (kennis) logica
- cheating husbands (muddy children).
hoorcollege maandag 14 september, reader blz 32 tot 34
- terzijde: niet phi U phi is niet equivalent met true U phi
- operator: kenner i weet phi (Ki phi)
- informele afleiding van 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 dinsdag 15 september, reader blz. 21 tot 34
- opgaven 2.4 tot en met 2.10 en 3.1
hoorcollege vrijdag 18 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 <=> reflexieve, A2 <=> transitief, A3 <=> euclidisch)
hoorcollege maandag 21 september, 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
- restant opgaven, 2.7 tot en met 2.10, temporele logica behandeld
werkgroep dinsdag 22 september, reader blz 30 tot eind
- opgaven 3.1 tot en met 3.13 (alleen 3.1 tot en met 3.3 behandeld)
hoorcollege vrijdag 25 september, hoofdstuk 4 uit boek in wording
- logica, normale logica, afleidbaarheid
- (normale) logica gegenereerd door een verzameling formules
  bestaat vanwege geslotenheid onder doorsnede van (normale) logica's
- voorbeelden van logica's (K,T, etc)
- Lambda-(in)consistentie
- correctheid en (zwakke, sterke) volledigheid
- volledigheidsstelling (alleen formulering)
- maximaal consistente verzamelingen
- lindenbaum's lemma
hoorcollege maandag 28 september, vervolg volledigheid
- top-down bewijs van de volledigheidsstelling 4.23
- Propositie 4.13: volledigheid <=> iedere consistente verzameling formules is vervulbaar op zekere structuur
- constructie van die structuur: kanonieke modelconstructie
  idee: `truth = membership'
- maximaal consistente verzameling formules
  idee: `wereld = verzameling van alle formules die waar zijn in die wereld'
- truth lemma 4.21: bewijs van `truth = membership' dmv inductie naar opbouw van de formule (alleen de propositiegevallen)
werkgroep dinsdag 29 september, restant opgaven epistemische logica (3.4 t/m 3.13)
vrijdag 2 oktober, geen hoorcollege ivm CKI 10 jaar.
hoorcollege maandag 5 oktober, volledigheid slot
- vervolg bewijs van het truth lemma, het diamond geval: als <>phi in w dan is er een v zodanig dat Rwv en phi in v
  bewijs dmv het existence lemma 4.20 (existentie van v)
- volledigheid van K+{p -> <>p}) en K+{<><>p -> <>p}
werkgroep dinsdag 6 oktober
- Exercise 4.2.1, 4.2.2 uit de handout en volledigheid van S5
hoorcollege vrijdag 9 oktober, handout: hoofdstuk 4 (Filtrations and Decidability) en hoofdstuk 10 (Propositional Dynamic Logic) uit Logics of Time and Computation, Robert Goldblatt, CSLI Lecture Notes 7 ISBN 0-937073-11-3
- syntax van propositionele dynamische logica (PDL): formules en programmas
- formules (A): propositielogica + modaliteit [alpha]A
- programma's (alpha): atomaire statements, sequentiele compositie, alternatieve compositie, iteratie, en test A?
- standaard semantiek van PDL: bereikbaarheids relaties van [alpha] compositioneel in het programma alpha gedefinieerd
- afleidingssysteem voor PDL: normale logica gebaseerd op axioma's `corresponderend' met programmaconstructies
- correctheid van afleidingen mbt standaard semantiek: as always
- volledigheid van afleidingen mbt standaard semantiek: kanonieke modelconstructie, met de moeilijkheid om te laten zien dat dit een standaard semantiek is (volgende keer)
hoorcollege dinsdag 13 oktober, handout van 9 oktober
- uitdelen naar een verzameling naar een equivalentie relatie
- uitdelen van een model naar een eindige verzameling van formules die gesloten is onder het nemen van subformules
  eindigheid van het resulterende model
- filtratie: toegankelijkheidsrelatie van een uitgedeeld model die aan eisen (F1) en (F2) (zie blz.~31) voldoet.
- filtratie lemma 4.3: M |=_s A desdals M' |=_|s| A
  uitdelen naar verzameling subformules van A bewaart en reflecteert waarheid van A
- eindige frame eigenschap: formule A is geldig in een klasse van frames desdals A geldig is in alle eindige frames
- stelling 4.6: eindige frame eigenschap voor K
- `subformules' van een PDL formule (10.5, zonder bewijs)
- filtratie van het kanonieke model tot een standaard model (10.7-10.9)