Základy matematiky a statistiky pro humanitní obory 1 Pavel Rychlý Vojtěch Kovář Fakulta informatiky, Masarykova univerzita Botanická 68a, 60200 Brno, Czech Republic {pary, xkovar3}(9fi .muni . cz část 5 Pavel Rydily, Vojtech Kovář (Fl MU Brno) PI INOfM část 5 1 / 15 Obsah přednášky Obsah přednášky Uspořádané dvojice, n-tice Relace Rozklad podle ekvivalence Celá čísla Pavel Rychlý, Vojtěch Kovář (Fl MU Brno) PLIN004 část 5 2/15 Uspořádané dvojice, n-tice Uspořádaná dvojice Uspořádaná dvojice ► (». b) ► má první a druhý prvek ► -> na rozdíl od množiny záleží na pořadí prvků ► Definice pomocí množin ► (a, b) = {{a}, {a, b}} *■ takto jednoznačně rozlišíme, který z prvků je první ► jsou možné i jiné definice? Jaké? ► Uspořádané n-tice (kde n je přirozené) ► trojice (a, b, c) = (a, (£>, c)) *■ obecně (aj, a2, a3,an) = (ai, (a2, (a3, (..., a„)...))) ► (funguje jen pro konečné rí) Pavel Rychlý. Vojtěch Kovář (Fl MU Brno) ľl 1 1 > > část 5 3/15 Uspořádaní' dvojice, n-tice Kartézský součin Kartézský součin ► Kartézský součin dvou množin A, B - Ax B = {(a, b) 1 a e A A b e B} ► —> množina uspořádaných dvojic prvků z A a B ► Kartézský součin více množin ►• analogicky - obsahuje uspořádané n-tice ►• A x B x C = {(a, b, c) \ a e A A be B A c e C} > podobně pro větší n Pavel Rychlý, Vojtech Kovář (Fl MU Brno) PLIN004 Ěást 5 4 / 15 Relace Relace Relace ► Motivace ► způsob, jak v matematice svázat dvě hodnoty (případně více) ► vyjadřujeme, že objekty (množiny) v relaci mají něco společného ► Binární' relace ► množina uspořádaných dvojic ► —> podmnožina kartézského součinu ► n-ární relace *■ množina uspořádaných n-tic ľ.iv. 1 Kýchly, \A,jl(,:li Kovář (Fl MU Brno) Pl INIKM Eást 5 5/15 Relace Relace Relace ► Často říkáme „relace na množině A" ► tzn. podmnožina součinu AxA ► resp. A x A x ... x A ► Přehledný zápis binárních relací ► tabulkou ► grafem Pavel Rychlý, Vojtěch Kovář (Fl MU Brno) PLIN004 Eást 5 6/15 Relace Relace - příklady Relace - příklady ► Relace identity na množině A ► ld(A) - binární relace ► ld(A) = {(a, a) e AxA a 6 A} ► Relace větší nebo rovno na přirozených číslech ► > (A/) - binární relace ► >{N) = {(a, b) e NxN í C 3} ►• (podle množinové konstrukce přirozených čísel - viz minulá přednáška) ► Relace plus na přirozených číslech ► +(A/) - ternární relace ► +(«) = {(a, b, c) e NxNxN | a + b = c} ► a + b = c je jen jiný zápis pro (a, b, c) e +{N) ► —> všechny operace na číslech jsou relace Pavel Rychlý, Vojtěch Kovář (Fl MU Brno) PLIN004 část 5 7 / 15 Relace Vlastnosti relací Vlastnosti binárních relací ► Už jste se s nimi setkali jinde ► Reflexivita ► R(A) je reflexivní, právě tehdy, když ► Va eA[ (a, a) G R ) ► Symetrie ►■ R(A) je symetrická, právě tehdy, když ► Va, b e A( (a, b) e R =ž> (b, a) e R ) ► Antisymetrie ► R(A) je antisymetrická, právě tehdy, když ► Va, b e A( (a, b) e R A (b, a) e R a = b ) Pavel Rychlý, Vojtěch Kovář (Fl MU Brno) PLIN004 Ěást 5 8/15 Relace Vlastnosti relací Vlastnosti binárních relací (2) ► Tranzitivita ► R(A) je tranzitivní, právě tehdy, když ► Va, b, c e A( (a, b) e R A {b, c) e R ^ (a, c) e R ) ► Ekvivalence ► R(A) je ekvivalence, právě tehdy, když je současně reflexivní, symetrická i tranzitivní ^ Uspořádání ► R(A) je uspořádání, právě tehdy, když je současně reflexivní, antisymetrická i tranzitivní Pavel Rychlý, Vojtěch Kovář (Fl MU Brno) l'l INIKM část 5 9/15 Relace Vlastnosti relací Vlastnosti binárních relací - příklady ► Identita na libovolné množině ► splňuje všechny výše uvedené vlastnosti ► -> ekvivalence i uspořádání ► Relace < na přirozených číslech ► není symetrická ► —> uspořádání ► Relace < na přirozených číslech ► není symetrická ani reflexivní ►• —> ani ekvivalence, ani uspořádání ► Relace na prázdné množině /?(0) ► je 0 (podmnožina 0x0) ► —> ekvivalence i uspořádání ► (pro všechny prvky prázdné množiny platí kde co) Pavel Rychlý, Vojtech Kovář (Fl MU Brno) ľl INIHM část 5 10 / 15 Relace Vlastnosti relaci Další příklady relací ► Diskutujte jejich vlastnosti ► pro malé množiny je zkuste zakreslit ► Relace ,,sedí vedle" na přítomných studentech ► Relace „sedí ve stejné řadě jako" na přítomných studentech ► Relace „je dělitelem" na přirozených číslech ► Relace „krát" (*) na přirozených číslech ► Relace „má stejný zbytek po vydělení 2" na přirozených číslech Pavel Rychlý. Vojtěch Kovář (Fl MU Brno) PLIN004 část 5 11/15 Rozklad podle ekvivalence Ekvivalence a rozklad ► Ekvivalence na množině A *■ reflexivní, symetrická, tranzitivní ► díky těmto vlastnostem vytvoří „ostrůvky" ► —> podmnožiny, v nichž každý prvek je v relaci s každým ► —> žádný prvek není v relaci s žádným prvkem z jiné podmnožiny ^\ > Rozklad podle ekvivalence /-^ / ^ *■ množina těchto „ostrůvků" #V Pavel Rychlý. Vojtěch Kovář (Fl MU Brno) PLIN004 část 5 12/15 Rozklad podle ekvivalence Ekvivalence a rozklad ► Třída ekvivalence ► „jeden ostrůvek" ► Ax = {a e A | (a,x) e R} ► Rozklad množiny A podle ekvivalence R ► A/R = {A | x e A} Pavel Rychlý, Vojtěch Kovář (Fl MU Brno) PLIN004 část 5 1 1 / \r> Celá čísla Definice celých čísel ► Uvažujme množinu dvojic přirozených čísel ... ► D = {(a,b) e NxN} ► ... spolu s ekvivalencí R ► ((a, b), (c, d)) e R = a + d = b+c ► Uvažujme rozklad podle této ekvivalence ► třídy rozkladu jsou D3tt> = {(x,y) | ((x,y), (a, b)) e R} ► rozklad D j R odpovídá množině {D3it, a, b G N} ► Tento rozklad je konstrukcí celých čísel Z ► každá třída D3^ odpovídá číslu a — b Pavel Rychlý, Vojtěch Kovář (Fl MU Brno) ľl INÍHM část 5 M / \r> Celá čísla Náměty k přemýšlení ► Jak bude vypadat definice operací + a * na celých Číslech? ► nápověda: s využitím příslušných operací nad přirozenými čísly ► Jak bude vypadat definice operace odečítání na celých číslech? ► nápověda: s využitím operace + ► Jak by vypadala definice racionálních čísel ► nápověda: použijeme podobnou konstrukci jako v případě celých čísel ► místo sčítání bude násobení ► příslušná třída rozkladu bude odpovídat podílu ► opět zkuste přemýšlet o definicích operací +, *, —, / Pavel Rychlý, Vojtech Kovář (Fl MU Brno) PLIN004 část 5 15 / 15