Ett bevis eller mer generellt en härledning, är en följd av slutledningar, vilka från bestämda axiom och givna premisser leder fram till en slutsats. I matematiken kallas ett påstående som formellt kan bevisas, för ett teorem eller en sats.

Ett påstående, som är obevisat, kallas för en förmodan. Hjälpsatser, som används vid bevisföringen kallas för lemman. I praktiken är bevisföring en kompromiss mellan stringens och enkelhet. Det har i matematikhistorien vid flera tillfällen hänt, att fel upptäckts i publicerade bevisförsök för satser, som tidigare betraktats som giltiga. Beviset för fyrfärgssatsen var under en period kontroversiellt eftersom det innehöll för tiden nya (datorberoende) kontrollmetoder, men numera accepteras dessa.

Ett matematiskt bevis [1] kan inte jämföras med bevis i andra vetenskaper, vars grundsatser kan förändras.

Härledningar redigera

Härledningsbegrepp
Närliggande begrepp

I logiken studeras bevis ingående. Matematiska bevis kan formaliseras till en följd av små argumentationssteg. Inom ramen för första ordningens logik kan man definiera dessa exakt och få vad man kallar ett härledningssystem. Ett sådant system har ett antal slutledningsregler, som motsvarar vart och ett av argumentationsstegen. En härledning i denna mening består av en ändlig följd av formler F0, F1, F2, ... , Fn, där dessa är axiom, premisser och slutledningar. För varje slutledning i härledningen, preciseras från vilka formler den följer. Den sista formeln Fn är härledningens slutsats (konklusion).

Exempel på en härledning:

F0: Varje primtal är udda. (Detta är inte sant; det finns ett jämnt primtal, nämligen 2.)
F1: p är ett primtal.
F2: p är udda.

F0 och F1 är härledningens premisser, dvs de påståenden som argumentationen utgår ifrån. F2 är härledningens konklusion. Att F2 följer ur F0 och F1 borde vara klart för alla som betraktar härledningen. Den härledningsregel som tillåter oss dra slutsatsen F2 ur F0 och F1 kallas universell specifikation. Observera att F0 är falsk, eftersom det jämna talet 2 är ett primtal. Detta faktum hindrar dock inte härledningen från att vara korrekt. Minns att en härledning är en argumentationskedja som garanterar att slutsatsen håller, förutsatt vissa premisser. Alltså är det sant att säga att p verkligen är udda under de givna antagandena. Om premissernas sanningshalt är oviss kallas konklusionen petitio principii, vilket är ett materiellt bevisfel och leder till att beviset inte är bindande.

Observera även att man behöver inte alls förstå betydelsen av begreppen "primtal" och "udda" för att inse att härledningen är korrekt. Man hade likaväl kunna byta ut dessa termer mot några mer generella:

F3: Varje X är Y.
F4: p är X.
F5: p är Y.

Detta är en korrekt härledning av vilken den tidigare är ett specialfall. Det som spelar roll för om en härledning är korrekt eller ej är alltså härledningens form, och inte betydelsen av de ingående termerna.

Bevismetoder redigera

Nedan tas några vanliga metoder för att bevisa satser upp.

Direkt bevis redigera

Huvudartikel: Direkt bevis

I ett direkt bevis används axiom, definitioner och tidigare kända satser för att bevisa den eftersökta satsen.[2] Exempelvis kan man bevisa att summan av två jämna heltal alltid är jämnt:

För alla två jämna heltal x och y gäller det att   och   för några heltal n och m, eftersom x och y är jämna. Men då är   och alltså är summan jämn.

Indirekt eller kontrapositivt bevis redigera

I ett indirekt eller kontrapositivt bevis bevisar man ett påstående på formen "om pq" genom att använda kontraposition och bevisa det ekvivalenta påståendet "om icke-q så icke-p". Det är ett slags motsägelsebevis.[2]

Motsägelsebevis redigera

Huvudartikel: Motsägelsebevis

I ett motsägelsebevis antar man motsatsen till vad man vill bevisa och visar att detta leder till en motsägelse, alltså måste påståendet man började med vara sant. Ett känt exempel är beviset till att kvadratroten ur 2 är irrationellt:

Anta att   är rationellt, dvs  , där a och b är nollskilda heltal utan gemensamma delare. Detta ger  . Kvadrering av båda sidor ger  . Eftersom 2 delar vänsterledet måste 2 vara en faktor i  . Alltså måste 2 vara en faktor även i a och vi kan skriva   för något heltal c. Den ursprungliga ekvationen ger nu   och alltså måste även b ha 2 som faktor. Men vi antog i början att a och b saknade gemensamma delare, så detta ger en motsägelse. Alltså är   inte rationellt.

Matematisk induktion redigera

Huvudartikel: Matematisk induktion

Vid ett induktionsbevis bevisas påståendet först för ett grundfall. Sedan används en induktionsregel för att bevisa att ett stort antal (ofta oändligt) fall är giltiga. Ofta används induktion över de positiva eller de naturliga talen, då man har ett påstående   för varje naturligt tal n. I ett induktionsbevis över de naturliga talen behöver man då visa två saker:

  1. P(0) är sant.
  2. P(n) är sant implicerar att P(n+1) är sant.

då man kan dra slutsatsen att   är sant för varje naturligt tal n. Ett exempel på felaktigt användande av induktion är paradoxen alla hästar har samma färg.

Existensbevis eller icke-konstruktivt bevis redigera

Ett existensbevis eller ett icke-konstruktivt bevis slår fast att det existerar objekt med en viss egenskap utan att visa hur dessa objekt kan konstrueras. Icke-konstruktiva bevis är ofta motsägelsebevis där icke-existensen av något objekt visas vara omöjligt.[3]

Konstruktivt bevis redigera

Ett konstruktivt bevis visar en metod att hitta objekten i fråga.[3]

Elementärt bevis redigera

I ett elementärt bevis används endast grundläggande begrepp och används speciellt inom talteori för bevis som inte använder komplexanalytiska metoder. Vissa resultat, som primtalssatsen, bevisades först med hjälp av icke-elementära metoder för att senare få ett elementärt bevis.

Oavgörbara påståenden redigera

Ibland går det att bevisa att ett påstående INTE går att bevisa eller motbevisa utgående från de givna premisserna, se till exempel kontinuumhypotesen. I alla logiska system som innefattar de naturliga talen går det att formulera påståenden som kräver lika många argumentationssteg som de naturliga talen för att bevisas eller motbevisas. Då antalet argumentationssteg är oändligt blir påståendet i praktiken obevisbart.

Se även redigera

Referenser redigera

Noter redigera

  1. ^ Thompson J. Martinsson T.: "Matematiklexikon", sidan 45. Wahlström & Widestrands, 2000
  2. ^ [a b] Eriksson, Gavel 2002, s. 207.
  3. ^ [a b] Eriksson, Gavel 2002, s. 208.

Källor redigera

  • Eriksson, Kimmo; Hillevi Gavel (2002). Diskret matematik och diskreta modeller. Lund: Studentlitteratur. ISBN 91-44-02465-7 
  • Metalogic. An Introduction to the Metatheory of Standard First-Order Logic, Geoffrey Hunter, MACMILLAN 1971.
  • Velleman, Daniel (2006). How To Prove It. Cambridge University Press. ISBN 0-521-67599-5