Teoretická informatika Tomáš Foltýnek Algebra Struktury s jednou operací

Teoretická informatika Tomáš Foltýnek [email protected]

Algebra Struktury s jednou operací

Teoretická informatika

Proč zavádíme algebru

•  hledáme nástroj pro popis objektů reálného světa (zejména pak matematiky) a pro popis operací s těmito objekty •  chceme tento nástroj budovat postupně od nejjednodušších objektů (univerzálních) po úzce specializované objekty

2


Základní pojmy •  Každý objekt je reprezentován –  datovým nosičem – množina popisující data, se kterými pracujeme –  operacemi – nejjednoduššími transformacemi, které nad daty můžeme provádět

•  Binární operace na množině je zobrazení A × A → A, obvykle použijeme infixový tvar pro zápis operace a ⋅ b

3


Grupoid •  Nejuniverzálnějším objektem je grupoid (A, ⋅), což je datový nosič A s jednou operací ⋅ •  Jedinou vlastností je fakt, že užitím operace na libovolné dva prvky z A dostaneme opět prvek z A. Tedy množina A je vzhledem k operaci ⋅ uzavřená. •  Zavádíme pojem komutativní grupoid ∀a,b ∈ A: a ⋅ b = b ⋅ a

4


Pologrupa •  Pro asociativní operaci platí ∀a,b,c ∈ A: (a ⋅ b) ⋅ c = a ⋅ (b ⋅ c) •  Pologrupa (A, ⋅) je grupoid s asociativní operací •  POZOR! Vlastnosti grupoidu zůstávají •  Opět můžeme hovořit o komutativní pologrupě, pokud je operace navíc komutativní •  Opakovanou aplikací operace na tentýž prvek získáme mocninu –  v monoidu (A, ⋅) označíme an = a⋅a⋅ ... ⋅a (n-krát) pro lib. n∈N

5


Neutrální prvek •  Levý neutrální prvek je takové e ∈ A, které splní ∀a ∈ A: e ⋅ a = a •  Analogicky pravý neutrální prvek je takové e ∈ A, kde ∀a ∈ A: a ⋅ e = a •  Levých neutrálních prvků může být více, pokud nejsou žádné pravé (a naopak). •  Obsahuje-li pologrupa levý a pravý neutrální prvek, pak se musí jednat o tentýž prvek, který se nazývá neutrální prvek –  důkaz: el = el ⋅ ep = ep

6


Monoid •  Monoid (A, ⋅) je pologrupa s neutrálním prvkem •  Monoid je tedy množina s operací, kde platí uzavřenost, asociativní zákon a existuje neutrální prvek (oboustranný). •  V případě komutativní operace hovoříme o komutativním monoidu.

7


Inverzní prvek •  Mějme monoid (A, ⋅) s neutrálním prvkem e •  Pak b ∈ A je levý (resp. pravý) inverzní prvek k a ∈ A, pokud platí b ⋅ a = e (resp. a ⋅ b = e) •  Inverzní prvek je pak takový prvek, který splní a ⋅ b = b ⋅ a = e •  Inverzní prvek k prvku a značíme a-1

8


Grupa •  Je dán monoid (A, ⋅), kde je a ∈ A, e neutrální prvek, l levý inverzní prvek k a a p pravý inverzní prvek k a. Pak platí: p = e ⋅ p = (l ⋅ a) ⋅ p = l ⋅ (a ⋅ p) = l ⋅ e = l –  Z uvedeného plyne, že l = p

•  V monoidu tedy neexistuje nic jako levý a pravý inverzní prvek! •  Grupa (A, ⋅) je monoid, kde ke každému prvku existuje prvek inverzní •  Opět hovoříme také o komutativní grupě

9


Řád prvku a řád grupy •  Řád prvku a grupy (G, ⋅) je nejmenší přirozené číslo n takové, že an = e. •  Pokud takové n neexistuje, pak a má řád 0. •  Řádem grupy se nazývá mohutnost, tj. počet prvků její nosné množiny.

10


strana 11

Zbytkové třídy •  Pro dané číslo n ∈ N definujeme na množině Z relaci ρ takto: a ρ b ⇔ a ≡ b (mod n) ⇔ n | a-b

–  Tedy v relaci jsou spolu právě taková čísla a a b, která dávají po dělení n stejný zbytek

•  Relace ρ je relací ekvivalence na množině Z. •  Této relaci přísluší rozklad Z/ρ –  značí se Zn –  jednotlivé prvky (třídy) rozkladu se nazývají zbytkové třídy a značí se [a]n •  tedy [a]n = {a + kn | k ∈ Z}


strana 12

Operace se zbytkovými třídami •  Na množině zbytkových tříd modulo n lze definovat operace + a * takto: –  [a]n + [b]n = [a+b]n –  [a]n ⋅ [b]n = [a⋅b]n

•  Operace jsou korektně definovány pomocí reprezentantů •  Modulární aritmetika; aplikace v kryptografii •  Množina zbytkových tříd je uzavřená vzhledem k operacím sčítání a násobení


strana 13

Grupy zbytkových tříd •  Algebraická struktura (Zn,+) je komutativní grupa pro libovolné n –  operace je uzavřená, komutativní a asociativní –  existuje neutrální prvek e = [0]n –  ke každému prvku [a]n existuje inverzní prvek [-a]n

•  Algebraická struktura (Zn, ⋅) je komutativní monoid pro libovolné n

–  operace je uzavřená, komutativní a asociativní –  existuje neutrální prvek e = [1]n –  inverzní prvky obecně existovat nemusí


strana 14

Invertibilní prvky •  Prvky, k nimž existuje inverze •  Třída [a]n má inverzi ⇔ NSD(a,n)=1 –  plyne z Bezoutovy rovnosti

•  Vypustíme-li všechny třídy soudělné s modulem (včetně nulové), získáme grupu zbytkových tříd – značíme (Zn*,⋅)


15

Tradiční matematické příklady •  •  •  •  •  •  •  •  •  •  • 

(N, +) (N0, +) (N, ⋅) (Z, +) (Z, ⋅) (Q, +) (Q, ⋅) (Q-{0}, ⋅) (Zn, +) (Zn, ⋅) (Zn*, ⋅)

komutativní pologrupa komutativní monoid komutativní monoid komutativní grupa komutativní monoid komutativní grupa komutativní monoid komutativní grupa komutativní grupa komutativní monoid komutativní grupa


Vlastnosti struktur •  V pologrupách nezáleží na uzávorkování •  V komutativní grupoidech nezáleží na pořadí •  V pologrupách definujeme mocninu an jako aplikaci operace na n činitelů a •  Mocnina se zápornými n se definuje jako inverze na mocninu •  V monoidu existuje také a0 = e •  V grupě je inverzí k prvku a ⋅ b prvek b-1 ⋅ a-1 •  Lze dokázat (v monoidu) platnost am ⋅ an = am+n, (am)n = am⋅n

16


17

Příklady • 

Na konečné množině A = {@, #, $, %} je možno zadat operaci * tabulkou. –  Rozhodněte, zda je operace * komutativní a asociativní –  Existuje v grupoidu (A,*) neutrální prvek? –  Pokud ano, existuje ke každému prvku inverzní prvek?

•  •  •  • 

Ukažte, že ({a,b}+, ·) je pologrupa, ale není monoid. Určete řád prvku 5 v grupě (Z7, +) Určete řád prvku 3 v grupě (Z5*, ·) Určete vlastnosti struktur ({0,1},+) a ({0,1},·)

*

@

#

$

%

@

@

@

@

@

#

@

#

@

#

$

@

@

$

$

%

@

#

$

%


Podstruktury •  Nechť (A,*) je grupoid / pologrupa / monoid / grupa a nechť B⊆A. Jestliže je i (B,*) grupoid / pologrupa / monoid / grupa, nazýváme jej / ji podgrupoid / podpologrupa / podmonoid / podgrupa. •  Například (S0, +) je podmonoidem monoidu (N0, +), kde S značí množinu všech sudých přirozených čísel.

18


Podgrupy •  (H, ⋅) je podgrupou grupy (G, ⋅) právě tehdy, když: –  –  –  – 

H⊆G e∈H a ∈ H ⇒ a-1 ∈ H a,b ∈ H ⇒ a ⋅ b ∈ H

•  Pomocí množiny M ⊆ G můžeme generovat podgrupu (M, ⋅) grupy (G, ⋅) – hovoříme o podgrupě generované množinou M •  Grupa generovaná jednoprvkovou množinou se nazývá cyklická

19

Teoretická informatika Tomáš Foltýnek Algebra Struktury s jednou operací

Recommend Documents