Redeneren en bewijzen

Logica in actie H O O F D S T U K 1

Redeneren en bewijzen Jan en Johan zijn net in Dunedin gearriveerd en Hans neemt ze mee naar een terrasje. “Wat willen jullie hebben?” “Koffie!” De bediening komt langs. Matt. “Two long black please and a flat white.” Dat begrijpt Matt wel, maar Jan en Johan begrijpen niet meteen waarom deze bestelling correct is. Ze concluderen dat een gewoon kopje koffie kennelijk in Nieuw‐Zeeland ‘long black’ heet. Inderdaad: een ‘long black’ is een ‘short black’ met extra water. En een ‘short black’ is een espresso. Terwijl een ‘flat white’ slaat op een koffie met melk; net zo’n lokale benaming als bij ons ‘koffie verkeerd’. Matt komt terug met een dienblad waarop drie kopjes staan. “Who’s got the flat white?” Hans reageert. Daarna worden de andere twee kopjes bij Jan en Johan neergezet. “Thanks, Matt!” Bij zo’n scenario zien we al heel wat logica in actie. Hans weet dat ‘kopje koffie’ lokaal ‘long black’ heet. En dat daarom de bediening dat ook weet, en dat het niet uitmaakt dat Jan en Johan dat niet weten. Jan en Johan bestelden hetzelfde. In de bestelling komt twee keer iets van hetzelfde voor. Hieruit volgt dus, concluderen ze, dat ‘long black’ overeenkomt met het gewone kopje koffie, en ‘flat white’ niet. Matt is ook niet dom. Hij vraagt namelijk niet wie long black heeft maar wie de flat white heeft. Hij krijgt dus maar één antwoord in plaats van twee antwoorden. Voor drie personen is dat nog te overzien, maar vraag nu eens ‘who’s got the beer’ aan een tafel met tien personen; terwijl je net zo goed met die ene gin tonic had kunnen beginnen. En na Hans de flat white gegeven te hebben, kan hij de rest van de bestelling in willekeurige volg‐ orde bij Hans’ tafelgenoten neerzetten, zonder daar verder over te hoeven nadenken. Voor Hans’ antwoord weet hij dat alle drie de gasten een long black of flat white hebben. Omdat Hans flat white heeft en er één flat white was, hebben Johan en Jan niet flat white. Uit ‘niet flat white’ en ‘long black of flat white’ volgt logisch ‘long black’. Johan en Jan hebben dus allebei een long black. Van oudsher is de logica de leer van dit soort correcte redeneringen. Nog steeds is het herkennen van correcte en incorrecte redeneringen een belang‐ rijke doelstelling van de logica, en het beschrijven van methoden om te bewijzen dat een conclusie volgt uit een verzameling aannames. Natuurlijk

1

Logica in actie / Hoofstuk 1 Redeneren en bewijzen

STELLING 1.1

speelt in ons openingsvoorbeeld veel meer dan alleen bewijzen, want er worden bijvoorbeeld ook vragen gesteld, met antwoorden die informatie overdragen. De bredere rol van de moderne logica als studie van iedere correcte vorm van informatieoverdracht zal ook volop aan bod komen in deze cursus, maar we beginnen in dit eerste hoofdstuk klassiek. Zelfs heel klassiek! Een exact wetenschapsgebied als de wiskunde is de beste plaats om te beginnen, omdat je daar redeneren in ‘reincultuur’ ziet. In dit eerste, inleidende, hoofdstuk geven we een aantal klassieke voor‐ beelden van dergelijke wiskundige bewijzen. Aan het eind van het hoofd‐ stuk geven we een kort overzicht van de inhoud van dit boek. 1.1 De stelling van Pythagoras Het hart van de exacte wetenschappen wordt gevormd door het begrip bewijs. De ontdekking van de methode om een onderwerp te presenteren in termen van axioma’s, definities en bewijzen is één van de grote uitvindin‐ gen van de mensheid. Het beroemdste voorbeeld van deze axiomatische methode is de systematische presentatie van meetkundige inzichten in de Elementen van Euclides, geschreven tussen 330 en 320 voor Christus. Om toegang te krijgen tot cultuurschatten zoals deze, moet je vertrouwd raken met de gebruikte manier van presenteren. Het stramien van een bewijs in Euclides’ Elementen is heel strak. Alle bewij‐ zen beginnen met een opsomming van wat gegeven is, gevolgd door ‘te bewijzen:’, met daarna de bewering waarvan de waarheid moet worden aangetoond. Dan volgen de stappen die nodig zijn om de ‘te bewijzen’ bewering af te leiden uit wat gegeven is. Door de stappen te volgen kunt u inzien dat de ‘te bewijzen’ bewering waar moet zijn. In die bewijsstappen kunnen ook beweringen worden gebruikt die al eerder bewezen zijn. Zulke al bewezen beweringen heten stellingen. Het bewijs eindigt wanneer we zijn aangeland bij de bewering die bewezen moet worden. De laatste zin van het bewijs luidt: ‘En dat is precies wat moest worden aangetoond’. De Latijnse versie van deze afslui‐ tende frase is quod erat demonstrandum, afgekort QED (in het Grieks stond er: οπερ εδει δειξαι). Dit is nog steeds een veelgebruikte afkorting om aan te geven dat een bewijs rond is. En als een bewijs rond is, is er een nieuwe stelling toegevoegd aan de lijst van stellingen. Zo groeit onze kennis stapje voor stapje. In plaats van QED noteren we het einde van een bewijs met een blokje: ‘ ’. Een van de stellingen die in het eerste boek van Euclides’ Elementen wordt bewezen is de stelling van Pythagoras. In een rechthoekige driehoek is de som van de kwadraten van de recht‐ hoekszijden gelijk aan het kwadraat van de schuine zijde.

2


FIGUUR 1.1 Een bewijs van de stelling van Pythagoras in de vorm van

twee plaatjes De stelling van Pythagoras kan op veel verschillende manieren worden bewezen. Een daarvan vindt u in figuur 1.1. (Dit plaatjesbewijs is overigens niet het bewijs dat Euclides geeft.) Een bewijs van een stelling heb je wan‐ neer je kunt laten zien waarom die stelling waar is. Hoe laten de twee plaatjes zien dat de stelling van Pythagoras waar is? Hieronder volgt het bewijs in woorden. Bewijs Figuur 1.1 bevat twee vierkanten van dezelfde grootte. Links staan er twee donkere vierkanten in, en rechts één. Noem de zijde van het kleinste vier‐ kant links a, de zijde van het grotere vierkant links b, en de zijde van het gekantelde vierkant rechts c. Zowel links als rechts zien we viermaal een rechthoekige driehoek. Al deze driehoeken hebben als korte rechthoeks‐ zijde a, als lange rechthoekszijde b en als schuine zijde c. De oppervlakte van het vierkant in het linkerplaatje wordt gegeven door: ( a + b)2 = a 2 + 2 ab + b2 Hierbij geeft 2ab dus de oppervlakte aan van de vier driehoeken samen. Het vierkant in het rechterplaatje is even groot, maar hier wordt de oppervlakte gegeven door: c 2 + 2 ab Immers, 2ab is weer de oppervlakte van de vier driehoeken samen. Omdat de volledige vierkanten even groot zijn, volgt nu: a 2 + 2 ab + b2 = c 2 + 2 ab Dit kan worden vereenvoudigd tot: a 2 + b2 = c 2 En dit laatste is precies wat moest worden aangetoond.

3


1.2 De wortel uit twee is geen breuk De oude Grieken waren dol op constructies met behulp van passer en liniaal. Meetkunde gaat over cirkels en lijnen; cirkels teken je met een passer en lijnen trek je met een liniaal. Met passer en liniaal kun je een loodlijn construeren in een punt P op een lijn l. De loodlijn moet lijn l in P snijden onder een hoek van 900 (een rechte hoek). De benaming ‘loodlijn’ is ontleend aan het ‘loodkoord’ waarmee een metselaar ervoor zorgt dat het muurtje dat hij aan het metselen is precies verticaal is.

FIGUUR 1.2 De passer‐en‐lineaalconstructie van een loodlijn

In figuur 1.2 visualiseren we de constructie. Punt P is het zwarte rondje, en de gegeven lijn l is de niet‐gestippelde lijn. Eerst trekken we een willekeu‐ rige cirkel met P als middelpunt. Dit is de kleine cirkel in de figuur. Deze cirkel snijdt de lijn in twee punten. We trekken nu twee cirkels met deze snijpunten als middelpunt. Als straal van die cirkels nemen we de afstand tussen deze twee snijpunten (in feite komt dit niet zo nauw, zolang deze twee grotere cirkels elkaar maar snijden). Door de snijpunten van deze twee grotere cirkels trekken we een lijn. Dit is de loodlijn l’ op l, door P. Hoewel het liniaal van de oude Grieken geen schaalverdeling had, kunnen we wel een eenheidsmaat afspreken. We passen dan een of andere lengte af met de passer, en spreken af dat we die lengte 1 noemen. Dat is dan de afgesproken eenheidsmaat. Bij een driehoek met een rechte hoek en rechthoekszijden van lengte 1 geldt volgens de Stelling van Pythagoras dat het kwadraat van de schuine zijde gelijk is aan 2 (tweemaal de eenheidsmaat). Als we de schuine zijde x noe‐ men, wil dit zeggen: x 2 = 2. Met passer en liniaal kunnen we nu een lijnstuk ter lengte van deze x construeren. Neem daartoe een lijnstuk AB en noem de lengte van dat lijnstuk 1. We hebben geen liniaal met schaalverdeling, maar we kunnen wel de lengte van AB als de eenheidsmaat beschouwen van een schaal die

4


we zelf construeren. Noem de lijn die door A en B gaat l. Teken nu een loodlijn op l in het punt A. Bepaal met een passer een punt C op die loodlijn (zet de passer in A, neem als straal AB, en trek de cirkel; het snijpunt met de loodlijn is het gewenste punt C), op afstand 1 van A. Het lijnstuk CB heeft lengte x. Zie figuur 1.3.

FIGUUR 1.3 Het construeren van 2

Constructies met passer en liniaal zijn elementair en van een bijzondere schoonheid. De oude Grieken geloofden ook in de schoonheid van simpele verhoudingen. Als een strak gespannen snaar wordt verdeeld in stukken die zich verhouden als 1 : 2 of 2 : 3 of 3 : 4 of 4 : 5, dan zijn de tonen die je krijgt door die twee snaarstukken te tokkelen of aan te strijken in samen‐ klank met elkaar en klinkt er een harmonisch interval (bij 1 : 2 een octaaf, bij 2 : 3 een kwint, bij 3 : 4 een kwart, bij 4 : 5 een grote terts, bij 5 : 6 een kleine terts). Dit komt omdat bij dezelfde snaardikte en snaarspanning een twee keer zo lange snaar twee keer zo langzaam trilt, maar dat wisten de Grieken nog niet. De snaarverhoudingen a : b corresponderen dus met verhoudingen van trillingsfrequenties b : a. Stapelingen geven harmonische drieklanken. Zo levert de frequentieverhouding 4 : 5 : 6 een grote terts‐ akkoord op. De buitenste twee tonen staan in verhouding 4 : 6 of 2 : 3, dus ze vormen een kwint, de laagste twee vormen samen een grote terts, en de hoogste twee vormen samen een kleine terts. Voor Pythagoras en zijn leerlingen, die deze verhoudingen ontdekten, illustreerde dit dat de kosmos geordend is door eenvoudige getalsverhoudingen. Alle mooie verhoudingen zijn eenvoudige breuken. Verhoudingen zijn direct verbonden met breuken. De breuken zijn alle getallen van de vorm: p q Hierin zijn p en q gehele getallen, en p is de teller en de noemer q is ongelijk aan 0. We duiden de verzameling van alle breuken aan met _ . Dit heet ook wel de verzameling van rationale getallen (getallen die een ratio of ver‐ houding aangeven). We schrijven zo’n breuk ook wel als p q . Deze breuk drukt eigenlijk de verhouding p : q uit.

5


STELLING 1.2

Tot hun verbijstering ontdekten Griekse wiskundigen op zeker ogenblik dat sommige van de lijnstukken die je met passer en liniaal kunt constru‐ eren een lengte hebben die niet als breuk valt uit te drukken. We zagen hiervoor dat je een rechthoekige gelijkbenige driehoek met rechthoekszijde 1 en schuine zijde x, met passer en liniaal kunt construeren. Maar x is geen breuk. Er bestaat geen breuk x met x 2 = 2. Bewijs Neem aan dat er een breuk x bestaat met x 2 = 2. Zo’n breuk heeft een teller m en een noemer n, met m en n allebei natuurlijke getallen, en de noemer n ongelijk aan 0. We mogen aannemen dat de breuk m n niet verder te vereenvoudigen is, dat wil zeggen m en n hebben geen gemeenschappelijke factoren. Preciezer: er zijn geen natuurlijke getallen k, p, q met k ≠ 1, m = kp en n = kq. De breuk 2 10 kan worden vereenvoudigd, want de teller en noemer heb‐ ben een factor 2 gemeenschappelijk. Deze breuk kan door teller en noemer door 2 te delen op haar eenvoudigste vorm worden gebracht: 1 5 . Teller en noemer hebben nu geen gemeenschappelijke factoren meer. Goed, we nemen aan dat x = m n , met m en n zonder gemeenschappelijke factoren. Dan geldt: 2

⎛m⎞ x2 = ⎜ ⎟ = 2 ⎝n⎠ Hieruit volgt dus: 2

⎛m⎞ m2 2=⎜ ⎟ = 2 n ⎝n⎠ Door beide zijden met n2 te vermenigvuldigen vinden we: 2n2 = m2 Met andere woorden: m2 is even. Omdat kwadraten van oneven getallen altijd oneven zijn (immers, (2n + 1)2 = 4n2 + 4n + 1 is oneven) moet m even zijn. Er is dus een natuurlijk getal p met m = 2p. Invullen van 2p voor m in 2n2 = m2 geeft nu: 2n2 = (2 p)2 = 4 p 2 Hieruit blijkt dat: n2 = 2 p 2

6


STELLING 1.3

En dit leidt weer tot de conclusie dat n ook even is. Maar dat betekent dat er een natuurlijk getal q is met n = 2q. Dit brengt ons in tegenspraak met de aanname dat m n een breuk is in eenvoudigste vorm: we hebben immers een gemeenschappelijke factor 2 gevonden. Hieruit volgt dat er geen breuk x is met x 2 = 2 , dat wil zeggen: de vierkantswortel uit 2 is geen breuk. De bewering die in stelling 1.2 wordt bewezen heeft de vorm van een ontkenning: het is niet zo dat de wortel uit 2 een breuk is. Die ontkenning wordt aangetoond door aan te nemen dat er wel zo’n breuk is. 1.3 Een bewijs zonder constructie We weten nu dat de wortel van twee geen rationaal getal is. Hiermee heb‐ ben we dus meteen in het algemeen aangetoond dat er rationale getallen x en y zijn, zodat x y niet rationaal is, namelijk x = 2 en y = 1 2 , want daarmee 1 volgt: 2 2 = 2 . Dus met machtsverheffen kunnen we uit de rationale getallen een irrationaal getal maken. We kunnen natuurlijk ook met machtsverheffen uit twee rationale getallen een ander rationaal getal maken, neem maar x = y = 2, dan hebben we 2 2 = 4 en 4 is rationaal. Laat r voor rationaal staan, en i voor irrationaal, dan hebben we nu r r = i en r r = r . Welke andere mogelijkheden zijn er nog? We hebben ook nog r i = r en i r = r , bijvoorbeeld 0 2 = 0 , want 0 blijft 0 ver‐ heven tot welke macht dan ook, en ( 2 )0 = 1 , want ieder getal (ongelijk 0) tot de macht 0 is 1. Zouden er twee irrationale getallen zijn die, als de een tot de macht van de ander wordt verheven, weer een rationaal getal opleveren? Dit kunnen we aantonen in wat een puur existentiebewijs wordt genoemd: we kunnen bewij‐ zen dat die getallen moeten bestaan, alleen weten we niet wat de getallen zijn. We formuleren dat hieronder in een stelling en geven daarvan het bewijs. Er zijn twee irrationale getallen, zodat de een tot de macht van de ander rationaal is. Bewijs We zoeken irrationale getallen x en y zodat x y rationaal is. Hieraan voldoen ofwel x = y = 2 (i) ofwel x= 2

7

2

en y = 2 (ii)


Waarom? Om te beginnen: het is duidelijk dat ( 2 ) 2 rationaal is of niet rationaal is. In het eerste geval zitten we in situatie (i). Maar zo niet, dan zitten we in situatie (ii), omdat immers geldt dat: 2

2 ⎞ 2× 2 2 ⎛ = 2 =2 ⎜ 2 ⎟ = 2 ⎝ ⎠ 2 De getallen die we zoeken zijn dan x = 2 en y = 2 . Helaas vertelt dit bewijs ons niet welke van (i) of (ii) waar is. Het bewijs helpt ons niet zo’n getallenpaar te construeren. Daarom heet het een exis‐ tentiebewijs. Overigens, om u niet al te onzeker te houden: in feite is (ii) het geval. Dit staat bekend als de stelling van Gelfond‐Schneider, uit 1934. Bewijs en constructie gaan al sinds de Oudheid samen, maar dit oude the‐ ma is tegelijkertijd hypermodern. In de informatica hebben we niets aan zuivere existentiebewijzen, en alleen iets aan bewijzen waarmee we objec‐ ten door middel van een programma of algoritme kunnen construeren. Dat thema zal in hoofdstukken 5 en 7 meer concreet terugkomen als we zien hoe computers rekenen. En zelfs in de dagelijkse praktijk hebben we weinig aan louter een bewijs dat we morgen in Dunedin kunnen zijn zon‐ der een expliciet plan om daar ook daadwerkelijk te komen. Een algemeen inzicht in bewijsvormen en bijbehorende constructies is dus ook relevant voor de dagelijkse praktijk van ons menselijk gedrag. 1.4 Overzicht van de inhoud van het boek We hebben deze verschillende voorbeelden van bewijzen gegeven om te illustreren dat precisering en formalisering van redeneringen een heel be‐ langrijke rol spelen in de wetenschap, en al sinds de oudheid met name in de wiskunde en in de wijsbegeerte. Een belangrijke traditionele rol van de logica is om wiskundige bewijsvoering precisie te geven, en om filosofische begripsvorming te ondersteunen. Tevens zijn er vele dwarsverbanden met recente wetenschaps‐ en toepassingsgebieden zoals de theoretische infor‐ matica en de kunstmatige intelligentie, en de laatste jaren ook de speltheo‐ rie en cognitiewetenschap. Deze breedte is niet toevallig. Het werkterrein van de logica is niet beperkt tot de wetenschap, want ook ons gewone gedrag wordt voortdurend gestuurd door redeneren. En al maken we dan soms fouten, dat alledaagse redeneervermogen is historisch‐evolutionair de oorspronkelijke bron van ons wetenschappelijk denken. Dit boek loopt dan ook van het meest verheven wiskundig bewijzen tot het meest alledaagse redeneren, en in feite tot informatieoverdracht van elke soort. Daarmee is

8


de logica een ideaal ‘uitkijkpunt’ om verbanden te zien tussen allerlei disciplines die vaak als gescheiden werelden worden beschouwd. Wel blijft een feit dat de wiskunde een speciale rol speelt, zelfs in de brede visie op logica die u zult vinden in dit boek. Het gaat dan niet om het ter‐ rein van studie op zich, maar om de methode waarmee we dat doen. Logici hebben in de loop van de geschiedenis geleerd dat het bijzonder goed werkt om stukjes redeneerpraktijk en informatiepraktijk als wiskundig systeem te definiëren, en dan verder te ontwikkelen. In de volgende twee hoofdstukken, ‘Hoofdstuk 2, Propositielogica, waar‐ heid en classificeren’ en ‘Hoofdstuk 3, Wie A zegt moet B zeggen’, behan‐ delen we de logica van beweringen op zinsniveau en hun onderlinge logische verbanden. Dit is de propositielogica waarin we redeneringen kunnen formaliseren zoals ‘als bewering p het geval is en als bewering p → q (p impliceert q) waar is, dan is q ook waar’. We onderzoeken ook propositielogische beweringen als p ∨ ¬p (p of niet‐p) die altijd waar zijn. In de twee daaropvolgende hoofdstukken, ‘Hoofdstuk 4, Predikaatlogica, modellen en programma’s’ en ‘Hoofdstuk 5, Predikaatlogica en infor‐ matica’, behandelen we de predikaatlogica. Dit is de logica waarin beroemde redeneringen als “Alle mensen zijn sterfelijk. Socrates is een mens. Dus: Socrates is sterfelijk.” geformaliseerd kunnen worden. We kunnen deze logica zien als een uitbreiding van de propositielogica, namelijk als een logica waarin beweringen op zinsniveau ook nog aanvullende structuur hebben: als de zin ‘Jan is de vader van Emma’ is, dan zouden we hier in propositielogica p voor kunnen schrijven, maar in predikaatlogica P(j, e), waarbij P voor ‘vader zijn van’ staat, j voor Jan, en e voor Emma. Meer structuur, dus. Deze structuur blijkt zowel getrouwer aan de natuurlijke taal waarmee wij communiceren als aan de beschrijving van meer tech‐ nische verschijnselen, zoals de rekenprocessen van een computer. Na het hoofdstuk over predikaatlogica komt een hoofdstuk over de logica van kennis, ‘Hoofdstuk 6, Kennis en communicatie’. Deze logica is ook te zien als een uitbreiding van de propositielogica, maar een heel ander soort uitbreiding dan de predikaatlogica. De laatste twee hoofdstukken behandelen een aantal nogal ‘moderne’ onderwerpen in de logica: ‘Hoofdstuk 7, Complexiteit van berekeningen’ laat zien hoe ‘lang’ berekeningen bij programmeren en bij logische taken kunnen duren. Dit weerspiegelt een belangrijk algemeen thema in vele wetenschappen, van de natuurkunde tot de taalkunde: hoe kunnen wij de in principe aanwezige informatie om ons heen ook werkelijk bevatten en verwerken? ‘Hoofdstuk 8, Spel en logica van interactie’ gaat over een ander fundamen‐ teel modern thema, te weten wisselwerking tussen meerdere personen. De klassieke logica richtte zich op eenzame denkers die conclusie na conclusie trekken. Maar net zoals de natuurkunde pas echt tot haar recht komt als we ‘meerlichamenproblemen’ aanpakken, met onderlinge wisselwerking van deeltjes, geldt dat ook voor ons eigen intelligente gedrag. ‘Logica in actie’

9


zie je op zijn best als mensen communiceren, argumenteren, en strategisch op elkaar ingaan. Het wiskundige model bij uitstek voor deze ‘meergees‐ tenproblemen’ is het spel. We leggen uit dat het spelen van spelletjes op heel serieuze manier bedreven kan worden, zowel binnen de economie als binnen de logica. We besluiten dit boek met een kort afrondend hoofdstuk, waarin een terugblik is opgenomen en een overzicht in vogelvlucht van enkele logische vakgebieden. Dit document bevat hoofdstuk 1 van de cursus Logica in actie. De volledige cursus is beschikbaar op http://www.spinoza.ou.nl. © Open Universiteit Nederland; Uitgeverij: Sdu Uitgevers, ’s‐Gravenhage. Dit materiaal is gelicentieerd onder een Creative Commons Licentie. Zie de licentie voor details. The content on this site is licensed under a Creative Commons Licentie. See licence for more details.

10

Redeneren en bewijzen

Recommend Documents