Overzicht colleges Inleiding Logica najaar 2008

Deze pagina wordt elke maandag en woensdag na het college bijgewerkt en vermeldt dan welke stof is behandeld. Voor de rest is het niet meer dan een prognose die zeker nog zal worden bijgesteld.

Hoorcollege 1 september:

• Inleiding propositielogica, Hoofdstuk 1 t/m Par. 1.1
  
• Formules formeel: inductieve definitie en parse trees, Par. 1.3
• Semantiek voor de propositielogica, Par.1.4.1
  
• Begrippen tautologie (valid formula), contradictie, contingentie
      NB: Een formule heet een contingentie als hij noch een tautologie is, noch een contradictie.
• Satisfiability en validity
  
• Semantische equivalentie
      NB: Formules φ en ψ heten semantisch (of logisch) equivalent, notatie φ ≡ ψ, als ze in een (gezamenlijke) waarheidstafel dezelfde kolom hebben. (Je kunt ook zeggen: als ze dezelfde waarheidsfunctie uitdrukken.)
  

Hoorcollege 3 september:

• Conjunctieve en disjunctieve normaalvormen
     Slides over cnf's: [1][2][3][4][5][6][7][8]
  
• Functionele volledigheid
  
• Binary decision diagrams
  

Hoorcollege 8 september:

• Ordered binary decision diagrams
• Natuurlijke deductie voor de propositielogica,
  Hoofdstuk 1 tot aan paragraaf 1.2.4, pagina 29
     NB: Nog niet behandeld: eliminatietieregel voor disjunctie, LEM en PBC.
     Slides over natuurlijke deductie: [ND]
  

Hoorcollege 10 september:

• Natuurlijke deductie voor de propositielogica, vervolg
  
• Semantische implicatie (of logisch gevolg)
     Slides over semantische implicatie: [LG]
• Nog niet behandeld:
  
  • Correctheid van natuurlijke deductie (soundness, theorem 1.35), Par. 1.4.3
  • Volledigheidsstelling (Par. 1.4.4, zonder bewijzen)
  Bekijk dit zelf, of onthoud vast: een formule ψ is afleidbaar uit de premissen φ₁, ... , φ_n dan en slechts dan als ψ semantisch volgt uit de premissen φ₁, ... , φ_n.

Hoorcollege 15 september:

• Correctheid en volledigheid
  
• Natuurlijke deductie met ProofWeb
  Na een korte klassikale kennismaking met ProofWeb in Q105 gaan we meteen aan de slag in de computerzalen S329 en S345
  NB: Meld je aan voor het practicum door een mailtje aan tcs@cs.vu.nl met subject "proofweb" en in de tekst alleen je voor- en achternaam. Doe het nu!

Hoorcollege 17 september:

• Modale logica: Hoofdstuk 5 tot en met par.5.2
  
• Modale logica: frames, geldigheid op frames

Hoorcollege 22 september:

• Correspondentie tussen modale formules en frame-eigenschappen
• Eigenschappen van relaties
• Weergave van eigenschappen in de predikatenlogica
  

Hoorcollege 24 september:

• Syntax van de predikatenlogica: termen, formules, parse trees
  
• Bereik (scope) van een kwantor
• Gebonden en vrije variabelen
  
• Vertalen in predikatenlogica
• Vertalen met gelijkheid

29 september geen hoorcollege i.v.m. voortentamen

Hoorcollege 1 oktober:

• Substitutie
• Natuurlijke deductie predikatenlogica
• Predikatenlogica in ProofWeb

Hoorcollege 6 oktober:

• Afronding natuurlijke deductie
• Gelijkheidsregels
• Semantiek predikatenlogica
• Geldigheid van semantische implicatie testen

Hoorcollege 8 oktober:

• Gelijkheid (=) in de predikatenlogica
• Speciale modellen: getalstructuren

Hoorcollege 13 oktober:

• Consistentie en syntactische consistentie
• Kappersparadox
• Volledigheid en correctheid
• Compactheidstelling
• Ondefinieerbaarheid van het begrip eindig

Hoorcollege 15 oktober:

• Definieerbaarheid en ondefinieerbaarheid
• Post Correspondence Problem (PCP)
• Onbeslisbaarheid van de predikatenlogica