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}@íi.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) ee {{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, (b, c)) ► obecně (ai, a2, a3,an) = (ai, (a2, (a3, (..., a„)...))) ► (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 Ax 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) \ a e A A b (E B A ceC} ► 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 A x A ► 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, a) eAxA\aeA} ► Relace větší nebo rovno na přirozených číslech ► > (N) - binární relace ► > (/V) = {(a, b) e NxN ď C a} ► (podle množinové konstrukce přirozených čísel - viz minulá přednáška) ► Relace plus na přirozených číslech ► +(N) - ternární relace ► +(/v) = {(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 e A{ (a, a)eR) ► Symetrie ► R(A) je symetrická, právě tehdy, když ► Va,Ďe^( (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(9) ► 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 / ]^ ( J C\ ► 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 I (a,x) e R} ► Rozklad množiny A podle ekvivalence R ► A/R = {Ac | x e /4} Pavel Rychlý, Vojtěch Kovář (Fl MU Brno) Sást 5 13/15 Definice celých čísel a + d = ď + 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 Dab = {(x,y) | ((x,y), (a, £>)) e /?} ► rozklad D//? odpovídá množině {£>a£> | a, Ď e N} ► Tento rozklad je konstrukcí celých čísel Z ► každá třída Dat, odpovídá číslu a — b Pavel Rychlý, Vojtěch Kovář (Fl MU Brno) 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 eást 5 15/15