Beweren en bewijzen/supplement/planning (voor docenten)/het werk/taak/04
Beweren en bewijzen: "redeneren op het hoogste niveau over gemaakte dingen". We hebben nu correctheidsstellingen in propositielogica opgeschreven en zullen binnenkort leren hoe men deze netjes kan bewijzen. Maar wat betekent "bewijzen" eigenlijk? Daartoe moeten we eerst precies weten wat "waarheid" in de propositielogica betekent. Wanneer is een bewering waar? Wanneer is een gevolgtrekking juist? |
Achtergrond
De propositielogica is zowaar de eenvoudigste taal waarin zich specificaties en correctheidsstelling laten opstellen - als tenminste de →focus van het correctheidsvraagstuk zich leent voor vergaande abstractie. In Taak03 heb je zoiets al geprobeerd. We concentreren ons nu op de vraag hoe je precies na kunt gaan wat het betekent
- dat een formule waar is en
- dat een formule geldig gevolg is uit een aantal andere formules.
Daarmee leggen we het exacte fundament voor het verhaal over de vier werelden uit Beweren en bewijzen/het verhaal/3. Formalisering. In de propositielogica lijkt dat met waarheidstabellen te lukken, al worden deze gauw groot en onoverzichtelijk.
De betekenis van de logische voegtekens laat zich vatten in kleine waarheidstabellen. Daaruit laat zich de waarheidstabel voor een samengestelde formule construeren.
Als je waarheidstabellen voor formules opstelt, moet je natuurlijk weten wanneer zo'n tabel compleet is. Als je iets bewijst, moet je weten wat je precies moet aantonen met wat voor tabel.
VALKUIL: Je hebt waarheidstabellen misschien al in eerdere cursussen leren kennen. Wellicht kun je al makkelijk een waarheidstabel voor een gegeven formule opstellen. Dat is niet voldoende! Je moet ook zeker weten hoe en met welk doel je waarheidstabellen gebruikt. En je moet dit kunnen uitleggen.
Doel
literatuur
*)of een andere logicaboek of -dictaat |
- Je kunt de begrippen model, situatie, tautologie en geldig gevolg op professionele manier gebruiken.
- Je kunt aangeven hoe groot de waarheidstabel voor een gegeven formule is.
- Je kunt voor formules de waarheidstabel op de standaardmanier opschrijven.
- Je kunt controleren met behulp van een waarheidstabel:
- of twee formules logisch equivalent zijn,
- of een formule een tautologie is,
- of een formule een geldig gevolg is van een verzameling van formules.
- Je kunt uitleggen hoe men met waarheidstabellen werkt.
Instructie
- Lees Beweren en bewijzen/het verhaal/3. Formalisering nog eens goed door. Het is uitgebreid, en jij hebt na diversie studietaken nieuwe inzichten.
- Lees het beginstuk (tot de dubbele streep) van Beweren en bewijzen/het verhaal/5. Bewijzen zeer zorgvuldig door. Eigenlijk staat hier alles, zij het uiterst compact. Je kunt dit als checklist gebruiken of je de nodige concepten begrepen hebt.
- Leer de kleine waarheidstabellen van de voegtekens ¬, ∧, ∨, , → en ↔ uit je hoofd en ga na of je vindt dat deze inderdaad de betekenis van deze voegtekens goed weergeven.
- Leer de definities van de begrippen model en situatie. Let op: een model in deze zin is iets anders dan een domeinmodel!
- Verschaf je vervolgens helderheid over de volgende vragen.
- Hoeveel regels heeft de waarheidstabel voor een formule waarin alleen de proposities p, q en r voorkomen?
- Hangt de lengte (het aantal regels) van zo'n waarheidstabel af van hoe vaak een propositie, bv. p, in de formule voorkomt?
- Hoeveel regels heeft de waarheidstabel van een formule waarin n verschillende proposities voorkomen?
- Hoe schrijf je alle combinaties van alle mogelijke waarden van alle proposities uit een formule systematisch op, zodat je makkelijk kunt zien dat je geen combinatie vergeten bent?
- Wat heeft de waarheidstabel van een formule te maken met de constructieboom van deze formule?
- Wanneer is een formule een tautologie? Wanneer zijn twee formules logisch equivalent?
- Oefen - indien je dit niet eerder hebt gedaan - het opstellen van waarheidstabellen aan de hand van ten minste 5 voorbeelden waarin diverse combinaties van voegtekens voorkomen.
- Herzie indien nodig je uitwerking van Taak03 en schrijf een kloppende correctheidsstelling op. Doe dit op de pagina van Taak03 zelf en niet op een nieuwe pagina. Het heeft geen nut om oude, foute uitwerkingen te bewaren.
- Formuleer ten slotte een systematisch voorschrift zoals hieronder aangegeven. (Het heeft geen enkel nut, dit voorschrift van iemand anders over te nemen; je moet dit een keer in je leven zelf onder woorden brengen en opschrijven.)
- Richt je nu op je correctheidsstelling uit Taak03:
- Laat deze alsnog controleren door Coq (zie de pagina over het gebruik van Coq).
Product
Op je oude pagina van taak 3
- De volledige uitwerking met een kloppende correctheidsstelling
- In 1 zin je ervaring bij de poging, deze stelling met Coq te controleren
- Hoe groot zou een waarheidstabel van je stelling worden?
Op je nieuwe pagina voor taak 4
Zet allereerst deze code in je nieuwe pagina om deze tijdelijk voor anderen ontoegankelijk te maken:
{{BenB/Taak4|~~~}}
Deze opdracht voer je even in het geniep uit:
- In je eigen woorden een systematisch voorschrift hoe men waarheidstabellen opstelt en hoe men nagaat...
- of twee formules logisch equivalent zijn,
- of een formule een tautologie is,
- of een formule een geldig gevolg is van een verzameling van formules.
In het komende responsiecollege zullen we je voorschrift uitvoeren en kijken of het "werkt".
Reflectie
- Heb je de begrippen model, situatie, tautologie en geldig gevolg op de juiste manier gebruikt?
- Kun je het verschil uitleggen tussen een model in de zin van de logica en een domeinmodel in de zin van deze cursus?
- Kan iemand die geen logica geleerd heeft met behulp van de volgende informatie een waarheidstabel opstellen en nagaan of een stelling klopt?
- je voorschrift,
- de waarheidstabelletjes voor de logische voegtekens,
- een volledig gehaakte stelling in de vorm
a1, a2, a3 |= C
- Heb je dit op een proefpersoon uitgeprobeerd?
Inleveren
- Je uitwerking maak je hier.
- Zet op de eerste regel van je uitwerking precies dit:
{{individuele opdracht}}
- Uiterste inleverdatum: {{{deadline}}} en geen minuut later -
- Wil je deelnemen aan het responsiecollege moet je uitwerking op tijd af zijn en (indien MediaWiki correct functioneert) in het goede lijstje hieronder verschijnen.