No title

Uspořádání doc. RNDr. Josef Kolář, CSc. Katedra teoretické informatiky FIT České vysoké učení technické v Praze c

Josef Kolar, 2014

Základy diskrétní matematiky, BI-ZDM ZS 2014/15, Lekce 4 https://edux.fit.cvut.cz/courses/BI-ZDM/

Evropský sociální fond. Praha & EU: Investujeme do vaší budoucnosti doc. Josef Kolář (FIT ČVUT)

Uspořádání

ZDM, ZS 2014/15, Lekce 4

1 / 16

Částečné uspořádání

Částečné uspořádání Co je to částečné uspořádání? Částečné uspořádání (nebo prostě jen uspořádání) je relace, která dovoluje prvky nějaké množiny porovnat podle nějakého kritéria “prvek a patří před prvek b”. Takové porovnání v posloupnosti různých hodnot ovšem nemusí být použitelné k získání seřazené permutace prvků dané posloupnosti, jako je tomu u problému řázení v programování.

Definice 1 ( částečné uspořádání) Binární relaci R na množině X nazýváme částečným uspořádáním, pokud je reflexivní, antisymetrická a tranzitivní. Dvojici (X, R) pak nazýváme částečně uspořádánou množinou neboli poset. Připomeneme: (RE): ∆X ⊆ R,

(ANS): R ∩ R−1 ⊆ ∆X , (TR): R ◦ R ⊆ R

doc. Josef Kolář (FIT ČVUT)

Uspořádání


2 / 16


Uspořádání - příklady Příklad 2 Následující příklady ukazují jak uspořádání, tak i relace, které uspořádáními nejsou: 1

2

3

4

5

“neostré” uspořádání x ≤ y čísel (přirozených, celých, racionálních, reálných) podle velikosti je relací (částečného) uspořádání “ostré” uspořádání x < y čísel (přirozených, celých, racionálních, reálných) podle velikosti není relací (částečného) uspořádání porovnání čísel podle absolutní hodnoty |x| ≤ |y| není relací (částečného) uspořádání porovnání kladných přirozených čísel podle dělitenosti m|n ⇔df “m dělí n beze zbytku” je relací (částečného) uspořádání porovnání nenulových celých čísel podle dělitenosti m|n není relací (částečného) uspořádání


Uspořádání


3 / 16


Odvozené ostré uspořádání Notace pro uspořádané množiny Pro odlišení používáme pro částečné uspořádání symbol a pro částečně uspořádané množiny zápis (X, ).

Definice 3 ( ostré uspořádání) Nechť je částečné uspořádání na množině X. Binární relaci ≺ definovanou vztahem x ≺ y ⇔ x y ∧ x 6= y nazýváme ostrým uspořádáním odvozeným od částečného uspořádání . V množinovém vyjádření to znamená: ≺ = −∆X . doc. Josef Kolář (FIT ČVUT)

Uspořádání


4 / 16


Vlastnosti ostrého uspořádání Věta 4 Nechť (A, ) je částečně uspořádaná množina a ≺ je odvozené ostré uspořádání. Potom platí: 1

≺ je ireflexivní, asymetrická a tranzitivní relace

2

(∀a, b ∈ X) a ≺ b ⇒ a b

3

(∀a, b, c ∈ X) (a ≺ b ∧ b c) ∨ (a b ∧ b ≺ c) ⇒ a ≺ c

Důkaz: 1

2 3

(IR) je zřejmá z množinového vyjádření ≺, (AS) plyne z (ANS) a (IR), (TR) plyne z částí 2 a 3 plyne z množinového vyjádření ≺ (a ≺ b ∧ b c) ⇒ (a b ∧ b c) ⇒ a c, přitom nemůže být a = c, neboť pak by bylo (a ≺ b ∧ b a) ⇒ (a b ∧ b a) ⇒ a = b, což je spor. Druhá část je analogická.


Uspořádání


5 / 16


Od ostrého k částečnému uspořádání Od částečného uspořádání jsme odvodili ostré uspořádání. Je možný i opačný postup?

Věta 5 Nechť R je binární relace na množině X, která je asymetrická a tranzitivní. Definujeme-li na X relaci = R ∪ ∆X , pak je (X, ) částečně uspořádaná množina. Navíc, relace ostrého uspořádání ≺ odvozená z částečného uspořádání je právě relace R. Důkaz: Platí R ∩ R−1 = OX a R ◦ R ⊆ R, takže (R ∪ ∆X ) ∩ (R ∪ ∆X )−1 = ∆X , což znamená antisymetrii relace . Tato relace je současně reflexivní, neboť vznikla sjednocením R a ∆X . Díky tranzitivitě relace R je ovšem také tranzitivní (ověřit!). Druhá část tvrzení plyne z toho, že ≺ = (R ∪ ∆X ) − ∆X = R, neboť R je asymetrická, tudíž také ireflexivní, tedy R ∩ ∆X = OX . doc. Josef Kolář (FIT ČVUT)

Uspořádání


6 / 16


Relace pokrytí Částečné uspořádání lze tedy získat zpětně z ostrého uspořádání jen přidáním diagonály. Je možné z nějaké “menší” relace rekonstruovat ostré uspořádání? Lze se zbavit tranzitivity - zpátky pomocí tranzitivního uzávěru! To vede k relaci pokrytí (též bezprostředního předcházení).

Definice 6 ( redukce relace) Nechť R je binární relace na množině X. Redukcí relace R nazýváme relaci Rr definovanou vztahem Rr = R − R 2 Je-li R ostrým uspořádáním na X, pak jeho redukci Rr nazýváme relací pokrytí nebo též bezprostředního předcházení. Pro tranzitivní relaci R : ∅ = OX ⊆ Rr ⊆ R. doc. Josef Kolář (FIT ČVUT)

Uspořádání


7 / 16


Hasseův diagram uspořádání Diagram relace pokrytí odpovídající uspořádání na částečně uspořádané množině (X, ) nazýváme Hasseovým diagramem (kreslíme ”‘zdola nahoru”’). OBRÁZEK

Věta 7 Nechť (X, ) je konečná částečně uspořádaná množina a ≺ = −∆X je odvozené ostré uspořádání na X. Potom platí: 1

ostré uspořádání ≺ je rovno tranzitivnímu uzávěru své redukce

2

výchozí částečné uspořádání je rovno reflexivně-tranzitivnímu uzávěru redukce odvozeného ostrého uspořádání.

Jak můžeme spočítat redukci odvozeného ostrého uspořádání?


Uspořádání


8 / 16


Příklady Hasseova diagramu Příklad 8 1

Uvažujme podmnožinu X = {1, 2, 3, 4, 5, 6, 8, 9, 10, 12} množiny přirozených čísel uspořádanou relací dělitelnosti m|n. Redukce odvozeného ostrého uspořádání bude obsahovat dvojice (1, 2), (1, 3), (1, 5), (2, 4), (2, 6), (2, 10), (3, 6), (3, 9), (4, 8), (4, 12), (5, 10), (6, 12). (viz HASSEŮV DIAGRAM)

2

Uvažujme potenční množinu tříprvkové množiny uspořádanou relací množinové inkluze (P ({a, b, c}), ⊆). Redukce odvozeného ostrého uspořádání (tj. ostré inkluze) bude obsahovat dvojice podmnožin (∅, {a}), (∅, {b}), (∅, {c}), ({a}, {a, b}), ({a}, {a, c}), ({b}, {a, b}), ({b}, {b, c}), ({c}, {a, c}), ({c}, {b, c}), ({a, b}, {a, b, c}), ({a, c}, {a, b, c}), ({b, c}, {a, b, c}). (viz HASSEŮV DIAGRAM)


Uspořádání


9 / 16


Úplné uspořádání Definice 9 ( úplné uspořádání) Nechť (A, ) je částečně uspořádaná množina. Řekneme, že a, b ∈ A jsou porovnatelné, jestliže a b nebo b a. Řekneme, že a, b ∈ A jsou neporovnatelné, jestliže ani a b ani b a neplatí. Řekneme, že je úplné uspořádání (též lineární uspořádání), jestliže jsou každé dva prvky z A porovnatelné. Které z následujících jsou úplně uspořádané množiny? Které prvky z neúplně uspořádaných množin jsou porovnatelné? (N, ≤), (N+ , |), (Z, ≥), (P(X), ⊆)

Věta 10 Pro každou konečnou částečně uspořádanou množinu (A, ) existuje rozšíření na úplné uspořádání u . doc. Josef Kolář (FIT ČVUT)

Uspořádání


10 / 16


Uspořádání a kartézský součin Definice 11 Nechť (A1 , 1 ), (A2 , 2 ), . . . , (Am , m ) jsou částečně uspořádané množiny. Na množině A = A1 × A2 × . . . × Am definujeme binární relaci direktní součin takto: (a1 , . . . , am ) (b1 , . . . , bm ) platí právě tehdy, jestliže ai i bi pro všechna i = 1, 2, . . . , m. lexikografické uspořádání L takto: (a1 , . . . , am ) L (b1 , . . . , bm ) platí právě tehdy, jestliže ai = bi pro všechna i = 1, 2, . . . , m nebo existuje index k takový, že ak ≺k bk a současně ai = bi pro všechna 1 ≤ i ≤ k − 1.


Uspořádání


11 / 16


Direktní součin a lexikografické uspořádání Jaké mají vlastnosti a jak se od sebe liší direktní součin částečných uspořádání a lexikografické uspořádání? Direktní součin je částečné uspořádání (ověřit!). uspořádání musí platit ve všech složkách lze použít k částečnému uspořádání n-té mocniny An uspořádané množiny (A, ) nelze použít k porovnání uspořádané n-tice s uspořádanou m-ticí Lexikografické uspořádání je rovněž částečné uspořádání (ověřit!). lexikografické uspořádání odvozené od úplných uspořádání je také úplné definici lexikografického uspořádání lze doplnit tak, že bude možné porovnávat uspořádané n-tice s uspořádanými m-ticemi lexikograficky můžeme (úplně) uspořádat i množinu A∗ = A0 ∪ A1 ∪ A2 ∪ . . . doc. Josef Kolář (FIT ČVUT)

Uspořádání


12 / 16


Minima a jiné podobné prvky Definice 12 Nechť (A, ) je částečně uspořádaná množina a ≺ je odvozené ostré uspořádání. Nechť M ⊆ A je neprázdná podmnožina množiny A. prvek a ∈ A je nejmenší prvek množiny M , jestliže a ∈ M a pro všechna x ∈ M platí a x prvek b ∈ A je největší prvek množiny M , jestliže b ∈ M a pro všechna x ∈ M plati x b prvek c ∈ A je minimalni prvek množiny M , jestliže c ∈ M a neexistuje x ∈ M : x ≺ c (značíme c = min(M )) prvek d ∈ A je maximalni prvek množiny M , jestliže d ∈ M a neexistuje x ∈ M : d ≺ x (značíme d = max(M )). Určíme nejmenší, největší, minimální a maximální prvky (pokud existují) posetů ({2, 3, 4, 5, 6, 8, 9, 10, 12}, |) a (P ({a, b, c}), ⊆). doc. Josef Kolář (FIT ČVUT)

Uspořádání


13 / 16


Vlastnosti minim, maxim, apod.

Věta 13 Nechť (A, ) je částečně uspořádaná množina, M ⊆ A nějaká její neprázdná podmnožina. 1

Jestliže existuje nejmenší prvek M , pak je jediný.

2

Jestliže m1 = min(M ), m2 = min(M ) a m1 m2 , pak m1 = m2 .

3

Jestliže je m nejmenší prvek M , pak m = min(M ) a jiné minimum už množina M nemá.

4

Obdobná tvrzení platí pro největší/maximální prvky.


Uspořádání


14 / 16


Minima a maxima na konečných množinách

Věta 14 1

Každá konečná neprázdná podmnožina M částečně uspořádané množiny (A, ) má (alespoň jeden) minimální a (alespoň jeden) maximální prvek.

2

Nechť (A, ) je úplně uspořádaná množina a M její neprázdná podmnožina. Je-li a = min(M ), pak je a nejmenší prvek M . Podobně je-li b = max(M ), pak je b největší prvek M .

3

Je-li (A, ) konečná úplně uspořádaná množina a M její neprázdná podmnožina, pak má M nejmenší i největší prvek.


Uspořádání


15 / 16


Dobře uspořádaná množina Definice 15 ( dobře uspořádaná množina) Nechť (A, ) je částečně uspořádaná množina. Řekneme, že (A, ) je dobře uspořádaná množina, jestliže každá neprazdná podmnožina M ⊆ A ma nejmenší prvek.

Věta 16 Každé dobré uspořádání je současně uspořádáním úplným.

Princip dobrého uspořádání (N, ≤) je dobře uspořádaná množina.

Věta 17 Principy indukce jsou ekvivalentní s principem dobrého uspořádání. doc. Josef Kolář (FIT ČVUT)

Uspořádání


16 / 16

No title

Recommend Documents