ooooooooooooooo oooooooooooooo Matematika I - 3. přednáška Geometrie v rovině Michal Bulant Masarykova univerzita Fakulta informatiky 4. 3. 2009 □ S Obsah přednášky Q Afinní rovina Q Lineární zobrazení a matice Euklidovská rovina • Obsah trojúhelníka • Viditelnost v rovině Q Relace a zobrazení • Relace na množině • Rozklad podle ekvivalence ooooooooooooooo ooooooooooooc □ s • Martin Panák, Jan Slovák - Drsná matematika, e-text. • Roman Hilscher - MB101, e-text. • Slidy z přednášek a democvičeni ooooooooooooooo oooooooooooooo Doporučené zdroje • Martin Panák, Jan Slovák - Drsná matematika, e-text. • Roman Hilscher - MB101, e-text. • Slidy z přednášek a democvičení • Pavel Horák, Úvod do lineární algebry, MU Brno, skripta (http://www.math.muni.cz/~horak) • Luboš Motl, Miloš Zahradník, Pěstujeme lineární algebru, 3. vydání, Univerzita Karlova v Praze, Karolinum, 348 stran (elektronické vydání také na http://www.kolej.mff.cuni.cz/~lmotm275/skripta/). □ s Plan přednášky Q Afinní rovina Q Lineární zobrazení a matice Q Euklidovská rovina • Obsah trojúhelníka • Viditelnost v rovině Relace a zobrazení • Relace na množině a Rozklad podle ekvivalence ooooooooooooooo oooooooooooooo □ s ooooooooooooooo oooooooooooooo Afinní rovina a vektorový prostor M2 Na konci minulé přednášky jsme intuitivně používali elementární pojmy z geometrie reálné roviny. Budeme teď podrobněji zkoumat jak se vypořádávat s potřebou popisovat polohu v rovině, resp. dávat do souvislostí polohy různých bodů roviny. ooooooooooooooo oooooooooooooo Afinní rovina a vektorový prostor M2 Na konci minulé přednášky jsme intuitivně používali elementární pojmy z geometrie reálné roviny. Budeme teď podrobněji zkoumat jak se vypořádávat s potřebou popisovat polohu v rovině, resp. dávat do souvislostí polohy různých bodů roviny. Zkusme si množinu A = R2 představit z pohledu pozorovatele, který sedí v některém pevně zvoleném místě (můžeme mu říkat třeba bod O = (xo,yo) G M2). Předpokládejme, že ji vnímá jako nekonečnou desku bez jakýchkoliv zvolených měřítek a popisů a ví, co to znamená posunout se v libovolném násobku nějakého směru. Takové rovině budeme říkat afinní rovina. ooooooooooooooo oooooooooooooo Aby pozorovatel mohl vidět kolem sebe dvojice reálných čísel, musí si vybrat nějaký bod E\, kterému řekne bod [1,0] a jiný bod Ei, kterému začne říkat bod [0,1]. □ s ooooooooooooooo oooooooooooooo Aby pozorovatel mohl vidět kolem sebe dvojice reálných čísel, musí si vybrat nějaký bod E\, kterému řekne bod [1,0] a jiný bod Ei, kterému začne říkat bod [0,1]. Do všech ostatních se pak dostane tak, že poskočí a-krát ve směru [1,0], pak b-krát ve směru [0,1] a takovému bodu bude říkat bod [a, b]. Pokud to bude dělat obvyklým způsobem, nebude výsledek záviset na pořadí, tzn. může také napřed jít b-krát ve směru [0,1] a pak teprve v tom druhém. □ s ooooooooooooooo oooooooooooooo Aby pozorovatel mohl vidět kolem sebe dvojice reálných čísel, musí si vybrat nějaký bod E\, kterému řekne bod [1,0] a jiný bod Ei, kterému začne říkat bod [0,1]. Do všech ostatních se pak dostane tak, že poskočí a-krát ve směru [1,0], pak b-krát ve směru [0,1] a takovému bodu bude říkat bod [a, b]. Pokud to bude dělat obvyklým způsobem, nebude výsledek záviset na pořadí, tzn. může také napřed jít b-krát ve směru [0,1] a pak teprve v tom druhém. To, co jsme popsali, se nazývá volba (afinního) souřadného systému v rovině, bod O je jeho počátkem, posunutí E\ — O ztotožňujeme s dvojicí [1, 0], podobně u Ei a obecně každý bod P roviny je ztotožněn s dvojicí čísel [a, b] = P — O. □ s ooooooooooooooo oooooooooooooo Aby pozorovatel mohl vidět kolem sebe dvojice reálných čísel, musí si vybrat nějaký bod E\, kterému řekne bod [1,0] a jiný bod Ei, kterému začne říkat bod [0,1]. Do všech ostatních se pak dostane tak, že poskočí a-krát ve směru [1,0], pak b-krát ve směru [0,1] a takovému bodu bude říkat bod [a, b]. Pokud to bude dělat obvyklým způsobem, nebude výsledek záviset na pořadí, tzn. může také napřed jít b-krát ve směru [0,1] a pak teprve v tom druhém. To, co jsme popsali, se nazývá volba (afinního) souřadného systému v rovině, bod O je jeho počátkem, posunutí E\ — O ztotožňujeme s dvojicí [1, 0], podobně u Ei a obecně každý bod P roviny je ztotožněn s dvojicí čísel [a, b] = P — O. Všimněme si, že volbou pevného počátku O jsou zároveň ztotožněny jednotlivé body P roviny se směry posuvu v = P — O a že všechny takové posuvy umíme skládat (budeme říkat sčítat) a také jednotlivé směry násobit v poměru každého reálného čísla (budeme říkat násobit skalárem). □ s Naše operace sčítání bodů v rovině a jejich násobení skaláry splňují hodně vlastností skalárů. Budeme místo o směrech posuvu mluvit o vektorech a od bodů je budeme rozlišovat tím, že budou dány dvojicemi souřadnic v kulatých závorkách místo hranatých. Naše operace sčítání bodů v rovině a jejich násobení skaláry splňují hodně vlastností skalárů. Budeme místo o směrech posuvu mluvit o vektorech a od bodů je budeme rozlišovat tím, že budou dány dvojicemi souřadnic v kulatých závorkách místo hranatých. Když se náš pozorovatel umí posouvat o libovolný násobek pevného vektoru, pak také ví, co je to přímka. Je to podmnožina p c A v rovině taková, že existují bod O a vektor v takové, že p = {PeA P-0 = t-v, te8}. Naše operace sčítání bodů v rovině a jejich násobení skaláry splňují hodně vlastností skalárů. Budeme místo o směrech posuvu mluvit o vektorech a od bodů je budeme rozlišovat tím, že budou dány dvojicemi souřadnic v kulatých závorkách místo hranatých. Když se náš pozorovatel umí posouvat o libovolný násobek pevného vektoru, pak také ví, co je to přímka. Je to podmnožina p c A v rovině taková, že existují bod O a vektor v takové, že p = {PeA P-0 = t-v, te8}. Popišme si P = P (t) G p ve zvolených souřadnicích s volbou v = (a,ß): x(t)=xo + a-t, y(t)=y0+ß-t. ooooooooooooooo oooooooooooooo Jednoduchým výpočtem dostaneme (vyloučíme t z parametrického vyjádření pro x a y, když pro určitost předpokládáme, že třeba «7^0) —ßx + ay + (ßxo - etyo) = 0. To je obecná rovnice přímky ax + by = c, se známým vztahem dvojice čísel (a, b) a vektoru */ = (a, ß) aa + bß = 0. □ S ooooooooooooooo oooooooooooooo Jednoduchým výpočtem dostaneme (vyloučíme t z parametrického vyjádření pro x a y, když pro určitost předpokládáme, že třeba «7^0) —ßx + ay + (ßxo - etyo) = 0. To je obecná rovnice přímky ax + by = c, se známým vztahem dvojice čísel (a, b) a vektoru */ = (a, ß) aa + bß = 0. Výraz nalevo v rovnici přímky můžeme vidět jako skalární funkci F závislou na bodech v rovině a s hodnotami v R, samu rovnici pak jako požadavek na její hodnotu. □ g - = ooooooooooooooo oooooooooooooo Mějme dvě přímky p a q a ptejme se na jejich průnik pD q. Ten bude popsán jako bod, splňující rovnice obou přímek: ax + by = r cx + dy = s. □ s ooooooooooooooo oooooooooooooo Mějme dvě přímky p a q a ptejme se na jejich průnik pD q. Ten bude popsán jako bod, splňující rovnice obou přímek: ax + by = r cx + dy = s. Opět můžeme levou stranu vnímat jako přiřazení, které každé dvojici souřadnic [x(P),y(P)] bodů v rovině přiřadí vektor hodnot dvou skalárních funkcí F\ a Fi- □ s ooooooooooooooo oooooooooooooo Mějme dvě přímky p a q a ptejme se na jejich průnik pD q. Ten bude popsán jako bod, splňující rovnice obou přímek: ax + by = r cx + dy = s. Opět můžeme levou stranu vnímat jako přiřazení, které každé dvojici souřadnic [x(P),y(P)] bodů v rovině přiřadí vektor hodnot dvou skalárních funkcí F\ a Fi- Můžeme tedy naše rovnice napsat jako jediný vztah F(v) = w, kde F je přiřazení, které vektor v popisující polohu obecného bodu v rovině zobrazí na vektor zadaný levou stranou rovnic, a požadujeme, aby se toto zobrazení strefilo do předem zadaného vektoru w = (r,s). □ s Plán přednášky Q Lineární zobrazení a matice Q Euklidovská rovina • Obsah trojúhelníka • Viditelnost v rovině Relace a zobrazení • Relace na množině a Rozklad podle ekvivalence ooooooooooooooo oooooooooooooo □ s ooooooooooooooo oooooooooooooo Přiřazení F, se kterým jsme pracovali při popisu průniku přímek, zjevně respektuje operace sčítání a násobení s vektory a skaláry: F(r- v + s -w) = r • F (v) + s ■ F(w) v.w E pro všechny r,s G zobrazení z R2 do R2, a píšeme F : R2 -pro přímku šlo o lineární zobrazení F : R2 hodnotu c. 2. Říkáme, že F je lineární 2. Obdobně, v rovnici R a jeho předepsanou □ s - ooooooooooooooo oooooooooooooo Přiřazení F, se kterým jsme pracovali při popisu průniku přímek, zjevně respektuje operace sčítání a násobení s vektory a skaláry: F(r- v + s -w) = r • F (v) + s ■ F(w) pro všechny r, s G R, i/, w G R2. Říkáme, že F je lineární zobrazení z R2 do R2, a píšeme F : R2 —> R2. Obdobně, v rovnici pro přímku šlo o lineární zobrazení F : R2 —> R a jeho předepsanou hodnotu c. Stručně budeme zapisovat taková zobrazení pomocí matic a jejich násobení, které definujeme takto: Av a b c d a b\ (x c d ľ [y x ax + by ex + d y □ s - ooooooooooooooo oooooooooooooo Podobně, můžeme místo vektoru v zprava násobit jinou maticí B stejného rozměru jako je A. Prostě aplikujeme předchozí formule po jednotlivých sloupcích matice B a obrdržíme jako výsledek opět matice. □ s ooooooooooooooo oooooooooooooo Podobně, můžeme místo vektoru v zprava násobit jinou maticí B stejného rozměru jako je A. Prostě aplikujeme předchozí formule po jednotlivých sloupcích matice B a obrdržíme jako výsledek opět matice. Snadno ověříme tzv. asociativitu násobení: (A- B)v = A(Bv). □ S ooooooooooooooo oooooooooooooo Podobně, můžeme místo vektoru v zprava násobit jinou maticí B stejného rozměru jako je A. Prostě aplikujeme předchozí formule po jednotlivých sloupcích matice B a obrdržíme jako výsledek opět matice. Snadno ověříme tzv. asociativitu násobení: (A- B)v = A(Bv). Stejně snadno je vidět i distributivita A ■ {B + C) = A ■ B + A ■ C, neplatí však komutativita a existují dělitelé nuly. Např. 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 □ S ooooooooooooooo oooooooooooooo Výrazu ad — bc říkáme determinant matice A a značíme jej detA = \A\, neboli detA a b c d ad — bc. □ g - = ooooooooooooooo oooooooooooooo Výrazu ad — bc říkáme determinant matice A a značíme jej detA = \A\, neboli detA a b c d ad — bc. Jestliže k výsledku lineárního zobrazení ještě dovolíme přičíst pevný vektor T = (x(7),y(7)), tj. naše zobrazení bude v = y \cx + dy + y(T)J máme popsána právě všechna tzv. afinní zobrazení roviny do sebe. Známými příklady jsou všechny afinní podobnosti. Lineární zobrazení pak odpovídají těm afinním zobrazením, které zachovávají pevný bod O. □ s - 52 Plán přednášky Q Lineární zobrazení a matice Q Euklidovská rovina • Obsah trojúhelníka • Viditelnost v rovině Relace a zobrazení • Relace na množině a Rozklad podle ekvivalence ooooooooooooooo oooooooooooooo □ s •oooooooooooooo oooooooooooooo Přidejme nyní schopnost našeho pozorovatele vidět vzdálenosti. Pak lze definovat pojmy jako jsou úhel a otočení v rovině. □ s •oooooooooooooo oooooooooooooo Přidejme nyní schopnost našeho pozorovatele vidět vzdálenosti. Pak lze definovat pojmy jako jsou úhel a otočení v rovině. Jednoduše si to můžeme představit takto: pozorovatel se rozhodne o nějakých referenčních bodech E\ a E2, že jsou od něj ve vzdálenosti jedna, a zároveň si řekne, že jsou na sebe kolmé. Vzdálenosti ve směrech těchto bodů, tj. ve směrech souřadných os jsou dány příslušným poměrem, obecně používá Pythagorovu větu. Odtud vyjde známý vzorec pro velikost vektoru v = (a, b) \\v\\ = \/a2 + b2. □ S •oooooooooooooo oooooooooooooo Přidejme nyní schopnost našeho pozorovatele vidět vzdálenosti. Pak lze definovat pojmy jako jsou úhel a otočení v rovině. Jednoduše si to můžeme představit takto: pozorovatel se rozhodne o nějakých referenčních bodech E\ a E2, že jsou od něj ve vzdálenosti jedna, a zároveň si řekne, že jsou na sebe kolmé. Vzdálenosti ve směrech těchto bodů, tj. ve směrech souřadných os jsou dány příslušným poměrem, obecně používá Pythagorovu větu. Odtud vyjde známý vzorec pro velikost vektoru v = (a, b) + b2. Jiný možný postup by byl, kdyby pozorovatel vyšel z pojmu vzdálenost (a věděl, co znamená být kolmý, třeba díky Pythagorově větě), zvolil první z vektorů velikosti jedna, zvolil si orientaci (třeba proti směru hodinových ručiček) a vybral jednotkový kolmý směr (jednoznačně určí z požadavku platnosti Pythagorovy věty třeba pomocí pravoúhlého trojúhelníku se stranami o velikostech 3, 4 a 5). □ s o«ooooooooooooo oooooooooooooo Úhel p dvou vektorů v, w vyjadřujeme pomocí goniometrické funkce cosp, která je dána hodnotou první souřadnice jednotkového vektoru, jehož úhel s vektorem (1,0) je p. Zjevně je pak druhá souřadnice takového vektoru dána reálnou hodnotou 0 < sin p < 1 splňující cos2 p + sin2 p 1. □ S o«ooooooooooooo oooooooooooooo Úhel p dvou vektorů v, w vyjadřujeme pomocí goniometrické funkce cosp, která je dána hodnotou první souřadnice jednotkového vektoru, jehož úhel s vektorem (1,0) je p. Zjevně je pak druhá souřadnice takového vektoru dána reálnou hodnotou 0 < sin p < 1 splňující cos2 p + sin2 p 1. Obecně pak pro dva vektory v a w popisujeme jejich úhel pomocí souřadnic v = (x(i/),y(i/)), w = (x(w),y(w)) takto: cos p x(v) ■ x(w) + y(v) ■ y(w) \w\ □ s oo»oooooooooooo oooooooooooooo Příklady lineárních zobrazení Příkladem lineárního zobrazení, které zachovává velikosti, je rotace kolem počátku O o předem daný úhel ip. Je dána formulí s maticí Rý-. R i> ' cos^ — sint/; sint/; cos^ □ s oo»oooooooooooo oooooooooooooo Příklady lineárních zobrazení Příkladem lineárního zobrazení, které zachovává velikosti, je rotace kolem počátku O o předem daný úhel ip. Je dána formulí s maticí Rý-. R i> ' cos^ — sint/; sint/; cos^ Aplikací na jednotkový vektor (1,0) dostáváme skutečně právě očekávaný výsledek (cos^, sin ip). ooo«ooooooooooo oooooooooooooo Rotaci kolem jiného bodu P = O + w, snadno napíšeme formulí s pomocí posunutí: w Rý • (v - w) Rý ■ (v — w) + w cosip(x — x(w)) — s\r\ ip(y — y(w)) + x(w)\ sintp(x — x(w)) + costp(y — y(w)) + y(w)J ' □ s - OOOO0OOOOOOOOOO oooooooooooooo Dalším příkladem je tzv. zrcadlení vzhledem k přímce. Opět nám bude stačit popsat zrcadlení vzhledem k přímkám procházejícím počátkem O a ostatní se z nich odvodí pomocí translací. Hledáme matici Z^ zrcadlení vzhledem k přímce s jednotkovým směrovým vektorem v svírajícím úhel íp s vektorem (1,0). Např. 1 0 0 -1 a obecně můžeme psát (otočíme do nulové polohy, odzrcadlíme a vrátíme zpět) Zý = R-tp ■ Zq ■ R-ý. □ s ooooo«ooooooooo oooooooooooooo Díky asociativitě násobení matic spočteme: cos^ — sint/; sint/; cos^ cos^ — sint/; sint/; cos^ cos2^ — sin2 íp 2 si n íp cos íp cos 2-0 sin 2-0 sin 2-0 —cos2-0 1 0 \ / costp s\r\tp 0 — 1/ \— smíp cost/' cost/' sirľ0 — sint/; cos^ 2 si n íp cos íp (cos2íp — s\n2íp) □ s Povšimněme si také, že 'cos 2-0 sin 2-0 sin 2-0 —cos2-0 To lze zformulovat jako Otočení o úhel íp obdržíme následným provedením dvou zrcadlení vzhledem ke směrům, které spolu svírají úhel ^ip. □ g - = Povšimněme si také, že 'cos 2-0 sin 2-0 sin 2-0 —cos2-0 To lze zformulovat jako Otočení o úhel íp obdržíme následným provedením dvou zrcadlení vzhledem ke směrům, které spolu svírají úhel ^ip. Pokud umíme odůvodnit předchozí tvrzení ryze geometrickou úvahou (zkuste), pak jsme takto dokázali standardní formule pro goniometrické funkce dvojnásobného úhlu. □ s draw unitsquare scaled s; draw unitsquare shifted (1,0) scaled s; kl=fullcircle scaled (s*sqrt(2)) shifted (s/2,s/2); k2=fullcircle scaled (s*sqrt(5)) shifted (s,s/2); draw kl; draw k2; Závěrem úvodního výletu do geometrie se zaměřme na pojem obsah. Trojúhelník je vymezen dvojicí vektorů v a w, které přiloženy do počátku 0 zadají zbylé dva vrcholy. Chtěli bychom tedy najít formuli (skalární funkci vol), která dvěma vektorům přiřadí číslo rovné obsahu vol A(i/, w) takto definovaného trojúhelníku A(i/, w). Ze zadání je vidět, že by mělo platit vol A(v + v', w) = vol A(i/, w) + vol A(i/, w) vol A(ai/, w) = a vol A(i/, w) Závěrem úvodního výletu do geometrie se zaměřme na pojem obsah. Trojúhelník je vymezen dvojicí vektorů v a w, které přiloženy do počátku 0 zadají zbylé dva vrcholy. Chtěli bychom tedy najít formuli (skalární funkci vol), která dvěma vektorům přiřadí číslo rovné obsahu vol A(i/, w) takto definovaného trojúhelníku A(i/, w). Ze zadání je vidět, že by mělo platit vol A(v + v', w) = vol A(i/, w) + vol A(i/, w) vol A(ai/, w) = a vol A(i/, w) a přidejme požadavek vol A(v, w) = — vol A(w, v), který odpovídá představě, že opatříme plochu znaménkem podle toho, v jakém pořadí bereme vektory. ooooooooo«ooooo oooooooooooooo Pokud vektory v a w napíšeme do sloupců matice A, pak A = (v, w) i->- det4 splňuje všechny tři naše požadavky. Kolik takových zobrazení ale může být? □ g - = ooooooooo«ooooo oooooooooooooo Pokud vektory v a w napíšeme do sloupců matice A, pak A = (v, w) i->- det4 splňuje všechny tři naše požadavky. Kolik takových zobrazení ale může být? Každý vektor umíme vyjádřit pomocí dvou souřadných vektorů v = (1,0) a w = (0,1) a evidentně tedy každá možnost pro vol A je jednoznačně určena už vyčíslením na této jediné dvojici argumentů (v, w). Jsou si tedy všechny možnosti rovny až na skalární násobek. Ten umíme určit požadavkem volA((l,0),(l,0)) = Í tj. volíme orientaci a měřítko. □ s ooooooooo«ooooo oooooooooooooo Pokud vektory v a w napíšeme do sloupců matice A, pak A = (v, w) i->- det4 splňuje všechny tři naše požadavky. Kolik takových zobrazení ale může být? Každý vektor umíme vyjádřit pomocí dvou souřadných vektorů v = (1,0) a w = (0,1) a evidentně tedy každá možnost pro vol A je jednoznačně určena už vyčíslením na této jediné dvojici argumentů (v, w). Jsou si tedy všechny možnosti rovny až na skalární násobek. Ten umíme určit požadavkem volA((l,0),(l,0)) = -, tj. volíme orientaci a měřítko. Vidíme tedy, že determinant zadává plochu rovnoběžníka určeného sloupci matice A (a plocha trojúhelníku je tedy poloviční). □ s - = 1 oooooooooo»oooo oooooooooooooo Obsah mnohoúhelníka Mnohoúhelník rozdělíme na trojúhelníky, jejichž obsahy sečteme (tzv. triangulace promyslete si, zeje to vždy - i u nekonvexních možné). Poznámka Úloha o hlídačích v galerii -je možné obarvit vrcholy každé triangulace n-úhelníka 3 barvami tak, že žádné 2 sousední nemají tutéž barvu (indukcí). □ s ooooooooooo«ooo oooooooooooooo Předchozí popis hodnot pro orientovaný objem nám dává do rukou elegantní nástroj pro určování viditelnosti orientovaných úseček. Orientovanou úsečkou rozumíme dva body v rovině R2 s určeným pořadím. Můžeme si ji představovat jako šipku od prvého k druhému bodu. Taková orientovaná úsečka nám rozděluje rovinu na dvě poloroviny, říkejme jim levou a pravou. □ s ooooooooooo«ooo oooooooooooooo Předchozí popis hodnot pro orientovaný objem nám dává do rukou elegantní nástroj pro určování viditelnosti orientovaných úseček. Orientovanou úsečkou rozumíme dva body v rovině R2 s určeným pořadím. Můžeme si ji představovat jako šipku od prvého k druhému bodu. Taková orientovaná úsečka nám rozděluje rovinu na dvě poloroviny, říkejme jim levou a pravou. Jestliže uvažujeme obvyklou orientaci proti směru hodinových ručiček pro hranici mnohoúhelníka, pak pozorovatel stojící vně takového mnohoúhelníka některé jeho hrany vidí a některé nevidí. Pokud je daný mnohoúhelník konvexní, tj. jeho hrany zatáčejí pouze doleva, potom pozorovatel vidí právě ty hrany (orientované úsečky), od nichž je napravo. □ s oooooooooooo«oo oooooooooooooo Je-li AB vektor takové orientované úsečky, potom pro bod C ležící napravo od ní platí, že vektory CA = A — C a CB = B — C, které směřují z bodu C do bodů A a B, jsou vzájemně orientovány v záporném směru, a proto je jejich jejich vol A(Č4, CB) < 0, úsečku AB z bodu C vidíme. Naopak, pro bod C ležící nalevo od AB platí, že vol A(CA, CB) > 0, úsečku AB z bodu C nevidíme. Protože je funkce vol A pouze kladným násobkem funkce det A kde sloupce matice A jsou vektory CA, CB v tomto pořadí, stačí pouze sledovat znaménka příslušných determinantů. Pro konvexní mnohoúhelník nastanou zřejmě právě 2 znaménkové změny v posloupnosti těchto determinantů. □ s oooooooooooo«oo oooooooooooooo Je-li AB vektor takové orientované úsečky, potom pro bod C ležící napravo od ní platí, že vektory CA = A — C a CB = B — C, které směřují z bodu C do bodů A a B, jsou vzájemně orientovány v záporném směru, a proto je jejich jejich vol A(Č4, CB) < 0, úsečku AB z bodu C vidíme. Naopak, pro bod C ležící nalevo od AB platí, že vol A(CA, CB) > 0, úsečku AB z bodu C nevidíme. Protože je funkce vol A pouze kladným násobkem funkce det A kde sloupce matice A jsou vektory CA, CB v tomto pořadí, stačí pouze sledovat znaménka příslušných determinantů. Pro konvexní mnohoúhelník nastanou zřejmě právě 2 znaménkové změny v posloupnosti těchto determinantů. Uvedený jednoduchý postup je často využíván pro testování polohy při standardních úlohách v 2D (a podobně pro příslušnou funkci vol v 3D) grafice. □ s - = 1 ooooooooooooo«o oooooooooooooo Příklad Určete, které hrany jsou vidět z bodu C = [2,0] pro čtyřúhelník daný vrcholy A = [0,0], ß = [2,l], D = [3,3], E = [1,4]. □ S ooooooooooooo«o oooooooooooooo Příklad Určete, které hrany jsou vidět z bodu C = [2,0] pro čtyřúhelník daný vrcholy A = [0,0], ß = [2,l], D = [3,3], E = [1,4]. Body jsou již seřazeny v kladném směru a tvoří konvexní čtyřúhelník. Vypočítáme příslušné determinanty \A-C,B-C\ \D-C,E-C\ -2 0 0 1 1 -1 3 4 -2,\B-C,D-C\ 7,\E- C,A-C\ 0 1 1 3 -1 -2 4 0 Pororovatel v bodě C tedy vidí pouze první dvě hrany: AB a BD. □ g - = oooooooooooooo« oooooooooooooo Příklad Na (nejvýše) kolik částí dělí rovinu n kružnic? Pro maximální počet pn oblastí, na které dělí rovinu kružnice, odvodíme rekurentní vzorec pn+1 = pn + 2n (n + 1). kružnice totiž protíná n předchozích maximálně v 2n průsečících (a tato situace skutečně může nastat). Navíc zřejmě P\ = 2. Pro počet pn tedy dostáváme Pn p„_i + 2(n - 1) = Pn-2 + 2(n - 2) + 2(n - 1) n(n-l) P1 + 2/ /=i 2 + 2 2 + n(n-l). Tedy např. 10 kružnic může rozdělit rovinu na nejvýše pio = 2 + 10.9 = 92 částí. Plán přednášky Q Lineární zobrazení a matice Q Euklidovská rovina • Obsah trojúhelníka • Viditelnost v rovině Q Relace a zobrazení • Relace na množině • Rozklad podle ekvivalence ooooooooooooooo oooooooooooooo □ s ooooooooooooooo •ooooooooooooo V závěrečné části úvodní motivační kapitoly se vrátíme k formálnímu popisu matematických struktur, budeme seje ale průběžně snažit ilustrovat na již známých příkladech. Zároveň můžeme tuto část brát jako cvičení ve formálním přístupu k objektům a konceptům matematiky. □ s ooooooooooooooo •ooooooooooooo V závěrečné části úvodní motivační kapitoly se vrátíme k formálnímu popisu matematických struktur, budeme seje ale průběžně snažit ilustrovat na již známých příkladech. Zároveň můžeme tuto část brát jako cvičení ve formálním přístupu k objektům a konceptům matematiky. Definice Binární relací mezi množinami A a B rozumíme podmnožinu R kartézského součinu A x B. Často píšeme a ~r b pro vyjádření skutečnosti, že (a, b) e R, tj. že body a e A a b e B jsou v relaci R. Definičním oborem relace je podmnožina D c A, D = {aeA;3b B jakožto relace f c A x B, f = {(a, f (a)); a G A} známe také pod názvem graf zobrazení f. □ s U zobrazení je jasná koncepce, jak se skládají. Máme-li zobrazení f: A—>Bag:B—>C, pak jejich složení g" o f je definováno (gof)(a) = g(f(a)). □ S U zobrazení je jasná koncepce, jak se skládají. Máme-li zobrazení f: A—>Bag:B—>C, pak jejich složení g" o f je definováno (gof)(a) = g(f(a)). Ve značení používaném pro relace totéž můžeme zapsat jako fcAxB, f = {(a, f(a)); a e A} gCBxC, g = {(b,g(b));b B) a na ní relací X C Z danou vlastností být podmnožinou. Evidentně jsou splněny všechny tři vlastnosti pro uspořádání: skutečně, je-li X C Y a zároveň Y C X musí být nutně množiny X a Y stejné. Je-li X c Y c Z je také X c Z a také reflexivita je zřejmá. □ s ooooooooooooooo ooooooo»oooooo Dobrým příkladem uspořádání je inkluze. Uvažme množinu 2A všech podmnožin konečné množiny A (značení je speciálním případem obvyklé notace BA pro množinu všech zobrazení A —> B) a na ní relací X C Z danou vlastností být podmnožinou. Evidentně jsou splněny všechny tři vlastnosti pro uspořádání: skutečně, je-li X C Y a zároveň Y C X musí být nutně množiny X a Y stejné. Je-li X c Y c Z je také X c Z a také reflexivita je zřejmá. Říkáme, že uspořádání je úplné, když pro každé dva prvky platí že jsou srovnatelné, tj. buď a < b nebo b < a. Všimněme si, že ne všechny dvojice (X, Y) podmnožin v A jsou srovnatelné v tomto smyslu. Přesněji, pokud je v A více než jeden prvek, existují podmnožiny X a Y, kdy není ani X C V ani Y C X. □ s ooooooooooooooo oooooooo«ooooo Připomeňme rekurentní definici přirozených čísel N = {0,1,2,3,...}, kde 0 n + l = {0,l,2,...,n}. Definujeme relaci m < n právě, když men. Evidentně jde o úplné uspořádání. Např. 2 < 4, protože 2 = {0,{0}} C {0, {0}, {0, {0}}, {0, {0}, {0, {0}}}} = 4. Jinak řečeno, samotná rekurentní definice zadává vztah n < n + 1 a tranzitivně pak n < k pro všechna k, která jsou tímto postupem definována později. □ g - = ooooooooooooooo OOOOOOOOO0OOOO Každá ekvivalence R na množině A zadává zároveň rozklad množiny A na podmnožiny vzájemně ekvivalentních prvků, tzv. třídy ekvivalance. Klademe pro libovolné a G A Ra = {beA;(a,b) e A}. Často budeme psát pro Ra prostě [a], je-li z kontextu zřejmé, o kterou ekvivalenci jde. □ s ooooooooooooooo OOOOOOOOO0OOOO Každá ekvivalence R na množině A zadává zároveň rozklad množiny A na podmnožiny vzájemně ekvivalentních prvků, tzv. třídy ekvivalance. Klademe pro libovolné a G A Ra = {beA;(a,b) e A}. Často budeme psát pro Ra prostě [a], je-li z kontextu zřejmé, o kterou ekvivalenci jde. Zjevně Ra = Rb právě, když (a, b) e R a každá taková podmnožina je tedy reprezentována kterýmkoliv svým prvkem, tzv. reprezentantem. Zároveň Ra n Rb ^ 0 právě, když Ra = Rb, tj. třídy ekvivalence jsou po dvou disjunktní. Konečně, A = Uae/4/?a, tj. celá množina A se suktečně rozloží na jednotlivé třídy. Můžeme také třídám rozkladu rozumět tak, že třídu [a] vnímáme jako prvek a až na ekvivalenci. □ s Na přirozených číslech umíme sice sčítat a víme, že přičtením nuly se číslo nezmění. Umíme i definovat odečítání, při něm ale jen někdy existuje výsledek. Na přirozených číslech umíme sice sčítat a víme, že přičtením nuly se číslo nezmění. Umíme i definovat odečítání, při něm ale jen někdy existuje výsledek. Základní ideou konstrukce celých čísel z přirozených je tedy přidat k nim chybějící rozdíly. To můžeme udělat tak, že místo výsledku odečítání budeme pracovat s uspořádanými dvojicemi čísel, které nám samozřejmě vždy výsledek dobře reprezentují. Zbývá jen dobře definovat, kdy jsou (z hlediska výsledku odečítání) takové dvojice ekvivalentní. Potřebný vztah tedy je: (a, b) ~ (a', tí) ^^ a-b = a'-b' ^^ a + b' = a' + b. Všimněme si, že zatímco výrazy v prostřední rovnosti v přirozených číslech neumíme, výrazy v pravo už ano. Snadno ověříme, že skutečně jde o ekvivalenci a její třídy označíme jako celá čísla Z. □ g - = ^ -00*0 ooooooooooooooo OOOOOOOOOOO0OO Na třídách ekvivalence definujeme operaci sčítání (a s ní i odečítání) pomocí reprezentantů. Např. [(a,b)] + [(c,d)] = [(a + c,b + d)], což zjevně nezávisí na výběru reprezentantů. Lze si přitom vždy volit reprezentanty (a, 0) pro kladná čísla a reprezentanty (0, a) pro čísla záporná, se kterými se nám bude patrně počítat nejlépe. □ s - ooooooooooooooo OOOOOOOOOOO0OO Na třídách ekvivalence definujeme operaci sčítání (a s ní i odečítání) pomocí reprezentantů. Např. [(a,b)] + [(c,d)] = [(a + c,b + d)], což zjevně nezávisí na výběru reprezentantů. Lze si přitom vždy volit reprezentanty (a, 0) pro kladná čísla a reprezentanty (0, a) pro čísla záporná, se kterými se nám bude patrně počítat nejlépe. Tento jednoduchý přklad ukazuje, jak důležité je umět nahlížet na třídy ekvivalence jako na celistvý objekt a soustředit se na vlastnosti těchto objektů, nikoliv formální popisy jejich konstrukcí. Ty jsou však důležité k ověření, že takové objekty vůbec existují. □ s U celých čísel nám už platí všechny vlastnosti skalárů (KG1)-(KG4) a (01)-(04), z popisu vlastností skalám. Pro násobení je neutrálním prvkem jednička, ale pro všechna čísla a různá od nuly a jedničky neumíme najít číslo a-1 s vlastností a • a-1 = 1, tzn. chybí nám inverzní prvky. Zároveň si povšimněte, že platí vlastnost oboru integrity (01), tzn. je-li součin dvou čísel nulový, musí být alespoň jedno z nich nula. □ s U celých čísel nám už platí všechny vlastnosti skalárů (KG1)-(KG4) a (01)-(04), z popisu vlastností skalám. Pro násobení je neutrálním prvkem jednička, ale pro všechna čísla a různá od nuly a jedničky neumíme najít číslo a-1 s vlastností a • a-1 = 1, tzn. chybí nám inverzní prvky. Zároveň si povšimněte, že platí vlastnost oboru integrity (01), tzn. je-li součin dvou čísel nulový, musí být alespoň jedno z nich nula. Díky poslední jmenované vlastnosti můžeme zkonstruovat racionální čísla Q přidáním všech chybějících inverzí zcela obdobným způsobem, jak jsme konstruovali Z z N. □ s ooooooooooooooo OOOOOOOOOOOOO»! Příklad - konstrukce racionálních čísel Na množině uspořádaných dvojic (p, q), q 7^ 0, celých čísel definujeme relaci ~ tak, jak očekáváme, že se mají chovat podíly p/q- (p, q) ~ (p', q') P/q = p'/q' pq = p q- □ s ooooooooooooooo OOOOOOOOOOOOO»! Příklad - konstrukce racionálních čísel Na množině uspořádaných dvojic (p, q), q 7^ 0, celých čísel definujeme relaci ~ tak, jak očekáváme, že se mají chovat podíly p/q- (p, q) ~ (p', q') P/q = p'/q' pq = p q- Opět neumíme očekávané chování v prostřední rovnosti v množině Z formulovat, nicméně rovnost na pravé straně ano. Zjevně jde o dobře definovanou relaci ekvivalence (ověřte podrobnosti!) a racionální čísla jsou pak její třídy ekvivalence. Když budeme formálně psát p/q místo dvojic (p, q), budeme definovat operace násobení a sčítání právě pomocí formulí, které nám jsou jistě dobře známy. Jiným dobrým a jednoduchým příkladem jsou tzv. zbytkové třídy celých čísel. Pro pevně zvolené přirozené číslo k definujeme equivalenci ~^ tak, že dvě čísla a, b G Z jsou ekvivalentní, jestliže jejich zbytek po dělení číslem k je stejný. Výslednou množinu tříd ekvivalence označujeme Z^. Jiným dobrým a jednoduchým příkladem jsou tzv. zbytkové třídy celých čísel. Pro pevně zvolené přirozené číslo k definujeme equivalenci ~^ tak, že dvě čísla a, b G Z jsou ekvivalentní, jestliže jejich zbytek po dělení číslem k je stejný. Výslednou množinu tříd ekvivalence označujeme Z^. Nejjednodušší je tato procedura pro k = 2. To dostáváme Z2 = {0,1}, kde nula reprezentuje sudá čísla, zatímco jednička čísla lichá. Opět lze snadno zjistit, že pomocí reprezentantů můžeme definovat násobení a sčítání. Zkuste si ověřit, že výsledná množina skalárů je komutativním tělesem (tj. splňuje i vlastnost (P) pole) právě když je k prvočíslo.