MASARYKOVA UNIVERZITA FAKULTA INFORMATIKY Relace, uspořádání a ekvivalence - sbírka řešených příkladů BAKALÁŘSKÁ PRÁCE Lukáš Charvát Brno 2009 Vedoucí bakalářské práce: Mgr. Jaroslav Hrdina, Ph.D. Prohlášení Prohlašuji, že tato práce je mým původním autorským dílem, které jsem vypracoval samostatně. Všechny zdroje, prameny a literaturu, které jsem při vypracování používal nebo z nich čerpal, v práci řádně cituji s uvedením úplného odkazu na příslušný zdroj. V Brně dne 21. května 2009 Lukáš Charvát Poděkování Děkuji panu Mgr. Jaroslavovi Hrdinovi, Ph.D. za podnětné připomínky k mojí bakalářské práci, v neposlední řadě pak za velkou trpělivost při psaní a úpravách jejího textu. Shrnutí Cílem mojí bakalářské práce bylo vytvořit studijní materiál pro studenty s vadami sluchu. Text je psán stručně tak, aby byl studentovi se sluchovým postiženým dobře srozumitelný. Celá práce je členěna do osmi přibližně stejně dlouhých kapitol. Práce poukazuje na obtížnost pochopení matematických souvislostí pro studenty se specifickými vzdělávacími potřebami. Klíčová slova: relace, uspořádaná dvojice, množina, grafické znázornění, binární relace, vlastnosti binárních relací, relace ekvivalence, rozklad množiny, třída, reprezentant třídy, relace uspořádaní, zobrazení množin, zbytkové třídy, celá čísla, racionální čísla, kartézský součin, kartézský graf, relace reflexivní, relace an-tirefiexivní, relace symetrická, relace antisymetrická, relace tranzitivní, ekvivalentní prvky, definiční funkce a obor hodnot, surjekce, injekce, bijekce Abstract The aim of my work is to creat an study material for people with an deficiency. The text is written simply so it is comprehensible for all students with an deficiency. My work is devided into nine chapters which are about the same length. The work shows how difficult it is for students with specific educational needs to understand mathematical conectivity. Obsah Úvod 8 1 Kartézský součin 12 1.1 Uspořádaná dvojice........................ 12 1.2 Kartézský součin dvou množin.................. 13 1.3 Grafické znázornění kartézského součinu ............ 16 2 Binární relace 19 2.1 Grafické znázornění typů relací ................. 25 2.2 Vlastnosti binárních relací v množině.............. 27 3 Relace ekvivalence 31 3.1 Ekvivalentní prvky........................ 31 3.2 Rozklad množin.......................... 31 3.3 Vlastnosti rozkladu........................ 32 3.4 Reprezentant třídy........................ 33 4 Relace uspořádaní 37 4.1 Hasseovský diagram - názorné zobrazení uspořádání...... 42 5 Relace zobrazení - zobrazení množin 45 5.1 zobrazení, definiční obor a obor funkce, zobrazení prosté ... 45 5.2 Injekce, surjekce a bijekce .................... 46 6 Zbytkové třídy 50 7 Konstrukce množiny celých čísel 58 8 Konstrukce množiny racionálních čísel 62 Závěr 64 6 Literatura 68 Úvod Technika proniká téměř do všech oblastí života. Osud neslyšících, nedoslýchavých a ohluchlých je stále pod vlivem jejího rozvoje. Kvalitu života nedoslýchavých změnila dramatickým způsobem moderní slúchadla. Zázračnou léčbu pro velikou většinu ohluchlých představují kochleární implantáty. Pro všechny bez rozdílu pak znamenají obrovský přínos moderní technologie elektronického přenosu dat v podobě skrytých titulků v televizi, elektronické pošty nebo v podobě snadného přístupu k záplavě psaných informací na internetu. Počítač nebo notebook je všeobecně považován za univerzální kompenzační pomůcku. Pro těžce tělesně postižené je důležité, že počítače lze ovládat nejrůznějšími způsoby - od upravených speciálních klávesnic, až po zadávání příkazů pomocí pohybů hlavy nebo oka nebo dokonce hlasem. Počítač tak může i pro zcela nepohyblivé osoby plnit řadu funkcí. Pro slabozraké dokáže psaný text na obrazovce libovolně zvětšovat a měnit barvy inkoustu a pozadí, jas i kontrast tak, aby bylo písmo čitelné i zbytky zraku. Zcela nevidomí mohou informaci z počítače získávat pomocí braill-ských řádků, popř. hlasových syntéz, které vytváří souvislou řeč. Nedoslýchavým a neslyšícím stačí použít běžný počítač, nepotřebují nutně speciální zařízení. Přesto i jim přináší počítač služby navíc. Mohou sledovat texty ve znakovém jazyce uložené na webu jako videozáznamy. Stále více a více institucí, nejen organizace sluchově postižených, nabízí informace ve znakových jazycících. Přibývá i slovníků znakového jazyka. A neslyšící mohou také sami ve znakovém jazyce posílat zprávy nebo chatovat pomocí webové kamery a video chatu. Zvyšují se nároky na kvalifikaci, a to všechno klade velký důraz na vzdělání. A stranou nezůstávají ani sluchově postižení lidé. Myslím si, že informační technologie mají těmto lidem pomoci. Ve svém studiu se zaměřuji na 8 aplikovanou informatiku, což je obor s vysokou mírou abstraktnosti. A to dělá některým sluchově handicapovaným potíže. Speciálně u sluchově postižených studentů je jeden velký handicap a to je konkrétní myšlení, protože rozvoj abstraktního myšlení souvisí s řečí. Neslyšící potřebují vizuální vjem, různé grafy a ilustrativní příklady. Cílem mé bakalářské práce je podat znalosti o množinách a operacích s nimi. Celkové zpracování je mým pokusem o vytvoření studijní opory pro vzdělání neslyšících a nevidomých studentů. Primárně pro neslyšící, kde je problémem jazyková kariéra. Jednoduchost textu je ale dobře využitelná pro tvorbu studijních materiálů i pro nevidomí. Snažím se o maximální jednoduchost, stručnost a přehlednost při vysvětlování matematických pojmů. Zadání neřešené příklady jsem použil některé učebnice ze seznamu literatury. Text je rozdělen do 9 kapitol a každá kapitola se skládá z teoretické a praktické části. V teoretické části jsem shrnul poznatky, které jsem získal studiem uvedené literatury. V části praktické se věnuji vlastnímu řešení příkladu s doplňujícím komentářem. 9 Úvod - motivace Zadat určitou relaci znamená předem uvést množinu, mezi jejímiž prvky platí příslušný vztah. Například relace je bratrem je úplně definována teprve tehdy, jestliže předem přesně určíme množinu lidí, mezi nimiž vztah je bratrem uvažujeme. Můžeme pak sestavit soupis všech takových uspořádaných dvojic lidí z této množiny, že první člověk v každé z těchto uspořádaných dvojic je bratrem druhého člověka z téže dvojice. [1], Relace, s. 27 Všimněme si několika jednoduchých příkladů ze školské matematiky : • být rovnoběžný v množině přímek dané roviny • být menší v množině všech přirozených čísel • žák x chodí do stejné třídy jako žák y v množině všech žáků určité školy Podobným způsobem hledá taneční mistr odpověď na otázku, zda má v sále stejný počet tanečnic i tanečníků: poručí pánům, aby vyzvali dámy k tanci, čímž se vytvoří dvojice, které se dokonce samy vytvářejí jdouce na taneční parket. Nejinak se počíná i hostinský při roznášení piva. Aby nemusel nosit v hlavě, kolik piv jednotlivým hostům dal, nepřináší hostům jen piva, ale uspořádané dvojice, jejichž prvními složkami jsou žádaná piva a druhými složkami čárky na hostův tácek. A potom: počet čárek = počet vypitých piv. [8], Konečné a nekonečné množiny, s. 50 Co je to relace, lze tedy nejsnáze objasnit na příkladech: Příklad 0.1. Domácnost rodiny Novákových se skládá ze šesti členů; v závorce je uveden věk příslušného člena domácnosti: otec (41) roků, matka (37) roků, babička (65) roků, teta (39) roků, strýc (40) roků, Jirka (15) roků. Zapište všechny prvky relace U, jež je v množině všech členů této domácnosti určena výrokovou formou x je starší než y. Řešení. Chceme-li najít všechny možnosti relace U, která je v množině všech členů této domácnosti určena výrokovou formou x je starší než y, zavedeme si označení: 10 otec ............................................ o matka ............................................ m babička ............................................ b teta ............................................ t strýc ............................................ s Jirka ............................................ J Podle označení i podle věku seřadíme všechny členy domácnosti na přímce viz obr. 1 J m t s o b (15) (37) (39) (40) (41) (65) Obrázek 1: Cleny domácnosti podle věků Nalezneme a zapíšeme všechny prvky, které jsou v množině všech členů této domácnosti určeny výrokovou formou x je starší než y. Už snadno dostaneme: U = {(b,o),(b,s),(b,t),(b,m),(b,J),(o,s),(o,t),(o,m),(o,J), (s, t), (s, m), (s, J), (ŕ, m), (ŕ, J), (m, J)} Komentář. Uspořádaná dvojice je často používána a je potřeba rozumět, jak usopřádána dvojice funguje. V matematice se často setkáváme s množinami, jejichž prvky jsou uspořádané dvojice. Z předchozí množiny {Věra, Jan, Michal} víme, že nemůžeme zaměnit pořadí. V uspořádané dvojici záleží na tom, v jakém pořadí prvky uvedeme. 11 Kapitola 1 Kartézský součin 1.1 Uspořádaná dvojice S uspořádanými dvojicemi se budeme dále velmi často setkávat. Pojem „uspořádaná dvojice" vysvětlí následující definice. Definice 1.1. Uspořádanou dvojicí prvků nazýváme množinu (a,b) definovanou vztahem (a,b) = {{a}, {a,b}}. Prvek a se nazývá první složka a prvek b se nazývá druhá složka uspořádané dvojice. Množina {a,b} udává složky uspořádané dvojice (a,6), množina {a} pak určuje, kterou z těchto složek je nutno chápat jako první [7]. Komentář. Důležité je rozlišovat tyto zápisy: {x,y} a (x,y). První zápis {x,y} znamená množinu, kterou tvoří prvky x, y. Druhý zápis (x,y) uvádí uspořádanou dvojici, kde první složka je x a druhá složka je y. Příklad 1.1. Podívejme se na obrázek 1.1a vypišme postupně všechny uspořádané dvojice (x,y), pro něž platí tyto tři podmínky: 1. X je některý z bodů množiny H = {Ai, A2, A3} 2. y je některá z přímek množiny K = {pi,P2,P3,P4} 3. Xey Komentář. Pro správné řešení příkladu je důležité splnit všechny tři dané podmínky. 1. X G H; H = {A1,A2,A3} 12 Obrázek 1.1: Přímky a body 2. y G K- K = {pi,P2,P:í,P4} 3. Xey Rešení. Množina H je tříprvková. Tvoří ji jednotlivé body Ai, A2, A$. Množina K je čtyřprvková. Tvoří ji jednotlivé přímky pi,p2,P3, P4- Ze zadání příkladu je jasné, že budeme tvořit uspořádané dvojice ve tvaru (X,y). Řešením příkladu budou uspořádané dvojice, kde X bude některý bod množiny H a y bude některá přímka a množiny K. Snadno dojdeme k množině U = {(^4i,pi), (Ai,ps), (^3,^2)}, která je řešením příkladu. Každá uspořádaná dvojice z množiny U vznikne průsečíkem bodu z množiny H s přímkou z množiny K. Bod A2 netvoří žádnou uspořádanou dvojici, protože nesplňuje druhou a třetí podmínku. Stejně tak přímka p4 není prvkem žádné uspořádané dvojice, protože neprotíná žádný bod množiny H - jinými slovy není splněna první podmínka X. Obrazem prvku X množiny H je bod (A±, A2, A3). Obrazem prvku y množiny K je přímka (pi,P2,P3,P4)- Obrazem uspořádané dvojice je průsečík první a druhé složky uspořádané dvojice - tím je splněna třetí podmínka X E y. Pomocí pojmu uspořádané dvojice zavedeme kartézský součin dvou množin. 1.2 Kartézský součin dvou množin Název „kartézský" (kartézský součin, kartézský graf, kartézská - pravoúhlá soustava souřaánic, kterou určují ávé osy navzájem kolmé) je oávozen oá jména René Descartes (1596 - 1650), latinsky Cartesius. Francouzský matematik, filosof a příroáovéáec. Jeho známý výrok „Cogito, ergo sum" 13 (Myslím, tedy jsem) je výchozí premisou pro nový filosofický systém založený na racionalismu, na aktivní činnosti rozumu, rozvíjí metodu dedukce. Je jedním z nejvýznamnějších matematiků novověku - zavedl pojem funkce a proměnné veličiny, je považován rovněž za jednoho ze zakladatelů analytické geometrie („Rozprava o metodě" z v.1631) [9], Kartézský součin dvou množin, s. 22 Definice 1.2. Kartézským součinem (libovolných) množin A, B nazýváme množinu všech uspořádaných dvojic (x,y), kde x E A, y E B. Kartézský součin množin A, B označujeme A x B. Je tedy A x B = {(x,y) | x E A A y E B} • Je-li aspoň jedna z množin A, B prázdná, je také jejich kartézský součin A x B prázdná množina, nebot není z čeho tvořit uspořádané dvojice. • Může také nastat případ, že A = B a pak hovoříme o kartézské mocnině A x A = A2. • Má-li množina A počet prvků a, množina B počet prvků 6, pak kartézský součin má a ■ b prvků. • Definici kartézského součinu dvou množin je možno rozšířit na kartézský součin libovolného počtu množin, jehož výsledkem je množina n-tic, takto: Xi x X2 x • • • x Xn = {(xi, x2,..., xn) : xl E Xt, 1 < i < n} Vlastnosti kartézského součinu Pro kartézský součin platí vlastnosti: a) komutativnost — kartézský součin není komutativní A x B ^ B x A b) asociativnost — kartézský součin je asociativní. Pro libovolné množiny A, 5, C (utvořené ze základní množiny Z) platí: A x (B x C) = (A x B) x C 14 c) distributivnost — distributivnost kartézského součinu vzhledem ke sjednocení a průniku. Pro libovolné množiny A, £>, C (utvořené ze základní množiny Z) platí: (A U B) x C = (A x C) U (B x C), tj. sjednocení množin (A D B) x C = (A x C) D (B x C), tj. průnik množin Příklad 1.2. Jsou dány množiny S = {1,2,3, 5}, T = {-3,0,7}. Určete S x T, T x S, S x S, T x T. Komentář. Vyjdeme z definice kartézského součinu. Víme, že je to množina uspořádaných dvojic, kde první složka patří do množiny A a druhá složka patří do množiny B. Řešení. Víme, že množina S má 4 prvky a množina T má 3 prvky. Výsledkem je 12 uspořádaných dvojic. Je důležité vědět, že kartézský součin TxS není stejný jako součin SxT. Prvky množiny S budou v tomto případě prvními složkami a prvky množiny T druhými složkami uspořádaných dvojic uvedeného kartézského součinu. TxS = {(-3,1), (-3, 2), (-3, 3), (-3, 5), (0,1), (0,2), (0,3), (0,5), (7,1), (7, 2), (7, 3), (7, 5)}. Z tohoto příkladu plyne, žeSxT^TxSto znamená, že kartézský součin není obecně komutativní. S x S - tj. S2. Víme, že podle definice A = B hovoříme o kartézské mocnině A x A = A2. V tomto případě 16 uspořádaných dvojic, protože množina S má právě 4 prvky. T x T řešení je podobné jako u předcházejícího příkladu S x S. Ale počet uspořádaných dvojic bude 9. SxT {(1,-3), (1,0), (1,7), (2,-3), (2,0), (2, 7) (3, -3), (3, 0), (3, 7), (5, -3), (5, 0), (5, 7)} SxS {(1,1), (1,2), (1,3), (1,5), (2,1), (2, 2), (2, 3), (2, 5), (3,1), (3, 2), (3, 3), (3, 5), (5,1), (5, 2), (5, 3), (5, 5)}. T x T {(-3, -3), (-3, 0), (-3, 7), (0, -3), (0, 0) (0, 7), (7,-3), (7,0), (7, 7)}. 15 Příklad 1.3. Je dána množina L = {(1,0),(0,1),(2,1),(0,0),(2,2),(0,2),(2,0)}. Rozhodněte, zda existují takové množiny M, O, pro něž platí L = M x O. Řešení. M = {0,1,2}, O = {0,1,2} Předpokládáme, že existují množiny M, O takové, že platí L = M x O. Určíme výčtem množinu M, tj. první složku uspořádané dvojici a množinu O, tj. druhou složku uspořádané dvojici. Uspořádané dvojice množiny L musí být takové, aby platil kartézský součin M x O. Zkoumáme-li tímto způsobem všechny prvky množiny Z, dojdeme k závěru, že chybí uspořádaná dvojice (1,1)- MxO = {(0,0), (0,1), (0,2), (1,0), (1,1), (1,2), (2,0), (2,1), (2, 2)}. Z definice kartézského součinu vyplývá, že každá uspořádaná dvojice (x,y), pro kterou platí, že x G M a zároveň y G O, patří do množiny L. Dvojice (1,1) G M x O a přitom (1,1) £ L, tedy L^M x O. 1.3 Grafické znázornění kartézského součinu Ke grafickému znázornění kartézského součinu slouží 3 postupy [7]. 1. Při znázornění kartézského grafu kartézského součinu A X B: • Zvolíme si dvě kolmé přímky, zpravidla vodorovnou a svislou. • Na vodorovné přímce znázorníme jednotlivé prvky množiny A jako body, na svislé přímce znázorníme jednotlivé prvky množiny 5, opět jako body. • Poté každým vyznačeným bodem vedeme kolmici k přímce, na níž leží, a vyznačíme průsečíky všech takto sestrojených kolmic. • Tyto průsečíky jsou obrazy prvků kartézského součinu AxB, tedy znázornění uspořádaných dvojic (x,y) G A X B. 2. Při znázornění šachovnicového grafu kartézského součinu A X B: • Zvolíme si dva kolmé přímky, např. vodorovné a svislé, a jednotkové úsečky. • Daným prvkům množiny A přiřadíme jednotkové úsečky na vodorovné přímce a jednotlivým prvkům množiny B přiřadíme jednotkové úsečky na svislé přímce. • Každým vyznačeným bodem vedeme kolmici na přímku, na níž leží. Dostaneme čtvercovou sít. 16 • Každý čtvereček v rovině je obrazem prvku kartézského součinu A x B, tedy je obrazem uspořádané dvojice (x,y) G A x B. 3. Uzlový graf kartézského součinu A x B: • Výčtem prvků určíme množinu A U B a každý její prvek znázorníme v rovině jako kroužek, kterému říkáme uzel. • Jednotlivé uspořádané dvojice (x, y) 6 A x B znázorníme následujícím způsobem: vyznačíme kolem uzlu smyčku za předpokladu, že první složka uspořádané dvojice se rovná její druhé složce, případně úsečku se šipkou směřující od uzlu x k uzlu y, pokud složky uspořádaných dvojic jsou různé. • Obloučky, respektive úsečky se šipkami nazýváme orientované hrany. Následující tabulka shrnuje obrazy prvků množiny A, B a A x B v jednotlivých grafech. název grafu obraz prvku množin A, B obraz prvku množiny A x B kartézský bod roviny na příslušné přímce bod roviny v rovině šachovnicový jednotková úsečka na příslušné přímce čtvereček v rovině uzlový kroužek, uzel oblouk se šipkou, orientovaná hrana Je důležité naučit se graficky znázorňovat kartézský součin. Jedná se o postup založený na vyhledávání bodů. Názorný graf a jednoduché vysvětlení častěji pomůže k pochopení. Budeme potřebovat při sestrojování kartézských grafů relací. Znázornění grafů pochopíme z jednoduchých příkladů. Příklad 1.4. Znázorněte kartézským a šachovnicovým grafem kartézský součin A x B, je-li: A = {a,b,c}, B = {o,p}. Řešení. Podle uvedeného postupu kartézského grafu sestrojíme kolmice x, y. Na přímce x vyznačíme prvky množiny A = {a,b,c}. Na přímce y vyznačíme prvky množiny B = {o,p}. Obrazem uspořádané dvojice je průsečík kolmic vedených obrazem první a druhé složky uspořádané dvojice. Nalezneme všechny uspořádané dvojice kartézského součinu A x B. Podobně sestrojíme šachovnicový graf Ax B. Obrazem prvků množiny A je úsečka na ose x s body a, 6, c. Obrazem prvků množiny B je úsečka na ose y s body o, p. Obrazem uspořádané dvojice je pole = čtvereček v rovině. AxB = {(a,o),(a,p),(b,o),(b,p),(c,o),(c,p)} 17 Obrázek 1.2: Kartézský graf A x B Obrázek 1.3: Šachovnicový graf A x B Příklad 1.5. Znázorněte uzlovým grafem kartézský součin Ax B, je-li A = {1,2}, B = {a,b}. Komentář. Vrátíme se k uvedenému postupu uzlového grafu kartézského součinu Ax B. Podmínkou pro sestrojení uzlového grafu je vytvoření sjednocení množin A x B. Každý prvek A U B znázorníme v rovině - představuje uzel grafu. Znázorníme uspořádané dvojice (x, y) 6 A x B tak, že vedeme úsečku se šipkou. Šipka vždy směřuje od uzlu x k uzlu y. Úsečky se šipkami jsou orientované hrany. Kolem uzlu nevyznačíme žádnou smyčku, protože první složka uspořádané dvojice se nerovná druhé složce. Obrazem prvků množiny A(B) je bod v rovině, tj. uzel. Obrazem uspořádané dvojice je šipka, tj. orientovaná hrana. (Oblouk se šipkou to znamená, že smyčka je obrazem uspořááané ávojice jen, káyž se první složka rovná áruhé složce uspořááané ávojice). Řešení. AU B = {1,2,a,b} AxB = {(1, a), (1,6), (2, a), (2, 6)} Uzlový graf AxB 18 Kapitola 2 Binární relace V kapitole je formulováno několik definic, které se pokusím svým řešením vysvětlit a přiblížit k chápání sluchově postižených. V předcházející kapitole jsme se seznámili s kartézským součinem dvou libovolných množin a také s kartézskou druhou mocninu. Nyní naším úkolem bude vymezení pojmu binární relace a pak vymezení dalších, které se k binárním relacím přímo vztahují. Definice 2.1. Binární relací z množiny A do množiny B se nazývá každá podmnožina kartézského součinu A x B. V případě, že A = B, budeme místo o „binární relaci z A do £>" mluvit o „binární relaci v množině A11. Binární relace může být dána výčtem všech svých prvků nebo je definována jako obor pravdivosti jisté výrokové formy V(x, y) o dvou proměnných v množině A x B (např. V = {(x, y) G IR x IR; y = x + 2} je definována jako obor pravdivosti výrokové formy y = x + 2 v množině IR X IR). Ve druhém případě budeme častěji říkat, že binární relace z A do B je dána (určena) výrokovou formou V(x,y). Je-li dána neprázdná množina MZ, pak každá podmnožina kartézského součinu M x M se nazývá binární relace v množině M. Píšeme: uspořádaná dvojice (x, y) G R nebo xRy. Všechny dvojice (x, y) G M x M, které nepatří do relace R, tvoří relaci, značíme ji R a nazýváme „doplňkovou" relací k relaci R. Necht R je relace, pak inverzní relaci fž_1 k relaci R dostaneme tak, že zaměníme pořadí složek ve všech uspořádaných dvojicích tvořících relaci R. Komentář. Definice nám vysvětluje pojem binární relace. Zavedeme si dvě libovolné množiny A, B. Můžeme určit, zda je množina A x B binární relací mezi A a B. Podle definice víme, že každou podmnožinou kartézského součinu A x B nazveme „binární relací mezi množinou A a množinu £>". Potom 19 množina A x B je binární relací mezi A a B. Relace mezi A a B je podmnožinou kartézského součinu A x B. Relace mezi B a A je podmnožinou kartézského součinu B x A. Pořadí, v jakém jsou napsána v příslušném názvu písmena A, B, je velice důležité. Nelze je zaměňovat!. Příklad 2.1. Jsou dány množiny C = {1, 7,17, 2, 8},-D = {l,m,n,o,p}. Uveďte aspoň po dvou příkladech relací: a) mezi C a D b) mezi D a C c) v C d) v D Řešení. Vyjdeme z definice binární relace. Popíšeme kartézský součin a příslušné relace jsou pak libovolné dvě jeho podmnožiny. ad a) Budeme řešit C x D. C x D = {(1, l), (1, m), (1, n), (1, o),..., (8, o), (8, p)} ad b) Vidíme, že je mezi dvěma relacemi opačně, je možné označit jako (C, D)~ DxC = {(l, l), (l, 7), (l, 17), (1,2),..., (p, 2), (p, 8)} ad c) Budeme místo relace mezi C a D řešit relace v C. Tj. kartézská mocnina C x C => C2 C x C = {(1,1), (1, 7), (1,17), (1,2),..., (8, 2), (8, 8)} ad d) relace v D D x D = {(1,1), (l,m), (l,n), (l, o),..., (p, o), (p,p)} Příklad 2.2. Jsou dány množiny C = {1,4,12}, D = {1, 7, 8}. Rozhodněte, zda množina U = {(1,1), (1, 4), (7,1)} je a) relace mezi C a D b) relace mezi D a C Týž úkol řešte pro množinu V = {(12, 7), (4,1), (1,1)}. 20 Řešení, ad a) Musíme řešit C x D. C x D = {(1,1), (1, 7), (1, 8), (4,1), (4, 7), (4, 8), (12,1), (12, 7), (12, 8)} Z řešení je jasné, že množina U není relace mezi CaD, protože uspořádané dvojice (1,4), (7,l) fiC x D. ad b) D x C = {(1,1), (1, 4), (1,12), (7,1), (7, 4), (7,12), (8,1), (8,4), (8,12)} Množina U je relací mezi D a C, protože množina U C D x C. Podobně budeme řešit pro množinu V = {(12, 7), (4, 1), (1,1)}. Relace mezi C a D Množina F je relací mezi C a D, protože množina V G C x D. Relace mezi D a C Množina V není relací mezi D a C, protože uspořádané dvojice (12, 7), (4,1) ^ Příklad 2.3. Necht je dána množina A = {x,y,z} a v ní je dána relace výčtem všech uspořádaných dvojic R = {(x,y), (x,x), (y,x), (z, z)}. Určete výčtem prvků relaci doplňkovou R a relaci inverzní R-1. Řešení. Důležité je určit A x A. A X A = {(x, x), (x, y), (x, z), (y, x), (y, y), (y, z), (z, x), (z, y), (z, z)} Z definice víme, že všechny uspořádané dvojice, které nepatří do iž, tvoří relaci doplňkovou R . U inverzní relace existuje plynulý přechod. Když vyjdeme z definice, pak inverzní relaci k relaci R dostaneme tak, že zaměníme pořadí ve všech uspořádaných dvojicích, které tvoří relaci R. Potom Příklad 2.4. Rozhodněte, zda uspořádané dvojice (2,4), (6,2), (8,3) patří relaci: DxC. R' = {(x, z), (y, y), (y, z), (z, x), (z, y)}. R-1 {{y,x), {x,x), {x,y), {z, z)} a) Ri {{x, y) G C x C, x - 2y - 2 < 0} b) R2 {{x, y) G C x C, x < y}. 21 Komentář. Relace může být dána buď výčtem prvků (tj. jsou vypsány všechny její prvky), nebo jako obor pravdivosti výrokové formy. Relace je dána výrokovou formou x — 2y — 2 < 0. Úkolem je vypsat všechny uspořádané dvojice (x,y) E C x C, pro které je x — 2y — 2 < 0 pravdivý výrok. Můžeme postupovat takto: Dosadíme do výrokové formy x — 2y — 2 < 0 za a; nejprve čísla 2 a za y čísla 4. Dostaneme rovnici 2-2-4-2 < 0 -8 < 0 Tento výrok je pravdivý. Uspořádaná dvojice (2,4) je tedy prvkem oboru pravdivosti výrokové formy x — 2y — 2 < 0. Patří tedy relaci R. (2,4) E Ri Tento postup opakujeme pro všechny další prvky uspořádaných dvojic. Připomeňme si, že pro obory pravdivosti výrokové formy V(x, y) platí, že právě když po dosazení prvků do V(x,y). Všude Zci x ci Zci y dostaneme pravdivý výrok. Podle definice je-li relace T definována jako obor pravdivosti výrokové formy V(x,y) v množině A x B píšeme T = {(x,y) E A x A;V(x,y)} Řešení, ad a) x-2y-2 < 0 6-2-2-2 < 0 6-4-2 < 0 0 < 0 To je pravdivý výrok, proto (6, 2) E R\ x-2y-2 < 0 8-2-3-2 < 0 8-6-2 < 0 0 < 0 To je pravdivý výrok, proto (8, 3) E R±. Došli jsme k závěru, že uspořádaná dvojice (2,4), (6,2), (8,3) patří relaci Rľ. 22 ad b) Relace je opět určena výrokovou formou. Podobně úkolem je vypsat všechny uspořádané dvojice (x, y) 6 C x C, pro které je x < y pravdivý výrok. 2 < 4^(2,4)eiž2 6 < 2 => (6, 2) £ Ri 8 < 3 => (8, 3) £ iž2 Došli jsme k závěru, že jen uspořádané dvojice (2,4) patří relaci f?2-Příklad 2.5. Necht M = {a, b}. Vypište: a) všechny relace na množině M b) všechny relace na M, které nejsou tranzitivní c) všechny relace na M, které nejsou antisymetrické (pojmy "tranzitivní", "antisymetrická" viz na str. 27) Řešení. a) relace na M (tj. každá podmnožina kartézského součinu M x M) M x M = {(a, a), (a, 6), (6, a), (6, 6)} b r 1 h. 4 F k a — f r f t s 1 3 možností: 24 = 16 Na množině M je celkem 16 relací. Relace nuloprvkové Ri = 0 23 Relace jednoprvkové R2 = {{a,a)} R3 = {(a,b)} R4 = {{b,a)} R5 = {(6,6)} Relace dvouprvkové: (2) = 6 možnosti R$ — {(«, a),(a,b)} R7 = {(«, a), (Ml R$ = {(«, a),(b,b)} Rg = {(«, b),(b,a)} R10 = {(«, 6), (6, 6)} Rn = a),(b,b)} Relace tříprvkové: (g) = (^) = 4 možnosti R12 = {{a,a),{a,b),{b,a)} R13 = {(a,a),(a,b),(b,b)} Ru = {(a, a), (6, a), (6, 6)} R15 = {(a, 6), (6, a), (6, 6)} Relace čtyřprvková: (4) = 1 možnost R16 = M x M b) všechny relace na M, které nejsou tranzitivní i?i = {(a, 6), (6, a)} R2 = {(a,b),(b,a),(a,a)} R3 = {(a, 6), (6, a), (6, 6)} c) všechny relace na M, které nejsou antisymetrické Podle definice je relace R je antisymetrická, pokud platí Vx, y £ ^4 : (x, y) £ R A (y, x) £ R => [x = y) a to neplatí pro R-i = {(a, 6), (6, a)} R2 = {(a,b),(b,a),(a,a)} R3 = {(a, 6), (6, a), (6, 6)} R4 = MxM 24 2.1 Grafické znázornění typů relací Komentář. Z předchozí kapitoly víme, že binární relace souvisí s kartézským součinem. Také grafické znázornění relace bude vycházet z kartézského součinu. Kartézský součin jsme znázorňovaly třemi způsoby: kartézským, šachovnicovým a uzlovým grafem. Relace v množině i relace z množiny do množiny budeme znázorňovat opět grafy: a) kartézským b) uzlovým Relaci znázorníme kartézským grafem tak, že do kartézského grafu kartézského součinu vyznačíme jen ty body, které patří do relace. Příklad 2.6. Na množině M = {1, 2, 3,4, 5} jsou definovány relace výrokovými formami: a) x < y b) x je dělitelem y. Určete výčtem prvků tyto relace. Znázorněte relace kartézským i uzlovým grafem. Určete definiční obory a pole binární relace. Komentář. Budeme se nyní zabývat problémem grafického znázornění binární relace. Významným elementem je v této věci graf kartézského součinu. Je třeba rozumět postupu. Vzhledem k tomu, že každá relace mezi A a B je podmnožinou kartézského součinu A x B - to již víme z definice, bude postup při sestrojování grafu shodný s konstrukcí grafu kartézského součinu. Řešení, ad a) určíme výčtem prvků R = {(x, y) E M x M, x < y}. M x M = {(1,1), (1,2), (1,3), (1,4), (1,5), (2,1), (2,2), (2,3), (2,4), (2,5), (3,1), (3, 2), (3, 3), (3, 4), (3, 5), (4,1), (4, 2), (4, 3), (4,4), (4, 5), (5,1), (5, 2), (5, 3), (5, 4), (5, 5)} Dále najdeme uspořádané dvojice pro které platí x < y R = {(1, 2), (1, 3), (1,4), (1, 5), (2, 3), (2,4), (2, 5), (3,4), (3, 5), (4, 5)} Určíme definiční obory hodnot relace R 25 LR = (1,2, 3,4), PR = (2,3,4,5) Pole binární relace tvoří množina M, která je pětiprvková. Sestrojíme kartézský graf relace R. Důležité je vědět, že vyznačíme jen uspořádané dvojice, které patří relaci R. 1 2 3 4 5 ad b) Podobně budeme řešit R = {(x, y) G M x M, x\y} Už jsme řešili M x M. Potom hledáme relaci R, pro kterou platí x\y, tj. y je dělitelné x. R = {(1,1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 2), (2,4), (3, 3), (4,4), (5, 5)} Určíme definiční obor hodnot relace R LR = (1,2, 3,4,5), PR = (1,2,3,4,5) Pole binární relace tvoří množina M, která je pětiprvková. Sestrojíme kartézský graf relace R. Důležité je vědět, že vyznačíme jen uspořádané dvojice, které patří relaci R. 1 2 3 4 5 Příklad 2.7. Sestrojte grafy relací: U, = {(0, -1), (2, 3), (i 5), (6, 0), (-2, -3), (-4, 0)} U2 = {(0, 0), (0,1), (0, 2), (3, 0), (1,4), (5, 6)}. 26 Komentář. Binární relaci graficky znázorňujeme dvěma způsoby a to kartézským a uzlovým grafem. Je případ od případu různý. Každý způsob znázornění má své přednosti. V případě relace JJ\ je vhodnější kartézský graf. V případě relace U2 sestrojíme uzlový graf. Řešení. Vytvoříme kartézský graf U\ a uzlový graf U2 * -3 2.2 Vlastnosti binárních relací v množině V případě, že R C A x A, říkáme, že R je relací na množině A. Definice 2.2. • necht A je množina. Binární relace R na A je libovolná podmnožina kartézského součinu A X A • necht i? je binární relace na A, pak 1. relace Z? je reflexivní, pokud platí (xRx), to znamená, že je prvek x v relaci sám se sebou: V.t G A : (x, x) G R O X 2. relace R je symetrická, pokud platí když: V.t, y G A : (x, y) G R. (y, x) e R 27 3. relace R je antisymetrická, pokud platí když: Vx, y G A : (x, y) G R A (y, x) G fž => (x = y) x«, x x x x „y 4. relace fž je tranzitivní, pokud platí když: Vx,y,z E A: (x, y) G R A (y, z) G i? => (x, z) E R Komentář. Na příkladech si ujasníme pojmy. Následující příklady ukazují jak rozpoznávat vlastnosti relací. Pří hledání jednotlivých relací, které mají danou vlastnost, si musíme uvědomit, jak je tato vlastnost definována. Důležitá je definice a její symbolické zápisy. Příklad 2.8. Je dána množina M = {p, q, r, s, t}. Určete vlastnosti relací Ri, i?2, R3 a R4 v množině M, které jsou znázorněny na uzlových grafech. t P. Obrázek 2.1: R Obrázek 2.2: R2 t t Obrázek 2.3: R3 Obrázek 2.4: R4 28 Komentář. Reflexivnost relace se projeví nápadně v uzlovém grafu smyčkou kolem každého uzlu. Žádná smyčka nesmí chybět. Chybí-li, pak relace není reflexivní, proto Ri není reflexivní. Symetričnost se projeví v uzlovém grafu dvojitými orientovanými hranami. Žádná hrana nesmí být jednoduchá. Když je v grafu jedna jednoduchá orientovaná hrana, tak relace už není symetrická => Ri není symetrická. Tranzitivnost z grafu poznáme obtížně. Nejlépe tuto vlastnost ověříme podle definice. Prošetříme všechny uspořádané dvojice relace. Relace Ri určíme výčtem prvků MxM = {(p,p),(q,q),(r,r),(s,s),(t,t),(p,q),(p,r),(p,s),(p,t), (q, p), (q, r), (q, s), (q, t), (r, p), (r, q), (r, s), (r, ŕ), (s, p), (s, q), (s, r), (s, t), (t, p), (t, q), (t, r), (t, s)} Ri není tranzitivní. Relace antireflexivní se v uzlovém grafu projeví tak, že kolem žádného uzlu není smyčka. Objeví-li se v grafu jedna smyčka, pak relace není antireflexivní. Graf může obsahovat jednoduché i dvojité orientované hrany a také je možné jednu hranu se dvěma šipkami. Tato relace nesmí obsahovat žádnou uspořádanou dvojici typu (x, x) £ M x M. Ri proto není antireflexivní. Antisymetričnost se v uzlovém grafu projeví tak, že žádná šipka není dvojitá, mohou se kolem uzlu objevit smyčky. Ri proto není antisymetrická. Řešení. • uzlový graf na obr. 2.1 i?! Ri není reflexivní ani symetrická ani tranzitivní ani antireflexivní a antisymetrická. • uzlový graf 2.2 R2 i?2 je reflexivní, symetrická, tranzitivní, ale není antireflexivní a antisymetrická. • uzlový graf 2.3 R3 i?3 není reflexivní, symetrická, tranzitivní, ale je antireflexivní a antisymetrická. • uzlový graf 2.4 fž4 iž4 není reflexivní, symetrická, antireflexivní, ale je antisymetrická, tranzitivní. Příklad 2.9. Jsou dány relace: a) Uľ = {(-2, 5), (5, 5), (5, -2), (0, 0)} b) U2 = {(-2, -2), (5, -2), (0, 5), (0, 0), (0, -2)} 29 c) £/3 = {(0,0),(-2,-2),(5,5)} d) U4 = B x B na množině B = {0, —2, 5}. Rozhodněte postupně, zda jsou reflexivní, symetrické, tranzitivní. Komentář, k ověření vlastností využijeme definice. Vyjdeme z definice refle-xivnosti, symetričnosti a tranzitivnosti. Relace R v množině B je reflexivní právě tehdy, když platí: Vx G B, (x, x) G R. Relace R v množině B je symetrická právě tehdy, když platí: Vx, y G -B, (x, y) G R => (y, x) G i?. (tj. xfžy => yRx) pro každé x a každé y z B. Relace R v množině B je tranzitivní právě tehdy, když platí: Vx, y,z G B, (x, y) G R A (y, z) G R => (x, z) G i?. Řešení, ad a) není reflexivní, protože (—2, —2) ^ R je symetrická, ale není tranzitivní, protože (—2, 5) G iž, ale (5, 0) ^ R, (-2,0) £ iž ad b) není reflexivní, protože (5, 5) ^ R, (—2, —2) ^ fž je tranzitivní, ale není symetrická, protože (0, 5) G iž, ale (5, 0) ^ R ad c) je reflexivní, symetrická, tranzitivní ad d) je reflexivní, symetrická, tranzitivní 30 Kapitola 3 Relace ekvivalence Ekvivalence = rovnocennost, stejná platnost. Ekvivalence je výrok vytvořený ze dvou výroků tím způsobem, že mezi oba výroky vsuneme slova „tehdy a jen tehdy, když" nebo přesněji „právě tehdy, když". Ekvivalence ^4 <^> i? je pravdivý výrok právě v těch případech, kdy mají výroky A, B stejnou pravdivostní hodnotu. Jsou ekvivalentní. Definice 3.1. Relace R definovaná na množině M se nazývá relace ekvivalence právě tehdy, když je reflexivní, symetrická a tranzitivní Pro všechny a, b, c z množiny A platí: • refiexivnost: (a, a) G R • symetričnost: (a, b) G R => (b, a) G R • tranzitivita: (a, b) G R A (b, c) G R => (a, c) G R 3.1 Ekvivalentní prvky Relaci ekvivalence na množině značíme symbolem ~. Jestliže pro prvky a, b E M platí, že a ~ b říkáme, že prvky a, b jsou navzájem ekvivalentní. Neformálně řečeno: ekvivalence je relace R C M x M taková, že (x, y) E R právě když x a y jsou v nějakém smyslu „stejné". 3.2 Rozklad množin Je-li jakákoliv relace ekvivalence definována na množině M, rozkládá tuto množinu na třídy rozkladu. 31 Definice 3.2. Rozkladem libovolné neprázdné množiny M rozumíme systém podmnožin Mi, M2, M3, ..., Mn, který splňuje následující vlastnosti: • Mj ^ 0,i = 1,2,... ,n, • Mi U M2 U • • • U Mn = M, • M, n M, = 0, pro každé í ^ j, pak množiny M\, M2,. .., Mn nazýváme „třídami rozkladu množiny M". Z uvedeného je zřejmé, že systém podmnožin množiny M může být i nekonečný. Nyní si vysvětlíme, jak tento rozklad probíhá. Zvolme libovolnou množinu M. Na ní je definována relace R, která je reflexivní, symetrická a tranzitivní a jedná se tudíž o relaci ekvivalenci. Zvolme libovolný prvek a G M a sestrojme množinu T\ všech prvků x z množiny M, které jsou s prvkem a ekvivalentní. Zapíšeme T\ = {x E M; x ~ a}. Existuje-li v množině M další prvek b, který nepatří do T\ (tzn. prvek b není ekvivalentní s prvkem a), sestrojíme množinu T2 všech prvků x z množiny M, které jsou ekvivalentní s prvkem b, tj. množinu T2 = {x E M; x ~ b}. Existuje-li v množině M další prvek c, který nepatří do množiny 7\ ani do množiny T2, pak vytvoříme množinu T3, která obsahuje prvek c a všechny další prvky x množiny M, které jsou s prvkem c ekvivalentní. Zapíšeme T's = {x E M;x ~ c}. Tímto způsobem pokračujeme tak dlouho, až vyčerpáme všechny prvky množiny M. Výsledkem tohoto postupu je množina T, jejíž prvky jsou neprázdné množiny, které nazveme třídy rozkladu Tl5 T2,..., Tn. Píšeme T = {Tl5 T2,..., Tn}. 3.3 Vlastnosti rozkladu 1. Sjednocení všech tříd rozkladu množiny M se rovná množině M. Jinak: každý prvek x E M patří do některé z množin Ti, T2,..., T„. 2. Průnik každých dvou tříd je množina prázdná. Jinak: každý prvek je zařazen právě do jedné třídy rozkladu množiny M 3. Žádná z množin Ti, T2,..., Tn nemůže být prázdná. 32 3.4 Reprezentant třídy Množina T, která má uvedené vlastnosti, se nazývá rozklad množiny M. Prvky množiny T se jmenují třídy rozkladu. Každá třída rozkladu je jednoznačné určena libovolným prvkem třídy. Říkáme, že libovolný prvek třídu reprezentuje, a proto se nazývá reprezentant. Ekvivalencemi jsou např. takové relace, jako je rovnost čísel, rovnost podmnožin dané množiny, rovnoběžnost přímek, shodnost trojúhelníků apod. Příklad 3.1. Je dána množina M = {1,2,3,4} a v ní jsou relace dány výčtem prvků: . R1 = {(1,1), (1,2), (2,1), (2, 2), (3, 3), (4,4)}, . ^ = {(4,4), (1,2), (2,1)}, . ^ = {(1,2), (2, 2), (1,1), (2,1)}, . R4 = {(1,1), (3, 4), (2, 2), (1, 2), (2,1), (4,4), (3,3), (4, 3)}. Rozhodněte o každé relaci, zda je relací ekvivalence a odůvodněte. Nalezněte třídy ekvivalentních prvků. Komentář. Relace jsou dány výčtem prvků. Ověříme, jestli Ri, R2, R3, R4 jsou reflexivní, symetrické a tranzitivní. Pokud všechny tři podmínky splněny, je tedy relace ekvivalence a vytvoří rozklad této množiny M. Každý prvek x E M patří do některé třídy rozkladu. Sjednocení všech tříd rozkladu množiny M se rovná množině M. (Definice rozkladu). Řešení. Relace ekvivalence znamená, že musí platit = relace je současně reflexivní, symetrická a tranzitivní. R1 = {(1,1), (1,2), (2,1), (2, 2), (3, 3), (4,4)} • relace Ri je reflexivní, symetrická a tranzitivní Tedy Ri je relace ekvivalence. Uzlový graf relace Ri 33 t = {Ti,r2,r3} Ti = {x G M,x ~ 1} = {1,2} T2 = {x G m, x ~ 3} = {3} T3 = {x G m, x ~ 4} = {4} T = {{1,2}, {3}, {4}} Relace 7?i je v množině m reflexivní, symetrická a tranzitivní, je tedy relací ekvivalence a vytváří třídy rozkladu Ti, T2, T3. ^ = {(4, 4), (1,2), (2,1)} • relace iž2 není reflexivní. Automaticky iž2 není relace ekvivalence a nevytváří třídy ekvivalentních prvků. iž3 = {(l,2),(2,2),(l,l),(2,l)} • relace ÍŽ3 není reflexivní. Automaticky iž3 není relace ekvivalence a nevytváří třídy rozkladu. R4 = {(1,1), (3, 4), (2, 2), (1, 2), (2,1), (4,4), (3, 3), (4, 3)} • relace R4 je reflexivní, symetrická a tranzitivní i?4 je tedy relace ekvivalence. Uzlový graf relace R4 34 T = {Ti,T2} Ti = {x G M,x ~ 1} = {1,2} T2 = {x G m, x ~ 3} = {3,4} T = {{1,2}, {3,4}} Relace r4 je v množině m reflexivní, symetrická a tranzitivní, je tedy relací ekvivalence a vytváří třídy rozkladu Ti, T2. Příklad 3.2. Doplňte relace definované na množině A = {1,2,3,4} minimálním počtem uspořádaných dvojic, abychom dostali relace ekvivalence. Potom najděte reprezentanty tříd rozkladu. a) 5i = {(3,4),(4,2),(2,2),...} b) 52 = {(1, 2), (2, 3), (3, 2), (1, 3), (3,1), (4,4), (2,1), (3, 3),...} Komentář. Relace 5i a 52 Q A x A jsou ekvivalence právě když R je reflexivní, symetrická a tranzitivní. Tyto tři vlastnosti je tedy třeba ověřit k důkazu toho, že dané relace 5i a 52 jsou ekvivalence. Relace 5i a 52 jsou dány výčtem prvků, které nesplňují podmínku definice ekvivalence. Když 5i a 52 C A x A doplníme uspořádané dvojice minimálním počtem uspořádaných dvojic tak, aby byla relace ekvivalence splněna. Pro ověření vlastností můžeme využít uzlový graf relace. Na uzlovém grafu dobře vidíme třídy ekvivalentních prvků a reprezentanty tříd rozkladu. Řešení: ad a) Z výčtu prvků relace 5i zjistíme, že relace není reflexivní. Aby byla 5i reflexivní doplníme {(1,1), (3, 3), (4, 4)}. Aby byla symetrická, musíme ji doplnit {(4, 3), (2, 4)}. Relace už je tranzitivní. 5i = {..., (1,1), (3, 3), (4, 4), (4, 3), (2,4)} Uzlový graf relace 5i. 35 T = {TUT2} Ti = {x G M, x ~ 2} = {2, 3, 4} T2 = {x G M, x ~ 1} = {1} T = {{2,3,4},{1}} Reprezentantem třídy T\ je např. 2. Může být i 3 nebo 4. Reprezentantem třídy T2 je 1. ad b) Z výčtu prvků relace S2 zjistíme, že relace není reflexivní. Aby byla reflexivní doplníme {(1,1), (2, 2)}. Relace je symetrická a tranzitivní. S2 = {..., (1,1), (2, 2)} T = {TUT2} Ti = {x G M,x ~ 1} = {1,2,3} T2 = {x G M, x ~ 4} = {4} T = {{1,2,3}, {4}} Reprezentantem třídy T\ je např. 1. Může být i 2 nebo 3. Reprezentantem třídy T2 je 4. 36 Kapitola 4 Relace uspořádaní Další velmi významný příklad relací jsou tzv. relace uspořádání, nazývané také někdy částečné uspořádání. Definice 4.1. • Řekneme, že relace R na množině A je uspořádání (částečné uspořádání), je-li R reflexivní, antisymetrická a tranzitivní relace. Množinu A na které je definována relace uspořádání pak nazýváme uspořádanou množinou. • Relace souvislá: Relace R v množině A se nazývá souvislá, právě když pro každé dva prvky x, y z množiny M platí: x ^ y => [(x, y) E R V (y, x) E R]. V uzlovém grafu se relace souvislá projeví tak, že každé dva uzly musí být spojeny hranou. Přitom šipky mohou být z obou stran a mohou se vyskytnout smyčky. • Relace R definována na množině A, která je reflexivní, antisymetrická, tranzitivní a souvislá se nazývá relace lineárního uspořádání. • Množina A, v níž je definována relace lineárního upořádání R se nazývá lineárně uspořádaná množina (A,R). • Je-li R relace uspořádání v množině A, pak skutečnost, že prvek a předchází před prvkem 6, zapíšeme vztahem: a ~< b. (Prvek a předchází před prvkem b v uspořádání R). 37 Definice 4.2. Necht (M, <) je uspořádaná množina. Prvek a G M se nazývá: • nejmenší, jestliže pro Vx G M platí: a < x • největší, jestliže pro Vx G M platí: x < a • minimální, jestliže neexistuje prvek x G M takový, že x < a • maximální, jestliže neexistuje prvek x G M takový, že a < x Dva prvky a, b G M se nazývají srovnatelné, jestliže platí, že a < b nebo b < a. V opačném případě jsou prvky nesrovnatelné. Neformálně řečeno: uspořádání je taková relace R Q A x A, kde (x, y) G R právě když x je v nějakém smyslu „menší nebo rovno" než y. Mohou ovšem existovat taková x, y G A, kde neplatí (x, y) G R ani (y, x) G R. (Pak říkáme, že x a y jsou nesrovnatelné.) Příklad 4.1. Rozhodněte, které z těchto relací v fž jsou uspořádání: a) Z7i = {(5, 5), (2,1), (4, 3), (7, 7), (4, 2), (1, 0), (2, 0)} b) U2 = {(2, 3), (3, 4), (2, 2), (1, 0), (-y/2, 5), (0,1), (2,4)} c) U3 = {(-3, 3), (2, -1), (3, 0), (-1, -1), (-3, 0), (-4, 8)} Komentář. Vyjdeme z definice uspořádání - musíme ověřit tři vlastnosti k důkazu toho, že daná relace R je uspořádání: reflexivnost, antisymetričnost a tranzitivnost. Řešení: ad a) Z7i = {(5, 5), (2,1), (4, 3), (7, 7), (4, 2), (1, 0), (2, 0)} Ui není reflexivní, protože (0, 0), (1,1),..., (7, 7) ^ R => XJ\ není uspořádání. ad b) U2 = {(2, 3), (3, 4), (2, 2), (1, 0), (-y/2, 5), (0,1), (2,4)} U2 není reflexivní, protože (0, 0), (1, 1),. .., (4, 4) ^ R => XJ\ není uspořádání. ad c) U3 = {(-3, 3), (2, -1), (3, 0), (-1, -1), (-3, 0), (-4, 8)} Vlastnosti relace U3 poznáme z uzlového grafu. Je dobré vytvořit množinu U3 = {-4, -3, -1, 0, 2, 3, 8} 38 Us je reflexivní, antisymetrická a tranzitivní. Tím jsem dokázali, že U3 je uspořádání. Příklad 4.2. Je dána množina M = {1, 2, 3, 4}. Určete vlastnosti relace R = {(2,1), (2, 3), (2, 4), (1, 3), (1,4), (4, 3)}. a) Rozhodněte, zda relace R je relací uspořádání. b) Množinu M uspořádejte pomocí relace R. Komentář. Aby byla relace R uspořádání, musí být reflexivní, antisymetrická a tranzitivní. Musíme dokázat tyto 3 vlastnosti. Vlastnosti relace poznáme nejlépe z uzlového grafu. Řešení: Uzlový graf relace R 1 2 3 4 Definice 4.3. Relace R definována na množině M, která je antireflexivní, antisymetrická, tranzitivní a souvislá se nazývá relace ostrého lineárního uspořádání. ad a) 1. Relace je antireflexivní, protože se v ní nevyskytují uspořádání dvojice (1,1), (2, 2), (3, 3), (4,4) => uzlový graf neobsahuje žádnou smyčku kolem uzlu 2. Relace je antisymetrická, protože se v ní vyskytuje uspořádaná dvojice např. (2,1) a nevyskytuje se dvojice (1, 2) => v grafu není žádná orientovaná hrana s oboustrannou šipkou. 39 3. Relace je tranzitivní, protože platí Vx, y,z £ M; ((x, y) £ R A (y, z) E R => (x, z) E R) např. (2,1) E R A (1,4) E R => (2, 4) E R Podmínka definice je splněna. 4. Relace je konektivní (souvislá), každé dva uzly jsou spolu spojeny hranou. Protože relace R je antirefiexivní, antisymetrická, tranzitivní a konektivní (souvislá), relace R se nazývá relace ostrého lineárního uspořádání. ad b) Uspořádáme množinu M pomocí relace R. Budeme brát postupně uspořádané dvojice a zjistíme, jak relace R uspořádá prvky množiny M. R = {(2,1), (2, 3), (2,4), (1,3), (1,4), (4, 3)} (2, 1) E R znamená, že 2 -< 1 (2.3) E R znamená, že 2 -< 3 (2.4) E R znamená, že 2 -< 4 Číslo 2 je před 1, 3, 4 => číslo 2 bude první prvek uspořádané množiny. (1.3) £ R znamená, že 1 -< 3 (1.4) £ R znamená, že 1 -< 4 Číslo 1 je před 3, 4. (4, 3) E R znamená, že 4 -< 3 Číslo 4 je před 3 => číslo 3 bude poslední prvek uspořádané množiny. Uspořádáme množinu M podle relace R. 2 ^ 1 ^ 4 ^ 3 Příklad 4.3. Na množině M = {1, 2, 3, 4} je dána relace Ä = {(2,1), (2, 3), (2,4), (1,3), (1,4), (4, 3)}. a) Určete relaci inverzní R~ľ. b) Nakreslete uzlový graf relace R-1. c) Určete vlastnosti relace R, R~ľ. 40 d) Ověřte, že relace inverzní je relace uspořádání. e) Uspořádejte množinu M v uspořádání R, R-1. Věta 4.1. Je-li relace R uspořádáním v množině M, je také inverzní relace R-1 uspořádáním v množině M. Řešení: ad a) Zaměníme-li pořadí složek ve všech uspořádaných dvojicích, které tvoří relaci R, dostaneme relace inverzní fž_1 (zaměníme x a y) R-1 = {(1, 2), (3, 2), (4, 2), (3,1), (4,1), (3,4)} ad b) uzlový graf relace fž_1 ad c) Vlastnosti relace R viz předchozí příklad č. 4.3 Podle definice je-li relace R uspořádání v množině M, je také inverzní relace fž_1 uspořádáním v množině M. R-1 je antireflexivní, antisymetrická, tranzitivní a konektivní (souvislá) ad d) Podmínky definice jsou splněny. ad e) Mi = {2,1,4,3} Relace fž_1 uspořádá množinu M takto: R-1 = {(1, 2), (3, 2), (4, 2), (3,1), (4,1), (3,4)} (3, 2) G R znamená, že 3 -< 2 (3,1) G R znamená, že 3 -< 1 (3, 4) E R znamená, že 3 -< 4 Číslo 3 je před 1, 2, 4 => číslo 3 bude první prvek uspořádané množiny. (4, 2) E R znamená, že 4 -< 2 (4, 1) E R znamená, že 4 -< 1 41 Číslo 4 je před 1, 2. (1,2) E R znamená, že 1 -< 2 Číslo 1 je před 2. Číslo 2 bude poslední prvek uspořádané množiny. Uspořádáme množinu M podle relace R. 3 -< 4 -< 1 -< 2 Relace R uspořádá množinu M takto: M2 = {3,4,1, 2}. 4.1 Hasseovský diagram - názorné zobrazení uspořádání Pro znázornění uspořádání se používá tzv. Hasseovský diagram. Je to grafické znázornění podobné jako uzlové grafy. Je to zobrazení diagramem, kde „větší" prvky jsou kresleny výše než ty „menší". Komentář. Diagramy jsou složeny z uzlů reprezentujících prvky, množiny X a hran, které vyznačují relaci pokrytí - příslušnou danému uspořádání < na X. Podrobněji, prvky množiny X znázorníme jako uzly (to jest „body") v rovině tak, aby v případě, kdy x < y ležel bod x níže než bod y. Dva body x,y E X spojíme v diagramu hranou (úsečkou), právě když x ~< y. Horizontální umístění bodů je vhodné volit tak, aby pokud možno nedocházelo ke křížení hran. Relaci -< nazýváme: relace pokrytí, (výraz x ~< y čteme „x je pokryt y nebo y pokrývá x"). Definice 4.4. Hasseovský diagram konečné uspořádané množiny (M, <) je (jednoznačné) grafické znázornění vzniklé takto: • Do první „horizontální vrstvy" zakreslíme body odpovídající minimálním prvkům (M, <). (Tj. které nepokrývají nic.) • Máme-li již zakreslenou „vrstvu" i, pak do „vrstvy" i + 1 (která je „nad" vrstvou i) zakreslíme všechny nezakreslené prvky, které pokrývají pouze prvky „vrstev" < i. Pokud prvek x „vrstvy" i + 1 pokrývá prvek y „vrstvy" < i, spojíme x a y neorientovanou hranou (tj. „čárou"). 42 Poznámka: Hasseovský diagram relace (M, <) sestrojíme takto: 1. všechny prvky množiny M vyznačíme kroužky - body v rovině 2. Je-li a < b, pak bod a nakreslíme niže než bod b 3. dva body a, b spojíme úsečkou o a < b a neexistuje k E M tak, že a < k A k < b. Výsledný graf se nazývá Hasseovský áiagram uspořádané množiny (M, <). Příklad 4.4. Buď M množina všech binárních relací na množině A = {a, b, c}, které jsou reflexivní a zároveň symetrické. Nakreslete Hasseovský diagram uspořádané množiny (M, C). Řešení. Ri = {(a, a) ,(6,6), (c, c} r2 = {(a, a) ,(6,6), (c, c), (a 6), (6, a)} R3 = {(a, a) ,(6,6), (c, c), (6, c),(c,fo)} = {(a, a) ,(6,6), (c, c), (a c), (c, a)} i?5 = {(a, a) ,(6,6), (c, c), (a 6), (6, a), (6, c), (c, 6)} R$ = {(a, a) ,(6,6), (c, c), (a 6), (6, a), (a, c) (c, a)} Ri = {(a, a) ,(6,6), (c, c), (6, c), (c, 6), (a, c), (c, a)} R$ = {(a, a) ,(6,6), (c, c), (a 6), (6, a), (6, c), (c, 6), (a, c), (c, a)} Pak přidáme do relace R R = {Rii r21r31 R^i r51 R&1 r71 Rs} Ri c r2 R3, i?4, ÍŽ5, rq, rj, R r2 c r5 R$, R$ Rs c R5 R7, R$ R4 c R$ R7, R$ R5 c R$ R$ c R$ Rr c R$ 43 Nyní je graf Kapitola 5 Relace zobrazení - zobrazení množin 5.1 zobrazení, definiční obor a obor funkce, zobrazení prosté Definice 5.1. • Nechť A, B jsou libovolné množiny. Relaci Z z A do B nazveme zobrazení z A do 5, právě když ke každému x E A existuje nejvýše jedno y E B takové, že (x, y) E Z. Je-li A = B, hovoříme o zobrazení v A. Neformálně řečeno: Zobrazení množiny z A do množiny B přiřazuje každému prvku množiny A nejvýše jeden prvek množiny B. Píšeme / : A —> B Definice 5.2 (definičního oboru a oboru hodnot). Jestliže (a, b) E Z, pak prvek a se nazývá vzorem prvku b, prvek b se nazývá obrazem prvku a v zobrazení Z. První obor zobrazení se nazývá definiční obor zobrazení, označujeme oi(Z) a druhý obor zobrazení se nazývá obor hodnot zobrazení a označuje se oi{Zľ) [12]. Definice 5.3. Zobrazení Z z A do B se nazývá prosté, právě když každým dvěma různým prvkům x E A přiřazuji dva různé prvky z množiny B. Pak hovoříme: o prostém zobrazení z množiny A do množiny B, o prostém zobrazení z množiny A na množinu B, o prostém zobrazení množiny A do množiny B, 45 o prostém zobrazení množiny A na množinu B. Pravidlo: Relace Z C A x B je zobrazení <í=> a) na uzlovém grafu relace Z vychází z každého uzlu nejvýše jedna šipka, b) na kartézském grafu relace Z na všech přímkách rovnoběžných se svislou osou je zakreslena nejvýše jedna uspořádaná dvojice. Termínu „zobrazení z množiny A do množiny Bu lze použít vždy. Tím není řečeno o oborech zobrazení nic víc, než oi(Z) C A a o2(Z) C B. Prostě zobrazení má na kartézském grafu v každém řádku nejvýše jeden bod grafu. Prostě zobrazení na uzlovém grafu charakterizuje, že z každého uzlu, který znázorňuje prvek množiny A vychází nejvýše jedna orientovaná hrana a do každého uzlu, který znázorňuje prvek množiny B nejvýše jedna orientovaná hrana vchází. 5.2 Injekce, surjekce a bijekce Definice 5.4. • Injektivní zobrazení (injekce) je prosté zobrazení množiny A do množiny B. Pro a, b E A platí f (a) = f(b) a dokazujeme, že a = b (když se 2 různé prvky z množiny A zobrazí na stejný prvek množiny B —> potom není zobrazení injektivní). • Surjektivní zobrazení (surjekce) je zobrazení množiny A na množinu B. Dokážeme, že pro libovolný prvek b E B existuje vzor (když nenajdeme v množině B konkrétní prvek, který nemá při zobrazení žádný vzor, není zobrazení surjektivní). • Bijektivní zobrazení (bijekce) je prosté zobrazení množiny A na množinu B. Bijekce je tedy zároveň injektivní zobrazení a surjektivní zobrazení. Platí oi(Z) = A a o2(Z) = B. Příklad 5.1. Necht je dána množina A = {a, b, c, d}, množina B = {x, y, z, u}. Relace Z\ jejíž graf je na obr. 5.1 a relace Z2 jejíž graf je na obr. 5.2 46 B B a o b C d o x oy *o Z U Obrázek 5.1: Relace Z\ Určete, která z relací jsou zobrazení. Obrázek 5.2: Relace Z2 Řešení: Relace Z\ je zobrazením, protože podle definice zobrazení z každého uzlu grafu vychází nejvýše jedna šipka. Relace Z2 není zobrazením, nebot z uzlu c vycházejí dvě šipky. Příklad 5.2. Určete, které z následujících relací v množině A = {0,1, 2,..., 6} jsou zobrazení. V případě zobrazení zapište definiční obor a obor hodnot. Zobrazení znázorněte graficky. a) R1 = {(0,0), (0,1), (4,4), (3, 2), (2, 3)}, b) R2 = {(4, 6), (2, 5), (3,4), (2, 3), (2, 0), (1,1), (0,0)}, c) R3 = {(2, 3), (3, 4), (1,3), (4, 5), (0,3)}, d) R4 = {(3, 2), (2, 3), (1,5), (3,4), (1,2)}. Řešení: ad a) není zobrazení, protože z čísla 0 vychází dvě šipky a uspořádané dvojice (3, 2) má více hran A A 0 —o 0 1 o 1 2 o 2 3 o 3 4 o— -«D 4 5 o O 5 6 o O 6 47 ad b) není zobrazení, protože z čísla 2 vychází tři šipky A A 0 o— 0 1 1 2 o 2 3 3 4 4 5 o x 5 6 o 6 ad c) je zobrazení, splňuje podmínky definiční obor, tj. množina všech prvních složek uspořádaných dvojic ze zobrazení R% a obor hodnot je množina všech druhých složek uspořádaných dvojic ze zobrazení R3 A A 0 0 0 1 0 1 2 2 3 3 4 4 5 0 5 6 0 0 6 01OR3) = {0,1,2,3,4} a o2{R3) = {3,4,5} ad d) není zobrazení, protože z čísla 1 a 3 vychází dvě šipky A A 0 0 0 0 1 0 1 2 2 3 3 4 0 4 5 0 5 6 0 0 6 Příklad 5.3. Zobrazení množiny nakreslete všechna zobrazení A —> B a uveďte, která z nich jsou injektivní, resp. surjektivní, resp. bijektivní. Přitom a) A = {a, b, c}, B = {x, y} 48 b) A = {a,b},B = {x,y,z} Řešení: a) / : A^B A X B = {a,b,c} X {x, y} = {(a, x), (a, y), (b, x), (b, y), (c, x), (c, y)} Zobrazení fl {(«, x) , (b, x) (c x)} h {(«, y) ,(b,y), (c, v)} h {(«, x) , (b, x) (c v)} h {(«, y) , (b, x), (c, x)} h {(«, y) ,(b,y), (c, x)} h {(«, y) , (b, x), (c, v)} h {(«, x) ,(b,y), (c, x)} h {(«, x) ,(b,y), (c, v)} Celkem je 8 zobrazení, z toho je 6 surjektivních a není injektivní a bijektivní. b) / : A -+ B A X B = {a, b} X {x, y, z} = {(a, x), (a, y), (a, z), (b, x), (b, y), (b, z)} Zobrazení fl {(«, x) ,(b,x)} h {(«, x) h {(«, x) ,(MI h {(«, y) h {(«, y) h {(«, y) ,(MI h {(«, z) (Ml h {(«, z) (Ml h {(«, z) (Ml Celkem je 9 zobrazení, z toho je 6 injektivních, není surjektivní a bijektivní. 49 Kapitola 6 Zbytkové třídy Definice 6.1. Necht n je přirozené číslo n G N; a, b je celá čísla a, b G Z. Řekneme, že čísla a, b jsou kongruentní podle modulu n, píšeme a = b (mod n). Když čísla a, b dají po dělení číslem n stejný zbytek. Ukážeme, že je to relace ekvivalence na celých číslech. Množinu zbytkových tříd značíme 7hn = {[a]n | cl G Z}, kde [a]n = {b \ b G Z, b — a mod n = 0}. Komentář. Rozklad množiny na tzv. „zbytkové třídy" je relací typu ekvivalence. Hledáme binární relaci, která rozkládá množinu tak, že každá dvě čísla patří do jedné a téže třídy, dávají při dělení stejným číslem stejný zbytek. Každá tato dvě čísla jsou spolu v relaci, kterou hledáme: tato binární relace je tedy množina všech uspořádaných dvojic (x, y) z dané množiny, pro která platí, že „x dává při dělení n stejný zbytek jako y". Tedy {(x, y) G A x A : x dává při dělení stejný zbytek jako y}. Tuto relaci je zvykem nazývat kongruence (podle modulu n). Můžeme si ověřit, že tato relace je skutečně relace typu ekvivalence, že relace je v dané množině reflexivní, symetrická a tranzitivní. Relace ekvivalence R je podmnožinou M x M. Podle definice 3.1 "ekvivalence" je na str. 31. Věta 6.1. Vztah kongruence je: 1. reflexivní, a = a (mod m), 2. symetrický, a = b (mod m) => b = a (mod m) a 3. tranzitivní, a = b (mod m) A b = c (mod m) => a = c (mod m). 50 Zdůrazníme, že = je vždy relací ekvivalence na množině Z. Definice 6.2 (kongruence podle modulu m). Nechť m je přirozené číslo větší než jedna. Potom binární relace {(x, y) E No x No : x dává při dělení číslem m stejný zbytek jako y}, se nazývá kongruence podle modulu m. Zápis kongruence podle modulu m: a = b mod m uvedený zápis čteme: „číslo a je kongruentní s číslem b podle modulu m". Např. kongruenci podle modulu 7 lze zapsat takto: {(x, y) E N0 x N0 : x = y mod 7}. Příklad 6.1. Zapište v množině všech přirozených čísel kongruenci podle modulu a) 3 b) 8 c) 11 Řešení: a) kongruence podle modulu 3: {(x,y) E No x No : x dává při dělení číslem 3 stejný zbytek jako y} nebo {(x, y) E N0 x N0 : x = y mod 3} Zápis čteme: {(x, y) E No x No : x, y jsou kongruentní podle modulu 3} b) kongruence podle modulu 8: {(x,y) E No x No : x dává při dělení číslem 8 stejný zbytek jako y} nebo {(x, y) E N0 x N0 : x = y mod 8} Zápis čteme: {(x, y) E No x No : x, y jsou kongruentní podle modulu 8} c) kongruence podle modulu 11: {(x,y) E No x No : x dává při dělení číslem 11 stejný zbytek jako y} nebo {(x, y) E N0 x N0 : x = y mod 11} Zápis čteme: {(x,y) E No x No : x, y jsou kongruentní podle modulu 11} 51 Definice 6.3 (dělitelnosti). Uvažujme dvě libovolná celá čísla a, b G Z. Říkáme, že b dělí a (případně a je dělitelné b) právě tehdy, existuje-li c G Z takové, že a = bc. Pokud b dělí a, píšeme a \ b. V opačném případě píšeme b\a. Věta 6.2. Jsou-li a, 6 kterákoliv přirozená čísla až na to, že b 7^ 0, existuje právě jedna dvojice přirozených čísel q, z, pro která platí [14] a = b ■ q + z a z < b Necht je dána uspořádaná dvojice přirozených čísel a, b tak, že b se nerovná nule. Zjištujeme-li uspořádané dvojice přirozených čísel q, z tak, že platí rovnost a = b ■ q + z a nerovnost z < b, říkáme, že provádíme „dělení se zbytkem". Definice 6.4 (dělení se zbytkem). Zobrazení kartézského součinu No x N na kartézský součin No x No se nazývá „dělení se zbytkem", právě když je v tomto zobrazení uspořádané dvojici (a,b) z kartézského součinu No x N přiřazena uspořádaná dvojice (q, z) z kartézského součinu No x No tak, že platí rovnost a = b ■ q + z a nerovnost z < b. Číslo z se nazývá „zbytek" a pokud z / 0, pak číslo q se nazývá „neúplný podíl" [14]. Příklad 6.2. Určete dvojice čísel q, z podle věty 6.2, pro a) a = 17, b = 5 b) a = 61, b = 7 c) a = 54, b = 9 d) a = 11, b = 13 Řešení: Komentář. Hledáme přirozená čísla q, z tak, aby platila rovnost: a = b- q + zř\z s modulem 4. C4 = {0,1, 2, 3} . .. tj. množina zbytkových tříd s modulem 4 Cm = {Ô,T,2,...,m=T}. 54 Tento rozklad způsobila relace ekvivalence. Je tranzitivní, reflexivní a symetrická. Relace R dává při dělení modulem stejný zbytek. Relace R definována na množině celých čísel způsobuje rozklad na zbytkové třídy. Těch je tolik, kolik je modulů. Příklad 6.4. Zapište množinu všech zbytkových tříd podle modulu 5. Úlohu opakujte, je-li modul roven číslu 3, 6, 8. Řešení: Množina zbytkových tříd podle modulu 5, tj. C5 = { 0,1, 2, 3,4 } Množina zbytkových tříd podle modulu 3, tj. C3 = { 0, 1, 2 } Množina zbytkových tříd podle modulu 6, tj. Cq = { 0,1, 2, 3,4, 5 } Množina zbytkových tříd podle modulu 8, tj. Cg = { 0,1, 2, 3,4, 5, 6, 7 } Příklad 6.5. Zapište všechna celá čísla, která patří do každé zbytkové třídy, je-li modul roven číslu 5. Úlohu opakujte, je-li modul roven číslu 3, 6, 8. Řešení: Zbytkové třídy podle modulu 5: Ô = {•• , -20, -15, -10,-5,0,5,10,15, ••} T = {•• , -19, -14, -9,-4,1,6,11,16,.. •} 2 = {•• , -18, -13, -8,-3,2,7,12,17,.. •} 3 = {•• ,-17, -12, -7,-2,3,8,13,18,.. •} 4 = {•• , -16, -11, -6,-1,4,9,14,19,.. •} Zbytkové třídy podle modulu 3: 0 = {...,-12,-9,-6,-3,0,3,6,9,...} 1 = {...,-11,-8,-5,-2,1,4,7,10,...} 2 = {...,-10,-7,-4,-1,2,5,8,11,...} Zbytkové třídy podle modulu 6: Ô = {•• , -24, -18, -12, -6,0,6,12, 18.. I = {•• , -23, -17, -11, -5,1,7,13, 19,. 2 = {•• , -22, -16, -10, -4,2,8,14, ...} 3 = {•• , -21, -15, -9,- -3,3,9,15,. ••} 4 = {•• , -20, -14, -8,- -2,4,10,16, ...} 5 = {•• , -19, -13, -7,- -1,5,11,17, ...} 55 Zbytkové třídy podle modulu 8: Ô = {•• •, -32, -24, -16, -8,0,8,16,24 ...} T = {•• .,-31, -23, -15, -7,1,9,17,25 ...} 2 = {•• •, -30, -22, -14, -6,2,10,18,.. •} 3 = {•• •, -29, -21, -13, -5,3,11,19,.. •} 4 = {•• •, -28, -20, -12, -4,4,12,20,.. •} 5 = {•• •, -27, -19, -11, -3,5,13,21,.. •} 6 = {•• •, -26, -18, -10, -2,6,14,22,.. •} 7 = {•• .,-25, -17, -9,- -1,7,15,23,... } Příklad 6.6. Naznačte zápis rozkladu množiny všech přirozených čísel, indukovaný kongruencí podle modulu a) 3 b) 8 c) 11 Řešení: Pracujeme s množinou přirozených čísel No- Třídy rozkladu množiny všech přirozených čísel, to jsou zbytkové třídy indukované kongruencí: ad a) podle modulu 3 Ô = {0,3,6,9,12,15,18,21,24,27...} zbytková třída 0 mod 3 T = {1,4,7,10,13,16,19,22,25,28...} zbytková třída 1 mod 3 2 = {2,5,8,11,14,17,20,23,26,29...} zbytková třída 2 mod 3 Rozklad množiny všech přirozených čísel, indukovaný kongruencí podle modulu 3 má 3 třídy: ^3 = {0,1, 2} C3 = {{0, 3, 6, 9,12,... }, {1,4, 7,10,13,. ad b) podle modulu 8 Ô = {0,8,16,24,32,40,48,56...} T = {1,9,17,25,33,41,49,57...} atd. až 6 = {6,14,22,30,38,46,54,62...} 7 = {7,15,23,31,39,47,55,63...} },{2,5,8,11,14,...}} zbytková třída 0 mod 8 zbytková třída 1 mod 8 zbytková třída 6 mod 8 zbytková třída 7 mod 8 56 Rozklad množiny všech přirozených čísel, indukovaný kongruencí podle modulu 8 má 8 tříd: C8 = {0,1,2,3,4,5,6,7} C8 = {{0, 8,16,... }, {1, 9,17,... } ,..., {6,14, 22,... }, {7,15,23,...}} ad c) Třídy rozkladu podle modulu 11 zjistíme podobně jako u modulu 3, 8. Příklad 6.7. Rozhodněte, zda a = b (mod 16), je-li: a) a = 75, b = 139 b) a = -75, b = 139 c) a = 0,b = 139 d) a = 0,6 = 0 Řešení: Komentář. Kongruence na množině celých čísel Z: Jestliže rozdíl a — b (a, b £ Z) je dělitelný číslem m říkáme, že číslo a je kongruentní s b podle modulu m [stručně: číslo a je kongruentní s modulo m] zapisujeme a = b (mod m) a) a = 75, b = 139 a - b = 75 - 139 = -64 16 | -64 75 = 139 (mod 16) b) a = -75, b = 139 a - b = -75 - 139 = -214 16 f -214 -75 ž 139 (mod 16) c) a = 0,b = 139 a-b = 0-139 = -139 16 f -139 => 0 ž 139 (mod 16) d) a = 0,b = 0 a - b = 0 16 | 0 0 = 0 (mod 16) 57 Kapitola 7 Konstrukce množiny celých čísel Množina Z = {..., —2, — 1, 0,1, 2,... } všech celých čísel s obvyklými operacemi sčítání a násobení a s obvyklým uspořádáním tvoří uspořádaný obor integrity (množina se dvěmi binárními operacemi, ve které nejsou dělitelné nuly) s jednotkovým prvkem 1 a nulovým prvkem 0. Opačným prvkem k číslu k je číslo —k. Rozdílem celých čísel a, b (v tomto pořadí) nazýváme celé číslo d, pro něž platí a = b + d, a píšeme a — b = d. Číslo a, resp. b se nazývá menšenec, resp. menšitel. Pro a, b G Z platí: a>6oa-i)eN Čísla z množiny N nazýváme celými nezápornými čísly = přirozená čísla. N = (1,2,3,...). Celá čísla tvoří množinu Z = přirozená + záporná čísla. Z = (...,-2,-1,0,1,2,...). Ke konstrukci celých čísel nám postačí čísla přirozená. Definice 7.1 (množiny všech celých čísel). Množinu všech celých čísel Z rozumíme množinu všech tříd rozkladu vytvořenou relací ekvivalence „být ekvivalentní mezi uspořádanými dvojicemi", která je definovaná na kartézském součinu No x No předpisem (x, y) ~ (u, v) <^> x + v = y + u 58 Ctěme: Uspořádaná dvojice přirozených čísel x, y je ekvivalentní s uspořádanou dvojicí přirozených čísel u, v právě tehdy, když platí x + v = y + u Relace „být ekvivalentní mezi uspořádanými dvojicemi" je reflexivní, symetrická a tranzitivní. Tyto vlastnosti relace lze dokázat. Je to tedy relace typu ekvivalence a vytvoří na kartézském součinu N0 X N0 rozklad na třídy, které obsahují navzájem ekvivalentní uspořádané dvojice. Množina všech tříd tohoto rozkladu je nekonečná a každá třída je nekonečná množina uspořádaných dvojic. [11], Konstrukce množiny celých čísel a rovnost celých čísel, s. 17 Definice 7.2. Konstrukce množiny Z Celá čísla lze sestrojit jako třídy ekvivalence na množině všech uspořádaných dvojic přirozených čísel, splňují-li tyto požadavky (mi, m2, ri\, n2 E No): (mi, m2) = (ni, n2) <^> m± + n2 = m2 + n±, (mi, m2) < (ni, n2) <^> m-y + n2 < m2 + ny, (mi, m2) > (ni, n2) <^> m± + n2 > m2 + n±, (mi, m2) + (ni, n2) = (mx + ni, m2 + n2), (mi, m2)(ni, n2) = (mini + m2n2, min2 + m2ni). Kladným celým číslem k nazýváme třídu obsahující tvaru [k + 1,1) a ztotožňujeme je s přirozeným číslem fc ^ 0. Množinu všech kladných celých čísel značíme N. Záporným celým číslem —k nazýváme třídu obsahující dvojici tvaru (1, k+l). Celým číslem nula nazýváme třídu obsahující dvojici tvaru (1, 1) a ztotožňujeme je s přirozeným číslem 0. Příklad 7.1. Rozhodněte a odůvodněte, zda následující uspořádané dvojice jsou ekvivalentní a) (4,4), (2, 2) b) (10, 6), (9, 7) c) (11,3), (12,4) Komentář. Ke zjištění a odůvodnění, zda uspořádané dvojice jsou ekvivalentní použijeme shora uvedený předpis (x, y) ~ (u, v) <^> x + v = y + u 59 Řešení: a) (4,4) ~ (2, 2) je ekvivalentní, protože 4 + 2 = 4 + 2 b) (10, 6) 9^ (9, 7) není ekvivalentní, protože neplatí rovnost 10 + 7 7^ 6 + 9 c) (11, 3) ~ (12, 4) je ekvivalentní, protože 11 + 4 = 3 + 12 Zapamatujte si: Rovnost celých čísel. Necht celé číslo a je reprezentováno uspořádanou dvojici (a,b) a celé číslo /5 je reprezentováno uspořádanou dvojici (c, d), pak a = [3 právě tehdy když, uspořádaná dvojice (a,b) je ekvivalentní s uspořádanou dvojicí (c,d). Píšeme: (a, b) e a, (c, d) e [3, pak a = [3 <^> (a, b) ~ (c, d) Zapamatujte si: Nerovnost celých čísel. Necht celé číslo a je reprezentováno uspořádanou dvojici (a, b) a celé číslo [3 je reprezentováno uspořádanou dvojici (c, d), pak a 7^ [3 právě tehdy když, uspořádaná dvojice (a, b) není ekvivalentní s uspořádanou dvojicí (c,d). Píšeme: (a, b) e a, (c, d) G pak a 7^ /3 <^> (a,b) ^ (c, d) Příklad 7.2. Ověřte na několika konkrétních příkladech, že relace „být ekvivalentní mezi uspořádanými dvojicemi" definovaná na Nq x Nq je reflexivní, symetrická a tranzitivní. Řešení: • REFLEXIVNOST V(x, y) e Nq x JV0; (x, y) ~ (x, y) např. (1,4) ~ (1,4) (2,3) - (2,3) • SYMETRIČNOST V(x, y), (u, v) e N0 x N0; (x, y) ~ (u, v) => (u, v) ~ (x, y) např. (4,8) - (1,5) => (1,5) - (4,8) (3, 4) - (6, 7) => (6, 7) - (3, 4) 60 • TRANZITIVNOST V (x, y), (u, v), (s, t) E No x No; (x, y) ~ (-u, u) A (-u, u) ~ (s, t) => (x, y) ~ M) např. (5, 3) - (6,4) A (6,4) ~ (4, 2) => (5, 3) - (4, 2) (8, 3) - (7, 2) A (7, 2) - (15,10) => (8, 3) - (15,10) Dennice 7.3. rovnosti uspořádaných dvojic (a; b) = (c; d) <^> a + d = b + c Komentář. Pomocí definice rovnosti uspořádaných dvojic ověříme, že uspořádané dvojice nejsou stejně, ale jsou si rovny. Ukázky rovnosti: a) Rovnost platí (20,13) = (10, 3) platí, protože 20 + 3 = 13 + 10 (7; 2) = (16; 11) platí, protože 7 + 11 = 2 + 16 (3; 3) = (7; 7) platí, protože 3 + 7 = 3 + 7 b) Rovnost neplatí (9; 4) = (1; 5) neplatí, protože 9+ 5 ^ 4 +1 (7; 3) = (3; 7) neplatí, protože 7 + 7^3 + 3 (13; 12) = (85; 83) neplatí, protože 13 + 83 ^ 12 + 85 Příklad 7.3. Udejte příklad celých čísel a, b, c tak, že a | b-c, ale a \ bAa \ c. Řešení: a = 21, b = 6, c = 7 a\b /\a\c , ale a\b /\a\c 21 | 6-7 , ale 21 f 6 A 21 \ 7 Poznámka: symbol a \ b, ve významu vypadá takhle: a dělí b neboli b je dělitelné a, např. 3 | 12, nebot 12 : 3 je celé číslo Z toho plyne, že 21 | 42 => 42 : 21 = 2, to je celé číslo, ale 21 \ 6 6 : 21 A 21 { 7 => 7 : 21, nejsou celá čísla. Podmínka je splněna. 61 Kapitola 8 Konstrukce množiny racionálních čísel Množina Q všech racionálních čísel o obvyklým operacemi sčítání a násobení a s obvyklým uspořádáním tvoří uspořádané komutativní těleso s jednotkovým prvkem 1 a nulovým prvkem 0 (množina se dvěmi binárními operacemi vůči, kterým existuje inverze). Podílem racionálních čísel p,q(q^ 0) nazýváme racionální číslo r, pro něž platí p = qr, a píšeme p : q nebo ve tvaru zlomku |, popř. p/q. Číslo p, resp. q se nazývá dělenec, resp. dělitel (u zlomku čitatel, resp. jmenovatel). Jako racionální číslo se v matematice označuje podíl dvou celých čísel, většinou zapsaný ve tvaru | nebo a/b, kde b ^ 0. Množina všech racionálních čísel se značí Q. Q = {f:a,foGZAfo^0} Každé racionální číslo se dá zapsat mnoha způsoby, např. 3/6 = 2/4 = 1/2. Základním (nejjednodušším) je tvar, ve kterém a a b nemají společné dělitele kromě jedničky. Každé racionální číslo takový nejjednodušší tvar má a tento tvar je pro dané číslo jednoznačný. Množina celých čísel je vlastní podmnožinou racionálních čísel, nebot celé číslo n lze zapsat jako zlomek n/1. Komentář. Uspořádané dvojice přirozených čísel, které reprezentují racionální čísla jsou zlomky. První složka uspořádané dvojici je „čitatel zlomku" a druhá složka uspořádané dvojice je „jmenovatel zlomku". Tento dvojicím budeme říkat zlomky, i když nejsou zapsány ve tvaru zlomku pomocí zlomkové čáry. 62 Definice 8.1. Konstrukce množiny Q Racionální čísla lze sestrojit jako třídy ekvivalence na množině všech uspořádaných dvojic celých čísel, splňují-li tyto požadavky (pi,p2, Qi, q2 G Z,p2 / 0, 92 7^0): ÍP1,P2) = ( 0) V (pig2 > ř>2 {qi, 92) (Pi P2 0) V (>i2 a ■ d = b ■ c Příklad 8.1. Dokažte, že (V(x, y) G N0 x N)(Vfc G N)(x,y) = (x • /c;y • fc). Důkaz: Podle definice rovnosti platí: (x, y) = (x-k;y-k), protože x- (y-k) = y ■ (x-k) a protože sčítání celých čísel je asociativní a komutativní. Komentář. V souvislosti s rozkladem množiny na třídy si vzpomeňme, že každý rozklad je indukován relací typu ekvivalence - viz. kapitola 3, 6. 63 Závěr I když jsem již v závěru mé bakalářské práce, nebude jistě na škodu, když si řekneme pár slov o jejím obsahu. Cílem této bakalářské práce je vytvoření studijního programu k předmětu Matematika pro neslyšící studenty, kteří si vybrali informatiku jako zaměření. Také já jsem neslyšící a znám problémy, které vyplývají z tohoto postižení. Zohledňuji specifické potřeby neslyšících. Pokusil jsem se ve své práci zobecnit mé zkušenosti s matematikou. Celou práci pojímám elementárně s ohledem na potřeby studia informatiky pro sluchově a zrakově postižené studenty. Mé zkušenosti mě vedly ke snaze o maximální jednoduchost, stručnost a přehlednost při vysvětlování matematických pojmů. Krátkým výkladem na začátku každé kapitoly připravuje studenty k zdolání překážek v závěru. Práce má charakter studijní opory pro vzdělávání. Je zaměřena na základní množinové operace, uspořádané množiny. Navazuje pojem relace a speciální případy relací jako ekvivalence, uspořádání, zobrazení a operace. Cílem je zopakovat a rozšířet středoškolskou látku z matematiky a následně probrat některá další témata, zejména algebraického charakteru. Dalším cílem této práce je pokud možno „srovnat" matematické znalosti studentů se sluchovým a zrakovým postižením, kteří přicházejí z různých středních škol, mnohdy s různou úrovní výuky matematiky. Z tohoto důvodu je práce orientována spíše na studenty s slabšími matematickými znalostmi. Ovšem i u těchto studentů se předpokládá, že vlastní pílí svoje případné nedostatky ve znalostech matematiky zacelí. Tento text by si měli pořídit všichni studenti, kteří cítí, že v jejich matematických znalostech jsou rezervy. Cílem práce je ulehčit a urychlit studium těmto studentům, sjednotit úroveň matematických znalostí a dovedností a poskytnout jim možnosti k případnému samostatnému domácímu studiu. Práce bude převedena do Braillova písma - to bylo součástí zakázky pro středisko pro pomoc studentům se specifickými nároky Masarykovy univerzity Teiresias. Práce je rozdělena do 9 kapitol. I když nemůžu nabídnout pohodlnou cestu k algebře (matematice). Snažil jsem se ji pokud možno usnadnit tím, že začí- 64 nám vždy klíčovými slovy, výklad je veden co možná nejjednodušší formou. Práce zobrazuje nej důležitější definice, věty a metody, k přesnému pochopení se dopracujeme postupně. Moje práce neznamená učit se definice zpaměti, ale především chápat jejich smysl. Podle mých zkušeností je dobré si průběžné vytvářet schémata, pojmy správně zařazovat, zapisovat své úvahy, výpočty, poznámky atd. Důležité je umět číst a psát různé symbolické zápisy. V textu je užívána běžná symbolika známá ze střední školy. Nově zaváděná označení jsou v textu vždy řádně vysvětlena. Téměř všechna tvrzení jsou podrobně dokazována s cílem, aby si student dobře osvojil základní matematické postupy a dovednosti, které bude následně během dalšího studia mnohokrát používat. V závěru každé kapitoly jsou uvedeny vyřešené příklady, které slouží k procvičování a upevnění učiva. Mnoho příkladů používám opakovaně a v různých problémových situacích. Obtížnost těchto úloh je zvolena tak, aby jejich vyřešení přineslo pochopení a jisté uspokojení i handicap studentům, a tím je dále motivovalo. Příklady jsou vybírány s úmyslem ukázat základní obraty a početní postupy používané při řešení konkrétních úloh vztahujících se k dané problematice. Jednotlivé pasáže jsou obsahově velmi podobné. Pokusil jsem se ve své práci zobecnit zkušenosti s matematikou. Vidíme například, že rozdělení racionálních čísel na třídy ekvivalentních zlomků nebo rozdělení do tříd navzájem ekvivalentních soustav spočívá na stejném myšlenkovém principu. V neposlední řadě je v textu věnována pozornost teorii grafů. Jako zdroj pro zpracování kapitol jsem použil odbornou literaturu uvedenou v seznamu použité dostupné literatury. Cílem mé práce je poskytnout studujícím takové vědomosti a dovednosti, které jim umožní řešit základní problémy a úkoly, s nimiž se budou setkávat v dalším studiu, praktickém životě a v pracovním procesu. Přeji si, aby má práce přinesla více radosti z pochopení matematického textu, než zklamání. Věřím, že se mi podařilo splnit cíl mé bakalářské práce a doufám, že mi tato práce bude přínosem v budoucí praxi. Tato práce je vysázena systémem ETgX 65 Označení a symboly Symbol Význam Použití symbolu Obecné matematické symboly není rovno, je různé od 3 + 4 < je menší než 4 < 5 < je menší nebo rovno x <1, x je menší nebo rovno 1 > je větší než 5 < 4 > je větší nebo rovno x > 1, x je větší nebo rovno 1 •) x krát, znak pro násobení, 3 • 3,3 x 3 výsledkem je součin a b a dělí b neboli b je dělitelné a 2 12, nebot 12 : 3 je celé číslo a\b a nedělí b an n-tá mocnina čísla a 23 = 2 • 2 • 2 (2) kombinační číslo, binomický koeficient, (7\ — 7! _ 7-6-5 _ oc V3/ 3!-4! 3-2-1 dJ „n nad k11 n\ n-faktoriál 4! = 4 • 3 • 3 • 2 • 1 = 24 f:X^Y funkce zobrazující množinu 23 = 2 • 2 • 2 X do množiny Y f: R R a = b (mod m) a je kongruentní s b modulo m Číselné množiny N množina přirozených čísel, tj. {1,2, ... } 5 E N, -6 £ N No množina přirozených čísel a nuly, tj. 0 G N0, 7 G N0 {0,1,2, ...} Z množina celých čísel, tj. {..., -1,0,1, ... } 5 G Z Q množina racionálních čísel, tj. čísel, -\ E Q, 8 G Q, V2~i Q která lze vyjádřit jako podíl celého a přirozeného čísla R množina reálných čísel, y/2 E R, -0, 23 £ R, 7 E R číselná osa, (—00, 00) R+ množina reálných čísel kladných, 7 E R+, 0 ^ 1R+ (0,oo) K+ množina reálných čísel nezáporných, 0 G Rq, -3 i Rq (0,oo) C množina komplexních čísel, tj. čísel tvaru 3 - 2% E C a + bi, kde a, b E R a í je tzv. imaginární jednotka, pro niž platí i2 = —1 66 Symbol Význam Použití symbolu Teorie množin P(A) potenční množina 0 prázdná množina {x G R; 1 x |= -1} {} složené závorky používané při výčtu prvků {1, 2, 3} množina vytvořená vytvořené množiny z prvků 1,2 a 3 G je prvkem, patří do množiny 2 G N i není prvkem, nepatří do množiny -7 £ N c je podmnožinou množiny {1,3} C {1,2,3}, {1,3} C {1,3} n průnik množin {1,3} n {2, 3} = {3} u sjednocení množin {1,3} U {2,3} = {1,2,3} — rozdíl množin {1,3}U{2,3} = {1} M) uspořádaná dvojice prvků a a b (5, —3) je vektor nebo bod o souřadnicích 5 a —3 (ai,.. ., an) uspořádaná n-tice prvků vektor (-6,1,4,5) R x R neboli ÍR2 je množina všech uspořádaných dvojic reálných čísel Ax B kartézský součin, tj. {(a, b); a E A, b E B} R C A x B R je relace z A do B aRb, (a, 6) G R a je v relaci s b aRb, (a, 6) £ iž a není v relaci s b aRb, (a, b) E R a je v relaci s b Logika A konjunkce pAq - platí p a q, je pravdivý výrok p i q V disjunkce p \/ q - je pravdivý alespoň jeden z výroků p, q <^> ekvivalence; právě když p <^> q - výroky p a q jsou ekvivalentní - výrok p je pravdivý, právě když je pravdivý výrok q => implikace p => q - jestliže platí p, pak platí q, - z p vyplývá q Vx P (x) pro všechna x platí -P(x); obecný (velký) kvantifikátor 3x P(x) existuje x, pro které platí -P(x); existenční kvantifikátor 3!x P(x) existuje právě jedno x, pro které platí P(x) 67 Literatura [1] ŠREJDER, Anatoljevič Julij. Binární relace. 1. vyd. Praha : SNTL -Nakladatelství technické literatury, 1978. ISBN 04-309-78. [2] ODVÁRKO, Oldřich; HANULA, Marián; RICHTÁRIKOVÁ, Soňa; ŠEDIVÝ, Jaroslav. Úlohy o relacích a vektorové algebře. 1. vyd. Praha : Státní pedagogické nakladatelství, 1971. ISBN 14-478-72. [3] ODVÁRKO, Oldřich; ŠEDIVÝ, Jaroslav. Binární relace a operace. 1. vyd. Praha : Státní pedagogické nakladatelství, 1978. ISBN 14-057-78. [4] Wikipedia, otevřená encyklopedie. Relace {matematika} [online]. Dostupný z WWW: [5] Wikipedia, otevřená encyklopedie. Kartézský součin [online]. Dostupný z WWW: [6] Wikipedia, otevřená encyklopedie. Zbytkové třídy [online]. Dostupný z WWW : [7] PISKLÁK, Bohuslav. Matematika pro učitele primárního vzdelávaní -Binární relace a zobrazení. 1. vyd. Ostrava : OSTRAVSKÁ UNIVERZITA - Pedagogická fakulta, 2004. ISBN 80-7368-013-0. [8] DLOUHÝ, Zbyněk; FRANĚK, Miloš; MIKULCÁK, Jiří; SMIDA, Jozef; VYŠÍN, Jan; ZEDEK, Miloslav. Komentář pro učitele k používání učebnic matematiky. 1. vyd. Praha : Státní pedagogické nakladatelství, 1969. ISBN 14-803-69. [9] NOVÁK, Bohumil; EBEROVÁ, Jindřiška; STOPENOVÁ, Anna. Základy elementární matematiky v úlohách. 1. vyd. Olomouc : Univerzita Palackého - Pedagogická fakulta, 2004. ISBN 80-244-0853-8. 68 [10] EBEROVÁ, Jindřiška. Základy matematiky 2 pro studenty učitelství 1.stupně ZS. 1. vyd. Olomouc : Univerzita Palackého - Pedagogická fakulta, 2003. ISBN 80-244-0759-0. [11] EBEROVÁ, Jindřiška. Základy matematiky 6. 1. vyd. Olomouc : Univerzita Palackého - Pedagogická fakulta, 2006. ISBN 80-244-1208-X. [12] EBEROVÁ, J., STOPENOVÁ, A. Matematika pro studium vychovatelství osob vyžadujícífchj zvláštní péči. 1. vyd. Olomouc : Univerzita Palackého - Pedagogická fakulta, 1989. ISBN 63-2-10. [13] HLINĚNÝ, Petr. Úvod do informatiky (FI: IB000). 2.1istopadu 2007, Brno: Masarykova univerzita - Fakulta informatiky [14] BĚLÍK, Miroslav. Celá a racionální čísla ve studiu učitelství prvního stupně základní školy. Ústí nad Labem : Univerzita J.E. Purkyně, 2000. ISBN 80-7044-294-8. [15] HORÁK, Pavel. Cvičení z algebry a teoretické aritmetiky I.. 3. vydání. Brno : Masarykova univerzita, 2006. ISBN 80-210-3970-1. 69