Matemaatiliste tõestuste meetodid (0)

Matemaatiliste tõestuste meetodid
1. Otsesed tõestuse meetodid
Matemaatiline süsteem koosneb aksioomidest, teoreemidest, definitsioonidest ja defineerimata objektidest.
Aksioom on lause, mida eeldatakse tõene olevat.
Definitsiooni kasutatakse uute kontseptsioonide ja mõistete selgitamiseks teadaolevate mõistete kaudu.
Teoreem on väide, mis on tõestatud.
Lemma - väiksema iseseisva tähtsusega teoreem, mis on enamasti abiks teoreemide tõestamisel.
Järeldus- toereemist otseselt järelduv tulemus
Näited:
Defineerimata objektid: punktid, jooned
Definitsioon: Kolmnurga ümbermõõt on võrdne selle kolmnurga külgede summaga
Teoreem: Täisnukse kolmnurga kaatetite ruutude summa võrdub hüpotenuusi ruuduga .
Järeldus: kui kolmnurga küljed on võrdse pikkusega, siis on selle kolmnuga nurgad samuti võrdsed.
Teoreemi tõesuse põhjendamist, nimetatakse tõestuseks.
Loogika on vahend tõestuse läbiviimiseks.
Vaatleme esialgu selliseid tõestamise meetodeid , mida esitatakse kujul
„, mille korral P(x)“. Sellised teoreemid tagavad, et eksisteerib vähemalt üks x mille korral predikaat P(x) on õige. Sellist tõestust nimetatakse konstruktiivseks.
Tõestus sisaldab sellise x leidmist mille korral P(x) on tõene või siis algoritmi koostamist sellise x leidmiseks.
Konstruktiivse tõestuse näide: tõestada et leidub täisarv mille ruut on 81.
Tõestus: 9*9=81
Mittekonstruktiivne tõestus sisaldav järgmisi võimalusi

väite kinnitamiseks kasutatakse juba tõestatud teoreeme

kasutatakse vastuväitelist tõestust, ehk põhjendatakse, et eeldus, et ei leidu sellist x-i mille korral P(x) on tõene viib vastuoluni.
Teoreemid esinevad sageli kujul:
. Kui on tõene P(x) siis on tõene ka Q(x)
P(x)-eeldus
Q(x)-väide
Näide : tõestada, et iga täisarvu n korral vahemikus
on
algarv
Tõestusseks teisendame esspooltoodud kujule
on algarv
Tõestus:
Arvutame välja kõik vajalikud väärtused:
Võimsaim tõestuse meetod on selline, mis üldistab ehk laiendab väite kehtivuspiirkonda.Antakse ette suvaline x mille korral eeldus P(x) on tõene ja kasutades definitsioone, eelnevaid tulemusi ja reegleid järeldatakse et Q(x) on tõene.
Otsene tõestuse meetod tähendab tõestuse esitamist kujul
Kui P(x) on tõene
.korral, siis on ka Q(x) tõene
Tõestuse üldise esitusega tutvumiseks vaatleme järgmist näidet:
Toereem 1: Iga m ja n
korral, kui m ja n on paarisarvud, siis on seda ka m+n
Tõestus: Olgu m ja n paarisarvud, siis saame nad esitada kujul
m=2*k1 ja n=2*k2
ning m+n saame esitada kujul m+n= 2*k1+2*k2=2*(k1+k2)=2*k
Et k=k1+k2, siis 2*k on paarisarv ehk m+n on paarisarv.
Teoreem 2: Kui a ja b , siis ka a+b.
Tõestus. Et a ja b on ratsionaalarvud, siis võime kirjutada a kujul
ja .
kus
ja ;
ja
ei oma ühistegureid, .ja
ei oma ühistegureid.
..........................................
Järeldus Ratsionaalarvu korrutamisel kahega saame ratsionaalarvu.
.............................................
Mõned tüüpilised vead teoreemide tõestamisel:

• Argumenteeritakse näidetega, mõne näite korra teoreemi kehtimine ei tähenda selle üldist kehtimist
  
• Samade tähistuste kasutamine erinevate terminite jaoks, näiteks kaks suvalist paarisarvu m ja n tähistatakse m=2*k ja n= 2*k, kui see on vale sest tekib seos m=n, mis suvaliste täisarvude korral ei kehti
  
• Hüppeline üleminek tulemusele
  
• Tulemust ennast kasutatakse tõestuse sees
  

Kontranäitel põhinev tõestus:
Tõestada et järgmine väide pole tõene
korral , kui
siis ka
Valime a=-2 ja b=-1.
Ülesanne1: Tõestada, et kahe ratsionaararvu korrutis on ratsionaalarv.
Ülesanne2:
Tõestada kontranäite abil, et järgnev programmikood ei leia alati minimaalset N täisarvu hulgast
2. Teisi tõestuse meetodeid
Tähenduseta (vacuous) tõestus: Järelduse
tõestus, milles näidatakse et p on väär.
Näide: kui Ø , siis Juku läheb kooli.
Et x ei saa kuuluda tühja hulka siis loetakse väide „Juku läheb kooli “ tähenduseta õigeks.
Triviaalne tõestus: Järelduse
tõestus, milles näidatakse q on tõene sõltumata p väärtusest.
Näide: Tõestada, et kui täisarv n on paarisarv , siis ta jagub 1-ga.
Tõestus: Et iga täisarv jagub ühega siis on väide tõene, sõltumata eeldusest et n on paarisarv.
Tõestus alamjuhtude põhjal: tõestatakse et, kõigil võimalikel juhtudel on väide tõene. :
Näide: Tõestada et iga positiivse täisarvu n korral on
paarisarv.
Tõestus: Jaotame positiivsete arvude hulga omakorda positiivseteks paaris- ja paarituteks arvudeks ehk saame kaks alamjuhtu, mille jaoks tüestuse läbi viime.

olgu n positiivne paarisarv
siis n=2*k
mis on paarisarv

olgu n positiivne paaritu arv
siis n=2*k+1
mis on paarisarv
Näide 2 (alamjuhtudega tõestus)
Tõestada , et reaalarvude x ja y korral kehtib

x>=0 ja y>=0
siis x+y>=0 ja |x+y|=x+y=|x|+|y|

x>=0 ja y=0)siis |x+y|=x+y=1 korral jagub avaldis
kolmega.
a) tõestame, et kehtib n=1 korral
S(1) on tõene.
b)eeldame, et kehtib S(n) korral
jagub kolmega
c)tõestame, et kehtib S(n+1)korral
S(n+1) jagub kolmega, kuna S(n) jagub 3-ga ja teises liikmes on 3 kordajaks.
Ülesanne 4: Tõestada, et kõigi mittenegatiivsete täisarvude korral kehtib .
a) P(0)>0:
b) P(n)>0:
c) P(n+1)>0
Et P(n)>0, ja
siis ka P(n+1)>0.
Ülesanne 5: Tõestada , et kõigi täisarvude n>=4 korral kehtib
a) P(4)>0:
b) P(n)>0:
c) P(n+1)>0:
n*n!>n! Kuna meil n>=4
seetõttu
Ülesanne 6: Tõestada Bernoulli võrratus:
kui n>=0 ja h>-1.
a) P(0)>=0:
b) P(n)>=0:
c) P(n+1)>=0:
Ülesanne 7: Arvujada esimane liige on 2 (), iga järmine liige (n>=2) arvutatakse eelmise kaudu valemiga. Leida üldine valem liikme
arvutamiseks, ja tõestada selle õigsus induktsiooni abil.
selle põhjal
a) n=2:
seos kehtib
b) eeldame et kehtib
c) tõestame, et kehtib n+1 korral:
Ülesanne 8: Tõestada, et n>=1 korral kehtib:
P(n)=2+4+6+...+2*n väide: P(n)=n*n+n
a)n=1: P(1)=2=1*1+1=2 kehtib
b) eeldame et kehtib:
c)Tõestame, et kehtib n+1 korral:
Ülesanne 9: Tõestada, et n>=0 korral

P(0):
Vasak pool: 1
Parem pool: 20+1-1=21-1=1

P(n) eeldame, et seos kehtib:

P(n+1) tõestame kehtivuse
Vasak pool: 1+2+22+...+2n+2n+1 = P(n)+ 2n+1 = 2n+1-1+2n+1 = 2*2n+1-1=2n+2-1
Parem pool: 2n+1+1-1=2n+2-1
Ülesanne 10: Tõestada, et n>=1 korral kehtib:

P(1) jaoks tõestada
Vp: 12=1
Pp: 1*(1+1)*(2*1+1)/6=1*2*3/6=1

Eeldame P(n):

P(n+1), tõestame kehtivuse
Vp: 12+22+32+...+n2+(n+1)2=P(n)+(n+1)2=n(n+1)(2n+1)/6+(n+1)2=
(1/6)*[ n(n+1)(2n+1)+6*(n+1)2]= (1/6)*(n+1)[n*(2n+1)+6*(n+1)]=
(1/6)*(n+1)[2n2+7n+6]= =(n+1)(n+2)(2n+3)/6
2n2+7n+6=0: lahend n1=(-7+sqrt(7*7-4*2*6))/(2*2)=(-7+1)/4=-3/2
n2=(-7-1)/4=-2
Pp: (n+1)(n+1+1)(2(n+1)+1)/6=(n+1)(n+2)(2n+3)/6
Ülesanne 11: Tõestada, et n>=1 korral kehtib:
Ülesanne 12: Tõestada, et n>=1 korral kehtib:
Ülesanne 13: Kasutades valemit
arvuta summa 3+4+...+1000.
Ülesanne 14: Tõestada, et n>=1 korral jagub avaldis
kolmega.
Ülesanne 15: Tõestada, et n>=1 korral jagub avaldis
seitsmega.
Mitme eelneva väärtusega indukstioon (J.K.Truss järgi)
Indukstiooni sammul kasutatakse mitme eelneva predikaadi väärtust või kõikide eelnevate predikaatide väärtusi
Näide: Fibonacci arvud on defineeritud järgmiselt:
, , .
Tõestada, et
kõigi n>=0 korral.
a) indukstiooni baas tähendab antud juhul kahe väärtuse arvutamist
n=0:
ja n=1:
b)indukstiooni hüpotees tähendab antud juhul kahe seose kehtivuse eeldamist:
ja
c)induktsiooni samm:
Tugev indukstiooniprintsiip (R. Palm järgi)
Olgu P(n) üldväide, mille parameetri n väärtusteks on naturaalarvud . Kui

väide P(1) kehtib

iga naturaalarvu k korral järeldub sellest, et väide kehtib kõigi P(m) korral, kus m