Werkcollege Logica en Modelleren najaar 2011

a: Anna;  b: Bea;  j: Jan
Sxy: x schaakt beter dan y;  Bxy: x is een broer van y;  Zxy: x is een zus van y;  Gxy: x is getrouwd met y

• Jan heeft één zus.
• Jan heeft één zus, die beter schaakt dan hij.
• Jan heeft één zus die beter schaakt dan hij.
  • Vertaal eerst de eigenschap: "x is een zus van Jan die beter schaakt dan hij"
• Jan heeft één ongetrouwde zus.
  • Vertaal eerst de eigenschap: "x is een ongetrouwde zus van Jan"
• Jan heeft twee zussen.
• Jan heeft twee zussen, waarvan er één beter schaakt dan hijzelf.

Werkcolleges 4 en 5 oktober:

• 5.2: 1-4, 5(a-g), 6
• 5.3: 11
• 5.3: 13 (voorlopig alleen de eerste 3 formules van de tabel: T, B, D)

Werkcolleges 6 en 7 oktober:

• 5.3: 3
• 5.3: 7 (alleen de eigenschappen symmetrie en funcionaliteit)
• 5.3: 12
• 5.3: 13 (nu alleen de 4de en 6de formule in de tabel)
• 5.3: 14, 16(a-b)
• 5.3: 16(c), 17

• Opgave 2.3.11(a-b), (c-d)
• Geef een afleiding voor    ∀ x (x = a ∨ x = b)   |-   (Pa ∧ Pb) → ∀ x Px
  NB: dit is een vereenvoudigde vorm van ProofWeb pred_081. Je kunt 'm in ProofWeb proberen door pred_081 zelf te editen (de c elimineren). Probeer ook pred_085.

Werkcolleges 11 en 12 oktober: 

• 2.4: 9(a-b)(c-d)
  Nadenkertje: Maakt het verschil of je deze opgave doet voor propositie- of predikatenlogica?
  
• 2.4: 12(a-c)(g-k)
• 2.5: 1(c)(a)(d-e)(f)(g)
• Extra 1: Bewijs dat een verzameling formules {φ₁, ..., φ_n} een model heeft ("consistent" of "satisfiable" is), precies dan als het niet mogelijk is er FALSE uit af te leiden. Dus:

  {φ₁, ..., φ_n} consistent <=> niet: φ₁, ..., φ_n |- FALSE

  NB: op het college werd FALSE niet kunnen afleiden ook "syntactisch consistent" genoemd.

• Extra 2: Laat zien dat uit een verzameling formules die niet consistent is ("inconsistent") alles afgeleid kan worden. Dus:

  {φ₁, ..., φ_n} inconsistent <=> voor elke ψ geldt: φ₁, ..., φ_n |- ψ

• Extra 3: We werken met een tweeplaatsig predikaatsymbool R en constanten c en c' (zoals in Stelling 2.26 in het boek, nieuwe druk).
  1. Geef een formule die uitdrukt dat c' vanuit c via een R-pad van 4 stappen kan worden bereikt.
  2. Geef een formule die uitdrukt dat c' vanuit c via een R-pad van minder dan 4 stappen kan worden bereikt
  3. Geef een verzameling Γ van formules die uitdrukt dat c' vanuit c niet via een (eindig) R-pad kan worden bereikt.
  4. Laat zien dat Γ niet uit eindig veel formules kan bestaan.
  5. Bestaat er een formule die uitdrukt dat c' vanuit c via een R-pad van meer dan 4 stappen kan worden bereikt?
  6. Bestaat er een formule die uitdrukt dat c' vanuit c via een R-pad van 4 stappen kan worden bereikt, maar niet van meer stappen?

Werkcolleges 13 en 14 oktober:

• Extra opgaven
  1. Beschouw de volgende instantie van het Post Correspondence Problem (PCP). Geef een oplossing, als die er is, of beredeneer dat er geen oplossing is.

     ((00,01), (0111,1), (1,11), (111,1100))

  2. Voer de codering van PCP in de predikatenlogica concreet uit voor de instantie ((00,001), (10,0)). D.w.z., bepaal voor dit geval de formules φ₁ en φ₂ (H&R, p. 134).
  3. Bestaat er een algoritme dat voor een willekeurige formule φ uit de predikatenlogica beslist of ⊨ φ ? Licht je antwoord toe.
• 2.5: 2
• Opgave 9 van het tentamen van 24 oktober 2008
  
  
• 4.2: 3(a)(b)
• 4.3: 1, 2, 3, 4
• 4.3: 6 (zonder bewijs)
• We willen een programma dat, indien mogelijk, als outputwaarde van z een integer oplevert die groter is dan de inputwaarde van x en kleiner dan die van y.
  1. Geef een programmaspecificatie als Hoare triple.
  2. Schrijf een programmaatje dat aan de specificatie voldoet.
  3. Nu willen we als extra eis dat de waarde van z zoveel mogelijk "in het midden" tussen x en y ligt. Geef weer een Hoare triple en een correct programma.
  4. Hebben we het hier over partiële of over totale correctheid?
  5. Stel we willen we het programma niet laten termineren als er geen z tussen x en y gevonden kan worden. Tegen welk probleem met partiële correctheid loop je dan aan?
• We willen een programma dat de waarden van x en y verwisselt.
  1. Geef een programmaspecificatie als Hoare triple (totale correctheid).
  2. Schrijf een programmaatje dat aan de specificatie voldoet.
• Opgave 9 van de tentamens van 23 oktober 2009, 7 januari 2010 en opgave 8 van het tentamen van 27 oktober 2010 .
• 5.3: 2

Werkcolleges 18 en 19 oktober:

• Formuleer in de predikatenlogica een query die uit de tabel Chats (zie de samenvatting van het college van 14 oktober) de (voornamen van) personen selecteert die hebben deelgenomen aan een chat.
  1. In het relationeel model
     
  2. In het tuple-model
     
• Formuleer in de predikatenlogica een query die uit de tabel Persons de steden selecteert waar maar één persoon uit de tabel woont.
  1. In het relationeel model
     
  2. In het tuple-model
     
  
  
• Opgave 6 van de tentamens van 23 oktober 2009 en 7 januari 2010.

Werkcollege 20 en 21 oktober:

• Tentamen van 23 oktober 2009, nog niet behandelde opgaven.
• Tentamen van 7 januari 2010, nog niet behandelde opgaven.
• Extra vertaalopgaven (bedenk zelf de vertaalsleutel)
  1. Anna heeft precies twee kinderen, een jongen en een meisje.
  2. Anna heeft meerdere kinderen.
  3. Anna heeft meerdere kinderen, maar slechts één jongen.
• Ter verdere oefening, opgaven 4, 5, 6, 7, 8 van het tentamen van 24 oktober 2008
• Ter verdere oefening, opgaven 4, 5, 6, 7, 8 van het tentamen van 12 februari 2004

Verdere vragen?