1. Geef een contextvrije grammatica voor propositielogica. Neem aan dat er oneindig veel propositieletters p_n in de taal zitten.
2. Geef een recursieve definitie van de functie pletters die voor elke propositielogische formule aangeeft welke propositieletters erin voorkomen.
3. Stel dat je Mastermind wilt spelen met behulp van propositielogica. Bij Mastermind moet je reeksen van vier kleuren raden, waarbij er keuze is uit een vast aantal kleuren. Laten we zeggen dat je kunt kiezen uit rood, geel, blauw, paars, oranje. De basispropositieletters zijn r₁, r₂, r₃, r₄, en net zo voor g, b, p, o. De formule g_3 drukt uit dat op positie 3 de kleur geel voorkomt, enzovoorts. Ga na dat de formule r₁ v r₂ v r₃ v r₄ uitdrukt dat rood minstens een keer voorkomt in de reeks van kleuren. Druk de volgende beweringen uit in propositielogica:
   1. Paars komt niet voor.
   2. Als rood voorkomt dan blauw ook.
   3. Rood komt op meer dan een positie voor.
   4. Geel komt precies een keer voor.
4. Geef een contextvrije grammatica voor zinnen van het twee-variabelen fragment van de predikatenlogica, over de volgende signatuur. P en Q zijn de eenplaatsige predikaten, R en S zijn de tweeplaatsige predikaten. Andere predikaten of functiesymbolen komen niet voor. Het twee-variabelen fragment van de predikatenlogica bestaat uit alle formules waarin maar twee variabelen voorkomen, laten we zeggen de variabelen x en y. Een zin is een predikatenlogische formule zonder vrije voorkomens van variabelen.
5. Geef zo precies mogelijk aan onder welke voorwaarden een contextvrije grammatica G een oneindige taal genereert.
6. Geef een rechts-lineaire grammatica voor de taal over het alfabet {0,1} die precies de rijtjes van nullen en enen genereert waar minstens een 1 in voorkomt.
7. Een knoop K in een boom domineert een knoop M in diezelfde boom onmiddellijk als M een dochter is van K. Geef aan hoe je de relatie van `domineren' kunt definieren in termen van `onmiddellijk domineren'.
8. Uit Hillary stelt Bill voor aan Barack kun je met lambda abstractie allerlei relaties definieren. Geef lambda expressies voor de volgende relaties:
   1. Bill voorstellen aan Barack,
   2. door Hillary aan Barack worden voorgesteld,
   3. voorstellen aan Barack,
   4. door Hillary voorgesteld worden,
   5. Bill voorstellen (aan),
   6. Een relatie vormen tussen Hillary, Bill en Barack.

   NB: de laatste vraag is een bonusvraag.

9. Kijk nogmaals naar Mastermind. Hoeveel mogelijke kleurencombinaties van vier posities zijn er als elk van de vijf kleuren hoogstens een keer mag voorkomen? Beschouw nu de propositielogische formule (r₁ v r₂) & (b₃ v b₄). Hoeveel van het totaal aan mogelijke situaties sluit deze formule uit (aannemende dat elk van de vijf kleuren hoogstens een keer mag voorkomen)?

Huiswerk: Tekstbestand met alle antwoorden. De laatste vraag is een bonusvraag. Deadline: dinsdag 23 juni, begin van het college. Let op: Deze keer per email inleveren bij Jan van Eijck, of uitgeprint mee naar het college brengen.