college 1, maandag 31 oktober 2011
- behandelde begrippen:
- taal van de propositielogica:
propositieletters, connectieven, formules (wff's) - parse trees
- waarheidstafels
- tautologie, contradictie, contingentie
NB: een contingentie is een formule met zowel F als T in de waarheidstafel - logische equivalentie (≡)
- geldigheid (validity, tautologie) en vervulbaarheid (satisfiability)
- taal van de propositielogica:
- Mendelson, hoofdstuk 1:
- tot en met §1.7
- in §1.7 alleen logical equivalence (logical implication is nog niet behandeld)
- Huth & Ryan, hoofdstuk 1:
- introductie, pagina's 1 en 2
- §1.1
- §1.3
- §1.4.1
- §1.5.1: tot en met definitie 1.40
- slides:
- propositielogica: syntax
- propositielogica: semantiek
- geldigheid (validity) en vervulbaarheid (satisfiability): venn diagram
college 2, maandag 7 november 2011
- logisch gevolg / semantische implicatie (semantic entailment)
H & R: §1.4.3 (alleen definitie 1.34) - logische puzzels
- slides:
- logisch gevolg: lg.pdf
- eiland.pdf
- Extra aantekeningen over het eiland
college 3, maandag 14 november 2011
- functionele volledigheid
- adequate stelsels
boolese operatoren (Mendelson §1.9)
- disjunctieve normaalvormen
- conjunctieve normaalvormen
- Mendelson, hoofdstuk 1:
- §1.8
- NB: Mendelson geeft een iets strictere definitie van DNF's dan wij. Onze definitie is analoog aan die van CNF, zie Huth en Ryan. Lees ook het commentaar in de addenda.
- Huth & Ryan, hoofdstuk 1:
- §1.5.1
- §1.5.2
- slides:
college 4, maandag 21 november 2011
- boole algebra (Mendelson: §3.1 en 3.2)
(aantekeningen)
- binary decision diagrams (Huth & Ryan §6.1)
college 5, maandag 28 november 2011
- getalrepresentaties, tweetallig stelsel (Mendelson §4.5)
- binair optellen (slides)
- logische circuits (Mendelson §4.4)
- circuits voor optellen: half adder en adder (Mendelson §4.6)
- switching circuits
- sequentieel-parallel (Mendelson §4.1),
- vereenvoudiging (Mendelson §4.2)
- NB: bestudeer ook het "solved problem" 4.2, Mendelson pagina 110
- bridge circuits (Mendelson §4.3)
- slides
- overzicht stof voortentamen
college 6, maandag 5 december 2011
- satisfiability
- consistentie (satisfiability) en inconsistentie
- modelleren van een vraag als satisfiability probleem
(bijvoorbeeld tafelschikking, sudoku)
- puzzel van geit, wolf en kool [gegoogled] [nog een] [ en nog een expliciete]
- satsolving: kennismaking met sat4j
- standaard format voor cnf-input satsolvers
- simpele voorbeelden satsolving
- sudoku
- automatisch vertalen propositionele formules naar standaard format
- rechtstreekse vertaling is exponentieel
- door tijdens de vertaling nieuwe propositievariabelen toe te voegen kan dit worden teruggebracht naar lineair
- kool, geit, wolf opgelost door satsolver
- de volgende vragen kunnen worden gerepresenteerd als
een satisfiability probleem, en opgelost door een satsolver:
- consistentie van een verzameling formules
- of een formule een tautologie, een contradictie of een contingentie is
sat-taut.pdf - logische geldigheid (semantische implicatie) slide
- logische equivalentie
- unique satisfiability
- Materiaal:
college 7, maandag 12 december 2011
- vervolg satsolving
- binair rekenen als satisfiabilty problem
- binair rekenen via satsolving
- leugenaarsparadox
- predikatenlogica (Huth & Ryan, Sectie 2.1, pagina's 93-95)
- overzicht behandelde stof