Werkcollege Inleiding Logica najaar 2008

1. kernopgaven
2. extra oefenopgaven

Overzicht huiswerkopgaven

NB: Dit overzicht is nog voor een deel gebaseerd op het schema van vorig jaar. Het wordt uiterlijk in het weekend voor de dan beginnende week bijgewerkt, zodat je weet wat er die week zal worden behandeld. Eventueel volgen kleine bijstellingen na ieder hoorcollege.

• Hoofdstuk 1, Propositielogica:  [78][81][82][83][84][85][87][88][89]
  
• Hoofdstuk 6, BDD's:  [398][399][400]

Werkcolleges 2 en 3 september:

• 1.1.1 (a-c)(e)(g-h)(i)
• 1.1.2 (a-b)(c)(d)(e-f)(g)
  
• 1.3: 1 (doe er enkele), 3(a-b)(c), 4(a)(b), 6(a)(b)
• 1.4: 1, 2(a)(c)(h), 3(c-d), 4(b), 5
• 1.5.2
  

Werkcolleges 4 en 5 september:

• 1.5.5
  
• De volgende variant van 1.5.1:
     Laat zien dat alle tautologieën onderling logisch equivalent zijn
• Bewijs of weerleg de volgende beweringen:
  
  1. Als φ en ψ tautologieën zijn, dan is ook φ ∧ ψ een tautologie.
  2. Als φ en ψ contingenties zijn, dan is ook φ ∧ ψ een contingentie.
  3. Als φ ∨ ψ een tautologie is, dan is φ een tautologie of ψ een tautologie.
  4. Als φ of ψ een tautologie is, dan ook φ ∨ ψ.
  5. Als φ en ψ contingenties zijn, dan is ook φ → ψ een contingentie.
• 1.5.6 (d_i)(e_ii)(g_i)(de rest)
• 1.4.6 (a-b)(c-d) en 1.5.3
  
• Puzzel: Definieer een connectief | zodat de singleton {|} al een adequate verzameling connectieven vormt.
     NB: Op het college werd naast "adequaat" ook de term "functioneel volledig" gebruikt.
• 1.5: 7, 9
  
• 6.1: 2, 3
• 6.2: 2, 4(a)(b)
• Extra opgave 1: Reduceer de in de vorige opgave gevonden BDD's met de regels C 1-3 naar een gereduceerde BDD.
• Extra opgave 2: Bepaal een gereduceerde BDD voor de minority functie f_min:

  f_min(x,y,z) = 1 als ten hoogste 1 van de argumenten x, y, z de waarde 1 heeft.

• 6.3: 2, 3

Werkcolleges 9 en 10 september:

• 6.2.3
  
• 6.4: 1, 2, 3(a)(b), 4(b), 5
• 6.5: 1(a-b)(c), 2
• Extra opgave: Vind een reduced OBDD voor (x₁ + x₂) . (x₃ + x₄) met de ordening [x₁, x₂, x₃, x₄].
• 1.2.1 (a-b)(c)(d)(e-g)(h-k)(m)(o)(r)
• 1.2.3 (a-b)(d-e)(s)(v)
• 1.2.8
• 1.2.9 

Werkcolleges 11 en 12 september:

• 1.2.1 (l)(n)(v)(x)(y)
• 1.2.2 (a-c)(e)(g-h)
• 1.2.3 (c)(f))(g-h)(k)(m-n)(o)(r)(u)
• 1.2.5 (a)(d)
• 1.4: 12(a-c)(d-e), 13(c-d), 14, 16(a-b), 17(a)
• Extra opgave 1: Controleer de geldigheid van de semantische implicaties
  • (a) p -> q, q -> -p |= p -> -q
  • (b) p v q -> r, q ^ r -> -p |= -(r ^ -q)
• Extra opgave 2: Vergelijk
  • A: |= fi -> psi
  • B: Als |= fi dan |= psi
  Geldt A => B? En B => A?
• Extra opgave 3: Idem met
  • A: |= fi ^ psi
  • B: |= fi en |= psi
• Extra opgave 4:
  • (a) Zijn er formules fi zo dat fi |= -fi?
  • (b) Is er een fi zodat fi semantisch equivalent met -fi?
  Motiveer telkens het antwoord, indien ja met een concreet voorbeeld voor fi.
• Extra opgave 5:
  Van connectief * is gegeven
  • (a) p * p is een tautologie
  • (b) p * q is niet semantisch equivalent met q * p
  • (c) q |= p * q geldt niet
  Bepaal de waarheidstafel van *

Werkcolleges 16 en 17 september:

• groep A: 16 september 9-11 uur in zaal S329
• groep B: 17 september 9-11 uur in zaal S345

De opdracht is:

• Bestudeer de file examples.v, alleen de propositielogica, examples 1 t/m 6. Loop er met de pijltjes doorheen, zodat je vertrouwd raakt met de tactics. Je kunt er ook mee oefenen, dezelfde voorbeelden nog oningevuld vind je aan het eind van de file.
• Maak naar keuze 16 opgaven propositielogica (prop_xxx.v), waarvan minimaal 6 Medium of Difficult.

• Een opgave is klaar als ie op "Solved" staat.
• De deadline is woensdag 24 september.

NB 1: Als je er tijd voor hebt is het aan te raden meer te oefenen.

NB 2 In wat ingewikkelder situaties kun je tegen een probleem oplopen met "Insert". Probleem en oplossing worden beschreven in dit stukje.

Werkcolleges 18 en 19 september:

• 5.2: 1-4, 5(a-g)
  
• 5.2: 6(a-d)(e)
• 5.3: 11-12

Werkcolleges 23 en 24 september:

• 5.3: 3
  
• 5.3: 7 (alleen de eigenschap symmetrie)
  
• 5.3: 8, 12, 13-14, 16(a-b)
• 2.1: 1, 3
  

Werkcolleges  25 en 26 september:

• 2.1: 2, 4(a-e)(i)(k)
• 2.2: 4(a-c)(e-f), 5(a-c)
• Extra vertaalopgave 1. Gebruik de volgende vertaalsleutel.

  m: Marie;  j: Jan;
  Ox: x is oppervlakkig
  Kxy: x kent y;  Wxy: x wantrouwt y
  

• Iedereen wantrouwt wel iemand.
• Niemand wordt door iedereen gewantrouwd.
  
• Jan wantrouwt iedereen die hij kent.
  
• Marie wantrouwt sommige mensen die ze kent, maar sommige ook niet.
  
• Alleen de oppervlakkigen kennen zichzelf.

• Extra vertaalopgave 2. Gebruik de volgende vertaalsleutel.

  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

  Vertaal de zinnen:
  • Jans zussen schaken beter dan zijn broers.
  • Jan heeft een zus die beter schaakt dan hij.
  • Jan heeft een broer die beter schaakt dan al zijn zussen.
  • Alleen Anna en Bea schaken beter dan Jan.
  • Behalve Anna heeft Jan nog meer zussen die beter schaken dan hij.
  • Jan heeft één zus die beter schaakt dan hij.
  • Anna heeft twee zussen, waarvan er één beter schaakt dan zij.

Geen werkcolleges op 30 september en 1 oktober

Werkcolleges 2 en 3 oktober:

• 2.2: 4(d), 5(d), 6
• 2.3: 6(b-c), 7(c), 8(b), 9(c)(e)(h-n)(o-q), 10(b)

Werkcolleges 7 en 8 oktober: 

• Bestudeer in de file examples.v nu examples 7 t/m 13, over de predikatenlogica. 
• Maak 12 opgaven predikatenlogica (pred_xxx.v), waarvan minimaal 4 Medium of Difficult.

• Een opgave is klaar als ie op "Solved" staat.
• De deadline is woensdag 15 oktober.

NB 1: Als je er tijd voor hebt is het aan te raden meer te oefenen.

NB 2: De opgaven met gelijkheid (voorbeelden 14 t/m 18 in de examples.v file) zijn alleen voor de liefhebber.

NB 3: In wat ingewikkelder situaties kun je tegen een probleem oplopen met "Insert". Probleem en oplossing worden beschreven in dit stukje.

Werkcolleges 9 en 10 oktober:

• 2.3: 2, 3(a-b)
• 2.4: 2, 3, 5, 6, 8, 10
• extra opgaven over tegenmodellen
• Extra: Beschouw de predikaatlogica met alleen een tweeplaatsige predikaatletter K. De getalstructuren N, Z, en R van respectievelijk de natuurlijke, de gehele en de reële getallen vormen hiervoor modellen, waarbij we telkens K interpretern als < ("kleiner dan").
  1. Geef een formule die waar is in R en Z, maar niet in N.
  2. Geef een formule die waar is in R, maar niet in Z.
  3. Geef een formule die waar is in R en N, maar niet in Z.
  4. Geef een formule die noch in N, noch in Z, noch in R waar is, maar die wel een model heeft ("consistent" is). Geef het model.

Werkcolleges 14 en 15 oktober:

• 2.4: 11, 12(a-c)(g)(h-k)
• 2.5: 1(a-c)(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 |- ψ

• 2.3: 3(c)
• 2.4: 9(a-b)(c-d)
  Nadenkertje: Maakt het verschil of je deze opgave doet voor propositie- of predikatenlogica?
  
• Ter oefening, tentamen van 20 december 2004

Werkcollege 16 en 17 oktober:

• 2.5: 2
  
• Laat zien dat eindigheid ook niet gedefinieerd kan worden door een verzameling formules. Dwz, er is geen verzameling formules Σ zodat

  M |= Σ <=> het domein van M is eindig

  M |= Σ betekent hier: M |= φ voor elke formule φ in Σ.
• Laat zien dat oneindigheid daarentegen wel gedefinieerd kan worden door een verzameling formules. Dwz, geef verzameling formules Δ zodat

  M |= Δ: <=> het domein van M is oneindig

• Laat zien dat oneindigheid niet gedefinieerd kan worden door een enkele formule φ.
• Laat zien dat de verzameling Δ die oneindigheid definieert ook niet eindig gekozen kan worden.
• We werken met een tweeplaatsig predikaatsymbool R en constanten c en c' (zoals in Stelling 2.26 in het boek, nieuwe druk).
  • Geef een verzameling Γ van formules die uitdrukt dat c' vanuit c niet via een (eindig) R-pad kan worden bereikt.
  • Laat weer zien dat Γ niet uit eindig veel formules kan bestaan.
• Extra opgave
  • 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))

  • Bestaat er een algoritme dat voor een willekeurige formule φ uit de predikatenlogica beslist of |= φ ? Licht uw antwoord kort toe.
• Ter oefening, tentamen van 12 februari 2004

Verdere vragen?

Martijn heeft ook een webpagina met uitwerkingen van sommige werkcollege-opgaven.