03 - Algebraické struktury
pátek 13. května 2016
9:42
Algebraické struktury (grupy, okruhy, obory integrity a tělesa, svazy a Boolovy algebry, univerzální algebry).
[link]
Algebraická struktura je v matematice každá množina, na které jsou definované nějaké operace a daná množina je vzhledem k těmto operacím uzavřená, tzn. že výsledkem operace nad prvky této množiny je vždy také prvek této množiny.
Příklady algebraických struktur
(N; +) - množina přirozených čísel s operací sčítání.
(N; .) - množina přirozených čísel s operací násobení.
(N; +, .) - množina přirozených čísel s operacemi sčítání a násobení.
Booleovy algebry, grupy, okruhy, tělesa, vektorové prostory a svazy jsou algebraické struktury.
Ještě nějaké protipříklady - tj. následující struktury nejsou algebraické:
(N; -) - množina přirozených čísel není vzhledem k operaci odčítání uzavřená. Např. 2 ∈ N, 3 ∈ N, ale 2-3 ∉ N.
(N; :) - množina přirozených čísel není vzhledem k operaci dělení uzavřená. Např. 5 ∈ N, 3 ∈ N, ale 5:3 ∉ N.
Operace
Zobrazení 𝐴𝑛→𝐴 se nazývá n-nární operace (A je množina, 0-nární operace = konstanta)
Zobrazení není definováno pro všechny možné hodnoty operandů (např.: dělění je parciální operace, protože není definováno dělění nulou)
Cayleyova tabulka 
Způsob zápisu definice binárních operací s konečným definičním oborem (řádky jsou hodnoty prvního operandu, sloupce hodnoty druhého operandu, příslušná buňka je výsledek operace)
+
0
1
0
0
1
1
1
1
Cayleyova tabulka pro binární sčítání
Typy operací
Asociativní
Nezáleží na tom, jestli použijeme závorky a v jakém pořadí budeme daný výraz počítat. Příklady asociativních binárních operací je sčítání (+) a násobení (*) reálných čísel.
𝑥∘𝑦∘𝑧=𝑥∘(𝑦∘𝑧)
Komutativní
U komutativních operací nezáleží na pořadí operandů. Příklady takových operací je zase + a *. Konkatenace řetězců není komutativní. Stejně tak odčítání. 
𝑥∘𝑦=𝑦∘𝑥
Distributivní (* distributivní nad +)
Distributivita je vlastnost binární operace, vůči jiné binární operaci. Tedy distributivní operaci můžeme distribuovat přes jinou operaci (např. roznásobení čísel).
𝑥(𝑦 + 𝑧) = 𝑥𝑦 + 𝑥𝑧
(𝑦 + 𝑧)𝑥 = 𝑦𝑥 + 𝑧𝑥
Operace s dělením
Pokud A není prázdná a operace ∘ je asociativní tak plati:
∘ je operace s dělěním
existuje neutrální prvek a každý prvek 𝑥∈𝐴 je invertibilní, tzn. 
Rovnice 𝑎∘𝑥=𝑏 a 𝑦∘𝑎=𝑏 mají v operaci s krácením maximálně jedno řešení. Pokud je operace i asociativní tak mají právě jedno řešení.
Pro konečnou množinu A platí: ∘ je operace s dělením ⇔ ∘ je operace s krácením
Absorpční zákony
(viz Svazy dole)
𝑎∩𝑎∪𝑏=𝑎
𝑎∪𝑎∩𝑏=𝑎
Algebry
Speciální prvky algeber
Neutrální prvek (vzhledem k operaci ∘)
Levý neutrální prvek 𝑒∘𝑥=𝑥
Pravý neutrální prvek 𝑥∘𝑒=𝑥
Neutrální prvek 𝑒∘𝑥=𝑥∘𝑒=𝑥
Existuje nejvýše jeden neutrální prvek pro každou operaci
V multiplikativním značení (pro operace značené jako násobení) jej nazýváme jednotkový prvek (1)
V aditivním značení (pro operace značené jako sčítání) jej nazýváme nulový prvek (0)
Inverzní prvek (k prvku x vzhledem k operaci ∘)
Levý inverzní prvek 𝑦∘𝑥=𝑒
Pravý inverzní prvek 𝑥∘𝑦=𝑒
Inverzní prvek 𝑦∘𝑥=𝑥∘𝑦=𝑒
Pokud existuje inverzní prvek k y, tak y nazýváme ínvertibilní
Pokud je operace asociativní existuje nejvýše jeden inverzní prvek
V multiplikativním značení jej značíme x − 1
V aditivním značení jej značíme − x
A je množina hodnot, I je množina indexů, ωi je ni-nární operace na A pro 𝑖∈𝐼
Typ algebry
Popisuje typy operací v algebře. Např.: (2, 2, 1) je algebra s dvěma binárními a jednou unární operací
Grupy
Grupy jsou algebry s jednou binární operací (a případně několika unárními operacemi)
Grupa formalizuje koncept symetrie.
Příklad grup
Celá čísla s operací sčítání (Z,+,0,−1).
Okruhy, obory integrity, tělesa, pole
Okruhy atd. jsou algebry s dvěma binárními operacemi + a * (a případně několika unárními operacemi)
Operace + tvoří abelovskou grupu (splňuje axiomy Abelovské grupy)
nulový prvek = 0 = neutrální prvek pro operaci +
jednotkový prvek = 1 = neutrální prvek pro operaci *
Operace * je distributivní nad + (* splňuje axiomy pologrupy)
Příklady
Okruh - celá čísla s operacemi + a *
Těleso - množina racionálních čísel
Obor integrity
Obor integrity je komutativní okruh R s jednotkovým prvkem, pro který navíc platí tak podmínka v tabulce, přičemž  𝑅\{0} značí množinu bez nulového prvku.
Těleso
Je rozšířením okruhu, oproti kterému navíc přináší existenci inverzního prvku pro obě binární operace (okruh vyžadoval existenci inverzního prvku jen pro operaci +).
Pole
Pole (Komutativní těleso, angl. field) je takové těleso, jehož obě operace jsou komutativní. V tělese (okruhu) se předpokládá komutativita pouze sčítání.
Svazy a Booleovy algebry
Definice č. 1: Svaz je uspořádaná množina, která je doplněna o vlastnost, že pro každé dva prvky z daného svazu musí existovat supremum a infimum, které také náleží danému svazu.
Definice č. 2: Algebry s dvěma binárními operacemi ∩ a ∪ (a případně několika unárními operacemi)
Obě operace mají stejné vlastnosti - binární operace, označují supremum a infimum dvouprvkové množiny.
Pro obě operace musí platit:
Idempotence (plyne z absorpce)
Komutativita
Asociativa
Absorpce
nulový prvek = 0 = neutrální prvek pro operaci ∪
jednotkový prvek = 1 = neutrální prvek pro operaci ∩
Komplementární prvky: 𝑎∩𝑎′=0 a 𝑎∪𝑎′=1
Jednotkový prvek a nulový prvek jsou komplementární: 0′=1, 1′=0
Příklady
Booleova algebra - Dvouprvková algebra je algebra nad množinou A = {0, 1}, kde operace jsou dány přirozeným způsobem, tj. 0 a 1 jsou vzájemně komplementární a protože platí 0 < 1, průsek (infimum) je menší z operandů, spojení (supremum) je větší z operandů:
Booleova algebra
Booleova algebra je algebraická struktura, která zobecňuje vlastnosti množinových a logických operací.
Je to šestice (𝐴,∩,∪,−,0,1), kde A je neprázdná množina, 0 ∈ A je nejmenší, 1 ∈ A největší prvek, − je unární operace (doplněk neboli komplement) a ∩, ∪ jsou binární operace (průsek a spojení) na A, splňující následující axiomy.
Věta o komplementech v Booleově algebře
𝑎′′=𝑎
Relace uspořádání a svazy
(Částečně) uspořádaná množina
množina na které je definována relace (obvykle značíme ≤) částečného uspořádání
každá podmnožina uspořádané množiny je také uspořádaná
Sousední prvky - prvky a, b mezi nimiž je relace ≤ a neexistuje žádný prvek c mezi nimi tj. takový, že a < c < b
Hasseův diagram - graf, kde uzly jsou prvky množiny a hrany jsou mezi prvky, které jsou sousední dle relace ≤
Lineárně uspořádaná množina (řetězec)
částečně uspořádaná množina pro kterou platí srovnatelnost (u každých dvou prvků lze rozhodnout, který "je větší")
Nejmenší/největší prvek množiny
všechny ostatní prvky množiny jsou větší/menší než nejmenší/největší prvek množiny
existuje vždy nejvýše jeden nejmenší/největší prvek
Maximální/minimální prvek množiny
žádný prvek není větší/menší než maximální/minimální prvek
může jich být více
Dolní/horní závora množiny 𝑴⊂𝑵
prvek z nad-množiny N, který je menší/větší než všechny ostatní prvky podmnožiny M
nejmenší/největší prvek je dolní/horní závora
interval (0,1) má dolní závoru například čísla -2, 0, -88
Infimum inf(M)
největší dolní závora
 Infimum je zaváděno jako alternativa k pojmu nejmenší prvek
(0,1), <0,1>, (0,1> - tyto všechny intervaly mají infimum rovno číslu 0.
Supremum sup(M)
nejmenší horní závora
omezené otevřené intervaly reálných čísel nemají největší prvek, ale mají supremum
(0,1), <0,1>, (0,1> - tyto všechny intervaly mají supremum rovno číslu 1.
Příklady algebraických struktur:
struktura
příklad
Abelovská grupa
(Z,+)
Monoid (+ komutat.)
(Z,*)
Obor integrity
(Z, +, *, 0, 1)
Pole
(Q, +, *, 0, 1)
Svaz
Potenční množina
Boolova algebra
({0,1}, AND, OR, NOT, FALSE, TRUE)
Notes
2. Otazka (predmet) (okruh): Algebraické struktury (grupy, okruhy, svazy (v závorce psáno že se mám zaměřit na ně zaměřit)).
Kdo me primarne zkousel: Holík 
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Začal jsem pěkně postupně grupou, vyjemoval její vlastnosti. Pak sem přešel k okruhu a za boha jsem si nemohl vzpomenout na jednu z těch tří podmínek ... po chvíli ale ze mě vylezlo, že samozřejmě - pologrupa nad násobením. Pak jsem zmínil svazy z dvou pohledů : částečného uspořádání a algebraicky. Popsal jsem podmínky. Holíka zajímal pohled z pohledu uspořádání. Tak jsem mu povykládal co je závora (horní/dolní) a že svaz musí mít infimum a supremum. Trochu sme se v začátku nerozuměli, ale cajk. Přetáhl jsem budík asi jen o 2 minutky.
From <[link]> 
1. Otazka (predmet) (okruh): Algebraické struktury (grupy, okruhy, obory integrity a tělesa, svazy a Boolovy algebry, univerzální algebry)
Kdo me primarne zkousel: Ing. Zdeněk Vašíček, Ph.D. 
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Začala jsem obecně, že algebra je (A, w_i) a že jsou na nich binární, unární a další operace. Následně jsem popsala, že algebry nad grupama mají jednu binární operaci a algebry nad okruhy dvě binární operace. Pak chtěl nějaké konkrétní příklady, tak jsem definovala grupoid, grupu a abelovskou grupu. Dále jsem se měla přesunout k algebrám se dvěma binárními operacemi, tak jsem popsala okruh a obor integrity a byl konec. Vašíček byl moc hodný a snažil se mě vždy navést na téma, o kterém mám mluvit. Mluvila jsem lehce zmateně, ale výsledná za A.
From <[link]> 
1. Otazka (predmet) (okruh): MAT Algebraicke struktury
Kdo me primarne zkousel: Externista - Šaloun Petr, doc. RNDr., Ph.D.
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Zacal som rovno s grupami, zadefinoval asociativny zakon, neutralne prvky. Externista sa cely cas usmieval a pritakaval, zabudol som do definicie asociativneho zakonu vlozit formalizmy ako "pre kazde a,b,c z nosnej mnoziny". Ku okruhom, zvazom som sa nedostal. Asi za tie formalizmy mi dali B
From <[link]> 
2. Otazka (predmet) (okruh): 3. Algebraické struktury (měl jsem se zaměřit na grupy, okruhy, obory integrity a tělesa)
Kdo me primarne zkousel: Steingartner William, Ing., Ph.D. (vlastně jenom on)
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Začal jsem tím, co je to algebra, pak řekl, že s jednou operací to může bát grupoid, pokud je asociativní. Z grupoidu jsem šěl klasicky (a zapisoval na tabuli) pologrupu -> monoid -> grupu (tady jsem zapomněl, čím se vyznačuje, ale když řekl, což tam dát nějakou operaci, tak jsem si vzpomněl na invertibilní prvky). Pak jsem šel na okruhy, kde jsem řekl, že ta množina s + a 0 je komutativní grupa (a zadefinoval komutativitu) a že s * a 1 je to pologrupa. Pak jsem zapomněj ještě na distributivitu, ale připomněl mi ji a zapsal jsem ji. Stačilo jim a poslali me ven. Výsledek A.
From <[link]> 
2. Otazka (predmet) (okruh): 3. Algebraické struktury (Booleovy svazy a algebry)
Kdo me primarne zkousel: Češka
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Definoval jsem svaz jako algebraickou strukturu, a postupně jsem se dostal až k Booleově svazu. Češka se pak zeptal jestli lze definovat svaz i jinak, řekl jsem, že přes poset a zbytek zkoušení byla rozprava na toto téma. Sem tam jsem věděl, sem tam mi Češka pomohl. Bylo vidět, že mi chybí spojitosti. Známka C.
From <[link]> 
1. Otazka (předmět) (okruh): 1. (MAT) Algebraické Struktury - Zaměření na Svazy a Boolovy algebry.
Kdo me primarne zkousel: Češka
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Začal jsem hned motivací, kde se svazy používají (statická analýza), nadefinoval jsem obě možnosti zápisu a možnosti převodu, párkrát jsem se zasekl, ale Češka nijak nepotápěl. Pak se ptal na velikost svazu (řekl jsem, že 2^(počet atomů)) a pak se zeptal na nejmenší svaz (chtěl slyšet Boolův, že má dva prvky 1 a 0), k tomu mě nakonec navedl a jak souvisí tento svaz s ostatními svazy, chvíli jsem nechápal, ale nakonec sem odpověděl, že se používá součin svazů, což chtěl slyšet. Nakonec otázka Tomáš V., že mám říct nějakou větu o svazích, tak jsem mu odvyprávěl Knaster Tarski Teorém, z čehož byl spokojen. Ještě jeden menší dotaz ohledně ordinál, ale to jsem věděl a určitě byl trochu nad rámec této problematiky 
From <[link]> 
2. Otazka (předmět) (okruh): 3 Algebraické struktury - svazy
Kdo me primarne zkousel: prof. Češka
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Absolutně jsem netušil co to jsou svazy. Nakreslil jsem hasseův diagram a tím to skončilo. Potom jsem dostal pár dotazů na ano/ne a pokaždé jsem odpověděl špatně. Na závěr se zeptal co je to grupa. Před zkouškou jsem to věděl, ale tam se mi to úspěšně vykouřilo z hlavy. Známka: F.
From <[link]> 
2. Otazka (předmět) (okruh): 3. Algebraické struktury (na štítku bolo len "Grupy, Okruhy") (MAT)
Kdo me primarne zkousel: Rogalewicz
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Len som zadefinoval Grupu, opýtal sa ma, či (N,+) je grupa, povedal som, že nie (niesú inverzné prvky), tak či (Z,+) teda je, alebo nieje grupa. Potom chcel len zadefinovať okruh. Ešte som sa aj sekol a povedal, že s jednou tou operáciou je to Abelovska grupa a s druhou pologrupa. Povedal, že tam nemusí byť k tej druhej operácii neutrálny prvok, tak som sa opravil, že teda monoid a povedal, že mu to stačí. Celkovo táto otázka asi dve minúty (nedošlo na budík). Dal mi A.
From <[link]> 
1. otazka (okruh): Algebraické struktury (3) 
Kto ma primarne skusal: Vojnar
Co som k tomu povedal/na co sa ma pytali:
Vzhladom na to ze MAT som bol dost biedne nauceny tak to bolo celkom peklo. Nastastie bol Vojnar so mnou celkom trpezlivy. Chcel vediet vsetko o svazoch. Na polovicu veci som si vedel spomenut ale zvysok vlastnosti zo mna tahal az z paty. Bola to dost bieda z mojej strany ale oni sa ma snazili dokopat k tomu aby som im povedal to co chceli pocut. Celkovo to trvalo tak cez 10 minut. Musim dat Vojnarovi bludistaka za pevne nervy a dost velku benevolenciu k absencii mojich vedomosti 
From <[link]> 
1. Otazka (okruh): algebraicke struktury a homomorfizmy
Kdo me primarne zkousel: Ceska
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: fail fail fail, vsetko som to chapal a nedokazal to zo seba vyklopit, ked sa ceskovi nepodarili zo mna dostat teoriu tak sa zacal pytat na konkretne pripady algebier a homomorfizmov, velmi pomahal a bol prijemny a slusny, zachranila ma diplomka a dostal som za D, inak by som mal urcite E
From <[link]> 
1. Otazka (okruh):3: Algebraické struktury
Kdo me primarne zkousel: Rogalewicz
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Byl jsem trošku zmatený. Chtěl po mě jenom Grupy. Jsem chtěl říct celou tu hierarchii grupoid->...-> grupy..Ale ho zajimali pouze grupy a jejich vlastnosti. Ale vše jsem věděl, na vše odpovídal. Výsledná B.
From <[link]> 
2. Otazka (predmet) (okruh): 3. Algebraické struktury (Booleovy svazy a algebry)
Kdo me primarne zkousel: Češka
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Definoval jsem svaz jako algebraickou strukturu, a postupně jsem se dostal až k Booleově svazu. Češka se pak zeptal jestli lze definovat svaz i jinak, řekl jsem, že přes poset a zbytek zkoušení byla rozprava na toto téma. Sem tam jsem věděl, sem tam mi Češka pomohl. Bylo vidět, že mi chybí spojitosti. Známka C.
From <[link]> 