Bert hamminga Back to: Index: Teaching Docs hamminga, B. (1997) Informatie, Waarheid en Werkelijkheid,inhoudsopgave Go to: Previous Section; Next Section

Page title: 13. Het bewijs van geldigheid door substitutie in een geldige formule

Als iemand schrijft:

l= A

dan bedoelt hij te beweren dat de formule A geldig is. Wij kunnen dat niet controleren v��r hij ons vertelt over welke formule het gaat. Als hij met A bedoelt: P, dan heeft hij ongelijk (de volzinsfunctie "l= A" wordt door deze invulling een onware volzin). Als hij met A bedoelt: P V �P, dan heeft hij gelijk (de volzinsfunctie "l= A" wordt door deze invulling een ware volzin).

Als een formule geldig is, kunnen we dat bewijzen door de waarheidskolom van de formule uit te rekenen en te laten zien dat er louter enen in voorkomen. Bij zo'n bewijs wordt de formule volledig gedemonteerd. De losse atomaire formules zijn dan het startpunt van het bewijs. Het ding wordt weer in elkaar gezet en al doende verkrijgen wij de waarheidskolom. Als we alle geldige formules willen hebben moeten we dit met alle formules uitproberen (we weten immers niet van te voren of een formule geldig is). Als we alle formules uitproberen zal er slechts af en toe een geldige formule tussen zitten. Het ziet er dus naar uit dat onze bewijsmethode nogal omslachtig is als zoekmethode naar geldige formules.

Kan dat niet handiger?

Dit kan handiger! Daarbij moeten we bedenken dat de waarheidstafelprocedure vanpar. 8 absoluut doorslaggevend blijft. Als we een andere bewijsmethode voor geldigheid gebruiken, moeten we dus eerst iets over zo'n bewijsmethode bewijzen, nl. dat hij op hetzelfde neerkomt als de waarheidstafelmethode vanpar. 8. Dan hebben we pas het recht om zo'n alternatieve methode te gebruiken.

Zo moet je dat doen omdat het geldigheidsbegrip immers met behulp van de waarheidstafels is gedefinieerd. En aan die definitie houden we vast. Gewoon omdat we dat willen.

Eerst een voorbeeld om te laten zien dat het soms handiger kan. De formule P & �P � P & �P heeft, net als de formule P � P, de vorm A � A. In tabel (a) is uitgerekend dat P � P louter enen heeft.

                                     Tabel 13.1.

Het ziet er naar uit dat P & �P � P & �P geldig is omdat P � P geldig is. Het ziet er, nog mooier gezegd, naar uit dat omdat P � P geldig is, alle formules A � A geldig zijn, wat je ook voor A invult. Zo kunnen we bijvoorbeeld voor A invullen: P & �P, en dan krijgen we "dus" (?) een formule met alleen enen in de waarheidskolom. In dit voorbeeld klopt dat (we gebruikten zelfs all��n maar de onderste rij van tabel (a) (onderstreept) voor alle rijen van tabel (b) (onderstreept) en de bovenste rij van tabel (a) hadden we dus niet eens nodig!). Maar klopt dat altijd? Dat gaan we nu bewijzen. En een bewijs begint met het netjes opschrijven van wat je wilt bewijzen:

THEOREMA: 13.1. (Substitutie van atomaire formules): Stel dat f  een formule is die alleen de atomaire formules P₁, ..., P_n bevat (notatie: f (P₁, ..., P_n)), en dat we de formule f  * kunnen verkrijgen door formules A₁, ..., A_n (atomair en/of samengesteld) in te vullen voor respectievelijk P₁, ..., P_n (notatie f  * (A₁, ..., A_n)). Dan is het zo: Als l= f (P₁, P₂, ..., P_n) dan l= f  * (A₁, A₂, ..., A_n).

Dus, nog even v��r ik hem ga bewijzen, ter verduidelijking enkele voorbeelden: als ik weet dat l= P � P, dan zou ik weten dat alle formules van de vorm A � A geldig zijn: Dus ik zou weten dat:

l= R & Q � R & Q

l= R & �Q � R & �Q

l= �R & Q ``� �R & Q

l= �R & �Q � �R & �Q

l= (P & Q) & R � (P & Q) & R

Enzovoorts

BEWIJS: Stel dat ik een formule f (P₁, ..., P_n) heb (die bestaat uit de atomaire formules P₁, ...,P_n) en dat l= f . Nu gaat de constructie van de waarheidskolom van f *(A₁, ..., A_n), uitgaande van de waarheidstafel van A₁, ..., A_n, precies net zo als de constructie van de waarheidskolom van f (P₁, ..., P_n), uitgaande van de waarheidstafel van P₁, ..., P_n. De waarheidskolom van f (P₁, ..., P_n) heeft, daar gingen we vanuit, louter enen wegens l= f . Dus moet zo'n waarheidskolom van f *(A₁, ..., A_n) uitgaande van de waarheidstafel van A₁, ..., A_n, ook louter enen hebben.

Wat we nu met f *(A₁, ..., A_n) hebben gedaan, mag eigenlijk niet, immers een waarheidstabel moet uitgaan van de atomaire formules van f *(A₁, ..., A_n) en de A'tjes hoeven niet atomair te zijn. Wat kunnen de gevolgen zijn van deze fout? Sommige A'tjes zijn misschien geldig. Die kunnen dan geen nul in hun kolom hebben. Het uitrekenen van rijen voor f *(A₁, ..., A_n) waarin zo'n A'tje een nul heeft was in dat geval een overbodige zaak. Het 1'tje in deze rij heeft geen betekenis. Zo zijn er wellicht (veel) enen in de kolom van f *(A₁, ..., A_n) die niet "kunnen". Dit kan analoog ook komen doordat een A'tje inconsistent is. Het is goed mogelijk dat vele enen uit de kolom van f *(A₁, ..., A_n) weggestreept moeten worden, maar er kunnen nooit nullen bijkomen.

Dus, welke combinaties van waarheid en onwaarheid voor A₁, ..., A_n ook mogelijk zijn, altijd resulteert een 1 in de waarheidskolom van f *(A₁, ..., A_n). Dus l= f *(A₁, ..., A_n).

Wij illustreren dit bewijs als volgt:

Van de bovenste tabel vooronderstellen wij dat hij goed is berekend, en dat l= f (P₁, ..., P_n). Doel is te bewijzen dat l= f *(A₁, ... A_n). We gaan nu iets doen dat niet mag: we maken de waarheidstafel van A₁, ..., A_n. Welke fout hebben we hier gemaakt (een fout die we gaan gebruiken om het bewijs te leveren)? We hebben de formule f *(A₁, ..., A_n) "onvolledig" gedemonteerd. De A'tjes zijn niet gegarandeerd atomair. Wat zijn hiervan de consequenties? Ten eerste er kunnen inconsistente A'tjes tussen zitten. Die kunnen nooit een 1 krijgen en in zo'n geval kunnen de rijen waarin zo'n A'tje een 1 heeft helemaal niet (ze zitten niet, plechtig gezegd, in de propositielogische ruimte van f *(A₁, ..., A_n)). Ten tweede kunnen er geldige A'tjes tussen zitten. Dan kunnen er ook rijen niet, namelijk die waarin een dergelijk A'tje een 0 heeft. Het komt er dus op neer dat onze fout tot gevolg heeft dat we "mogelijkheden" meerekenen bij onze berekening van de waarheidskolom van f *(A₁, ..., A_n) die helemaal geen mogelijkheden zijn!

Maar we moeten bewijzen dat die kolom alleen maar enen heeft. Nou, een 1 teveel, die helemaal niet kan, is helemaal niet erg. Als we maar zeker weten dat er nergens nullen komen. En dat weten we! Want aangezien f * precies zo uit A₁, ..., A_n is opgebouwd als f  uit P₁, ..., P_n, moet ik precies dezelfde behandelingen verrichten om de waarheidskolom van f *(A₁, ..., A_n) uit te rekenen als ik heb moeten verrichten om f (P₁, ... P_n) uit te rekenen. Dus moet er ook hetzelfde uitkomen. Denk erom, theorema 13.1. mag je niet omdraaien en zeggen dat het ��k als volgt is: als l= f *(A₁, ..., A_n) dan l= f (P₁, ..., P_n). Dat is namelijk niet zo, en om te bewijzen dat iets niet zo is hoef je er maar ��n tegenvoorbeeld aan te geven:

Neem P & �P � Q voor f *(A, B) waarin A voorstelt P & �P en B voorstelt Q. f * heeft dan de vorm A � B. Nu weten wij al lang dat P � Q (dit is de f  hier) een 0 in zijn waarheidskolom heeft en dus niet geldig is. Toch is f *(A, B) geldig! f *(A, B) stelt immers P & �P � Q voor en heeft dus louter enen in zijn kolom uitgaande van de waarheidstafel voor P en Q. De geldigheid van f * zegt dus niets over de geldigheid van f ! Ongeldigheid is derhalve met behulp van theorema 13.1. dus niet aan te tonen.

Doordat we theorema 13.1. bewezen hebben, hebben we een produktiemethode van geldige formules. (We hadden tot nu toe alleen een produktiemethode van - alle - formules, ziepar. 4 enpar. �). We mogen nu het volgende doen:

Vraag: l= P V Q � P & �P � �(P V Q) V (P & �P)?

Produktiemethode

Stap 1: (uit tabel 10.3., kol. 6) l= P � Q � �P V Q

Stap 2: voor elke A en B l= A � B � �A V B

Stap 3: neem voor A: P V Q en neem voor B: P& �P, dan krijg je:

l= P V Q � P & �P ��(P V Q) V (P & �P)

In stap 1 beginnen we met het opschrijven van een door ons gekozen f , een geldige formule. We schrijven "l= " erv��r, zodat er in symbolentaal komt te staan: "formule P � Q � �P V Q is geldig". In stap 2 schrijven we een formuleschema op. We noemen het een schema omdat je voor de A'tjes en B'tjes elke formule mag invullen. Het is een geldig formuleschema krachtens theorema 13.1. Zo bereiken we met stap 3 ons doel, onze formule f *.

Dankzij theorema 13.1. weten wij dat dit een bewijs is van l= P V Q � P & �P � �(P V Q) V (P & �P). Een bewijs, dus, dat deze formule geldig is. Een bewijs dus dat deze formule louter enen in zijn waarheidskolom moet hebben, ook al hebben we hem niet uitgerekend! Om te weten te komen of zoiets echt een bewijs is, moesten we eerst theorema 13.1. bewijzen. Dus een stelling (= theorema) die zegt dat iets een bewijs is, hebben wij bewezen. Toen we dat gedaan hadden, beschikten we over een produktiemethode. Theorema 13.1. noemen we een metastelling. We zagen dat het bewijs van deze metastelling er veel minder streng uitzag dan de bewijzen met de waarheidstafels en de produktiemethodes. Het bewijs van de metastelling was eigenlijk meer een soort verhaaltje, dat eindigde met: "Dus ...". Toch is het verhaaltje voor de zorgvuldige student, die in zijn hoofd nadoet wat het verhaaltje hem vraagt te doen, volstrekt overtuigend. Zo'n student kan zich niet meer indenken hoe het verhaaltje onwaar zou kunnen zijn.

Metastellingen over de propositielogica hoeven zelf niet geldig te zijn. Over geldigheid praten we slechts bij formules van de propositielogica. Wel moet van een metastelling bewezen zijn dat hij waar is, en dat betekent dat hij in alle denkbare gevallen waar is. De verzameling van alle denkbare gevallen ziet er bij metastellingen als theorema 13.1. h��l anders uit: hij beslaat alle manieren waarop je formules kunt invullen voor de A'tjes, B'tjes etc., van elk geldig formuleschema.

Op grond van het bewijs van theorema 13.1. geloof ik dat dit theorema waar is in al deze denkbare gevallen, hoewel het er oneindig veel zijn en ik ze dus nooit allemaal zou kunnen controleren. Toch geloof ik het.

Oefeningen

Hier volgt een partij schema's voor geldige formules. Het is zeer prettig om een geldige formule te hebben, want met behulp van zo'n geldige formule kun je geldige formules produceren door voor alle letters die in de formule voorkomen andere formules in te vullen (Telkens wel dezelfde formule voor dezelfde letter natuurlijk). Hier volgen een aantal beweringen over de geldigheid van formules.

THEOREMA 13.2. Voor alle (produceerbare) formules A, B en C:

1. l= ((A � B) � A) � A

2. l= A � (B � A)

3. l= (A � B) � ((A � (B � C)) � (A � C))

4. l= A � (B � A & B)

5. l= A & B � A

6. l= A & B � B

7. l= A � A V B

8. l= B � A V B

9. l= (A � C) � ((B � C) � (A V B � C))

10. l= (A � B) � ((A � �B) � �A)

11. l= ��A � A

12. l= (A � B) � ((B � A) � (A � B))

13. l= (A � B) � (A � B)

14. l= (A � B) � (B � A)

15. l= A � (B V A)

16. l= A V A � A

17. l= A V (B V C) � (A V B) V C

18. l= (A V B) V C � A V (B V C)

19. l= (A V B) & (�A V C) � B V C

20. l= �A � (A � B)

21. l= A � B � �B � �A

22. l= ��A � A

23. l= A V �A

24. l= �(A V B) � �A & �B

25. l= �(A & B) � �A V �B

BEWIJS: vul voor de letters A, B en C letters in die atomaire volzinnen aanduiden: P, Q en R. Bereken de waarheidskolommen van de resulterende formules. In alle 25 gevallen zullen er louter enen in de waarheidskolom staan. Pas dan theorema 13.1. toe.

Het is niet de bedoeling deze geldige schema's uit het hoofd te leren. Bedenk bij wijze van oefening Nederlandse uitspraken die voldoen aan de formules 5, 6, 7, 8, 11, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25. Onhoud daarbij dat een Nederlandse "als ... dan ..." zin all��n een goed voorbeeld is als hij hetzelfde betekent als "niet ... en/of ...".

Bewijs met behulp van de bovenstaande formules de geldigheid van:

1. (P & � P) V �(P & �P)

2. ��(P � Q) � P � Q

3. (P & Q) V ((P & Q) V R) � ((P & Q) V (P & Q)) V R

4. �((P & R) V (Q � R)) � �(P & R) & �(Q � R)

Maak zelf enkele van dergelijke oefeningen, dus maak enkele nieuwe formules door in de A'tjes, B'tjes en C'tjes van 1 t/m 25 formules in te vullen (Deze nieuwe formules moeten dus krachtens theorema 13.1. slechts enen in hun waarheidskolom hebben).

Tenslotte: is A V B een geldige formule? Geldt voor A V B hetzelfde als voor de formules in theorema 13.2., namelijk dat voor alle formules A en B, l= A V B? Zijn er formules A en B, waarvoor geldt dat l= A V B? Als ze er zijn, zou het een eindig aantal zijn of oneindig veel?

Klik voor de antwoorden bij de oefeningen

Go to: Previous Section; Next Section