Základy matematiky a statistiky pro humanitní obory 1 Pavel Rychlý Vojtěch Kovář Fakulta informatiky, Masarykova univerzita Botanická 68a, 602 00 Brno, Czech Republic {pary, xkovar3}@fi.muni.cz část 5 Pavel Rychlý, Vojtěch Kovář (Fl MU Brno) PLIN004 čá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 ► (a, 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ýž prvků je první ► jsou možné i jiné definice? Jaké? ► Uspořádané n-tice (kde n je přirozené) ► trojice (a, b, c) = (a, (b, c)) ► obecně (ai, a2, a3,an) = (ai, (a2, (a3, (..., an)...))) ► (funguje jen pro konečné n) Pavel Rychlý, Vojtěch Kovář (Fl MU Brno) PLIN004 čá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 ► A x B = {(a, b) | 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)\aeA A b e B A c e C} ► podobně pro větší n Pavel Rychlý, Vojtěch 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 Pavel Rychlý, Vojtěch Kovář (Fl MU Brno) PLIN004 čá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 čá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) e AxA \ a e A} ► Relace větší nebo rovno na přirozených číslech ► > (A/) - binární relace ► > (A/) = {(a, b) e NxN \ b C a} ► (podle množinové konstrukce přirozených čísel - viz minulá přednáška) ► Relace plus na přirozených číslech ► +(A/) - ternární relace ► +(/V) = {(a, b, c) e NxNxN \ a + b = c} ► a + b = c je jen jiný zápis pro (a, b, c) € +(A/) ► —>• 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 e A{ (a, a)eR) ► 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) PLIN004 čá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ě R(0) ► je 0 (podmnožina 0x0) ► —>• ekvivalence i uspořádání ► (pro všechny prvky prázdné množiny platí kde co) Pavel Rychlý, Vojtěch Kovář (Fl MU Brno) PLIN004 část 5 10/15 Relace Vlastnosti relací 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 /v. / 1^ ► množina těchto ,,ostrůvků" 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 = {AX \ xeA} Pavel Rychlý, Vojtěch Kovář (Fl MU Brno) PLIN004 část 5 13/15 Definice celých čísel a + d = b + c ► Uvažujme množinu dvojic přirozených čísel ► D = {(a, b) e NxN} ► ... spolu s ekvivalencí R ((a,b),(c,d))eR = ► Uvažujme rozklad podle této ekvivalence ► třídy rozkladu jsou D3t, = {{x,y) \ {{x, y), (a, b)) e R} ► rozklad D jR odpovídá množině {Da£> | a, b € N} ► Tento rozklad je konstrukcí celých čísel Z ► každá třída Da ^ odpovídá číslu a — b Pavel Rychlý, Vojtěch Kovář (Fl MU Brno) PLIN004 Sást 5 14/15 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ý, Vojtěch Kovář (Fl MU Brno) PLIN004 část 5 15/15