Modellen van de Propositie- en Predicatenlogica

Achtergrond

De syntax van de propositie- en predicatenlogica legt vast hoe de formules eruitzien. Het is echter ook interessant om de betekenis van deze symbolen te bepalen. Net als bij de natuurlijke taal gaat het er bij de semantiek van de logica ook om om te bepalen of een formule waar of onwaar is.

Dit wordt uitgezocht door te kijken naar modellen. Bij de propositielogica gaat het hier om bepaalde situaties en de bijbehorende waarderingen. Bij de predicatenlogica is het iets ingewikkelder. Het gaat nog steeds om waarderingen van formules, maar nu is er een interpretatiefunctie en een bedeling nodig om vast te kunnen stellen of een formule waar is of niet.

Leerdoel

Na het voltooien van deze taak kunt u

Instructie

  1. Lees hoofdstuk 2 uit "Logica voor Informatici" vanaf paragraaf 2.3.
  2. Bepaal de modellen die horen bij de zin "Als de tram komt als de trein niet komt, dan komen de trein en de bus niet allebei".
  3. Bewijs dat het NOR-connectief ('noch') functioneel volledig is.
  4. Welke van de volgende eigenschapen geldt? (I) "Als |= A\/B, dan |= A of |= B" (II) "Als |= A/\B, dan |= A en |= B" Geef een bewijs of een tegenvoorbeeld.
  5. Geef een waarheidstabel voor een connectief dat tenzij representeert. Hier is een truth table generator. Je moet het natuurlijk ook met de hand kunnen.
  6. Is de volgende formule een tautologie?
    (p -> ((p -> q) -> q)) <-> ((p -> q) -> (q -> p))
    
    Ondersteun uw conclusie met een waarheidstabel.
  7. Lees hoofdstuk 7 vanaf definitie 7.1 uit "Logica voor Informatici": bestudeer de gegeven voorbeelden. U kunt de definitie van de interpretatiefunctie, zoals we die op college besproken hebben, terugvinden in de bijlage.
    Maak de onderdelen van opgave 7.10 die nog niet op het college voorgemaakt zijn. (Mocht je zo'n formule niet kunnen vinden, kun je aannemelijk maken waarom die niet bestaat?)
  8. Bekijk de graphstructuren G = (D,R) met R een binaire relatie op D, waarbij R(a,b) betekent dat er een pijl van a naar b loopt.
    1. Geef een zin A waarvoor geldt MOD(A) = { G | vanuit ieder punt in G vertrekt precies 1 pijl }
    2. Geef een zin B waarvoor geldt MOD(B) = { G | vanuit ieder punt in G vertrekken minstens 2 pijlen }
  9. Maak opgave 7.9

Product

Reflectie