Opdrachten Taal, Wiskunde, Logica
Laatste week
-
Geef een contextvrije grammatica voor propositielogica. Neem aan
dat er oneindig veel propositieletters pn in de
taal zitten.
- Geef een recursieve definitie van de functie pletters
die voor elke propositielogische formule aangeeft welke propositieletters
erin voorkomen.
- 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 r1, r2,
r3, r4, 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
r1 v r2 v r3 v r4
uitdrukt dat rood minstens een keer voorkomt in de reeks van
kleuren. Druk de volgende beweringen uit in propositielogica:
- Paars komt niet voor.
- Als rood voorkomt dan blauw ook.
- Rood komt op meer dan een positie voor.
- Geel komt precies een keer voor.
- 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.
-
Geef zo precies mogelijk aan onder welke voorwaarden een contextvrije
grammatica G een oneindige taal genereert.
- 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.
- 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'.
- Uit Hillary stelt Bill voor aan Barack kun je met lambda
abstractie allerlei relaties definieren. Geef lambda expressies voor
de volgende relaties:
- Bill voorstellen aan Barack,
- door Hillary aan Barack worden voorgesteld,
- voorstellen aan Barack,
- door Hillary voorgesteld worden,
- Bill voorstellen (aan),
- Een relatie vormen tussen Hillary, Bill en Barack.
NB: de laatste vraag is een bonusvraag.
- 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
(r1 v r2) & (b3 v b4).
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.