Beweren en bewijzen/de opzet/literatuur

Leerboek

Elk goed boek of collegedictaat over propositie- en predikaatlogica kun je als achtergrondliteratuur voor deze cursus gebruiken. Er zijn er veel op de markt. Ze gebruiken wel allemaal hun eigen notatie, en er kunnen ook verschillen zijn bij de regels voor natuurlijke deductie. Hiermee moet je kunnen omgaan, want dat is nu eens zo in de wetenschappelijke wereld.

Het logica-boek dat het dichtst bij de in de cursus gebruikte deductieregels komt is dit: J.F.A.K. VAN BENTHEM, H.P. VAN DITMRASCH, J.KETTING en W.P.M.MEYER-VIOL. Logica voor informatici / Logica voor informatica (de oplage doet er niet toe; de titel is ooit van oplage tot oplage veranderd Addison-Wesley

Het is een goed en breed leerboek over logica, en je zult het later vaak kunnen gebruiken, in andere colleges en practica, gedurende het afstudeerwerk en in de beroepspraktijk. Aanschaf is geen slechte investering.

Dit boek is niet specifiek voor dit college gemaakt; het gaat veel verder dan de collegestof. Het college biedt een inleiding die je helpt om zelf met het boek verder te gaan.

In de cursus Beweren en Bewijzen worden de volgende onderdelen opgegeven ter zelfstudie

• Hoofdstuk 1
• Hoofdstuk 2
• Hoofdstuk 3
• Hoofdstuk 4.1 en 4.2
• Hoofdstuk 6.1, 6.2, 6.3 en 6.5
• Delen van hoofdstuk 7
• Hoofdstuk 10.1

Dwarsverbanden met andere informaticacolleges

• functionele programmeertalen: 12.6, 12.7
• het college Logica van Wim Veldman: 12.10 (en het hele boek natuurlijk)
• berekenbaarheid: 14
• imperatieve programmeertalen: 15
• logische programmeertalen: 16
• K.I.: 17ff.
• taalkunde: 19

Drukfouten in oudere oplagen

de ontdekker datum ontdekking bladzijde de fout Rene Wolferink 9-10-2000 paragraaf 4.2 bladzijde 57 Betreffende de "=> Introductieregel". Er staat het volgende: NOT p /\ NOT q ------------------------------------------- =>I, [-3] NOT (p \/ q) => (NOT p \/ NOT q) (aanname 3 := NOT (p \/ q)) Hierin is de bewering rechts van de => omgeklapt van /\ naar \/. Er moet staan: NOT p /\ NOT q ------------------------------------------- =>I, [-3] NOT (p \/ q) => (NOT p /\ NOT q) (aanname 3 := NOT (p \/ q)) Hanno Wupper 27-3-2003 voorbeeld 6.8 bladzijde 95 Twee stukjes van de constructieboom staan verkeerd! De formule bestaat uit twee onderdelen: een kwantor met variabele een formule waarin de gekwantificeerde variabele voorkomt Het bovenste streepje van de boom hoort daarom niet onder de pijl maar onder de witte ruimte tussen deze twee delen - net al het bij het alleronderste streepje het geval is. Het streepje bij de existentiële kwantor staat ook verkeerd.

We maken onze eigen taal

In de wetenschappelijke wereld is er geen consensus over terminologie en notatie. Zo gebruiken logici (waaronder Van Benthem) een historisch gegroeide schrijfwijze voor formules, die uit informaticastandpunt niet erg handig is.

Daarom gebruiken we in het practicum een iets andere notatie.

Deductieschema

In het college worden de regels voor natuurlijke deductie uitgedeeld op papier. Je vindt ze ook hier: Beweren en bewijzen/de zuilen/Zekerheid/5. Natuurlijke deductie/deductieschema

In hoofdstuk 4 van het boek van Van Benthem e.a. zien de regels er op het eerste gezicht anders uit. In de meeste andere logicaboeken ook.

Het is belangrijk dat je je overtuigt dat dit alleen een cosmetisch verschil is.

Van Benthem gebruikt een notatie die er op het eerste gezicht overzichtelijk en compact uit ziet maar erg foutgevoelig is. De aannames die op elk moment gelden schrijft hij namelijk niet op; die moet men altijd in het hoofd bijhouden. Als je met Jape of Coq werkt of met potlood en papier volgens de handouts, staan alle aannames er altijd duidelijk.

Vergelijk de regel voor /\I op blz. 51 met die op de hand-out. In het boek staan de verzamelingen PHI en SIGMA boven een stippellijn. Op de handout staan ze links van het symbool |- . In het boek moet je onthouden dat onder de horizontale streep altijd de vereniging van alle aannames boven de streep geldt. Op de handout staat onder de streep expliciet PHI U SIGMA.

Kijk naar de bewijsboom 4.2 op blz. 53. De aannames helemaal boven hebben nummers. Bij de => - introductieregels staat [-1] en [-2] om aan te geven dat bepaalde aannames ingetrokken worden. Dat betekent: in de aannames boven de streep komen ze nog voor; onder de streep niet meer. De bedoeling begrijp je als je de regels voor =>I op blz. 52 en op de handout nauwkeurig vergelijkt.

In het boek moet je dus overal in je hoofd hebben welke aannames waar geldig zijn en bij sommige overgangen wordt alleen door een getalletje aangegeven welke aanname je moet schrappen. (Het boek geeft een voorbeeld 4.3 voor expliciete aannames. Onder op blz. 53 staat een bewijsboom; op blz. 54 vind je een versie met alle expliciete aannames, maar dan vreemd genoeg tussen akkolades ACHTER de beweringen.)

Vergelijk onze hand-out goed met de regels op blz. 59. Op de hand-out staan meer regels, maar die hebben we pas later nodig voor de predikatenlogica

Op het tentamen en in practicumuitwerkingen worden geen bewijzen zonder volledige expliciete aannames geaccepteerd. Waarom? Omdat ze niet betrouwbaar na te kijken zijn. Omdat fouten veel te gemakkelijk overzien worden, door de schrijver en ook door de lezer.

Taxonomie

Taxonomy/Beweren en bewijzen