Leertaak 16

Modellen van de Propositie- en Predicatenlogica

Achtergrond

De syntax van de propositie- en predicatenlogica legt vast hoe de formules eruitzien. Het is echter ook interessant om de betekenis van deze symbolen te bepalen. Net als bij de natuurlijke taal gaat het er bij de semantiek van de logica ook om om te bepalen of een formule waar of onwaar is.

Dit wordt uitgezocht door te kijken naar modellen. Bij de propositielogica gaat het hier om bepaalde situaties en de bijbehorende waarderingen. Bij de predicatenlogica is het iets ingewikkelder. Het gaat nog steeds om waarderingen van formules, maar nu is er een interpretatiefunctie en een bedeling nodig om vast te kunnen stellen of een formule waar is of niet.

Leerdoel

Na het voltooien van deze taak kunt u

• de waarde van formules in de propositielogica onder een waardering bepalen
• de modellen bij een formuleverzameling bepalen
• vaststellen of een formule een tautologie is
• vaststellen of twee formules logisch equivalent zijn
• kunnen bewijzen dat een set connectieven functioneel volledig is
• de interpretatie van termen en formules in de predicatenlogica in een model bepalen
• een eenvoudige informeel geformuleerde uitspraak over een model of een klasse van modellen uitdrukken met behulp van een predicaatlogische formule

Instructie

1. Lees hoofdstuk 2 uit "Logica voor Informatici" vanaf paragraaf 2.3.
2. Bepaal de modellen die horen bij de zin "Als de tram komt als de trein niet komt, dan komen de trein en de bus niet allebei".
3. Bewijs dat het NOR-connectief ('noch') uit voorbeeld 2.18 functioneel volledig is.
4. Geef een waarheidstabel voor een connectief dat 'tenzij' representeert.
5. Is de volgende formule een tautologie?

   (p -> (p -> q) -> q) <-> ((p -> q) -> (q -> p))
   

   Ondersteun uw conclusie met een waarheidstabel.
6. Lees hoofdstuk 7 vanaf definitie 7.1 uit "Logica voor Informatici": bestudeer de gegeven voorbeelden. U kunt de definitie van de interpretatiefunctie, zoals we die op college besproken hebben, terugvinden in de bijlage.
   1. Als u dat nog niet gedaan heeft, maak dan opgaven 7.10(i), (iii) en (v). (In alle gevallen geldt dat Th(M) en Th(N) niet gelijk zijn, dus u kunt zo'n zin phi vinden.)
   2. Als u 7.10(i), (iii) en (v) al gemaakt heeft, maakt u dan 7.10(iv).
7. Bekijk de graphstructuren G = (D,R) met R een binaire relatie op D, waarbij R(a,b) betekent dat er een pijl van a naar b loopt.
   1. Geef een zin A waarvoor geldt MOD(A) = { G | vanuit ieder punt in G vertrekt precies 1 pijl }
   2. Geef een zin B waarvoor geldt MOD(B) = { G | vanuit ieder punt in G vertrekken minstens 2 pijlen }

Product

• Een lijst met modellen over trams, treinen en bussen die al dan niet komen.
• Een bewijs dat het NOR-connectief functioneel volledig is.
• Een waarheidstabel voor 'tenzij'.
• Waarheidstabel waaruit blijkt of bovenstaande formule een tautologie is.
• Zinnen met verschillende waarden in de gegeven modellen.
• Zinnen die de gegeven graphstructuren karakteriseren.

Reflectie

• Kunt u zonder problemen de waarheidstabellen van de standaard connectieven opschrijven?
• Hoe heeft u uw modellen gekarakteriseerd?
• Kunt u helder het verband tussen een disjunctieve normaalvorm en de modellen van een formule beschrijven?
• Is uw bewijs van functionele volledigheid een helder betoog of een informele beschrijving?
• Heeft u bij het eerste product de interpretatiefunctie gebruikt om aan te tonen dat phi in M waar is en phi in N onwaar is?
• Kunt u bij het tweede product uitleggen (aan de hand van de interpretatiefunctie) dat uw zin A (resp. B) het gevraagde begrip axiomatiseert (niet meer en niet minder)?