En Kortfattet Innføring i Logikk

8.1 Et historisk eksempel på

I sin bok, To Nye Vitenskaper, Galileo Galilea (1564-1642) gir flere argumenter ment å vise at det kan være noe slikt som faktisk infinities eller faktiske infinitesimals. Ett av hans argumenter kan settes sammen på følgende måte. Galileo foreslår at vi tar som en forutsetning at det er en faktisk uendelighet av naturlige tall (de naturlige tallene er de positive hele tallene fra 1 på):

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

Han foreslår også at vi tar som en forutsetning at det er en faktisk uendelighet av kvadratene av de naturlige tallene.

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

Nå, Galileo grunner, merk at disse to gruppene (i dag ville vi kalle dem «setter») har samme størrelse. Vi kan se dette, fordi vi kan se at det er et en-til-en-korrespondanse mellom de to gruppene.,

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

Hvis vi kan knytte ethvert naturlig tall med ett, og bare ett kvadrat av tall, og hvis vi kan knytte hver kvadrat nummer med ett og bare ett naturlige tall, så er disse angir må være av samme størrelse.,

Men vent et øyeblikk, Galileo sier. Det er tydeligvis veldig mange flere naturlige tall enn det er kvadrattall. Det er, hver kvadrat nummer i listen av naturlige tall, men mange av de naturlige tallene er ikke i listen over kvadrattall. Følgende tall er alle på listen av naturlige tall, men ikke i den listen av kvadrattall.

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

Så, Galileo grunner, hvis det er mange tall i gruppen av naturlige tall som ikke er i gruppen av plassen tall, og hvis det er ingen tall i gruppen av plassen tall som ikke er i naturals tall, da de naturlige tallene er større enn kvadrattall. Og hvis gruppen av de naturlige tallene er større enn gruppen av kvadrattall, så de naturlige tallene og kvadrattall er ikke av samme størrelse.,

Vi har nådd to konklusjoner: den sett av de naturlige tallene, og sett av kvadrattall er i samme størrelse, og det sett av de naturlige tallene, og sett av kvadrattall er ikke av samme størrelse. Det er motstridende.

Galileo hevder at grunnen til at vi har nådd en selvmotsigelse er fordi vi antok at det er faktiske infinities. Han konkluderer derfor med at det ikke er noen faktiske infinities.

8.2 Indirekte bevis

Vår logikk er ennå ikke sterk nok til å bevise noen gyldige argumenter. Vurder følgende argument som et eksempel.,

(P→(QvR))

Q

– R

S

Dette argumentet ser ut gyldig. Ved den første forutsetningen vi vet: hvis P var sant, så ville (Q v R) være sann. Men så enten på Q eller R eller begge ville være sant. Og ved andre og tredje lokaler vet vi: Q er usann og R er falske. Så det kan ikke være at (Q v R) er sann, og slik kan det ikke være at P er sann.

Vi kan sjekke argumentet ved hjelp av en sannhet bordet. Vårt bord vil være komplisert fordi en av våre forutsetningen er komplekse.,

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., Det er: lokalene er oppfylt bare i den siste raden. For raden, og konklusjonen er også sant. Så, dette er et gyldig argument.

Men tar en liten og prøve å bevise dette argumentet. Vi begynner med

Og nå er vi stoppet. Vi kan ikke bruke noen av våre regler. Her er et gyldig argument om at vi ikke laget vårt resonnement system er sterk nok til å bevise.

Det er flere måter å rette opp dette problemet og for å gjøre våre resonnement system er sterk nok., En av de eldste løsninger er å introdusere et nytt bevis metode, tradisjonelt kalt «reductio ad absurdum», som betyr en reduksjon til absurditet. Denne metoden er også ofte kalt en «indirekte bevis» eller «indirekte avledning».

ideen er at vi antar at fornektelse av vår konklusjon, og deretter viser at en selvmotsigelse resultater. En selvmotsigelse vises når vi beviser at vi er noen setningen Ψ, og dens negasjon Ψ. Dette kan være en setning. Poenget er at, i lys av prinsippet om bivalence, vi må ha bevist noe usant. For hvis Ψ er sann, så Ψ er usann (false); og, dersom Ψ er sann, så Ψ er falske., Vi trenger ikke å vite noe som er usant (Ψ eller Ψ); det er nok til å vite at en av dem må være.

Husk at vi har bygget vår logisk system, slik at det ikke kan produsere en usannhet fra sant utsagn. Kilden til usannhet som vi produserer i indirekte avledning må derfor være noen usannheter som vi har lagt til vår argument. Og hva vi har lagt til vårt argument er fornektelse av konklusjonen. Dermed konklusjonen må være sant.,

Det formen på argumentet er som dette:

Tradisjonelt forutsetningen for indirekte avledning har også vært vanlig kalt «forutsetningen for reductio».

Som et konkret eksempel, kan vi bevise vår forvirrende sak.

Vi antok fornektelse av vår konklusjon på linje 4. Den konklusjon vi trodde var riktig ble P, og fornektelse av dette er S. I linje 7, og vi viste R., Teknisk, vi er ferdig på det tidspunktet, men vi ønsker å være snill mot alle som forsøker å forstå vår bevis, så vi gjentar linje 3, slik at setninger R-og R er side ved side, og det er veldig lett å se at noe har gått galt. Det er, hvis vi har bevist både R og R, da vi har bevist noe usant.

Våre resonnement nå går som dette. Hva gikk galt? Linje 8 er en riktig bruk av repetisjon, linje 7 kommer fra en riktig bruk av modus tollendo ponens, linje 6 fra en riktig bruk av modus ponens, linje 5 fra en riktig bruk av dobbel negasjon., Så gjorde vi ikke gjør en feil i vår tankegang. Vi brukte linjene 1, 2, og 3, men de er lokalene som vi ble enige om å anta er riktig. Dette etterlater linje 4. Det må være kilden til min selvmotsigelse. Det må være usann. Hvis linje 4 er usann, så er P sann.

Noen mennesker vurdere indirekte bevis mindre sterk enn direkte bevis. Det er mange og komplekse årsaker til dette. Men, for vår proposisjonale logikk, ingen av disse grunnene gjelder. Dette er fordi det er mulig å bevise at vår proposisjonale logikk er konsistent., Dette betyr at det er mulig å bevise at vår proposisjonale logikk kan ikke bevise en usannhet med mindre man først innfører en usannhet i systemet. (Det er generelt ikke mulig å bevise at mer kraftige og avanserte logiske eller matematiske systemer er konsistent, fra innsiden av de systemer, for eksempel, man kan ikke bevise i matematikk som aritmetikk er konsistent.) Gitt at vi kan være sikker på konsistensen av proposisjonale logikk, kan vi være sikker på at i vår proposisjonale logic et indirekte bevis er en god form for resonnement., Vi vet at hvis vi beviser at vi er en usannhet, vi må ha satt en usannhet i, og hvis vi er overbevist om at alle andre forutsetninger (det lokale) av våre bevis bortsett fra den forutsetning for indirekte avledning, da kan vi være sikre på at forutsetningen for indirekte avledning må være kilden til usannhet.

Et notat om terminologi er nødvendig her. Ordet «motsigelse» blir brukt ambiguously i de fleste logikk diskusjoner. Det kan bety en situasjon som vi ser ovenfor, hvor to setningene er hevdet, og disse setningene kan ikke både være sant., Eller det kan bety en enkelt setning som ikke kan være sant. Et eksempel på en slik setning er (P^P)., Sannheten tabell for denne setningen er:

Dermed, denne typen setning kan aldri være sant, uavhengig av betydningen av S.,

for Å unngå tvetydighet, i denne teksten, vil vi alltid ringe en enkelt setning som ikke kan være sant en «motstridende setning». Dermed, (P^P) er en motstridende setning. Situasjoner der to setningene er hevdet at ikke begge være sanne, vil bli kalt en «strid».

8.3 Vårt eksempel, og andre eksempler på

Vi kan rekonstruere en versjon av Galileo argumentet nå. Vi vil bruke følgende taster.

P: Det er faktisk infinities (inkludert de naturlige tallene og plassen tall).,

Q: Det er en en-til-en korrespondanse mellom de naturlige tallene og kvadrattall.

R: størrelsen på settet med de naturlige tallene og størrelsen på settet av kvadrattall er den samme.

S: Alle kvadrattall er naturlige tall.

T: Noen av de naturlige tallene er ikke kvadrattall.

U: Det er mer naturlig tall enn kvadrattall.,

Med dette viktige argumentet om vil bli oversatt:

(P→Q)

(Q→R)

(P→(S^T))

((S^T)→U)

(U→R)

S

Og vi kan bevise at dette er et gyldig argument ved hjelp av indirekte avledning:

På linje 6, som vi antok P fordi Galileo antatt at P og hadde som mål å bevise at P. det vil si At han mente at det er ingen faktiske infinities, og så antatt at det var feil å tro at det er ikke tilfelle at det ikke er noen faktiske infinities. Dette usannhet vil føre til andre villfarelser, å utsette seg selv.,

For de som er interessert: Galileo konkluderte med at det ikke er noen faktiske infinities men det er potensielle infinities. Dermed er han begrunnet, det er ikke tilfelle at alle de naturlige tallene finnes (i noen følelse av «eksisterer»), men det er sant som du kan stole naturlige tall for alltid. Mange filosofer før og etter Galileo holdt denne visningen, det ligner på et vis holdt av Aristoteles, som var en viktig logician og filosof skriver nesten to tusen år før Galileo.,

Merk at det i et argument som dette, kan du grunn til at ikke den forutsetning for indirekte derivasjon, men heller en av de lokale var kilden av motsetningene. I dag, de fleste matematikere tror dette om Galileo er argumentet. En logician og matematikeren Georg Cantor (1845-1918), oppfinneren av set teori, hevdet at uendelig sett kan ha skikkelig undergrupper av samme størrelse., Det er, Cantor nektet premiss 4 ovenfor: selv om alle kvadrattall er naturlige tall, og ikke alle naturlige tall er kvadrattall, det er ikke slik at disse to settene er av ulik størrelse. Cantor akseptert imidlertid premiss 2 ovenfor, og derfor trodde at størrelsen på settet av naturlige tall og størrelse på settet av kvadrattall er den samme. I dag, ved hjelp av Cantor er resonnement, matematikere og logicians studie uendelig, og har utviklet en stor kropp av kunnskap om natur av uendelig. Hvis dette interesserer deg, se punkt 17.5.,

La oss se på et annet eksempel for å illustrere indirekte avledning. En veldig nyttig sett av teoremer i dag kalles «De Morgan ‘ s Teoremer», etter logician Augustus De Morgan (1806-1871). Vi kan ikke staten disse fullt til i kapittel 9, men vi kan si sin tilsvarende i engelsk: DeMorgan observert at (PvQ) og (P^Q) er ekvivalente, og også at (P^Q) og (PvQ) er tilsvarende. Gitt dette, bør det være et teorem i vårt språk som ((PvQ)→(P^Q)). La oss bevise dette.

hele formelen er en betinget, så vil vi bruke en betinget avledning., Våre bevis må dermed begynner:

for Å fullføre betinget avledning, vi må bevise (P^Q). Dette er en forbindelse, og vår regel for å vise konjunksjoner er adjunction. Siden bruk av denne regelen kan bli vår beste måte å vise at (P^Q), kan vi sikte på å vise P og deretter vise Q, og deretter utføre adjunction. Men, vi åpenbart har svært lite å jobbe med—bare linje 1, som er en negasjon. I et slikt tilfelle, er det vanligvis lurt å forsøke seg på et indirekte bevis. Start med et indirekte bevis på S.,

Vi trenger nå å finne en selvmotsigelse—noen selvmotsigelse. Men det er et åpenbart allerede. Linje 1 sier at verken P eller Q er sanne. Men linje 3 sier at P er sann. Vi må gjøre dette avviket eksplisitt ved å finne en formel og sin fornektelse. Vi kan gjøre dette ved hjelp av tillegg.

for Å fullføre beviset, vil vi bruke denne strategien igjen.

Vi vil bevise at De Morgan ‘ s teoremer som problemer for kapittel 9.,

Her er en generell tommelfingerregel for å gjøre bevis: Når beviser et betinget, gjør alltid betinget avledning; hvis ikke, prøv direkte avledning; hvis det ikke fungerer, så prøv indirekte avledning.

8.4 Problemer

– >

1. utføre følgende bevis. Hver vil kreve en indirekte avledning. De to siste er utfordrende.

1. Bevise følgende er teoremer.

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

1. I normal dagligdags engelsk, kan du skrive din egen gyldige argumentet med minst to lokaler., Ditt argument bør bare være et avsnitt (ikke en ordnet liste av setninger eller noe annet som ser ut som formell logikk). Oversette det til proposisjonale logikk og bevise at den er gyldig ved hjelp av en indirekte avledning.