IZ TEORIJE ZA PRAKSO 18 Matematika v šoli, št. 2., letnik 28, 2022 Dokaz v srednješolski matematiki Dr. Brigita Ferčec Fakulteta za Energetiko Univerze v Mariboru in Center za uporabno matematiko in teoretično fiziko Univerze v Mariboru in Fakulteta za naravoslovje in matematiko Univerze v Mariboru Dr. Matej Mencinger Fakulteta za gradbeništvo, prometno inženirstvo in arhitekturo Univerze v Mariboru in Inštitut za matematiko, fiziko in mehaniko, Ljubljana Izvleček V članku obravnavamo pomen dokaza v matematiki. Po kratkem zgodovinsko-teoretičnem uvodu se dota- knemo pomena dokaza v srednji šoli. Omenimo tudi Pitagorov izrek, ki velja za enega glavnih rezultatov v matematiki, in navedemo dva dokaza, ki temeljita na geometrijski podlagi. Obravnavamo tudi glavne tehnike dokazovanja (ki so primerne za srednješolski nivo): dedukcija, dokaz s protislovjem, kontrapozicija, protipri- mer in indukcija. Pri vsaki tehniki podamo tudi (srednješolskemu nivoju) ustrezne primere. Omenimo tudi eno najslavnejših domnev – Collatzovo domnevo, katere tezo lahko brez težav razumejo celo osnovnošolci, dokaz (ali protiprimer) pa še vedno čakamo. Ključne besede: dokaz, srednja šola, matematična indukcija, dedukcija, protislovje, proti-primer, Collatzova domneva Mathematical Proof in Upper Secondary School Abstract This article covers the significance of proof in mathematics. It starts with a brief historical-theoretical backgro- und before highlighting the role of proof in the context of upper secondary school mathematics. We also refer to the Pythagorean theorem, one of the most important mathematical concepts, and provide two proofs based on geometric foundations. Further, we examine the main proof techniques at the secondary-school level: de- duction, proof by contradiction, counterexample, contrapositive and induction, along with suitable examples. We also look at one of the most famous conjectures, i.e., the Collatz conjecture, whose thesis is simple enough for primary school students to understand but whose proof (or counterexample) has not yet been provided. Keywords: proof, upper secondary school, mathematical induction, deduction, contradiction, counterexam- ple, Collatz conjecture. 1 Uvod Začetniki dokazovanja matematičnih trditev v smislu sodobne matematike so bili starogrški matematiki, ki so v aritmetiki in geometriji odkrili, da lahko trditvam dokažemo »pravilnost« ali »točnost«, oziroma kar danes v logiki imenujemo resničnost tr- ditve/izjave (Franklin, Daoud, 2011). V slovenskih gimnazijah v učnem načrtu za matematiko (Žakelj, 2008) dokaz nastopa na več mestih. V osnovi lahko govorimo o dveh nivojih dokazovanja: pasivnem (ko dijak »prejme« dokaz in ga je potencialno sposoben ponoviti/reinterpretirati) in aktiv- nem (ko dijak pozna neko metodo dokazovanja in jo je sposo- ben aktivno uporabiti v novih situacijah). Slednje je v gimnaziji večinoma omejeno (Žakelj, 2008) na popolno matematično in- dukcijo, medtem ko pasivno dokazovanje nastopa na primer pri vsakem izpeljevanju (formul pri danih predpostavkah). Dokazovanje spada v višji nivo znanja. Z dokazovanjem so po- vezana procesna znanja, kot je abstraktno razmišljanje, formalno sklepanje, intuitivne izpeljave ter kritično razmišljanje o potreb- nih in zadostnih pogojih. V učnem načrtu (Žakelj, 2008) je do- kazovanje obravnavano kot posebno znanje in je delno vključeno tudi v izbirne vsebine (npr. polarni zapis kompleksnega števila, analitična geometrija v prostoru, vektorski produkt). Vsebine (in cilji), ki so potencialno povezane s pridobivanjem takšnih proces- nih znanj, so (glej (Žakelj, 2008)) predvsem osnove logike izjave (zapis izjave in določevanje logične vrednosti izjave, ugotavljanje enakovrednosti dveh izjav) in številske množice – naravna šte- vila (induktivno sklepajo, posplošujejo, posplošitev dokažejo ali ovržejo in dokazujejo z matematično indukcijo (Žakelj, 2008, str. 11). Primeri nalog, kjer lahko uporabimo induktivni dokaz, so povezani s številskimi množicami, algebrskimi izrazi, (ne)enač- bami ter zaporedji in vrstami. IZ TEORIJE ZA PRAKSO 19 Matematika v šoli, št. 2., letnik 28, 2022 Najpomembnejše (dokazano resnične) trditve v matematiki ime- nujemo izreki, malo manj pomembne imenujemo preprosto tr- ditve, tiste, ki same po sebi niso tako zanimive, so pa pomembne kot del dokaza nekega (širšega) izreka, pa imenujemo leme. Za razliko od aksiomov, ki so vnaprej dogovorjena dejstva oziroma resnice, moramo veljavnost (resničnost) vsake trditve preveriti z dokazom. Izpeljave formul (pri danih predpostavkah) imajo seveda pomen izreka oziroma trditve. Dokazovanje veljavnosti formul je v gi- mnazijskem programu zelo pogosto in je namenjeno prej ome- njenim višjim/procesnim ciljem, ki so povezani s sposobnostjo dokazovanja. Omenimo samo nekaj primerov izpeljav, ki so res nujne: kot med premicama v ravnini, vsota geometrijske vrste in vsota poljubnega števila členov aritmetičnega zaporedja, dokazi nekaterih limit in osnovni odvodi z limitami ipd. Pri dokaz(ovanj)u ločimo dva vzporedna vidika: miselni proces in oblikovanje dokaza. Rezultat dokazovanja je dokaz, rezultat miselnih procesov je razumevanje. Samo dokazovanje lahko po- teka na več načinov: induktivno, deduktivno, s protislovjem, s kontrapozicijo in s protiprimerom (če ovržemo trditev o splo- šnosti neke izjave). Posamezne miselne sheme so povezane z organizacijo miselnih procesov (torej z različnimi strategijami pri oblikovanju dokaza). V (Harel, 2008) avtor omenja doka- zne sheme (indukcija, dedukcija, dokaz s protislovjem, dokaz s protiprimerom), ki si jih lahko predstavljamo kot »protokole« razmišljanja in poti do razumevanja, ki se jih lahko priučimo (procesni cilj), medtem ko dokazane izreke (pa tudi sam dokaz) uvrsti v kategorijo institucionalne matematike (zbirka struktur, aksiomov, trditev, dokazov). Težimo torej k temu, da dijaki usvo- jijo prej omenjene protokole razmišljanja z namenom, da sledijo (institucionalnemu) dokazovanju učitelja. Alternativno lahko dokazovanje v grobem razdelimo v tri skupi- ne (Harel, Sowder, 1998): avtoritativno (učitelj ali knjiga ponudi dokaz), empirično (na osnovi primerov meritev količin, konkre- tnih števil vizualizacij itd. induktivno sklepamo/posplošujemo) in deduktivno (zaporedno dokazovanje implikacije A ⇒ B z raz- delitvijo na več korakov: iz A sledi B 1 , iz B 1 sledi B 2 , …, iz B n sledi B, pri čemer je pomembno razumevanje pomena »za vse« oziroma »ne obstajajo izjeme«). Empirično razmišljanje je najbolj pogost način utemeljevanja, vendar nujno zahteva posplošitev. Proces posploševanja lahko (glej (Harel, 2008)) ločimo na rezultatsko in procesno posplo- ševanje. Da so števila 1, 2, 4, 8, 16 … členi zaporedja s splošnim členom 2 n , lahko preverimo z računanjem (preverimo ujemanje členov za prvih pet vrednosti z dano formulo). V procesnem razmišljanju je treba uvideti, da vsak naslednji člen iz prejšnje- ga dobimo s podvajanjem (prejšnjega). Pri dokazovanju je lahko rezultatski način razmišljanja zgolj osnovna ideja (ki jo potem nadgradimo z matematično indukcijo). Procesno razmišljanje nas običajno pripelje do »pravega« dokaza. Oba primera razmišljanja lahko ponazorimo na primeru. Trditev v obliki implikacije je: za vsako naravno število n je a n < 2. Kot rečeno, lahko rezultatsko razmišljanje (izračun približ- nih vrednosti za prvih nekaj členov) služi kot osnovni preizkus potrebnosti pogoja (če bi za nek n ∈ veljalo a n ≥ 2 smo našli protiprimer in implikacija ni veljavna). Približne decimalne vre- dnosti prvih nekaj členov zaporedja so 1. 4142, 1. 8478, 1. 9616, 1. 9904 ... Zavedati se moramo, da to ne more biti dokaz zgor- nje trditve. Po drugi strani pa vemo, da ravno na osnovi takega rezultatskega raziskovanja postavimo domnevo, da zgornja trdi- tev velja za vsak n ∈ . Za dokaz trditve je potrebno procesno razmišljanje: za n = 1 je očitno , saj po kvadriranju sledi 2 < 4. Za n = 2 po kvadriranju neenačbe sledi oziroma (kar smo že dokazali). Za n = 3 po kvadriranju neenačbe sledi 2 + a 2 < 4 oziro- ma a 2 < 2, kar smo že dokazali. Takšno procesno razmišljanje nas privede do induktivnega dokaza. Induktivni korak zahteva zgolj razmislek, da je za vsak n ∈ . Ker je , je izraz za vsak n ∈ dobro definiran. Najpogosteje uporabljen izrek v celotni učni vertikali (ki povezu- je matematiko s fiziko, mehaniko, geodezijo, statiko, elektroteh- niko) je zagotovo Pitagorov izrek. Dokaj preprosta premisa (ki je pogosto vsaj s strani učencev zamolčana oziroma pozabljena) in zaključek sta zelo razumljiva in zato obravnavana že v osnovni šoli. Kljub pozabljanju se bi verjetno največ bivših sošolcev na 20 ali celo 40 obletnici zaključka OŠ spomnilo Pitagorovega izreka (vsaj obrazca a 2 + b 2 = c 2 ). V srednji šoli pri trigonometriji izrek nadgradimo s sinusnim in kosinusnim izrekom. Pitagorov izrek ima zagotovo še en rekord, namreč številnost različnih dokazov (nekateri se razlikujejo zgolj v niansah, pa vendar). V (Dunham, 1994) najdemo kar nekaj dokazov izreka: Izrek (Pitagora). (V evklidski geometriji) za vsak pravokotni trikotnik s katetama a in b ter hipotenuzo c velja a 2 + b 2 = c 2 . (Kot vemo, velja tudi obrat: če za stranice trikotnika velja a 2 + b 2 = c 2 , je trikotnik pravokoten.) Zaključek oziroma sklep izreka so (vsaj 1000 let pred Pitago- ro) uporabljali že stari Babilonci. Pitagora in pitagorejci (cca. 560-480 p. n. št.) so ga uporabljali, Evklid (cca. 300 let p. n. št.) ga je dokazal na dva načina (Ratner, 2009). Izrek so (za vrednosti a = 3, b = 4 in c = 5) uporabljali že stari egipčani (cca. 4000 p. n. št.). Pred Pitagoro so ga zagotovo poznali tudi stari Kitaj- ci (Cullen, 1996). Pitagorov izrek je najbolj znana trditev v ma- tematiki. Enačba a 2 + b 2 = c 2 pa velja za četrto najlepšo enačbo nasploh (Ratner, 2009). Einstein ga je dokazal pri 12 letih. Zato si Pitagorov izrek zagotovo zasluži predstavitev vsaj dveh doka- zov. Najpreprostejši dokazi temeljijo na geometrijski predstavi. Na sliki 1 je prikazan miselni proces, ki vodi do dveh preprostih dokazov trditve Pitagorovega izreka. Dokaz 1. Narišimo kvadrat s stranico a + b. Vodoravni in nav- pični stranici razdelimo na odseka a in b, kot kaže slika 1 (levo). Ostra kota α in β sta določena z razmerjem odsekov a in b in s pravim kotom γ. (Ker smo začeli s kvadratom s stranico a + b, je kot γ pravi: 90°. Zato so svetlo-sivi trikotniki pravokotni triko- tniki s hipotenuzo c in katetama a in b.) Ker smo v evklidski ravnini, je α + β + γ = 180°. Kot α + β + φ je iztegnjen in zato je tudi kot φ pravi. Torej je modri štirikotnik kvadrat. Ploščinski argument pove, da je Primer 1. Želimo dokazati, da je 2 zgornja meja zaporedja IZ TEORIJE ZA PRAKSO 20 Matematika v šoli, št. 2., letnik 28, 2022 in Iz obeh enačb sledi kar smo želeli dokazati.  2 Sheme dokazovanja v srednji šoli Zgoraj smo omenjali več načinov dokazovanja in z njimi pove- zane miselne procese. V tem poglavju na kratko opišemo glavne načine/sheme dokazovanja: a) dedukcija; b) dokaz s protislovjem; c) kontrapozicija; d) dokaz s protiprimerom (ko ovržemo trditev o splošnosti); e) popolna matematična indukcija. Poleg omenjenih načinov obstajajo še drugi, kot so npr. kon- struktivni dokaz, verjetnostni dokaz in kombinatorični dokaz (Weisstein, 2022). Pomembno je ločiti med (enostavno) izjavo s kvantifikatorji in pa sestavljeno izjavo (kot npr. implikacijo A ⇒ B). Opozorimo, da načini a)-c) opisujejo dokazovanje im- plikacije A ⇒ B medtem ko d) in e) opisujeta izjavo s kvantifika- torji, kjer govorimo o izjavi, da neka trditev T(n) velja za vsak n. V primeru d) izrek »T(n) velja za vsak n« ovržemo, v primeru e) pa izrek »T(n) velja za vsak n« dokažemo na osnovi baze induk- cije ter induktivnega koraka. Seveda mora biti v primeru e) n ∈ , medtem ko v primeru d) to ni nujno. V nadaljevanju temelji- teje predstavljamo dokazne sheme za vseh pet primerov. a) Dedukcija Izjavo A ⇒ B lahko dokažemo povsem deduktivno (direktno): torej najdemo zaporedje implikacij, ki dokazujejo, da iz A sledi B. Logična shema dedukcije je (A ⇒ B) ⇒ (A ⇒ B 1 , B 1 ⇒ B 2 , …, B n–1 ⇒ B n , B n ⇒ B). Ponazorimo to z dvema primeroma. Slika 1: Dve preprosti geometrijski ideji za dokaz Pitagorovega izreka. Zgoraj: miselna shema na osnovi večjega in manjšega kvadrata. Spodaj: skica Einsteinovega dokaza (pri 12 letih). Dokaz 2. Einsteinov dokaz Pitagorovega izreka, ki ga je napisal pri 12 letih, temelji na ploščinah znotraj osnovnega trikotnika s stranicami a, b in c: oranžni pravokotni trikotnik ima hipotenu- zo a, zeleni pravokotni trikotnik ima hipotenuzo b, skupni pra- vokotni trikotnik ima hipotenuzo c (Slika 1, desno). Za vsakega od teh treh pravokotnih trikotnikov velja, da je ploščina številsko enaka produktu kvadrata njegove hipotenuze in faktorja . Ko razmislimo, da je za podobne tri- kotnike faktor f enak, iz enačbe ploščin a 2 ∙ f + b 2 ∙ f = c 2 ∙ f po krajšanju s skupnim faktorjem f sledi a 2 + b 2 = c 2 .  Med bolj znanimi dokazi Pitagorovega izreka je še Leonardov dokaz (najdete ga npr. v Mencinger, 2022) in dokaz ameriškega predsednika J. A. Garfielda (Dunham, 1994). Veliko zanimivih geometrijskih dokazov, ki so primerni za dokazovanje v srednji šoli, najdete v (Nelsen, 1993; 2000; 2016). Primer 2. Dokažimo, da za vsako naravno število n velja: n 2 – n je sodo število. Primer 3. Dokažimo, da je izraz x 2 – 6x + 16 pozitiven za vsako realno število x. Sklepamo tako, da najprej število n 2 – n zapišemo kot n 2 – n = n(n – 1). Ker sta to dve zaporedni naravni števili, lahko brez izgube za splošnost (b. i. z. s.) pišemo n = 2k + 1 in n – 1 = 2k za neko naravno število k. Potem je n 2 – n = n(n – 1) = (2k + 1)2k = 4k 2 + 2k = 2(2k 2 + k), kar je očitno sodo število, saj je deljivo z 2. Izraz x 2 – 6x + 16 lahko zapišemo kot x 2 – 6x + 16 = (x – 3) 2 + 7. Število (x – 3) 2 je pozitivno za vsak x saj je kvadrat števila. Če dodamo 7, število ostane pozitivno. b) Dokaz s protislovjem Dokaz s protislovjem je za razliko od dedukcijskega dokaza in- direktna metoda dokazovanja: poskušamo zaobiti problem in IZ TEORIJE ZA PRAKSO 21 Matematika v šoli, št. 2., letnik 28, 2022 najti pameten argument, ki ustvari logično protislovje. Izjavo A lahko dokažemo s protislovjem (kontradikcijo) tako, da ob pre- misi privzamemo ¬A in dokažemo, da iz tega sledi protislovje, ki običajno nastopa v obliki B ∧ ¬B (za neko drugo izjavo B). Če protislovje označimo s P to pomeni pomeni ¬A ⇒ P, kar pome- ni, da je ¬A neresnična izjava. Trditev A je lahko bodisi resnična bodisi neresnična (ne more biti hkrati resnična in neresnična, kar je obravnaval že Aristotel (Zalta, 2019)). Logična shema (tav- tologija) za tak dokaz je (¬A ⇒ P) ⇒ A, kar pomeni: če dokažemo pravilnost trditve, da iz premise in ne- gacije A sledi protislovje, smo s tem dokazali pravilnost izjave A. Privzamemo nasprotno, da . Torej je mogoče zapisati v obliki okrajšanega ulomka, t. j. , kjer je D(a, b) = 1. Po kvadriranju in množenju z b 2 dobimo 2b 2 = a 2 . Vidimo, da je a 2 sodo število in posledično je tudi a sodo število, torej oblike a = 2m, kjer je m naravno število. Tako velja 2b 2 = (2m) 2 = 4m 2 . Po deljenju z dva dobimo b 2 = 2m 2 od koder vidimo, da je tudi b 2 sodo število in posledično je b sodo število. Torej sta oba a in b deljiva z 2, kar nas privede do protislovja (s tem, da je ulomek okrajšan). To pa pomeni, da je resnična izjava (in ne njena negacija ). c) Kontrapozicija Dokaz s protislovjem ni edini način indirektnega dokazovanja – obstaja še dokaz s kontrapozicijo, ki je prav tako indirektna metoda dokazovanja in ki poteka po naslednji shemi: namesto implikacije A ⇒ B dokažemo implikacijo ¬B ⇒ ¬A. Primer 4. Dokaži, da ne obstaja celo število, ki bi bilo sodo in liho hkrati. Primer 5. Dokaži, da za vsa naravna števila n velja: če je n 3 + 5 liho, je n sodo število. Primer 7. Dokaži, da za a, b, n velja: če n ab, potem n a in n b. Primer 8. Dokaži, da za x velja: če je x 2 – 6x + 5 sodo število, potem je x liho število. Primer 9. Naj bo odvedljiva in monotono naraščajoča funkcija (torej iz x > y sledi f(x) > f(y)). Trditev, da za vsak x ∈ velja f'(x) > 0, ne velja. Protiprimer je funkcija f(x) = x 3 , za katero v točki x = 0 sklep ne velja, saj je f'(0) = 0. Primer 10. Za vsak n ∈ velja, da je iracionalno število. Primer 6. Najbolj klasični primer dokaza trditve s protislovjem, ki se obdela tudi v gimnaziji, je dokaz izjave . Dokaz. Dokaz te (enostavne izjave) s protislovjem poteka takole. Poglejmo negacijo izjave, torej izjavo, da obstajajo cela števila n, k in l, da velja n = 2k ∧ n = 2l + 1. Izračunamo . Iz tega sledi, da je , kar je protislovje, saj je množica celih števil zaprta za odštevanje. Dokaz. Naj bo n poljubno naravno število in predpostavimo, da sta tako n 3 + 5 kot n lihi števili. V tem primeru obstajata takšni števili k in l, da je n 3 + 5 = 2k + 1 in n = 2l + 1. Torej velja: n 3 + 5 = 2k + 1 (2l + 1) 3 + 5 = 2k + 1 8l 3 + 12l 2 + 6l + 1 + 5 = 2k + 1 8l 3 + 12l 2 + 6l + 5 = 2k. Če zadnjo enakost delimo z 2, dobimo , kar je protislovje, saj je k – 4l 3 – 6l 2 – 3l celo število. Torej mora veljati, da v primeru, ko je n 3 + 5 liho število, n ne more biti liho število oz. je lahko samo sodo število.  Pogosta alternativna oblika dokazovanja s protislovjem je dokaz, da iz ¬A ⇒ A, kar je očitno protislovje (razen, če je izjava ¬A ne- resnična, kar pomeni, da mora biti A resnična). Logična shema za ta tip dokaza je A ⇒ (A ⇒ A) ⇒ ¬(¬A) ⇒ A ⇒ (¬A ⇒ A) (tu smo uporabili tavtologijo (A ⇒ B) ⇒ (¬A ⇒ B)). Najprej moramo najti negacijo izjave ''n a in n b''. Tukaj je potrebna previdnost, kajti negacija je ''n|a ali n|b'' (Uporabili smo DeMorganov zakon). Recimo, da n deli a. Potem je a = nc za nek c in ab = ncb = n(cb). Torej n|ab. Podobno, če n deli b, je b = nd za nek d in ab = and = n(ad). Zato n|ab. Dokažimo s kontrapozicijo: predpostavimo, da je x sodo število in dokažimo, da je potem x 2 – 6x + 5 liho število. Če je x sodo število, je oblike x = 2k za nek k , od koder sledi x 2 – 6x + 5 = (2k) 2 – 6(2k) + 5 = 4k 2 – 12k + 5 = 2(2k 2 – 6k + 2) + 1. Vidimo, da je x 2 – 6x + 5 liho število. d) Dokaz s protiprimerom Če želimo ovreči, da je neka trditev tipa »za vsak element m ∈ M je trditev T(m)« resnična, iščemo protiprimer. V jeziku logike to pomeni »obstaja (vsaj en) element (iz množice M), za katerega T ni resnična«. Trditev ni resnična, saj lahko najdemo protiprimer. Če izberemo npr. n = 7, vidimo, da trditev je iracionalno število« ni resnična. IZ TEORIJE ZA PRAKSO 22 Matematika v šoli, št. 2., letnik 28, 2022 Izračunamo vrednost izraza za prvih nekaj praštevil in rezultate zapišemo v spodnji tabeli. p 2 3 5 7 11 2 p – 1 3 7 31 127 2047 Števila 3, 7, 31 in 127 so praštevila, medtem ko 2047 = 23 · 89 ni praštevilo. Torej smo našli protiprimer, zato zgornja trditev ne velja. e) Matematična indukcija Matematična indukcija je močna in elegantna tehnika za doka- zovanje določenih vrst matematičnih trditev: splošne izjave, ki trdijo, da je nekaj res za vsa naravna števila ali za vsa naravna šte- vila od nekega naravnega števila naprej. Z naslednjim primerom se je že kot mlad učenec ukvarjal znani matematik C. F. Gauss (1777–1855). snična. Iz tega sledi, da so vse trditve pravilne. Zapišimo ta dva koraka v formalnem navodilu. Baza indukcije (začetni korak). Dokaži, da je trditev resnična za n = 1. (Ali, če dokazujemo trditev za n ≥ a, dokažemo njeno resničnost za n = a.) Indukcijski korak. Dokaži, da če je trditev resnična za n = k, potem je resnična tudi n = k + 1. Ta korak predstavlja zahtevnejši del indukcije, zato ga razdelimo na več manjših korakov. Korak 1: Zapišemo trditev za n = k in predpostavimo, da ta trdi- tev velja. Zato jo ponavadi imenujemo indukcijska predpostavka. Korak 2: Zapišemo trditev za n = k + 1, t. j. trditev, ki jo želimo dokazati. Korak 3: Dokažemo korak 2 ob indukcijski predpostavki iz ko- raka 1. Za ta korak ni splošnega recepta, saj se razlikuje za različ- ne primere in je odvisen od matematičnega konteksta. Uporabiti je treba iznajdljivost in znanje matematike. Ko enkrat izvedemo oba koraka (baza indukcije in indukcijski korak), lahko takoj zaključimo, da je trditev resnična za vsak n ≥ 1 (ali za vsak n ≥ a, če smo začeli z n = a). Na celotni po- stopek lahko gledamo kot na nek »avtomatski stroj dokazovanja izjav«. Dokažemo trditev za n = 1. Po indukcijskem koraku, ker trditev velja za n = 1, velja tudi za n = 2. Nato ponovno po in- dukcijskem koraku, ker trditev velja za n = 2, velja tudi za n = 3 itd. Ker smo dokazali indukcijski korak, se ta proces nikoli ne zaključi. Ta »avtomatski stroj« nikoli ne preneha delati ne glede na to, kako veliko je število n. Recimo, da obstaja število K, za katerega je trditev neresnična. V tem primeru, ko pridemo do števila K – 1, imamo situacijo: trditev je resnična za n = K – 1 ampak napačna za n = K. To na- sprotuje induktivnemu koraku in zato se to ne more zgoditi, kar pomeni, da je trditev resnična za vsa naravna števila. Matematično indukcijo lahko primerjamo s procesom zanke v računalniškem programiranju, kjer začnemo tako, da določimo začetno vrednost, kar je pri indukciji analogno bazi indukcije. Nato pa definiramo zanko, ki s pomočjo prejšnjih vrednosti spremenljivk računa nove vrednosti, kar je analogno indukcij- skemu koraku v matematični indukciji. V računalniškem pro- gramu je potrebna še ena stvar: nastaviti je treba pogoj »stop«, sicer bo program deloval večno. To pa nima analogije v našem procesu – naš teoretični stroj bo deloval večno in zato smo lahko prepričani, da je naš rezultat resničen. Poglejmo, kako matematična indukcija deluje na konkre- tnem primeru. Dokažimo trditev iz primera 11, torej, da je . Baza indukcije. Če je n = 1, je vsota 1. Po drugi strani pa je za n = 1 vrednost izraza prav tako enaka 1. Torej je trditev resnična za n = 1. Indukcijski korak. Korak 1: Zapišemo indukcijsko predpostavko: (Lastnost za n = k). Primer 11. Preveri, ali velja trditev: če je p praštevilo, je tudi 2 p – 1 praštevilo. Primer 12. Dokaži, da je vsota prvih n naravnih števil enaka . Preverimo trditev za prva štiri naravna števila in rezultate zapi- šimo v tabelo: n 1 2 3 4 Vsota prvih n naravnih števil 1 1 + 2 = 3 1 + 2 + 3 = 6 1 + 2 + 3 + 4 = 10 Morda je to precej prepričljivo in lahko se vprašamo, ali je po- treben še kakšen dokaz. Če trditev velja za vsa števila, ki smo jih preizkusili, ali lahko sklepamo, da je resnična za vse vrednosti n? Spomnimo se primera 11, kjer je trditev veljala za prva štiri praštevila, pri petem praštevilu pa se je izkazalo, da je splošna trditev napačna. Vrnimo se k primeru 12 in se vprašajmo, koliko naravnih števil bi morali preveriti, da bi lahko z gotovostjo trdili, da je trditev pravilna. Recimo, da nam računalnik po vrsti po na- ravnih številih računa vsote. Ne glede na to, za koliko naravnih števil n smo ugotovili, da je trditev pravilna, ne bomo prepričani, ali obstaja večje naravno število n za katero je trditev napačna. Ravno to pa narekuje potrebo po splošnem dokazu, ki zajema vse vrednosti n. Eden od načinov razmišljanja o matematični indukciji je, da ne dokažemo ene trditve za splošen n ampak celo zaporedje trditev za posamezna naravna števila n. Bistvo matematične indukcije je, da dokažemo prvo trditev zaporedja, nato pa, če je katerakoli trditev v zaporedju resnična, je tudi njena naslednja trditev re- IZ TEORIJE ZA PRAKSO 23 Matematika v šoli, št. 2., letnik 28, 2022 Korak 2: Zapišemo indukcijski sklep Korak 3: Dokažemo, da iz indukcijske predpostavke sledi in- dukcijski sklep (t. j. desno stran enačbe v koraku 2 pridobimo s pomočjo leve strani enačbe v koraku 1 z dodajanjem člena k + 1: kar zaključuje induktivni korak. Zato trditev velja za vse . Na koncu si poglejmo še geometrijski primer, kjer trditev velja od n = 4. Zato se baza indukcije začne pri 4. Korak 3: Dokažemo, da iz indukcijske predpostavke sledi induk- cijski sklep. Zato konveksnemu -kotniku dodamo novo oglišče, da dobimo konveksni (k + 1)-kotnik (pazimo, da nastali lik osta- ne konveksen). Nato pogledamo, koliko novih diagonal s tem pridobimo (glej sliko 3). Slika 3: Konveksni k-kotnik (levo) in konveksni (k + 1)-kotnik (desno). Ko dodamo še eno oglišče k večkotniku s k oglišči, vse diago- nale, ki so bile že v prejšnjem k-kotniku, ostanejo tudi v novem (k + 1)-kotniku in teh je po indukcijski predpostavki . Dodatno nastane še k – 2 diagonal, ki jih narišemo iz oglišča P k + 1 do drugih nesosednjih oglišč (glej sliko 3 (desno), kjer so te diagonale narisane z rdečo barvo). Ena dodatna diagonala pa nastane iz stranice, ki je v k-kotniku povezovala oglišči P 1 in P k . Tako dobimo diagonal (kar potrjuje, da iz indukcijske predpostavke sledi in- dukcijski sklep).  Nazadnje obravnavajmo primer, ki je zanimiv predvsem zaradi enostavnosti trditve. Kljub temu pa matematiki (še) niso postre- gli z dokazom (ali ovrgli veljavnost trditve s protiprimerom), kar pomeni, da ima trditev status domneve (in ne izreka). Domneva se imenuje po nemškem matematiku Lotharju Collatzu, druga imena so tudi »3x + 1 domneva«, Ulamova domneva, Kakutani- jev problem, Thwaitesov problem, Hassejev algoritem in sirakuški problem. Collatzova domneva je zanimiva , ker je njena trditev tako preprosta, da jo lahko razume učenec v osnovni šoli, pa vendar je v 85-ih letih od njene formulacije niso uspeli niti do- kazati, niti ovreči. Domneva (Collatz, 1937). Collatzova funkcija C(n) naravne- mu številu priredi število če je število n sodo, oziroma 3x + 1, če je število n liho. Collatzova domneva pravi, da za vsako naravno število n zaporedno izračunavanje Collatzove funkcije na nekem koraku privede do števila 1. Opomba. Če zaporedno iteracijo označimo s C k (n), lahko zgornjo domnevo zapišemo takole: za vsak obstaja , da je C k (n) = 1, vendar ta formulacija ni primerna za osnovno šolo. Omenimo, da poskusi, da bi domnevo ovrgli segajo v neverjetne višave. Največje število doslej, ki so ga testirali kot potencialni proti-primer (Ren, 2019), je število n = 2 100000 – 1. Po neverjet- Primer 13. Za vsak n ≥ 4 je število diagonal v konveksnem n-kotniku enako . n-kotnik je večkotnik, ki ima n oglišč. n-kotnik je konveksen, če za vsako njegovo nosilko stranice velja, da preostala oglišča ležijo na isti polravnini te nosilke. V konveksnem n-kotniku so diago- nale vedno znotraj lika. Slika 2 prikazuje konveksni petkotnik z diagonalami. Slika 2: Konveksni petkotnik. Sedaj s pomočjo indukcije pokažimo, da trditev v primeru 12 velja za vsak n ≥ 4. Baza indukcije. Če je n = 4, je lik štirikotnik, za katerega vemo, da ima dve diagonali. Prav tako je za n = 4 vrednost izraza enaka 2. Torej je trditev resnična za n = 4. Indukcijski korak. Korak 1: Indukcijska predpostavka: trditev velja za n = k. Število diagonal v konveksnem k-kotniku je enako . Korak 2: Indukcijski sklep: trditev velja za n = k + 1. Število dia- gonal v konveksnem (k + 1)-kotniku je enako . IZ TEORIJE ZA PRAKSO 24 Matematika v šoli, št. 2., letnik 28, 2022 nih k = 1344926 iteracijah sledi C k (n) = 1; od tega je bilo treba 481603-krat uporabiti funkcijo n 3n + 1 in 863323-krat del- jenje z 2. Omenimo še, da so raziskave na področju Collatzove domneve številne in zelo aktualne (Ren, 2019). Problem narav- no spada v teorijo (diskretnih) dinamičnih sistemov (iteracije). Bistvo težavnosti problema seveda ne tiči v sodih številih, ki jih delimo z 2, ampak v lihih številih, ki jih množimo s tri (in prište- jemo ena). Zato je indukcijski sklep težko izpeljati. Za dovolj majhne množice niti v osnovni šoli, še manj pa v srednji šoli ni težko dokazati veljavnost trditve, »za vsak obstaja , da je C k (n) = 1«. Pripadajoče orbite so naslednje: 1421 (za n = 1), 21 (za n = 2), 3105168421 (za n = 3), 421 (za n = 4), 5168421 (za n = 5), 63105168421 (za n = 6), 722113417522613402010516 8421 (za n = 7), 8421 (za n = 8), 928147221134175226134020 105168421 (za n = 9) in 105168421 (za n = 10). Zgornji seznam pomeni, da je za množico Collatzova dom- neva dokazana. Opazimo, da so dolžine orbit enake n 1 2 3 4 5 6 7 8 9 10 k 3 1 7 2 5 8 16 3 19 6 Iz zgornje tabele je razvidno, kaj je potencialna težava pri induk- tivnem dokazovanju za splošno naravno število. Gre za dolžino (najdaljšega) cikla: za m = 10 je dolžina maksimalnega cikla pri naravnem številu n = 9 enaka k = 19. Drugi problem je največje število, kamor nas iteracije »odnesejo«: v tem primeru število 52. To število je lahko bistveno večje, kot sam m = 10, ki nastopa v trditvi. Primer 14. Za je trditev »za vsak obstaja , da je C k (n) = 1« resnična. Primer 15. Za je trditev »za vsak obstaja , da je C k (n) = 1 resnična. Za n = 1 izračunamo: C(1) = 4, C(4) = 2in C(2) = 1, kar pomeni C 3 (1) = 1. Za n = 2 izračunamo: C(2) = 1. Za n = 3 izračunamo: C(3) = 10, C(10) = 5, C(5) = 16, C(16) = 8, C(8) = 4, C(4) = 2 in C(2) = 1 kar pomeni C 7 (3) = 1 Za n = 4 izračunamo: C(4) = 2 in C(2) = 1 kar pomeni C 2 (4) = 1. Zgornji izračuni potrjujejo/dokazujejo, da ima za množico Collatzova domneva status (dokazane) trditve. Opomba. Zgornje zaporedne izračune lahko krajše zapišemo v obliki orbite, ki nastane z iteriranjem Collatzove funkcije C. Za n = 3 je pripadajoča orbita 3  10  5  16  8  4  2  1. Zaključek Na preprostih primerih smo spoznali različne tehnike dokazovanja, katerih poznavanje in razumevanje je (tako za učitelja kot za dijaka) zelo pomembno. Dokaz mora pokazati, da je trditev (vedno: za vse pogoje premise oziroma za vse vrednosti iz dane množice) resnična, pri čemer lahko včasih navedemo vse možne primere in preverimo veljavnost za vsak konkreten primer, ni pa dovolj zgolj navesti končnega števila primerov, za katere trditev velja, če naj nekaj velja za vsa naravna števila. Navajanje primerov, za katere trditev velja, lahko zgolj privede do nepotrjene trditve, za katero se domneva, da je resnična in jo zato imenujemo domneva, če zanjo še ni bilo mogoče najti dokaza. Ena izmed najbolj znanih domnev je Collatzova domneva, ki smo jo navedli kot primer domneve, katere dikcija je zelo preprosta, dokaz pa je zelo zahteven. Literatura [1] Cullen, C. (1996). Astronomy and mathematics in ancient China: the Zhou bi suanjing. Cambridge University Press. https://avser- zhen.files.wordpress.com/2016/06/astronomy-and-mathematic-in-ancient-china.pdf [2] Dunham, W . (1994). The Mathematical Universe. New Y ork: John Wiley & Sons. [3] Franklin, J., Daoud, A. (2011). Proof in Mathematics, An Introduction, Quakers Hill Press. https://web.maths.unsw.edu.au/~jim/ proofs.html [4] Harel, G. (2008). A DNR perspective on mathematics curriculum and instruction. Part II: with reference to teacher’s knowledge base. ZDM Mathematics Education 40, str.893–907. [5] Harel, G., Sowder, L. (1998). Student’s proof schemes: Results from exploratory studies. In A. Schoenfeld, J. Kaput & E. Dubinsky (ur.), Research in collegiate mathematics education 3, str. 234–283. IZ TEORIJE ZA PRAKSO 25 Matematika v šoli, št. 2., letnik 28, 2022 [6] Mencinger, M. (2022). Simetrijske grupe končnih vzorcev , Univerzitetna založba UM. https://dk.um.si/IzpisGradiva.php?id=81064 [7] Nelsen, R. B. (1993). Proofs Without Words. ZDA: The Mathematical Association of America. [8] Nelsen, R. B. (2000). Proofs Without Words II. ZDA, The Mathematical Association of America. [9] Nelsen, R. B. (2016). Proofs Without Words III. ZDA, The Mathematical Association of America. [10] Ratner, B. (2009). Pythagoras: Everyone knows his famous theorem, but not who discovered it 1000 years before him. J Target Meas Anal Mark 17, 229–242. https://doi.org/10.1057/jt.2009.16 [11] Ren, W . (2019). A New Approach on Proving Collatz Conjecture, Journal of Mathematics, Hindawi. https://www.hindawi.com/ journals/jmath/2019/6129836/ [12] Weisstein, E. W. (2022). Constructive Proof, From MathWorld-A Wolfram Web Resource. https://mathworld.wolfram.com/ ConstructiveProof.html [13] Zalta, E. N. (ur.) (2019). The Stanford Encyclopedia of Philosophy. https://plato.stanford.edu/ [14] Žakelj, A. Učni načrt: Matematika, Gimnazja (Splošna, klasična in strokovna gimnazja), Ministrstvo za šolstvo in šport, Zavod RS za šolstvo 2008. http://eportal.mss.edus.si/msswww/programi2017/programi/media/pdf/un_gimnazija/un_matematika_gimn. pdf IZ RAZREDA Matematika v šoli, št. 1., letnik 24, 2018 Formativno spremljanje pri MATEMATIKI mag. Mojca Suban, mag. Melita Gorše Pihler, Jerneja Bone, Karmen Debenjak, Loreta Hebar, Špela Jenko, Tatjana Kerin, Mojca Novoselec, Mateja Peršolja, mag. Sonja Rajh, Amela Sambolić Beganović, mag. Mateja Sirnik, Karmen Škafar, Jana Šturm, Andreja Verbinc V priročniku so opisana različna preizkušena ORODJA V PODPORO UČENJU IN POUČEVANJU MATEMATIKE skupaj z naborom učnih ur, v katerih orodja zaživijo v vsej svoji funkcionalni vrednosti. V ospredje je postavljen učenec in njegova vloga pri oblikovanju lastne učne poti. 152 strani, A4 format Cena: 11,90 € Naročila: Priročnik za učitelje tiskani priročnik