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}flfi.muni.cz část 5 Pavel Rychlý. Vojtěch Kovář (Fl MU Brno) II IJjj čast 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) rill> čas: 5 / /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ý 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ě (aj, a2,a3,an) = (a1,(a2, {a3, (..., an)...))) ► (funguje jen pro konečné n) Pavel Rychlý, Vojtech 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) aeA 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)\aeAAbeBAceC} *■ 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, a) e AxA \ a 6 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 ► +(«) = {(a, b, c) e NxNxN a + b = c} ►■ a + b = c je jen jiný zápis pro (a, b, c) e +(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) e R ) ► Symetrie ► R(A) je symetrická, právě tehdy, když \/a,be A( (a,b) 6 R (b,a) e R ) ► Antisymetrie ► R(A) je antisymetrická, právě tehdy, když ► Va, b e A( (a, b) 6 R A [b, a) £ R => a = b ) Pavel Rychlý, Vojtěch Kovář (Fl MU Brno) PLIN004 část 5 H / \r, Relace Vlastnosti relací Vlastnosti binárních relací (2) ► Tranzitivita ►• R(A) je tranzitivní, právě tehdy, když ► Va,b,ceA( (a,fa) e R A (b, c) e R => (a, c) e /? ) ► 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) II IJjj čá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ý. Vojtěch Kovář (Fl MU Brno) čá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 s\ ► Rozklad podle ekvivalence /v / ^ ► množina těchto „ostrůvků 9-J 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) € R} ► Rozklad množiny A podle ekvivalence R ► A/R = {Ax | x e A} Pavel Rychlý. Vojtěch Kovář (Fl mu Brno) PLIN004 část 5 13 / 15 Cc-l.i ;:i:,l.i Definice celých čísel ► Uvažujme množinu dvojic přirozených čísel ... *■ D = {(a, b) e NxN} ► ... spolu s ekvivalencí R > ((a, Ď), (c, d)) e R = 3 + d = b+c ► Uvažujme rozklad podle této ekvivalence ► třídy rozkladu jsou D3i£> = {(x, y) ((x, y), (a, b)) G R} > rozklad D/R odpovídá množině {D3^ a,6eM} ► 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) PLIN004 část 5 14/15 Cela čísla Náměty k přemýšleni ► 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