Formele methoden

Vakcode:WIFM
Studiepunten:5.72 ECTS (=4 oude studiepunten)
Periode:periode 1 (week 36 t/m 43, dwz 2-9-2002 t/m 25-10-2002; herkansing week 1)
Deelnemers:tot nu toe 115 inschrijvingen
Rooster:Dit is een oud rooster!
vormgroeptijdweekzaaldocent
college   di 13-1536-43 Rup-wit Gerard Vreeswijk
  
vr 09-1136-37,39-42 Rup-rood
38 KRUYT-W105
tentamen   vr 09-121 EDUC-gamma
werkcollege groep 1 di 15-1736-42 BBL-505 Henry Prakken
Wijnand Suijlen
   
vr 13-1536-42 BBL-505
groep 2 di 15-1736-42 BBL-508 Robin Langerak
Niels van der Velden
   
vr 13-1536-42 BBL-508
groep 3 do 13-1536-42 BBL-505 Gerard Vreeswijk
Stefan Leijnen
   
vr 11-1336-42 BBL-108a
groep 4 do 13-1536-42 BBL-508 Frank de Boer
Lukas Spee
   
vr 11-1336-42 BBL-107a
Inhoud:De taal van de logica ken je inmiddels door het vak Beschrijven en Bewijzen. Ook heb je daar kennis gemaakt met redeneerpatronen en bewijsstrategieën. In Formele Methoden maken we die strategieën wat preciezer.
Literatuur:Syllabus Formele Methoden
Werkvorm:Per week 2 keer 2 uur hoorcollege en 2 keer 2 uur werkcollege
Toetsvorm:Een combinatie van huiswerkopgaven, tussentijdse toetsen en finaal tentamen.
Inspanningsverplichting voor aanvullende toets:Om aan de aanvullende toets te mogen meedoen is ontbreken van ten hoogte 1 toetsactiviteit toegestaan.
Beschrijving:Inhoud:
  • Taal, semantiek en deductie van de eerste orde logica. Meta-theorie en toepassingen.
  • Taal: proposities en predikaatlogische formules inductief gedefinieerd. Bereik van quantoren, eerlijke substituties, verband met het assingment.
  • Semantiek: waarderingen, bedelingen, eerste orde structuren, betekenis van substitutie. Interpretatie van n-aire relaties. Systematisch zoeken van kleinste (tegen-)modellen: semantische tableaus.
  • Deductie: het systeem van natuurlijke deductie, equationeel redeneren voor zowel propositie als predikatenlogica.
  • Meta-theorie: beslisbaarheid, volledigheid (schetsen), compactheid, monotonie.
  • Toepassingen: normaalvormen, logische schakelingen, query-talen.
Kennisdoelen:
  • Syntax van formules uit de propositie- en predikatenlogica. Quantoren, Predikaten, vrije en gebonden variabelen.
  • Bedelingen, waarheidstafels, semantisch gevolg. Eerste-orde modellen, vervulbaarheid, geldigheid, tegenvoorbeeld, contradictie, contingentie, tautologie.
  • Semantische tableaus.
  • Het systeem van natuurlijke deductie. Consistentie, maximaal consistent, bewijs.
  • Beslisbaarheid, volledigheid, compactheid, correctheid, en het belang ervan.
Vaardigheden: In staat beweringen over formules met inductie naar de opbouw te bewijzen. Met een waarheidstafel (in het geval van de propositie-logica) of via semantische tableaus kunnen bepalen of een conclusie volgt uit een verzameling premissen, eventueel een tegenmodel kunnen aangeven. Weten wat vervulbaarheid, geldigheid, contradictie en contingentie betekent in termen van modellen. Systematisch, met de methode van semantische tableaus, tegenmodellen kunnen vinden. De tekortkomingen van deze methoden kunnen aangeven. Bewijzen kunnen maken in het systeem van natuurlijke deductie. Door middel van voorbeelden kunnnen aangeven waarom de restricties op de regels voor de kwantoren nodig zijn. Kunnen aangeven wat het verband tussen afleidbaarheid en geldigheid is. Eerste orde formules in normaalvorm kunnen brengen. Kunnen skolemniseren. Weten wat het betekent dat de eerste orde logica onbeslisbaar is, in het bijzonder kunnen aangeven waarom dat geldt voor de semantische tableau methode.

Indeling:

  1. propositielogica: taal en semantiek. Bedelingen, semantisch gevolg. Bewijs via inductie naar opbouw
  2. Conjunctieve en disjunctieve normaalvormen, equationeel redeneren.
  3. propositielogica: semantische tableaus
  4. propositielogica: natuurlijke deductie. Eliminatie en Introductieregels
  5. predikatenlogica: taal en semantiek. Bedelingen, vrije variabelen
  6. predikatenlogica: natuurlijke deductie
  7. predikatenlogica: semantische tableaus
  8. predikatenlogica: normaalvormen (prenexvormen, skolemniseren)
  9. toepassing predikatenlogica: theorieën, standaardmodellen, ordeningen.
  10. meta-eigenschappen. Volledigheid, beslisbaarheid, monotonie, compactheid.
wijzigen?