[informatica] Propositielogica: oefening

[SlimmeRick]

Zie:

Ik heb de gegevens omgezet in de volgende propositieletters:

a: achter deur 1 zit een prinses
b: achter deur 2 zit een prinses
c: achter deur 1 zit een tijger
d: achter deur 2 zit een tijger

en de volgende formule gevormd:

φ = ¬(a ∧ c) ∧ ¬(b ∧ d) ∧ (c -> d) ∧ (d->a) ∧ (b -> c)

Voor alle modellen van deze formule geldt: ¬b ∧ ¬c.
Dus:
Achter deur 1 zit een prinses en achter deur 2 zit een tijger.

Klopt dit een beetje? Volgens mij niet, want ik kom een model uit voor: V(a)=V(b)=V(c)=V(d)=0 en dat is onmogelijk volgens de opgave.

Uit de tekst kan ik ook het volgende afleiden:
(c ∧ d) ∨ (a ∧ b) ∨ (a ∧ d) ∨ (b ∧ c)

Dus
φ = ((c ∧ d) ∨ (a ∧ b) ∨ (a ∧ d) ∨ (b ∧ c)) ∧ (c -> d) ∧ (d->a) ∧ (b -> c) is ook correct?
Maar hiermee bekom ik andere modellen...

Ik had uit (c -> d) ∧ (d->a) ook meteen kunnen afleiden dat c onwaar is, want ¬(a ∧ c) moet waar zijn. Dus ik had meteen kunnen afleiden dat achter deur 1 een prinses zit. Toch?

Alvast bedankt!

[Xilvo]

Ik weet weinig van propositielogica maar is het niet handiger om in plaats van c en d, ¬a en ¬b te schrijven?

Hoe dan ook, ik heb een tabelletje opgesteld en kom ook uit op 1: prinses, 2: tijger.
Alle andere mogelijkheden leveren strijdigheden op.

[kwasie]

Voor het raadseltje kom ik daar ook op uit, maar misschien gaat de oefening er wel om dat er in de opdracht helemaal geen vraag geformuleerd is.

[EvilBro]

φ = ¬(a ∧ c) ∧ ¬(b ∧ d) ∧ (c -> d) ∧ (d->a) ∧ (b -> c)

Ik snap niet hoe je hier aan komt.

Ik denk dat het startpunt het volgende zou moeten zijn:
a: Achter deur 1 zit een prinses.
b: Achter deur 2 zit een prinses.
Uit het stukje tekst "deuren waar ofwel een prinses ofwel een tijger achter verscholen zit" volgt:
\(\neg{a}\): Achter deur 1 zit een tijger.
\(\neg{b}\): Achter deur 2 zit een tijger.
Dit zou je natuurlijk ook met een c en een d kunnen doen, maar dan moet je vervolgens ook de extra regels introduceren die dit equivalent maken aan het bovenstaande (en daar heb ik nu geen zin in )

De inscriptie op deur 1:

\(a \lor b\)

De inscriptie op deur 2:

\(a\)

Uit de tekst "Bovendien vertelt ...", over deur 1:

\(a \implies (a \lor b)\)

\(\neg{a} \implies \neg{(a \lor b)}\)

over deur 2:

\(\neg{b} \implies a\)

\(b \implies \neg{a}\)

Dit alles wordt dan:

\((a \implies (a \lor b)) \land (\neg{a} \implies \neg{(a \lor b)}) \land (\neg{b} \implies a) \land (b \implies \neg{a})\)

Dit kun je vereenvoudigen (succes!). Je komt dan uit op dat dit equivalent is met:

\(a \land \neg{b}\)

[SlimmeRick]

φ = ¬(a ∧ c) ∧ ¬(b ∧ d) ∧ (c -> d) ∧ (d->a) ∧ (b -> c)

Ik snap niet hoe je hier aan komt.

Eerst en vooral, hartelijk bedankt voor uw antwoord.


"De koning (die altijd de waarheid spreekt) vertelt aan de gevangene dat er ofwel
in beide kamers tijgers zitten, ofwel in beide kamers prinsessen vertoeven, ofwel
in één kamer een prinses en in de andere een tijger zit."
=> hieruit heb ik afgeleid dat alle combinaties van a, b, c en d mogen, behalve: (a ∧ c) en (b ∧ d), dus: ¬(a ∧ c) ∧ ¬(b ∧ d)

"Bovendien vertelt de koning dat wanneer er achter Deur 1 een prinses zit te wachten de inscriptie op
Deur 1 waar"
a-> a v b
dit is volgens mij altijd zo, dus heb ik dit weggelaten... (mag dit eigenlijk?)

"en wanneer er een tijger achter Deur 1 verschuilt de inscriptie op
Deur 1 niet waar is."

"Deur 1: In ten minste één kamer zit een prinses" is dan onwaar,
dus: (c -> d)

"Het omgekeerde geldt voor Deur 2 (de inscriptie op Deur
2 is waar als er een tijger achter verschuilt en vals als er een prinses vertoeft)"
dus: (d->a) ∧ (b -> c)

samen: ¬(a ∧ c) ∧ ¬(b ∧ d) ∧ (c -> d) ∧ (d->a) ∧ (b -> c)

Dit zou je natuurlijk ook met een c en een d kunnen doen, maar dan moet je vervolgens ook de extra regels introduceren die dit equivalent maken aan het bovenstaande (en daar heb ik nu geen zin in )

Ik begrijp niet zo goed wat u bedoelt met extra regels introduceren, wilt u dit alstublieft verduidelijken?

[SlimmeRick]

Ik weet weinig van propositielogica maar is het niet handiger om in plaats van c en d, ¬a en ¬b te schrijven?

Dat is natuurlijk veel handiger, bedankt voor de tip.

[SlimmeRick]

Voor het raadseltje kom ik daar ook op uit, maar misschien gaat de oefening er wel om dat er in de opdracht helemaal geen vraag geformuleerd is.

Oeps...

a. Van welke deur kan de gevangene, indien mogelijk, zeker zijn dat er een
prinses vertoeft?
b. Zet de tekst om in propositielogica.
c. Gebruik de methode van semantische tableaus om
formeel aan te tonen dat jouw antwoord op vraag a correct is

[EvilBro]

"De koning (die altijd de waarheid spreekt) vertelt aan de gevangene dat er ofwel
in beide kamers tijgers zitten, ofwel in beide kamers prinsessen vertoeven, ofwel
in één kamer een prinses en in de andere een tijger zit."
=> hieruit heb ik afgeleid dat alle combinaties van a, b, c en d mogen, behalve: (a ∧ c) en (b ∧ d), dus: ¬(a ∧ c) ∧ ¬(b ∧ d)

Dit klopt echter niet.
beide kamers hebben een prinses: \(a \land b\)
beide kamers hebben een tijger: \(c \land d\)
Kamers verschillend (beide opties): \((a \land d) \lor (b \land c)\)
Totaal wordt dan: \((a \land b) \lor (c \land d) \lor (a \land d) \lor (b \land c)\)

Je kunt nu bewijzen dat dit niet equivalent is met hetgeen jij hebt afgeleid. Bekijk bijvoorbeeld eens de situatie dat a, b, c en d onwaar zijn.

"Bovendien vertelt de koning dat wanneer er achter Deur 1 een prinses zit te wachten de inscriptie op
Deur 1 waar"
a-> a v b
dit is volgens mij altijd zo, dus heb ik dit weggelaten... (mag dit eigenlijk?)

Misschien netter om het even aan te tonen, maar het is wel redelijk voor de hand liggend.

"en wanneer er een tijger achter Deur 1 verschuilt de inscriptie op
Deur 1 niet waar is."

"Deur 1: In ten minste één kamer zit een prinses" is dan onwaar,
dus: (c -> d)

Ik zou denken dat het netter is om te zeggen:

\(c \implies \neg{(a \lor b)}\)

"Het omgekeerde geldt voor Deur 2 (de inscriptie op Deur
2 is waar als er een tijger achter verschuilt en vals als er een prinses vertoeft)"
dus: (d->a) ∧ (b -> c)

\(b \implies \neg{a}\)

Dit zou je natuurlijk ook met een c en een d kunnen doen, maar dan moet je vervolgens ook de extra regels introduceren die dit equivalent maken aan het bovenstaande (en daar heb ik nu geen zin in )

Ik begrijp niet zo goed wat u bedoelt met extra regels introduceren, wilt u dit alstublieft verduidelijken?

In het verhaal hierboven zit nog nergens dat een kamer slechts 1 monster bevat (danwel een prinses danwel een tijger). Dit zou wel het geval moeten zijn. Dit zijn dus regels die je extra dient te introduceren. Voorbeeld van zo'n extra regel:

\(a \implies \neg{c}\)

zodat als kamer 1 een prinses bevat, deze kamer geen tijger bevat (al is dat in de praktijk toch al geen stabiele situatie )

[SlimmeRick]

Hartelijk bedankt voor de verduidelijking!