Werkcollege Logische Structuren 11-12

werkcolleges:   1 | 2 | 3 | 4 | 5 | 6 | 7

Defitief overzicht van de behandelde stof

werkcollege 1, woensdag 2 november 2011

• uit Mendelson (pagina's 26-29):
  • 1.21(b)(c)
  • 1.23
  • 1.24
  • 1.28 (a) tot en met (g)
  
  In Mendelson vind je ook "solved problems" (p.19 e.v.). De volgende zijn aanbevolen: 1.1, 1.3, 1.5-7.
  
  
• uit Huth & Ryan (pagina's 78-91):
  • Exercises 1.1: 1(c-i), 2
  • Exercises 1.3: 1, 3, 4(a), 5, 6
  • Exercises 1.4: 2
  • Exercises 1.5: 6 (enkele onderdelen)

werkcollege 2, woensdag 9 november 2011

• Mendelson (pagina's 26-29):
  • 1.22
  • 1.29, 1.30, 1.31
  • 1.32 (c) tot en met (f)
  • 1.33, 1.34(a)(d)
  • 1.50(a)
  • 1.51(a) (NB: consistency is hier hetzelfde als satisfiability)
  • 1.52 (echte breinbreker)
  • 1.54 (moeilijk!)
  
  
• Huth & Ryan (pagina's 84-85):
  • Exercises 1.4: 4(a)
  • Exercise 1.4: 6(a-c)
  • Exercise 1.4: 12(a-c), 13(a-b)
    NB: Lees in deze opgaven het symbool ⊨ (logisch gevolg) i.p.v. ⊢
  
  
• (Smullyan, "What is the name of this book?")
  Op het eiland van leugenaars en waarheidssprekers worden drie inwoners, a, b  en c, ondervraagd:

  1. eilandbewoner a  zegt: "b is een waarheidsspreker."
  2. eilandbewoner b  zegt: "als a een waarheidsspreker is, dan is c  dat ook."

  • Bepaal van elk van a, b  en c  of ze waarheidssprekers dan wel leugenaars zijn.
  • Op de geldigheid van welke semantische implicatie berust deze gevolgtrekking?
  
  Verdere aanbevolen "solved problems" uit Mendelson: 1.17, 1.18

NB: deze week is er ook huiswerk

werkcollege 3, woensdag 16 november 2011

NB: nieuwe werkcollegetijd: 13:30-15:15, zaal M-664.
De groepen A en B worden gecombineerd.
Kom wannneer je dat helemaal niet schikt op de oude tijd, dus om 15:30, naar zaal S-655.

• uit Mendelson (pagina's 26-29):
  • 1.36 (gebruik de definitie van het college, zie addenda)
  • 1.37 (a) en (b)
  • 1.39 : alleen CNF
  • 1.40
  • 1.41 (a) en (b) : alleen DNF
  • 1.43, 1.44, 1,45, 1.47, 1.49
  • 1.48 (interessant maar lastig, gaat analoog aan de uitgewerkte opgave 1.16)
  
  
• uit Huth & Ryan (pagina's 78-91):
  • Exercises 1.5: 1, 2, 3, 7 (a-b) en 9

werkcollege 4, woensdag 23 november 2011

• boole algebra, Mendelson (pagina 70):
  • 3.17 a,b,c
  • 3.21 a,b
  • als voorbeeld uitwerkingen van 3.17(d) en 3.21(c)
  
  NB: Je kunt voor betere leesbaarheid ook de algebraïsche notatie met + en ⋅ gebruiken, zoals in Huth en Ryan, Ch. 6.
  (Eventueel met overline voor de negatie.)

• BDD's, Huth & Ryan (398-401):
  • Exercises 6.1: 2, 3
  • Exercises 6.2: 2, 3, 4(a-b)
  • Exercises 6.3: 2, 3 (+ reduceren)
  • Exercises 6.4: 1, 2, 3(a-b), 4(b), 5
  • Exercises 6.5: 1(b), 2, 3, 4, 6
  • als voorbeeld uitwerkingen van 6.5: 1(a) en (c)

werkcollege 5, woensdag 30 november 2011

NB: Het werkcollege is om 13.30, daarna om 15.30 het voortentamen!

• getalrepresentaties:   Mendelson 4.36, 4.37, 4.38, 4.41, 4.43 b
• extra opgave binaire optelling:
  We willen een 2-bits binair getal x₁x₀ en een 1-bits binair getal y₀ bij elkaar optellen, met uitkomst r₂r₁r₀. Geef expliciete boolese expressies voor r₀, r₁ en r₂ en de carry's c₀, c₁ en c₂, zoals in het op het college behandelde algoritme [slides]. Vereenvoudig waar mogelijk.

  Om je op weg te helpen: c₀ = 0, r₀ = x₀ + y₀, etc.

• logic circuits: Mendelson 4.34, 4.35 b

  Voorbeelduitwerkingen Logische Circuits

• switching circuits:  
  • 4.27 en 4.29
  • 4.33
  
  
• opgave 4, 7 en 9 van het tentamen van 17 februari 2011
  

Om meer te oefenen: voortentamen 29 november 2010 met uitwerkingen op extra pagina

werkcollege 6, woensdag 7 december 2011

• Bespreking van het voortentamen.
  Daaarbij de volgende aanvullende vragen:
  • Bij Opgave 2:
    • transformeer deze vraag naar een satisfiability-probleem
      
    • geef de benodigde input voor een satsilver in het standaardformat
    • hoe interpreteer je de output?
  • Bij Opgave 6:
    • wat is de cruciale semantische implicatie?
    • hoe kun je deze opgave oplossen met een satsolver?
    • met name ook: hoe controleer je uniciteit van de gevonden opolossing?
• Formaliseer de volgende vragen als een satisfiability probleem
  
  • Er heeft beroving plaatsgevonden waarbij gebruik is gemaakt van een vluchtauto. De volgende feiten worden vastgesteld:
    1. Er kunnen geen andere betrokkenen zijn dan A, B, C
    2. C doet nooit kwaad zonder B
    3. B kan niet autorijden
    Welke conclusie kunnen we trekken ten aanzien van de betrokkenheid van A, B, C?
  • The case of McGregor's Shop (vrij naar Smullyan, What is the name of this book?, 1978, pagina 80):
    Een winkelier beweert dat zijn winkel is beroofd. Drie verdachten A, B, en C worden ondervraagd. De volgende feiten worden vastgesteld:
    1. Elk van A, B, C is op de dag van de (veronderstelde) overval in de winkel geweest. Er waren geen andere klanten die dag.
    2. Als A schuldig is, is er precies één medeplichtige.
    3. Als B onschuldig is, dan is C dat ook.
    4. Als er exact twee schuldigen zijn, dan is A daar een van.
    5. Als C onschuldig is, dan is B dat ook.
    Welke conclusie kunnen we trekken?
• opgaven 7 en 11 van het tentamen van 22 december 2010
• opgaven 5 en 6 van het tentamen van 17 februari 2011

NB Er is deze week ook huiswerk (opdracht 2 op de opdrachtenpagina).
De deadline is maandag 12 december, voor het college.

werkcollege 7, woensdag 14 december 2011

• Predikatenlogica
  • Huth & Ryan (pagina 158), Exercises 2.1: 1, 3, 4(a-d)
  • Opgaven uit modellen.pdf
• De extra opgave uit het werkcollege van 30 november, over het optellen van een 2- en een 1-bits binair getal, kun je presenteren als een satisfiability probleem. Laat dat zien.
• Oefenen met oude tentamens
• Oefen extra het transformeren van cnf's naar het standaard inputformat voor satsolvers. Doe dit door in oefententamens:
  • telkens wanneer gevraagd wordt een cnf te bepalen deze ook in het standaardformat te schrijven
  • wanneer wordt gevraagd een probleem voor te stellen als satisfiability problem, ook te zorgen voor een vertaling naar het standaardformat.
  • NB: de gevonden representaties kun je zelf testen met sat4j

Daarnaast gelegenheid tot het stellen van vragen over alle stof