Een beknopte inleiding tot de logica

8.1 een historisch voorbeeld

in zijn boek, De twee nieuwe wetenschappen, Galileo Galilea (1564-1642) geeft een aantal argumenten bedoeld om aan te tonen dat er niet zoiets kan bestaan als werkelijke oneindigheden of werkelijke infinitesimalen. Een van zijn argumenten kan als volgt worden gereconstrueerd. Galileo stelt voor dat we ervan uitgaan dat er een werkelijke oneindigheid van natuurlijke getallen is (de natuurlijke getallen zijn de positieve gehele getallen vanaf 1):

{1, 2, 3, 4, 5, 6, 7, ….,}

hij stelt ook voor dat we als een premisse nemen dat er een werkelijke oneindigheid is van de kwadraten van de natuurlijke getallen.

{1, 4, 9, 16, 25, 36, 49, ….}

nu, Galileo redenen, merk op dat deze twee groepen (vandaag zouden we ze “sets” noemen) hebben dezelfde grootte. We kunnen dit zien omdat we kunnen zien dat er een één-op-één correspondentie tussen de twee groepen is.,

{1,	2,	3,	4,	5,	6,	7, ….,div>
{1,	4,	9,	16,	25,	36,	49, …}

Als we in verband kunnen brengen elk natuurlijk getal met één en slechts één vierkante nummer, en als we kunnen associëren elke vierkante aantal met slechts één natuurlijk getal, dan is deze sets moeten van dezelfde grootte zijn.,

Maar Wacht even, zegt Galileo. Er zijn natuurlijk veel meer natuurlijke getallen dan er vierkante getallen zijn. Dat wil zeggen, elk vierkant getal staat in de lijst van natuurlijke getallen, maar veel van de natuurlijke getallen staan niet in de lijst van vierkante getallen. De volgende getallen staan allemaal in de lijst van natuurlijke getallen, maar niet in de lijst van vierkante getallen.

{2, 3, 5, 6, 7, 8, 10, ….,}

dus, Galileo redeneert, als er veel getallen in de groep van natuurlijke getallen zijn die niet in de groep van de kwadraatgetallen zitten, en als er geen getallen in de groep van de kwadraatgetallen zijn die niet in de naturalengetallen zitten, dan zijn de natuurlijke getallen groter dan de kwadraatgetallen. En als de groep van de natuurlijke getallen groter is dan de groep van de vierkante getallen, dan zijn de natuurlijke getallen en de vierkante getallen niet dezelfde grootte.,

We zijn tot twee conclusies gekomen: de verzameling van de natuurlijke getallen en de verzameling van de vierkante getallen zijn dezelfde grootte; en, de verzameling van de natuurlijke getallen en de verzameling van de vierkante getallen zijn niet dezelfde grootte. Dat is tegenstrijdig.

Galileo stelt dat de reden dat we een tegenstrijdigheid hebben bereikt, is omdat we veronderstelden dat er werkelijke oneindigheden zijn. Hij concludeert dan ook dat er geen werkelijke oneindigheden zijn.

8.2 indirecte bewijzen

onze logica is nog niet sterk genoeg om enkele geldige argumenten te bewijzen. Beschouw het volgende argument als een voorbeeld.,

(P→(QvR))

Q

R

P

Dit argument lijkt geldig. Door de eerste aanname weten we: als P waar was, dan zou (Q v R) waar zijn. Maar dan zou Q of R of beide waar zijn. En door de tweede en derde premissen weten we: Q is onwaar en R is onwaar. Het kan dus niet zo zijn dat (Q v R) waar is, en dus kan het niet zo zijn dat P waar is.

we kunnen het argument controleren met behulp van een waarheidstabel. Onze tafel zal complex zijn omdat een van onze premissen complex is.,

T F T F T T F T T F F T T T T F T F F F F T T T T

In any kind of situation in which all the premises are true, the conclusion is true., Dat wil zeggen: de premissen zijn allemaal waar alleen in de laatste rij. Voor die rij is de conclusie ook waar. Dus, dit is een geldig argument.

maar neem een minuut en probeer dit argument te bewijzen. We beginnen met

en nu zijn we gestopt. We kunnen geen van onze regels toepassen. Hier is een geldig argument dat we ons redeneersysteem niet sterk genoeg hebben gemaakt om te bewijzen.

er zijn verschillende manieren om dit probleem te verhelpen en ons redeneersysteem sterk genoeg te maken., Een van de oudste oplossingen is het introduceren van een nieuwe bewijsmethode, traditioneel “reductio ad absurdum” genoemd, wat een reductie tot absurditeit betekent. Deze methode wordt ook vaak een “indirect bewijs” of “indirecte afleiding”genoemd.

het idee is dat we uitgaan van de ontkenning van onze conclusie, en dan laten zien dat een tegenstrijdigheid resulteert. Een tegenstrijdigheid wordt getoond wanneer we een zin Ψ bewijzen, en zijn negatie Ψ. Dit kan elke zin zijn. Het punt is dat, gezien het principe van bivalentie, we iets vals moeten hebben bewezen. Want als Ψ waar is, dan is Ψ onwaar; en als Ψ waar is, dan is Ψ onwaar., We hoeven niet te weten wat vals is (Ψ Of Ψ); het is genoeg om te weten dat een van hen moet zijn.

onthoud dat we ons logische systeem zo hebben gebouwd dat het geen valsheid kan produceren uit ware verklaringen. De bron van de leugen die we produceren in de indirecte afleiding moet daarom een leugen zijn die we aan ons argument hebben toegevoegd. En wat we aan ons argument hebben toegevoegd is de ontkenning van de conclusie. De conclusie moet dus waar zijn.,

de vorm van het argument is als volgt:

traditioneel wordt de aanname voor indirecte afleiding ook vaak”de aanname voor reductio” genoemd.

als concreet voorbeeld kunnen we onze verbijsterende zaak bewijzen.

we veronderstelden de ontkenning van onze conclusie op Regel 4. De conclusie die we dachten dat juist was, was P, en de ontkenning hiervan is P. in lijn 7 beweerden we R., Technisch gezien zijn we klaar op dat punt, maar we willen vriendelijk zijn voor iedereen die ons bewijs probeert te begrijpen, dus we herhalen regel 3 zodat de zinnen R en R naast elkaar staan, en het is heel gemakkelijk om te zien dat er iets mis is gegaan. Dat wil zeggen, als we zowel R als R hebben bewezen, dan hebben we iets vals bewezen.

onze redenering gaat nu als volgt. Wat ging er mis? Lijn 8 is een correct gebruik van herhaling; lijn 7 komt van een correct gebruik van modus tollendo ponens; lijn 6 van een correct gebruik van modus ponens; lijn 5 van een correct gebruik van dubbele negatie., We hebben dus geen fout gemaakt in onze redenering. We gebruikten Lijnen 1, 2 en 3, maar dat zijn veronderstellingen waarvan we hebben aangenomen dat ze juist zijn. Dan blijft lijn 4 over. Dat moet de bron zijn van mijn tegenstrijdigheid. Het moet vals zijn. Als regel 4 onwaar is, dan is P waar.

sommige mensen vinden indirecte bewijzen minder sterk dan directe bewijzen. Er zijn vele, en complexe, redenen hiervoor. Maar, voor onze propositionele logica, geen van deze redenen van toepassing. Dit komt omdat het mogelijk is om te bewijzen dat onze propositionele logica consistent is., Dit betekent dat het mogelijk is om te bewijzen dat onze propositionele logica een leugen niet kan bewijzen tenzij men eerst een leugen in het systeem introduceert. (Het is over het algemeen niet mogelijk om te bewijzen dat meer krachtige en geavanceerde logische of wiskundige systemen consistent zijn, van binnen deze systemen; men kan bijvoorbeeld in de rekenkunde niet bewijzen dat de rekenkunde consistent is. Aangezien we zeker kunnen zijn van de consistentie van de propositionele logica, kunnen we er zeker van zijn dat in onze propositionele logica een indirect bewijs een goede vorm van redeneren is., We weten dat als we een leugen bewijzen, we een leugen in moeten hebben gezet; en als we vertrouwen hebben over alle andere veronderstellingen (dat wil zeggen, de premissen) van ons bewijs, behalve voor de aanname voor indirecte afleiding, dan kunnen we er zeker van zijn dat deze aanname voor indirecte afleiding de bron van de leugen moet zijn.

een opmerking over terminologie is hier vereist. Het woord “tegenstrijdigheid” wordt dubbelzinnig gebruikt in de meeste logische discussies. Het kan een situatie betekenen zoals we hierboven zien, waar twee zinnen worden beweerd, en deze zinnen kunnen niet beide waar zijn., Of het kan een enkele zin betekenen die niet waar kan zijn. Een voorbeeld van zo ‘ n zin is (P^P)., De waarheidstabel voor deze zin is:

Dus, dit soort van de straf kan nooit waar zijn, ongeacht de betekenis van P.,

om dubbelzinnigheid te voorkomen, noemen we in deze tekst altijd een enkele zin die niet waar kan zijn een “tegenstrijdige zin”. (P^P) is dus een tegenstrijdige zin. Situaties waarin twee zinnen worden beweerd die niet beide waar kunnen zijn, worden een “contradictie”genoemd.

8.3 ons voorbeeld en andere voorbeelden

We kunnen nu een versie van Galileo ‘ s argument reconstrueren. We zullen de volgende sleutel gebruiken.

P: Er zijn werkelijke oneindigheden (inclusief de natuurlijke getallen en de vierkante getallen).,

Q: er is een één-op-één overeenkomst tussen de natuurlijke getallen en de vierkante getallen.

R: de grootte van de verzameling van de natuurlijke getallen en de grootte van de verzameling van de vierkante getallen zijn hetzelfde.

S: alle vierkante getallen zijn natuurlijke getallen.

T: sommige natuurlijke getallen zijn geen vierkante getallen.

U: er zijn meer natuurlijke getallen dan vierkante getallen.,

Met deze toets drukt, wordt het argument zal vertaald worden:

(P→Q)

(Q→R)

(P→(S^T))

((S^T)→U)

(U→R)

P

En we kunnen bewijzen dat dit een geldig argument met behulp van indirecte afleiding:

Op regel 6, zijn we ervan uitgegaan P omdat Galileo aangenomen dat P en gericht om te bewijzen dat P. Dat is, hij geloofde dat er geen werkelijke infinities, en zo is aangenomen dat deze vals was om te geloven dat het niet het geval dat er geen werkelijke infinities. Deze valsheid zal leiden tot andere valsheid, zichzelf bloot te stellen.,

voor degenen die geïnteresseerd zijn: Galileo concludeerde dat er geen werkelijke oneindigheden zijn, maar er zijn potentiële oneindigheden. Zo redeneerde hij dat het niet zo is dat alle natuurlijke getallen bestaan (in zekere zin “bestaan”), maar het is waar dat je voor altijd natuurlijke getallen zou kunnen tellen. Veel filosofen voor en na Galileo hield deze visie; het is vergelijkbaar met een visie van Aristoteles, die een belangrijke logicus en filosoof schrijven bijna tweeduizend jaar voor Galileo was.,

merk op dat in een argument als dit, je zou kunnen redeneren dat niet de aanname voor indirecte afleiding, maar eerder een van de premissen de bron van de tegenstrijdigheid was. Tegenwoordig geloven de meeste wiskundigen dit over Galileo ‘ s argument. Een logicus en wiskundige genaamd Georg Cantor (1845-1918), de uitvinder van de verzamelingenleer, stelde dat oneindige verzamelingen goede deelverzamelingen van dezelfde grootte kunnen hebben., Dat wil zeggen, Cantor ontkende uitgangspunt 4 hierboven: hoewel alle kwadraten natuurlijke getallen zijn, en niet alle natuurlijke getallen vierkante getallen zijn, is het niet zo dat deze twee verzamelingen van verschillende grootte zijn. Cantor accepteerde echter uitgangspunt 2 hierboven, en geloofde daarom dat de grootte van de verzameling van natuurlijke getallen en de grootte van de verzameling van vierkante getallen hetzelfde is. Tegenwoordig bestuderen wiskundigen en logici met Cantors redenering oneindigheid en hebben ze een grote hoeveelheid kennis over de aard van oneindigheid ontwikkeld. Als dit u interesseert, zie paragraaf 17.5.,

laten we een ander voorbeeld bekijken om indirecte afleiding te illustreren. Een zeer nuttige verzameling stellingen wordt vandaag de dag de “stellingen van de Morgan” genoemd, naar de logicus Augustus De Morgan (1806-1871). We kunnen deze niet volledig vermelden tot hoofdstuk 9, maar we kunnen hun equivalent in het Engels vermelden: DeMorgan merkte op dat (PvQ) en (P^Q) gelijkwaardig zijn, en ook dat (P^Q) en (PvQ) gelijkwaardig zijn. Gegeven dit, zou het een stelling van onze taal moeten zijn die ((PvQ)→(P^Q)). Laten we dit bewijzen.

de hele formule is een voorwaardelijke, dus we zullen een voorwaardelijke afleiding gebruiken., Ons bewijs moet dus beginnen:

om de voorwaardelijke afleiding te voltooien, moeten we bewijzen (P^Q). Dit is een conjunctie, en onze regel voor het tonen van conjuncties is adjunction. Aangezien het gebruik van deze regel onze beste manier kan zijn om te laten zien (P^Q), Kunnen we ernaar streven om P te laten zien en vervolgens Q, en dan het uitvoeren van adjunction. Maar, we hebben natuurlijk heel weinig om mee te werken – alleen lijn 1, dat is een negatie. In een dergelijk geval is het meestal verstandig om een indirect bewijs te proberen. Begin met een indirect bewijs van P.,

We moeten nu een tegenstrijdigheid vinden—elke tegenstrijdigheid. Maar er is al een duidelijke. Regel 1 zegt dat noch P noch Q Waar is. Maar regel 3 zegt dat P waar is. We moeten deze tegenstrijdigheid expliciet maken door een formule en de ontkenning ervan te vinden. We kunnen dit doen met optellen.

om het bewijs te voltooien, zullen we deze strategie opnieuw gebruiken.

We zullen de stellingen van de Morgan bewijzen als problemen voor hoofdstuk 9.,

Hier is een algemene vuistregel voor het doen van bewijzen: bij het bewijzen van een voorwaardelijke afleiding, doe altijd voorwaardelijke afleiding; anders, probeer directe afleiding; als dat faalt, probeer dan indirecte afleiding.

8.4 problemen

1. completeren de volgende bewijzen. Elk zal een indirecte afleiding vereisen. De laatste twee zijn uitdagend.

1. bewijs dat de volgende stellingen zijn.

1. (p^P).
2. ((p→P)^(P→P)).
3. (P→(p^Q)).
4. ((p^Q)→(P→Q)).

1. in normaal spreektaal Engels, schrijf uw eigen geldige argument met ten minste twee premissen., Je argument moet gewoon een alinea zijn (geen geordende lijst met zinnen of iets anders dat lijkt op formele logica). Vertaal het in propositionele logica en bewijs dat het geldig is met behulp van een indirecte afleiding.