Úvod do informatiky pˇrednáška sedmá
Miroslav Kolaˇrík ˇ Zpracováno dle uˇcebního textu R. Belohlávka: Úvod do informatiky, KMI UPOL, Olomouc 2008.
Obsah
1
ˇ Císla a cˇ íselné obory
2
Princip indukce
3
Vybrané poznatky z teorie cˇ ísel
Obsah
1
ˇ Císla a cˇ íselné obory
2
Princip indukce
3
Vybrané poznatky z teorie cˇ ísel
ˇ Pˇrirozená císla Jsou to cˇ ísla 1, 2, 3, 4, 5, 6, . . . . Množinu všech pˇrirozených cˇ ísel oznaˇcujeme N. ˇ Celá císla Jsou to cˇ ísla 0, 1, −1, 2, −2, 3, −3, 4, −4, 5, −5, . . .. Množinu všech celých cˇ ísel znaˇcíme Z. ˇ Racionální císla Jsou to cˇ ísla, která lze vyjádˇrit ve tvaru zlomku m n , kde m je celé cˇ íslo a n je pˇrirozené cˇ íslo. Množinu všech racionálních cˇ ísel 21 −6 oznaˇcujeme Q. Racionální cˇ ísla jsou tedy napˇr. 13 , −2 5 , 37 , 12 6 atd. Poznamenejme, že 13 , 62 , 18 jsou ruzné ˚ zápisy téhož racionálního cˇ ísla. Racionální cˇ ísla zapisujeme také pomocí tzv. desetinného rozvoje. Napˇr. cˇ íslo 23 zapisujeme jako 1, 5. 1 ˇ Císlo cný desetinný rozvoj a je jím 0, 3333 . . ., 3 má tzv. nekoneˇ což také zapisujeme jako 0, 3.
ˇ Reálná císla Jsou to všechna cˇ ísla, která se nacházejí na cˇ íselné ose. ˇ Kromeˇ racionálních cˇ ísel zahrnují reálná cˇ ísla i tzv. císla iracionální. To jsou cˇ ísla, která nelze vyjádˇ r it ve tvaru zlomku. √ √ Pˇríkladem iracionálních cˇ ísel jsou 2, 3, π , e. Množinu všech reálných cˇ ísel oznaˇcujeme R. ˇ Komplexní císla Množinu všech uspoˇrádaných dvojic reálných cˇ ísel ha, bi zapisovaných obvykle ve tvaru a + bi, kde symbolem i oznaˇcujeme tzv. imaginární jednotku, pro niž platí i 2 = −1, nazýváme komplexní cˇ ísla; znaˇcíme C. Zásluhou K.F. Gausse ˇ komplexní cˇ ísla v rovine. ˇ se od roku 1831 znázornují Každé komplexní cˇ íslo z = a + bi mužeme ˚ vyjádˇrit i v tzv. goniometrickém tvaru z = r (cos ϕ + i sin ϕ ), kde cˇ íslo √ 2 2 r = a + b je tzv. absolutní hodnota a úhel ϕ argument komplexního cˇ ísla.
Obsah
1
ˇ Císla a cˇ íselné obory
2
Princip indukce
3
Vybrané poznatky z teorie cˇ ísel
Princip (matematické) indukce ˇ Princip indukce umožnuje dokazovat tvrzení tvaru "pro každé ˇ pˇrirozené cˇ íslo n platí V (n)", kde V (n) je nejaké tvrzení, které n(n+1)(2n+1) 2 2 2 ). závisí na n (napˇr. 1 + 2 + · · · + n = 6 ˇ (princip indukce) Veta Necht’ je pro každé n ∈ N dáno tvrzení V (n). Pˇredpokládejme, že platí V (1) . . .
ˇ pˇredpoklad (1. krok) indukcní
∀n ∈ N: z V (n) plyne V (n + 1)
...
ˇ krok. indukcní
Pak V (n) platí pro každé n ∈ N.
Princip dobrého uspoˇrádání: Dále budeme pˇredpokládat, že každá neprázdná podmnožina K ⊆ N má nejmenší prvek (což je pravdivý a intuitivneˇ jasný pˇredpoklad).
Dukaz: ˚ Princip indukce dokážeme sporem. Pˇredpokládejme, že princip ˇ oba indukce neplatí, tj. existují tvrzení V (n), n ∈ N, která splnují ˇ pˇredpoklady principu indukce, ale pro nejaké n′ ∈ N tvrzení V (n′ ) neplatí. Oznaˇcme K = {m ∈ N | V (m) neplatí} množinu všech takových n′ . K je tedy neprázdná, nebot’ n′ ∈ K . Množina K má tedy nejmenší prvek k (dle principu dobrého uspoˇrádání) a ten je ruzný ˚ od 1 (dle indukˇcního pˇredpokladu 1 ∈ / K ). Pak tedy k − 1 ∈ / K , tedy V (k − 1) platí. Z indukˇcního kroku plyne, že platí i V (k), tedy k ∈ / K , což je spor s k ∈ K .
Pˇríklad Dokažme výše uvedený vztah 12 + 22 + · · · + n2 = n(n+1)(2n+1) . 6 ˇ rit indukˇcní pˇredpoklad a Podle principu indukce staˇcí oveˇ indukˇcní krok. ˇ pˇredpoklad: V (1) je tvrzení 12 = Indukcní
1·2·3 6 ,
a to platí.
ˇ krok: Pˇredpokládejme, že platí V (n) a dokažme Indukcní V (n + 1). 12 + 22 + · · · + n2 + (n + 1)2 =
n(n + 1)(2n + 1) + (n + 1)2 = 6
(n + 1)(2n2 + 7n + 6) (n + 1)(n + 2)(2(n + 1) + 1) = , 6 6 což je práveˇ tvrzení V (n + 1). Podle principu indukce je tedy tvrzení dokázané. =
Pˇríklad Dokažte, že poˇcet úhlopˇríˇcek pravidelného n-úhelníka (n ≥ 3) . je n(n−3) 2 ˇ Rešení: viz pˇrednáška.
Obsah
1
ˇ Císla a cˇ íselné obory
2
Princip indukce
3
Vybrané poznatky z teorie cˇ ísel
ˇ Delitelnost
Definice ˇ n, píšeme m | n, práveˇ když Pro m, n ∈ Z ˇríkáme, že m delí ∃k ∈ Z tak, že m · k = n. Když m | n, ˇríkáme také, že m je ˇ ˇ delitelem n nebo n je delitelné m. ˇ n zapisujeme m ∤ n.) (Fakt, že m nedelí
ˇ Veta Pro a, b, c ∈ Z platí
a) Jestliže a | b a b | c, pak a | c.
b) Jestliže a | b a a | c, pak ∀x, y ∈ Z platí a | (bx + cy). Dukaz: ˚ viz pˇrednáška.
Pˇríklad Dokažte indukcí, že pro ∀n ∈ N platí: 7 | (2n+2 + 32n+1 ). ˇ Rešení: viz pˇrednáška.
ˇ (o jednoznaˇcnosti delení ˇ Veta se zbytkem) Pro a, b ∈ Z existují jednoznaˇcneˇ urˇcená q, r ∈ Z tak, že a = bq + r a 0 ≤ r < b. ˇ ˇ ˇ ˇ Císlo r se nazývá zbytek po celocíselném delení císla a ˇ císlem b. Píšeme také (a mod b) = r . Definice ˇ Pˇrirozené cˇ íslo n se nazývá prvocíslo, jestliže n 6= 1 a jestliže n ˇ je delitelné jen cˇ ísly 1 a n.
ˇ Veta Existuje nekoneˇcneˇ mnoho prvoˇcísel. Dukaz: ˚ Sporem, viz pˇrednáška.
ˇ (o jednoznaˇcnosti delení ˇ Veta se zbytkem) Pro a, b ∈ Z existují jednoznaˇcneˇ urˇcená q, r ∈ Z tak, že a = bq + r a 0 ≤ r < b. ˇ ˇ ˇ ˇ Císlo r se nazývá zbytek po celocíselném delení císla a ˇ císlem b. Píšeme také (a mod b) = r . Definice ˇ Pˇrirozené cˇ íslo n se nazývá prvocíslo, jestliže n 6= 1 a jestliže n ˇ je delitelné jen cˇ ísly 1 a n.
ˇ Veta Existuje nekoneˇcneˇ mnoho prvoˇcísel. Dukaz: ˚ Sporem, viz pˇrednáška.
ˇ Veta √ 2∈ / Q. Dukaz: ˚ Sporem, viz pˇrednáška. ˇ Veta Množina Z je spoˇcetná. Dukaz: ˚ Najdeme bijekci Z na N, viz pˇrednáška. ˇ Veta Množina Q je spoˇcetná. Dukaz: ˚ Najdeme bijekci Q na N, viz pˇrednáška.
ˇ Veta √ 2∈ / Q. Dukaz: ˚ Sporem, viz pˇrednáška. ˇ Veta Množina Z je spoˇcetná. Dukaz: ˚ Najdeme bijekci Z na N, viz pˇrednáška. ˇ Veta Množina Q je spoˇcetná. Dukaz: ˚ Najdeme bijekci Q na N, viz pˇrednáška.
ˇ Veta Interval (0, 1) ⊆ R je nespoˇcetná množina. Dukaz: ˚ Tzv. Cantorovou diagonální metodou, viz pˇrednáška. Dusledek ˚ Množina R je nespoˇcetná.
Dusledek ˚ Množina všech iracionálních cˇ ísel je nespoˇcetná.
ˇ aritmetiky Základní veta ˇ než jedna lze vyjádˇrit jednoznaˇcneˇ Každé pˇrirozené cˇ íslo vetší až na poˇradí cˇ initelu˚ jako souˇcin prvoˇcísel.
ˇ o jednoznaˇcnosti zápisu pˇrirozeného cˇ ísla v soustaveˇ o Veta základu b Necht’ b > 1 je pˇrirozené cˇ íslo. Pro každé x ∈ N existují jednoznaˇcneˇ urˇcená cˇ ísla an , an−1 . . . , a1 , a0 , pˇriˇcemž 0 ≤ ai < b, an 6= 0 tak, že x = an b n + an−1b n−1 + · · · + a1 b + a0 . Poznámka: Pro zápis cˇ ísel ve dvojkové soustaveˇ (b = 2) používáme symboly 0 a 1. Pro zápis cˇ ísel v šestnáctkové soustaveˇ používáme symboly 0, 1, . . . , 9, A, B, C, D, E , F .
ˇ aritmetiky Základní veta ˇ než jedna lze vyjádˇrit jednoznaˇcneˇ Každé pˇrirozené cˇ íslo vetší až na poˇradí cˇ initelu˚ jako souˇcin prvoˇcísel.
ˇ o jednoznaˇcnosti zápisu pˇrirozeného cˇ ísla v soustaveˇ o Veta základu b Necht’ b > 1 je pˇrirozené cˇ íslo. Pro každé x ∈ N existují jednoznaˇcneˇ urˇcená cˇ ísla an , an−1 . . . , a1 , a0 , pˇriˇcemž 0 ≤ ai < b, an 6= 0 tak, že x = an b n + an−1b n−1 + · · · + a1 b + a0 . Poznámka: Pro zápis cˇ ísel ve dvojkové soustaveˇ (b = 2) používáme symboly 0 a 1. Pro zápis cˇ ísel v šestnáctkové soustaveˇ používáme symboly 0, 1, . . . , 9, A, B, C, D, E , F .
