Lewis Carrolls logische boommethode

Phlizz

Online magazine van het Lewis Carroll Genootschap

Inleiding

Dit is het vierde artikel in een reeks over de logica van Lewis Carroll. De eerste twee artikelen waren enigszins algemeen van karakter en gingen over Carrolls belangstelling voor de logica en de stand van de Britse logica in de 19e eeuw. Het derde artikel behandelde Carrolls logische diagrammen[1]. Deze diagrammen waren één van Carrolls methoden om een groot publiek vertrouwd te maken met logica. Vanwege het visuele karakter zijn ze een goede illustratie van Carrolls streven om de logica te populariseren. Lewis Carroll had nog een sterk visuele methode voor de oplossing van logische problemen, namelijk zijn Method of Trees ofwel Boommethode.
In Carrolls dagboekaantekeningen van 16 juli 1894 lezen we over de ontdekking van deze methode die hij, met een verwijzing naar de vorm van een omgekeerde boom, de voorlopige benaming ‘genealogische methode’ gaf[2]. De boommethode komt niet voor in het eerste deel van Symbolic Logic dat uitkwam in 1896, maar was onderdeel van Carrolls manuscript voor het door hem geplande tweede deel van Symbolic Logic. Dit tweede deel is, als gevolg van zijn dood in 1898, echter onvoltooid gebleven. Pas in 1977 werd een aantal manuscripten ontdekt door W.W. Bartley III, die daarmee een reconstructie heeft gemaakt van het tweede deel van Symbolic Logic[3].
Door die late ontdekking hebben tijdgenoten van Carroll echter geen kennis kunnen nemen van zijn methode. Ten tijde van de ontdekking in 1977 was de logica ingrijpend veranderd, maar het principe van zijn methode was nog steeds toepasbaar. Sterker nog, er waren inmiddels nieuwe technieken ontwikkeld op basis van ditzelfde principe. Hoewel er daardoor geen directe behoefte meer is aan Carrolls uitwerking, is zijn boommethode nog steeds interessant. Hij is een goed voorbeeld van zijn aanpak van en kijk op de logica en tevens een illustratie van de mate waarin hij vooruitliep op toekomstige ontwikkelingen.
Hieronder ga ik eerst algemeen in op de aard van de boommethode, vervolgens schets ik, met behulp van een voorbeeld, Carrolls aanpak en ik sluit af met een evaluerende paragraaf.

Het principe van logische bomen of logische tableaus

Het gebruik in de logica van grafische methoden in de vorm van een boom gaat op zijn minst terug tot de Boom van Porphyrius in de 3e eeuw. Het ging hierbij vooral om een verdeling genera – species, geslacht- en soortbegrippen, gebaseerd op Aristoteles’ categorieën. Mogelijk maakte ook Aristoteles al gebruik van boomstructuren.
We zien de Boom van Porphyrius terug bij Ramon Llull als Arbor Scientiae (1296) en ook bij Leibniz in de tweede helft van de 17e eeuw[4].

De logische boommethode van Lewis Carroll heeft echter een ander karakter. Deze methode komen we sinds de jaren ’50 van de vorige eeuw regelmatig tegen in verschillende variaties en ook in diverse takken van de logica; hij wordt daar vaak aangeduid als de methode van logische tableaus. Ondanks alle variaties heeft de methode steeds een aantal duidelijke karakteristieken[5].

De crux van de methode zit in het gebruik van reductio ad absurdum.
Er is een variëteit aan definities van definities van reductio ad absurdum[6]. In het dagelijks spraakgebruik bedoelt men meestal de debattechniek waarmee wordt beargumenteerd dat het standpunt van de opponent implicaties heeft die bizar zijn, onacceptabel of gewoon onjuist.
In de formele logica wordt de mathematische variant van de reductio gehanteerd. Dat is een redeneervorm met de volgende stappen:[7]

  1. introduceer als aanname het omgekeerde van wat je wilt bewijzen;
  2. leid een tegenspraak af uit deze aanname;
  3. bevestig de gewenste conclusie als een logische consequentie van deze tegenspraak.

Ik geef een eenvoudig voorbeeld. Stel je wilt aantonen dat de wereld rond is. Aangezien de wereld ofwel rond ofwel plat is, moet je als eerste stap aannemen dat de wereld niet rond is maar plat. Dat zou betekenen dat we van de wereld vallen, als we maar lang genoeg doorlopen. Omdat dit duidelijk niet het geval is, betekent dit dat de wereld niet plat is. Dit is in tegenspraak met onze aanname (stap 2). De logische consequentie is dan dat de wereld rond is, omdat hij ofwel rond ofwel plat is (stap 3).
Deze redeneervorm veronderstelt twee door Aristoteles geformuleerde principes:

  • het principe van contradictie: Er is geen ding waarop zowel de eigenschap P als de eigenschap niet-P van toepassing is, en
  • het principe van het uitgesloten derde: Op ieder ding is P of niet-P van toepassing[8].

Een logische boom- of tableaumethode begint dus met een aanname die het omgekeerde is van wat we willen bewijzen. Voor dit bewijs wordt de aanname ‘afgebroken’, d.w.z. gesplitst in verschillende mogelijke gevallen, alternatieve scenario’s en deze worden weergegeven als takken van een boom.
Het gaat er vervolgens om voor al deze takken afzonderlijk aan te tonen dat ze tot een tegenspraak leiden. De betreffende tak wordt dan ‘gesloten’. De methode kent regels die de voorwaarden aangeven waaronder de verschillende takken gesloten kunnen worden. Als iedere tak gesloten is, wordt gezegd dat de boom of het tableau zelf gesloten is. Een gesloten tableau dat begint met de bewering dat A niet geldig is, betekent een tableau-bewijs van A.
De vorm van het tableau is een omgekeerde boom, met vertakkingen naar beneden.

Omdat ten tijde van Lewis Carroll categorische uitspraken, d.w.z. uitspraken over verzamelingen, overheersend waren in de formele logica, gebruikte hij zijn boommethode voor redeneringen met categorische uitspraken. Later is de methode vooral vaak toegepast in de propositielogica en de uitbreiding daarvan in de predicatenlogica. Propositielogica gaat over de relaties tussen proposities, d.w.z. uitspraken die waar of onwaar zijn.
Als bijvoorbeeld A en B proposities zijn, dan zijn ‘en’ en ‘of’ mogelijke relaties tussen A en B, met als resultaat de samengestelde proposities ‘A en B’ en ‘A of B’.
In de oudheid was bij de Stoicijnen (4e eeuw BC) al sprake was van propositielogica en ook in de Middeleeuwen (Pierre Abelard, 12e eeuw). Carrolls tijdgenoot George Boole zette een flinke stap voorwaarts met een symbolische propositielogica, maar de basis van de moderne propositielogica danken we aan Gottlob Frege’s Begriffschrift uit 1879,  een werk dat bij de Britse logici pas in de 20e eeuw bekend werd dankzij Bertrand Russell.  In de symbolische logica van  Lewis Carroll vinden we geen propositielogica.

In feite is de propositielogica de eenvoudigste vorm van logica. Daarom zal ik het principe van de boommethode uitleggen aan de hand van een voorbeeld uit de propositielogica. In de volgende paragraaf zullen we de toepassing van Lewis Carroll zien voor redeneringen met categorische uitspraken; deze is ingewikkelder en daardoor minder geschikt als illustratie van de methode voor lezers die er nog niet mee vertrouwd zijn.

Voor een goed begrip van het voorbeeld zijn wel twee zaken nodig:

  • een overzicht van de belangrijkste symbolen van de propositielogica;
  • een overzicht van de geldende regels, bepalingen, voor zover relevant voor ons voorbeeld.

De belangrijkste symbolen uit de propositielogica zijn de volgende[9]:

Relevante bepalingen uit de boommethode voor propositielogica[10]:

Gebruikmakend van deze symbolen en bepalingen, geef ik nu een voorbeeld in de propositielogica. We gaan de juistheid checken van de volgende redenering (met voorbeeld-uitspraken voor A, B en C, ter verduidelijking):

We gaan voor deze check nu uit van de ontkenning van de conclusie (d.w.z. ‘Het is niet zo dat als A dan C’), die we toevoegen aan de hypothesen. Het is de bedoeling om aan te tonen dat deze ontkenning van de conclusie in alle gevallen tot een tegenspraak leidt.
We construeren nu als volgt een boom:

Weergegeven in een boomstructuur ziet dat er als volgt uit:
(Met ‘X’ wordt aangegeven dat een tak afgesloten is)

Uitgaande van de hypotheses in regel 1 en 2, leidt de ontkenning van de gewenste conclusie (regel 3) in alle gevallen tot een tegenspraak. Daarmee is aangetoond dat de gewenste conclusie AC  juist is.

Carrolls boommethode

Zoals in de vorige artikelen naar voren kwam, hield Carrolls symbolische logica zich bezig met redeneringen in de vorm van syllogismen (twee premissen en een conclusie) of van sorites (meer dan twee premissen en een conclusie). Centraal daarbij stond het zgn. eliminatieprobleem: het onttrekken aan informatie aan de vooronderstellingen om een conclusie te formuleren. Zowel de premissen als de conclusie hadden in syllogismen en sorites de vorm van categorische uitspraken: uitspraken over verzamelingen.
Carroll had al een aantal methoden ontworpen voor het eliminatieprobleem, waaronder zijn logische diagrammen, maar hij vond deze methoden niet bevredigend als er sprake was van een groot aantal premissen. Daartoe bedacht hij de boommethode. Voor zover nu bekend was Lewis Carroll de eerste die de hierboven beschreven logische boommethode gebruikte.

Carroll hanteerde de boommethode om de juistheid van een conclusie te bewijzen. Eerder had hij al een mechanische methode ontworpen om te bepalen welke termen uit de premissen zouden moeten voorkomen in de conclusie (retinends) en welke termen geëlimineerd zouden moeten worden (eliminands)[11].

Essentieel voor de boommethode was, zoals gezegd, het gebruik van reductio ad absurdum, een redeneerwijze waarmee Carroll meer dan vertrouwd was.
Carroll was een bewonderaar van de Griekse wiskundige Euclides (ca. 300 v. Chr.), die veelvuldig gebruik maakte van reductio ad absurdum.  In zijn voornaamste werk (Elementen) presenteerde Euclides zijn meetkunde als een samenhangend systeem, afgeleid uit een beperkte set axioma’s. In Euclid and his Modern Rivals uit 1879 verdedigde Carroll Euclides’ Elementen tegenover tijdgenoten die het wilden vervangen door moderne meetkunde-leerboeken. Ook in de Alice-boeken komen we regelmatig vormen van reductio ad absurdum tegen[12].

Carrolls boommethode vertoont enige verwantschap met de methode van het Antilogisme van zijn tijdgenote Christine Ladd-Franklin. Zij ontwierp deze methode voor het testen van de juistheid van de conclusie op basis van een vorm waarin alle syllogismen kunnen worden gegoten, uitgaande van de premissen en de ontkenning van de conclusie (“an inconsistent triad”). Deze methode is te vinden in een publicatie uit 1883; Carroll had deze publicatie in zijn bezit en nam er (met verwijzing) ook enkele voorbeelden uit over[13]. Het lijkt daarom niet onwaarschijnlijk dat hij door Ladd-Franklins artikel beïnvloed is, doch hij legt de link niet bij de beschrijving van zijn methode[14].

Ik zal nu een voorbeeld geven van Carrolls gebruik van de boommethode voor een sorites met 7 premissen. Het is afkomstig van Carroll en ontleend aan Symbolic Logic, part II[15].
Het voorbeeld werkt op basis van de hierboven beschreven principes, maar wordt dus toegepast op categorische uitspraken. Het is in vergelijking met de andere voorbeelden die Carroll geeft, nog relatief eenvoudig.

Om het voorbeeld te kunnen volgen, geef ik nu eerst een overzicht van de door Carroll zelf ontworpen en gebruikte notatie.

Het voorbeeld gaat uit van zeven premissen:

In een boomstructuur ziet dat er als volgt uit[16]:

(Een afgesloten tak wordt aangegeven met ‘Ο’)

Zoals gezegd, was dit nog een relatief eenvoudig voorbeeld. Ter illustratie geef ik hier de boom weer voor een sorites met 26 premissen: [17]

Betekenis en impact

Mechanische technieken en apparaten hadden een bijzondere aantrekkingskracht op Lewis Carroll. Hij had een elektrische pen en een chromograaf, die beide als voorloper van de typemachine kunnen worden beschouwd. Hij bedacht een ‘nyctograaf’ als hulpmiddel om in het donker te kunnen schrijven en experimenteerde met verschillende coderingsmethoden. Hij bracht een bezoek aan Charles Babbage doch moest tot zijn teleurstelling constateren dat door Babbage beschreven ‘analytical engine’ nog slechts in zijn hoofd bestond.
Met zijn boommethode was Lewis Carroll de eerste in de moderne tijd die een mechanische procedure ontwierp om de geldigheid aan te tonen van de conclusie van een ingewikkeld probleem[18]. Deze uitvinding had echter geen directe impact, mede omdat Carroll er niet over communiceerde met zijn vakgenoten en het zou tot 1977 duren voordat zijn vinding ‘ontdekt’ werd. In de tussenliggende tijd was niet alleen de logica ingrijpend veranderd maar hadden ook andere logici vergelijkbare methoden ontworpen die aansloten bij de ontwikkelingen van de logica.

Sinds de jaren ‘50 van de vorige eeuw worden boomstructuren gebruikt in computerprogramma’s om wiskundige stellingen te bewijzen; daarbij wordt veelvuldig gebruik gemaakt van reductio ad absurdum. De moderne boommethode voor propositie- en predicatenlogica vindt zijn oorsprong in het werk van Gerhard Gentzen uit 1934. Dit inspireerde de Nederlandse logicus Evert Beth tot zijn tableaumethode die sterke overeenkomsten vertoont met de boommethode van Carroll. Beth presenteerde zijn tableaumethode voor het eerst in een lezingencyclus in Parijs op 31 maart 1954. Maar de betreffende tekst werd pas uitgegeven in 1955 en intussen had de Fin Jaakko Hintikka een vergelijkbaar idee gekregen. Beth en Hintikka publiceerden min of meer gelijktijdig en onafhankelijk van elkaar. De door Beth en Hintikka beschreven methode werd vervolgens voortgezet door o.a. Smullyan en Jeffrey. De tableaumethode was een belangrijke stap in de ontwikkeling van de geautomatiseerde bewijsvoering[19].

Op basis van de tableaus van Beth ontwierp Paul Lorenzen de methode van dialogische tableaus: een formeel spel met de vorm van een discussie tussen een voor- en tegenstander van een uitspraak[20]. De tableaumethode is bijzonder goed bruikbaar voor de dialoogvorm. In dit verband is het opvallend dat Carroll bij de uitleg die hij bij zijn voorbeelden verschaft de vorm kiest van een soliloquy, waarin hij zijn overwegingen verwoordt in een vraag- en antwoordspel met zichzelf.

De boommethode is een illustratie van de specifieke meerwaarde van Carrolls symbolische logica: naast het populariserende, visuele karakter is dat het mechaniseren van logische redeneringen.
Het moet uitgesloten worden geacht dat een van de hierboven genoemde logici kennis had genomen van Carrolls boommethode. Dit doet echter niets af aan het feit dat Carroll met zijn methode anticipeerde op ontwikkelingen in de geautomatiseerde bewijsvoering en daarmee zijn tijd in feite ruim vooruit was.

—–

Voetnoten

[1] Deze artikelen verschenen in 2019 en 2020 in Phlizz, online magazine van het Lewis Carroll Genootschap.

[2] “Today has proved to be an epoch in my Logical work. It occurred to me to try a complex Sorites by the method I have been using for ascertaining what cells, if any, survive for possible occupation when certain nullities are given. I took one of 40 premisses, with ‘pairs’ within pairs,’ and many bars, and worked it like a genealogy, each term proving all its descendants. I came out beautifully, and much shorter than the method I have used hitherto. I think of calling it the ‘Genealogical Method.’” [Wakeling 2005, p.155]

[3] Bartley 1977.

[4] Zie Anellis & Abeles 2016.

[5] Zie Fitting 1999.

[6] Zie Savenije 2017.

[7] Zie bijvoorbeeld Suppes 1957.

[8] De wet van het uitgesloten derde wordt overigens niet universeel geaccepteerd: de intuïtionistische wiskunde, bijvoorbeeld, verwerpt deze wet.

[9] Bij een inclusief ‘of’ is de uitspraak ‘A of B’ waar als één van beide uitspraken waar is maar ook als beide uitspraken waar zijn. Deze laatste mogelijkheid is uitgesloten bij een exclusief ‘of’.

[10] Twee uitspraken A en B zijn equivalent als A dan en slechts dan waar is als B ook waar is.

[11] Ik zie er van af om deze methode, ‘Register of Attributes’ hier uiteen te zetten: hij is niet wezenlijk voor het begrip van de boommethode die uitgaat van een geformuleerde conclusie.

[12] Zie Savenije 2017 en 2019.

[13] Bartley 1977, p.478.

[14] Zie Abeles 1990, Anellis & Abeles 2016.

[15] Bartley 1977, pp.292-295.

[16] Bartley 1977, p.295.

[17] Bartley 1977, p.312.

[18] Abeles 1990.

[19] Abeles 2005, van Ulsen 2001.

[20] Zie Lorenzen & Lorenz 1978.


Literatuur

Abeles, Francine, 1990, ‘Lewis Carroll’s Method of Trees: Its Origins in Studies in Logic’, The Review of Modern Logic, Vol. 1 (1), pp.25-35.

Abeles, Francine, 2005, “From the Tree Method in Modern Logic to the Beginning of Automated Theorem Proving’, in Shell-Gellasch & Jardine (eds.), pp.149-160.

Abeles, Francine & Mark E. Fuller, 2016, Modern Logic 1850-1950, East and West, Birkhäuser.

Anellis, Irving H. & Francine Abeles, 2016, ‘The Historical Sources of Tree Graphs and the Tree Method in the Work of Peirce

and Gentzen’, in Abeles & Fuller (eds.), 2016, pp.35-97.

Bartley, William Warren III (ed.), 1977, Lewis Carroll’s Symbolic Logic, New York: C.N. Potter.

Beth, Evert, 1955, Semantic Entailment and Formal Derivability, Amsterdam: North-Holland.

D’Agostino, Marcello, Dov M. Gabbat, Reiner Hähnle & Joachim Posegga (eds.), 1999, Handbook of Tableau Methods, Dordrecht: Kluwer Academic Publishers.

Fitting, Melvin, 1999, ‘Introduction’, in D’Agostino et al. (eds.), 1999, pp.1-44.

Gentzen, Gerhard, 1934, ‘Untersuchungen über das logische Schliessen’, Mathematische Zeitschrift, vol. 39, pp.176-210, pp.405-431.

Hintikka, Jaakko, 1955, ‘Form and Content in Quantification Theory’, Acta Philosophica Fennica – Two Papers on Symbolic Logic, 8, pp.8-55.

Jeffrey, Richard, 1967, Formal Logic. Its Scope and Limits, New York: McGraw-Hill.

Ladd-Franklin, Christine, 1883, ‘On the Algebra of Logic’, in Peirce 1883, pp.17-71.

Lorenzen, Paul, & Kuno Lorenz, 1978, Dialogische Logik, Darmstadt: Wissenschaftliche Buchgesellschaft.

Peirce, C.S. (ed.), 1883, Studies in Logic by the Members of the Johns Hopkins University, Boston: Little, Brown & Co.

Savenije, Bas, 2017, ‘Contrariwise. Reductio ad Absurdum in the Alice Books’, dodo/nodo, No. 1, pp.32-43. Zie ook https://bassavenije.nl/pdf/56-2017-Contrariwise.pdf.

Savenije, Bas, 2019, ‘Tweedledee’s Logic: Squaring Reductio ad Absurdum’, in The Carrollian: The Lewis Carroll Journal, No. 32, p. 3-26. Zie ook https://bassavenije.nl/wp-content/uploads/2019/06/Savenije-2019-Tweedledees-Logic.pdf.

Shell-Gellash, Amy & Dick Jardine (eds.), 2005, From Calculus to Computers. Using the Last 200 Years of Mathematics History in the Classroom, Mathematical Association of America.

Suppes, Patrick, 1957, Introduction to Logic, New York: Van Nostrand.

Ulsen, Paul van, 2001, E.W. Beth als logicus, verbeterde elektronische versie van het academisch proefschrift ter verkrijging van de graad van doctor aan de Universiteit van Amsterdam, 2000, https://www.illc.uva.nl/Research/Publications/Dissertations/DS-2000-04.text.pdf.

Wakeling, Edward (ed.), 2005, Lewis Carroll’s Diaries. The private journals of Charles Lutwidge Dodgson (Lewis Carroll), vol. 9, Clifford, Herefordshire: Lewis Carroll Society.