Diskrétní matematika --- sbírka · PDF fileÚvod Text, který...

České Vysoké Učení Technické v Praze

Fakulta elektrotechnická

Diskrétní matematikaSbírka řešených příkladů

Jiří Velebilkatedra matematikyPraha, 2007

[email protected]://math.feld.cvut.cz/velebil

A

mailto:[email protected]

http://math.feld.cvut.cz/velebil

Obsah

Úvod 4

1 Matematická indukce 51.1 Klasická matematická indukce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.2 Strukturální indukce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2 Binární relace na množině 132.1 Vlastnosti konkrétních relací . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.2 Práce s relacemi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3 Počítání modulo číslo 193.1 Inverse, lineární rovnice a diofantické rovnice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193.2 Čínská věta o zbytcích a Eulerova věta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

4 RSA a lineární kódy 234.1 Útoky na RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234.2 Generující a kontrolní matice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

5 Počítání modulo polynom 295.1 Lineární algebra modulo polynom . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295.2 Konečná tělesa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

6 Abstraktní výpočty 346.1 Grupoidy, pologrupy, monoidy a grupy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346.2 Posety, svazy a Booleovy algebry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 376.3 Jednoduché rovnicové specifikace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

Jiří Velebil: Y01DMA -- sbírka 3 1. srpna 2007

Úvod

Text, který máte před sebou, by měl posloužit jako sbírka řešených příkladů k předmětuDiskrétní matematikaY01DMA pro druhý ročník. Jde o jeho první variantu, proto přivítám jakékoli reakce.

Řazení textu. Text je rozdělen do kapitol zhruba podle témat syllabu přednášky Diskrétní matematika. Většinupříkladů doprovází komentáře, upozorňující na důležité momenty řešení nebo na časté chyby v postupu řešení.

Důležité upozornění. Řadu dalších řešených příkladů lze najít ve skriptech Diskrétní matematika, viz stránkyhttp://math.feld.cvut.cz/velebil.

Text je zveřejněn jako „klikací PDFÿ, tj. jako soubor s hypertextovými odkazy. Přesto nejde o „klikací knihuÿ,takový text bych psal a řadil úplně jinak. Hypertextové odkazy jsou vytvořeny jen pro zpříjemnění prohlíženíelektronické podoby dokumentu.

Poděkování. K napsání byl použit systém LATEX Leslieho Lamporta, hypertextové odkazy byly vytvořenybalíkem hyperref Sebastiana Rahtze a Heiko Oberdiek, obrázky byly nakresleny pomocí maker XY-pic KristofferaH. Rose a Rosse Moorea.

Přeji Vám příjemnou četbu.

Jiří VelebilV Praze, v červenci 2007


http://math.feld.cvut.cz/velebil

Kapitola 1

Matematická indukce

V odstavci 1.1 je vyřešeno několik klasických příkladů principy matematické indukce. Není možné postihnoutvšechny možné způsoby, kterými lze indukcí dokazovat. Přesto je možné říci, co musí každý korektní důkazmatematickou indukcí obsahovat:

1. Přesnou formulaci tvrzení, které dokazujeme. Toto tvrzení musí vždy mít tvar Pro všechna přirozená číslan ≥ n0 platí V(n).

Vlastnost V (n) může být komplikovaná a vždy se vyplatí si uvědomit přesné znění V (n), viz napří-klad 1.1.3.

2. Oznámení, podle čeho indukci provádíme. Pro tvrzení tvaru Pro všechna přirozená čísla n ≥ n0 platí V(n)je to n, pro tvrzení tvaru Pro všechna přirozená čísla m ≥ m0 platí W(m) je to m, a tak dále.

3. Jasný důkaz základního kroku indukce. Někdy musí být takových základních kroků více, viz příklad 1.1.3.

4. Indukční krok: zde musíme oznámit tvrzení, které chceme v indukčním kroku dokázat. Toto tvrzení pakmusíme jasně dekomponovat a to nám umožní zformulovat a poté správně použít indukční předpoklad.Indukční předpoklad je zapotřebí přesně zformulovat.

Soustružnické postupy (viz komentář k příkladu 1.1.1) při důkazu indukčního kroku nás většinou zavedoudo slepých uliček. Mějte neustále na paměti, že korektní důkaz indukcí je dynamický: běží jako rekursivníalgoritmus. Jste-li na pochybách o korektnosti svého důkazu, důkaz spusťte.

5. Dekompozice a formulace indukčního předpokladu signalisují, který z principů indukce náš důkaz využívá.

Dále jsou v odstavci 1.2 spočteny příklady na použití principu strukturální indukce. Použití tohoto principu jeextrémně jednoduché: jde vždy o to, zda je jistá vlastnost invariantní na průchod zadanými pravidly. Přesto jei zde nutno jasně oddělit základní krok indukce a indukční krok.

1.1 Klasická matematická indukce

1.1.1 Příklad Dokažte, že pro všechna přirozená čísla n ≥ 1 platí rovnostn∑

k=1

(−1)k+1 ·k2 = (−1)n+1n(n+ 1)2

.

Řešení. Budeme využívat některý princip indukce a indukci povedeme podle n.

Komentář. Fakt, že můžeme zkusit využít princip indukce plyne z toho, že námi dokazované tvrzení má tvar Pro

všechna přirozená čísla n ≥ 1 platí V (n)., kde vlastnost V (n) je platnost rovnostiPn

k=1 (−1)k+1 ·k2 =(−1)n+1n(n+1)

2pro pevné číslo n. Nevíme ovšem zatím, který z principů indukce použijeme. To nám řekne až dekomposice problému.

1. Základní krok: pro n = 1 ověříme platnost V (n) přímým výpočtem. Levá strana rovnosti je:

1∑k=1

(−1)k+1 · k2 = (−1)1+1 · 12 = 1


6 Kapitola 1. Matematická indukce

a pravá strana rovnosti je(−1)1+11 · (1 + 1)

2=22= 1.

Ověřili jsme, že V (1) platí.

2. Indukční krok: zvolíme libovolné, ale pevné číslo n ≥ 1. Máme ukázat platnost V (n+1), neboli platnostrovnosti

n+1∑k=1

(−1)k+1 · k2 = (−1)(n+1)+1(n+ 1) · ((n+ 1) + 1)

2.

Všimneme si, že levou stranu rovnosti lze přirozeným způsobem dekomponovat:

n+1∑k=1

(−1)k+1 · k2 =n∑

k=1

(−1)k+1 · k2 + (−1)(n+1)+1 · (n+ 1)2

To nám dává návod, jak zformulovat indukční předpoklad: pro libovolné pevné n ≥ 1 platí rovnostn∑

k=1

(−1)k+1 · k2 = (−1)n+1n(n+ 1)2

.

Komentář. Tento postup je typický: dekomposice nám dává návod, jak zformulovat indukční předpoklad a jakjej použít. Zároveň se dozvídáme, který princip indukce budeme používat (v tomto případě jde o slabý principindukce, protože dekomposice sahá o jeden krok zpátky do historie).

Indukční předpoklad nyní použijeme na levou (dekomponovanou) stranu rovnice:

n∑k=1

(−1)k+1 · k2 + (−1)(n+1)+1 · (n+ 1)2 = (−1)n+1n(n+ 1)2

+ (−1)(n+1)+1 · (n+ 1)2

V součtu napravo už můžeme použít normální aritmetiku f a dostáváme tak rovnost

(−1)n+1n(n+ 1)2

+ (−1)(n+1)+1 · (n+ 1)2 = (−1)(n+1)+1(n+ 1) · ((n+ 1) + 1)

2.

Indukční krok je u konce, dokázali jsme platnost rovnosti

n+1∑k=1

(−1)k+1 · k2 = (−1)(n+1)+1(n+ 1) · ((n+ 1) + 1)

2.

Komentář. Častou chybou při důkazu indukčního kroku je „soustruženíÿ dokazovaného vztahu. V našem případěby takový postup mohl vypadat takto:

n+1Xk=1

(−1)k+1 · k2 =(−1)(n+1)+1(n+ 1) · ((n+ 1) + 1)

2

(−1)(n+1)+1 · (n+ 1)2 =(−1)(n+1)+1(n+ 1) · ((n+ 1) + 1)

2−(−1)n+1n(n+ 1)

2...

0 = 0

Proč je tento postup nesprávný? Především: rovnost 0 = 0 jsme jistě dokázat nechtěli. Předchozí řádky mámetedy číst odspodu nahoru, abychom z platnosti rovnosti 0 = 0 odvodili platnost rovnosti

Pn+1k=1 (−1)

k+1 · k2 =(−1)(n+1)+1(n+1)·((n+1)+1)

2 . K tomu je zapotřebí vědět, že všechny použité úpravy jsou reversibilní. Často tomutak skutečně může být (v našem příkladě jsme při přechodu z prvního na druhý řádek „odčítali rovnostÿ), častoje reversibilita velmi problematická (příklady 1.1.2 a 1.1.3) a často je zcela nemožná (příklad 1.1.4). Závěr?Soustružení nepoužívejte!

Důkaz indukcí je u konce, použili jsme slabý princip matematické indukce. �

1. srpna 2007 Jiří Velebil: Y01DMA -- sbírka

1.1. Klasická matematická indukce 7

1.1.2 Příklad Dokažte, že nerovnost1

n+ 1+

1n+ 2

+ . . .+12n

>12platí pro všechna přirozená čísla n ≥ 2.

Řešení. Budeme postupovat nějakým principem indukce podle n ≥ 2.

1. Základní krok: pro n = 2 je levá strana nerovnosti výraz12 + 1

+14neboli číslo

712. Pravá strana

nerovnosti je12. Protože

712

>12platí, je základní krok u konce.

2. Indukční krok: zvolíme libovolné, ale pevné číslo n ≥ 2. Máme ukázat platnost nerovnosti

1(n+ 1) + 1

+1

(n+ 1) + 2+ . . .+

12(n+ 1)

>12

(1.1)

Pokusíme se o dekomposici a zřejmě máme dekomponovat levou stranu. Protože smyslem dekomposice jeobjevit „problém menších rozměrůÿ, pokoušíme se v levé straně objevit výraz

1n+ 1

+1

n+ 2+ . . .+

12n

. (1.2)

Levá strana (1.1) však „začíná a končí pozdějiÿ než výraz (1.2). Použijeme tedy obvyklého triku přičtenía odečtení a levou stranu (1.1) dekomponujeme takto:

1(n+ 1) + 1

+1

(n+ 1) + 2+. . .+

12(n+ 1)

=1

n+ 1+1

n+ 2+. . .+

12n+

(1

2n+ 1+

12n+ 2

− 1n+ 1

)(1.3)

Na základě této dekomposice můžeme zformulovat indukční předpoklad: pro libovolné pevné n ≥ 2platí nerovnost

1n+ 1

+1

n+ 2+ . . .+

12n

>12.

Dekomposice (1.3) dává návod, jak indukční předpoklad použít:

1(n+ 1) + 1

+1

(n+ 1) + 2+ . . .+

12(n+ 1)

=1

n+ 1+

1n+ 2

+ . . .+12n+

(1

2n+ 1+

12n+ 2

− 1n+ 1

)>12+

(1

2n+ 1+

12n+ 2

− 1n+ 1

)Nyní by k ukončení důkazu indukčního kroku stačilo ukázat, že platí nerovnost

12n+ 1

+1

2n+ 2− 1

n+ 1≥ 0

neboli, že platí nerovnost1

2n+ 1≥ 1

n+ 1− 12n+ 2

(1.4)

To je ale snadné: pravá strana (1.4) je rovna výrazu1

2n+ 2a nerovnost

12n+ 1

≥ 12n+ 2

jistě pro n ≥ 2 platí. Celkový důkaz indukčního kroku tedy vypadá takto:

1(n+ 1) + 1

+1

(n+ 1) + 2+ . . .+

12(n+ 1)

=1

n+ 1+

1n+ 2

+ . . .+12n+

(1

2n+ 1+

12n+ 2

− 1n+ 1

)>12+

(1

2n+ 1+

12n+ 2

− 1n+ 1

)≥ 12

Jiří Velebil: Y01DMA -- sbírka 1. srpna 2007


Použili jsme slabý princip indukce. �

1.1.3 Příklad Dokažte, že nerovnost

∣∣∣∣∣n∑

i=1

xi

∣∣∣∣∣ ≤n∑

i=1

|xi| platí pro libovolné n ≥ 1 a libovolná reálná čísla

x1, . . . , xn.

Řešení. Budeme postupovat nějakým principem indukce podle n ≥ 1.

Komentář. Vyplatí se si přesně uvědomit, že dokazujeme tvrzení tvaru Pro všechna přirozená čísla n ≥ 1 platí V (n),kde V (n) znamená platnost nerovnosti

˛̨Pni=1 xi

˛̨≤

Pni=1 |xi| pro libovolná reálná čísla x1, . . . , xn. Tento dodatek

(pro libovolná reálná. . . ) budeme muset „tahat s sebouÿ!

1. Základní krok: pro n = 1 máme ukázat platnost nerovnosti∣∣∣∑1i=1 xi

∣∣∣ ≤∑1i=1 |xi| pro libovolné reálnéčíslo x1.

Levá strana této nerovnosti je |x1| a pravá strana této nerovnosti je opět |x1|.

Nerovnost∣∣∣∑1i=1 xi

∣∣∣ ≤∑1i=1 |xi| pro libovolné reálné číslo x1 je dokázána.

2. Indukční krok: pro libovolné pevné n ≥ 1 máme dokázat platnost nerovnosti∣∣∣∣∣n+1∑i=1

xi

∣∣∣∣∣ ≤n+1∑i=1

|xi|

pro libovolná reálná čísla x1, . . . , xn, xn+1. Dekomponovat budeme zřejmě levou stranu:∣∣∣∣∣n+1∑i=1

xi

∣∣∣∣∣ =∣∣∣∣∣(

n∑i=1

xi

)+ xn+1

∣∣∣∣∣což nám dovoluje zformulovat indukční předpoklad: pro libovolné pevné n ≥ 1 platí nerovnost∣∣∣∣∣

n∑i=1

xi

∣∣∣∣∣ ≤n∑

i=1

|xi|

pro libovolná reálná čísla x1, . . . , xn.

Co ale máme dělat dál? Jak indukční předpoklad použít? Nabízí se tento další postup:∣∣∣∣∣(

n∑i=1

xi

)+ xn+1

∣∣∣∣∣ ≤(∣∣∣∣∣

n∑i=1

xi

∣∣∣∣∣)+ |xn+1| ≤

(n∑

i=1

|xi|

)+ |xn+1| =

n+1∑i=1

|xi| (1.5)

který v první nerovnosti využívá platnost tvrzení V (2) a ve druhé nerovnosti indukční předpoklad. TvrzeníV (2) totiž říká: nerovnost |A+B| ≤ |A| + |B| platí pro libovolná reálná čísla A, B. (Přejmenovali jsmevázané proměnné x1 a x2 na A a B, víme z logiky, že se to smí, říká se tomu α-konverse.) My jsme tvrzeníV (2) použili pro

A =

(n∑

i=1

xi

)B = xn+1.

Komentář. Zde se naplno projevuje nutnost tahat s sebou dodatek pro všechna reálná. . . Bez tohoto dodatkuby náš důkaz nebyl korektní.

Protože tvrzení V (2) jsme ale nedokázali, přerušíme důkaz indukčního kroku a dokážeme druhou částkroku základního pro n = 2.

Komentář. To je nutné udělat: příslušný rekursivní algoritmus by totiž neběžel. Náš algoritmus totiž platnost(například) V (4) redukuje na platnost V (3), platnost V (3) redukuje na platnost V (2) a tam se zastaví s chybovýmhlášením. Platnost V (2) jsme zatím nedokázali.


1.1. Klasická matematická indukce 9

3. Základní krok (druhá část): máme dokázat platnost nerovnosti

|x1 + x2| ≤ |x1|+ |x2| (1.6)

pro libovolná reálná čísla x1, x2. Nejjednodušší je postupovat odstraňováním absolutních hodnot:

(a) V případě, že x1 + x2 ≥ 0, je pravá strana nerovnosti (1.6) rovna x1 + x2. Protože pro (jakákoli)reálná čísla x1, x2 platí nerovnosti x1 ≤ |x1| a x2 ≤ |x2|, dostáváme nerovnost (1.6)

|x1 + x2| = x1 + x2 ≤ |x1|+ |x2|

(b) V případě, že x1 + x2 < 0, je pravá strana nerovnosti (1.6) rovna −x1 − x2. Protože pro (jakákoli)reálná čísla x1, x2 platí nerovnosti −x1 ≤ |x1| a −x2 ≤ |x2|, dostáváme nerovnost (1.6)

|x1 + x2| = −x1 − x2 ≤ |x1|+ |x2|

Důkaz tvrzení V (2) je u konce.

4. Indukční krok (druhá část): nyní je již postup v (1.5) v pořádku a indukční krok je dokázán.

Použili jsme slabý princip indukce. �

1.1.4 Příklad Místností rozměru n budeme rozumět šachovnici rozměru 2n × 2n, kde n ≥ 1, ze které je jedno(libovolné) pole vyjmuto. Toto je příklad místnosti rozměru 3:

????

? ��

Trimino je parketa následujícího tvaru:

Vyřešte následující problémy:

1. Sestavte rekursivní algoritmus, který vyparketuje libovolnou místnost rozměru n ≥ 1 triminy. Vyparke-továním triminy rozumíme rozložení trimin po místnosti tak, aby žádné pole nezbylo volné. Trimina sepřitom mohou pouze dotýkat hranou a nesmí pokrýt vyjmuté pole.

2. Ukažte (indukcí) totální korektnost tohoto algoritmu.

Řešení. Nejprve sestavíme rekursivní algoritmus, který vyparketuje libovolnou místnost rozměrů n ≥ 1 triminy.Důkaz korektnosti algoritmu okamžitě poplyne z návrhu algoritmu.

Komentář. Zde naplno uvidíme, proč je důkaz indukcí totéž jako rekursivní algoritmus. Uvidíme také, že důkazindukcí pracuje „směrem dolůÿ, tj., že indukční krok redukuje úlohu velkých rozměrů na úlohy rozměrů menších (tentorozklad je přesně dekomposice problému) a že rekursivní volání odpovídá přesně použití indukčního předpokladu.

1. Základní krok algoritmu: pro n = 1 náš algoritmus nebude pracovat rekursivně. Místnost rozměrů 1totiž vypadá (až na rotaci) takto:

????

?

��

�

a my ji tudíž vyparketujeme jedním triminem.



2. Rekursivní práce algoritmu: Máme vyparketovat místnost rozměrů n+1. Protože 2n+1 = 2 ·2n, nabízíse stranu příslušného čtverce rozpůlit a získat tak čtyři čtverce rozměrů 2n × 2n:

????

? ��

Komentář. Všimněme si, že nevznikly čtyři místnosti rozměrů n, dekomposice tudíž ještě není u konce.

Nyní položíme na střed místnosti jedno trimino a dostaneme tak:

????

? ��????

? ��??

??? �� ??

??? ��

(1.7)

V tento okamžik je dekomposice u konce: máme vyparketovat čtyři místnosti rozměrů n. To udělámerekursivně.

Korektnost algoritmu dokážeme indukcí podle n ≥ 1:

1. Základní krok: Místnost rozměrů n = 1 náš algoritmus vyparketuje.

2. Indukční krok: Máme ukázat, že náš algoritmus vyparketuje místnost rozměrů n+1. Provedeme dekom-posici výše uvedeným způsobem a zformulujeme indukční předpoklad takto: každou místnost rozměrů nnáš algoritmus vyparketuje. Indukční předpoklad použijeme čtyřikrát : jednou na každou místnost rozměrůn v dekomposici na obrázku (1.7).

Důkaz indukčního kroku je skončen.

Podle principu slabé indukce je důkaz korektnosti u konce. �

1.2 Strukturální indukce

1.2.1 Příklad Ať Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} je konečná abeceda. Zadejte induktivně množinu L všech slovnad Σ, která representují nenulová přirozená čísla.

Řešení. Nejprve popíšeme charakteristickou vlastnost prvků množiny L. Pro slovo w ∈ Σ∗ zavedeme značení:V (w) platí právě když platí |w| ≥ 1 a první znak zleva ve w není 0. Potom platí rovnost L = {w ∈ Σ∗ | V (w)}.Tuto množinu L zadáme induktivně.


1.2. Strukturální indukce 11

Naše gramatika bude mít devět axiomů

1(1) |

2(2) |

3(3) |

4(4) |

5(5) | (1.8)

6(6) |

7(7) |

8(8) |

9(9)

a deset deduktivních pravidel

ww0

(10) | ww1

(11) | ww2

(12) | ww3

(13) | ww4

(14) | (1.9)

ww5

(15) | ww6

(16) | ww7

(17) | ww8

(18) | ww9

(19)

Tato gramatika induktivně zadává jistou množinu slov G. Naším úkolem je dokázat rovnost G = L.Úkol rozdělíme na dvě části:

1. G ⊆ L: máme ukázat: jestliže w ∈ G, potom w ∈ L, a to pro libovolné slovo w.

Zvolme libovolné slovo w z množiny G. To znamená, že slovo w je vygenerováno koonečným použitímpravidel (1.8) a (1.9). To znamená, že máme k disposici syntaktický strom Tw slova w a slovo w jekořenem stromu Tw.

Chceme dokázat, že platí V (w). K tomu nám postačí ukázat, že platnost vlastnosti V (w) je invariantnína průchod gramatikou (1.8) a (1.9). (Používáme tedy princip strukturální indukce.)

Komentář. To je zcela typický postup. V tomto směru (G ⊆ L) je vždy vhodný princip strukturální indukce.

(a) Základní krok: závěr každého axiomu z (1.8) má vlastnost V (w), jde o slovo délky jedna a prvníznak zleva není nula.

Důkaz základního kroku strukturální indukce je ukončen.

(b) Indukční krok: vězměme libovolné deduktivní pravidlo ze seznamu (1.9). Máme ukázat, že závěrtohoto deduktivního pravidla má vlastnost V , jestliže předpoklad tohoto pravidla má vlastnost V .

Důkaz provedeme pro pravidlo (19), pro ostatní deduktivní pravidla je důkaz analogický.

Předpokládáme tedy platnost V (w) a chceme dokázat platnost V (w9). To je triviální: w9 je slovodélky alespoň 1 a první znak zleva slova w9 není znak 0, protože víme, že slovo w nezačíná znakem0.

Důkaz indukčního kroku je u konce.

Dokázali jsme G ⊆ L.

2. L ⊆ G: máme dokázat: jestliže w ∈ L, potom w ∈ G, a to pro libovolné slovo w.

Zvolme libovolné slovo w z množiny L. To znamená, že V (w) platí. Naším úkolem je sestavit syntaktickýstrom slova w. Jediné, co lze využít, je znalost délky |w| slova w.

Zkusíme tedy (klasickou) indukcí dokázat toto tvrzení: pro všechna n ≥ 1 platí: jestliže platí V (w) proslovo w délky n, potom existuje syntaktický strom Tw vytvořený podle pravidel (1.8) a (1.9).

Komentář. V tomto směru (L ⊆ G) se pro konstrukci syntaktického stromu musí vždy použít některý klasickýprincip indukce. Nejobtížnější tu bývá zjistit, podle čeho indukci provádět.

(a) Základní krok: máme dokázat, že každé slovo w délky 1 takové, že V (w) platí, má syntaktickýstrom Tw vytvořený podle pravidel (1.8) a (1.9).

Protože slovo w má délku jedna a platí V (w), je slovo w některým ze znaků 1, 2, 3, 4, 5, 6, 7, 8, 9.

Důkaz provedme pro případ w = 7, pro ostatní případy je důkaz analogický.

Hledaný syntaktický strom Tw je 7(7) .

Důkaz základního kroku je u konce.



(b) Indukční krok: máme slovo w délky n + 1 a víme, že V (w) platí. Chceme ukázat, že existujesyntaktický strom Tw vytvořený podle pravidel (1.8) a (1.9).

Protože postupujeme klasickou indukcí, hledáme nějakou dekomposici. Protože slovo w má délkun+ 1, nabízí se dekomposice w = w′a, kde w′ má délku n a a ∈ Σ. Navíc zjevně platí V (w′).

Indukční předpoklad tedy zformulujeme takto: každé slovo w′ délky n, pro které platí V (w′), másyntaktický strom Tw′ vytvořený podle pravidel (1.8) a (1.9).

Budeme předpokládat, že poslední znak a slova w je znak 3, pro ostatní případy se důkaz vedeanalogicky.

Hledaný syntaktický strom Tw jeTw′

w′3(13) .


Slabým principem indukce jsme dokázali, že L ⊆ G.

�

1.2.2 Příklad Ať At je množina atomických formulí. Množina F (At) všech formulí výrokové logiky je induk-tivně zadána následujícími axiomy

tt(true) | a (a) kde a ∈ At (1.10)

a deduktivními pravidly

ϕ

(¬ϕ)(¬) |

ϕ1 ϕ2(ϕ1 ∧ ϕ2)

(∧) |ϕ1 ϕ2(ϕ1 ∨ ϕ2)

(∨) | (1.11)

ϕ1 ϕ2(ϕ1 ⇒ ϕ2)

(⇒) |ϕ1 ϕ2(ϕ1 ⇔ ϕ2)

(⇔)

Dokažte, že v každé formuli ϕ ∈ F (At) je počet levých a pravých závorek shodný.

Řešení. Protože množina F (At) je induktivně vytvořena, zkusíme k důkazu využít princip strukturální indukce.Na množině všech slov nad abecedou Σ = {¬,∧,∨,⇒,⇔, tt, (, )} ∪ At zavedeme následující vlastnost: V (w)platí, pokud je ve slovu w počet levých a pravých závorek stejný.

Komentář. Samozřejmě: ne každé slovo w nad Σ je formule. Například slovo ∧∧ () není formule, ale má vlastnost V .

Chceme dokázat, že platí V (w), a to pro každé slovo z množiny F (At). Podle principu strukturální indukcestačí ukázat, že vlastnost V je invariantní na průchod pravidly (1.10) a (1.11).

1. Základní krok: máme ukázat, že závěr každého axiomu z (1.10) má vlastnost V .

To je zřejmé: závěr každého axiomu má nula pravých a nula levých závorek.

Důkaz základního kroku je u konce.

2. Indukční krok: máme ukázat, že pro každé deduktivní pravidlo z (1.11) platí: jestliže všechny předpo-klady pravidla mají vlastnost V , má vlastnost V i závěr tohoto pravidla.

To je zřejmé: vezměme například pravidlo (⇔), pro ostatní pravidla proběhne důkaz analogicky.Pokud platí V (ϕ1) a V (ϕ2), platí zřejmě i V ((ϕ1 ⇔ ϕ2)).


Podle principu strukturální indukce je důkaz ukončen. �


Kapitola 2

Binární relace na množině

V odstavci 2.1 jsou vyřešeny standardní příklady týkající se vlastností binárních relací na množině, v odstavci 2.2pak jsou řešeny některé složitější příklady.Připomeňme některé definice a značení, použitá ve skriptech Diskrétní matematika:

1. Binární relace R na množině A je podmnožina R ⊆ A×A. Místo (x, y) ∈ R píšeme x R y.

Komentář. Slovo relace znamená česky vztah. Nejrozumnější je představit si relaci R jako seznam dvojic, kdeprvní položka má (jakýsi) vztah s druhou položkou.

Zápis x R y není totéž jako relace R. Zápis x R y je tvrzení, že x má vztah R s y. Takové tvrzení může býtpravdivé nebo nepravdivé. Jde o podobné rozlišení jako u funkcí: zápis sinx není funkce, ale funkční hodnota.Příslušnou funkcí je sin.

2. Identická relace ∆A na množině A je definována vlastností: x ∆A y právě když x = y.

3. Relace opačná k R je relace značená Rop s vlastností: x Rop y právě když y R x.

4. Složení relací R a S je relace značená R;S s vlastností: x R;S y právě když existuje z ∈ A tak, že platíx R z a z S y současně.

2.1 Vlastnosti konkrétních relací

2.1.1 Příklad Na množině Z celých čísel je zadána relace T vlastností: a T b právě když a + b je dělitelnétřemi. Rozhodněte, zda relace T je:

1. Reflexivní. 2. Symetrická. 3. Transitivní. 4. Antisymetrická.

Komentář. V definici relace T je použita vlastnost dělitelnost třemi , nikoli operace dělení třemi . Mezi těmito pojmyje zásadní rozdíl! Zaměňování těchto pojmů vede k nesprávným úvahám.

Řešení.

1. Reflexivita: máme ukázat, že pro všechna a ∈ Z platí a T a. Neboli: máme rozhodnout, zda číslo a+ aje dělitelné třemi pro všechna a ∈ Z.To není pravda: číslo a = 1 je celé a číslo a = 1 + 1 = 2 není dělitelné třemi.

Zadaná relace T není reflexivní.

Komentář. Častou chybou je tvrzení: pro a = 24 je a+a = 48 a to je číslo dělitelné třemi. Relace T je reflexivnípro a = 24. Pozor! Nic takového jako reflexivita pro nějakou hodnotu nebylo definováno! Relace buď reflexivní jenebo není. Pokud máme dojem, že relace reflexivní je, musíme podmínku reflexivity dokázat pro všechny prvkyzadané množiny, pokud máme dojem, že relace reflexivní není, stačí najít (co nejjednodušší) protipříklad napodmínku reflexivity.

2. Symetrie: máme ukázat, že z platnosti a T b plyne platnost b T a, a to pro všechna celá čísla a, b.

Pokud a+ b je dělitelné třemi, znamená to, že umíme najít celé číslo k tak, že a+ b = 3k. Protože sčítánícelých čísel je komutativní, víme, že b+ a = 3k. Proto platí b T a.

Zadaná relace T je symetrická.


14 Kapitola 2. Binární relace na množině

Komentář. Nejspíš není možné popsat všechny možné chyby, které se u práce se symetrií mohou vyskytnout.Zde je výčet dvou nejčastějších:

(a) Symetrie naší relace T není vlastnost a T b a současně b T a pro všechna a, b ∈ Z. Viz příklad 2.2.3.Tuto podmínku relace T nesplňuje: zvolte a = 1, b = 2. Neplatí ani a T b, ani b T a.

(b) Pokud jsme ukázali, že nějaká relace je symetrická, neplyne z toho automaticky, že není antisymetrická.Relace, které jsou symetrické a antisymetrické současně, existují. Podívejte se na příklad 2.2.2.

3. Transitivita: máme ukázat, že z platnosti a T b a současně b T c plyne a T c, a to pro libovolná celáčísla a, b, c.

Tato podmínka splněna není: pro a = 1, b = 2, c = 1 platí a T b a současně b T c, ale a T c neplatí.

Zadaná relace T není transitivní.

4. Antisymetrie: máme ukázat, že z platnosti a T b a současně b T a plyne a = b, a to pro libovolná celáčísla a, b.

Tato podmínka splněna není: pro a = 1, b = 2 platí a T b a současně b T a, ale a = b neplatí.

Zadaná relace T není antisymetrická.

�

2.1.2 Příklad Na množině R reálných čísel je zadána relace S takto: x S y právě když x2 + 2xy ≤ y4.Rozhodněte, zda platí (−1) Sop;S 1.

Řešení. Vztah (−1) Sop;S 1 platí právě tehdy, když existuje z ∈ R tak, že platí (−1) Sop z a z S 1 současně.A to platí právě tehdy, když existuje z ∈ R tak, že platí z S (−1) a z S 1 současně.Jinými slovy: hledáme z ∈ R tak, že platí z2 − 2z ≤ 1 a z2 + 2z ≤ 1. Takovým z je třeba číslo 0.

Komentář. Častou chybou u příkladů tohoto typu je snaha nějak definiční vztah relace upravovat. Často je to téměřnemožné a skoro vždy to vůbec není zapotřebí. Správná strategie tu je lazy evaluation: pracujte s nepříjemnými výrazyteprve tehdy, když to situace skutečně vyžaduje.

Protože jsme číslo z s požadovanými vlastnostmi našli, vztah (−1) Sop;S 1 platí. �

2.1.3 Příklad Na množině R reálných čísel je zadána relace W takto: x W y právě když x ≥ y. Rozhodněte,zda platí (−5)W ;W 1.

Řešení. Vztah (−5)W ;W 1 platí právě tehdy, když existuje z ∈ R tak, že platí (−5)W z a z W 1 současně.Jinými slovy: hledáme z ∈ R tak, že platí −5 ≥ z a z ≥ 1. Takové reálné číslo z neexistuje.Protože číslo z s požadovanými vlastnostmi neexistuje, vztah (−5)W ;W 1 neplatí. �

2.1.4 Příklad Ukažte, že relace | (dělitelnost) na množině N je uspořádání.

Řešení. Máme ukázat, že relace | je reflexivní, transitivní a antisymetrická.

Komentář. Je dobré si uvědomit, že jde o dělitelnost . Vztah a | b znamená: existuje přirozené číslo k tak, že b = k ·a.

1. Reflexivita: Máme ukázat, že a | a pro všechna přirozená čísla a.

Vezměme tedy libovolné přirozené číslo a. Hledáme přirozené číslo k takové, že platí rovnost a = k · a.Hledaným číslem k je číslo 1.

Důkaz reflexivity je u konce.

2. Transitivita: Máme ukázat, že z platnosti a | b a b | c plyne vlastnost a | c, a to pro všechna přirozenáčísla a, b, c.

Protože a | b, existuje přirozené číslo k tak, že platí b = k · a. S tímto číslem k můžeme dále pracovat.

Protože b | c, existuje přirozené číslo l tak, že platí b = l · a. S tímto číslem l můžeme dále pracovat.


2.1. Vlastnosti konkrétních relací 15

Komentář. Všimněme si, že jsme k označení svědků dělitelnosti použili různá písmena. Úvaha b = k ·a a c = k ·b(stejní svědci dělitelnosti) je častou chybou.

Chceme-li ukázat, že a | c, stačí najít nějaké přirozené číslo m tak, aby platilo c = m · a. Zjevně prom = k · l rovnost c = m · a platí: c = l · b = l · k · a.Důkaz transitivity je u konce.

3. Antisymetrie: Máme ukázat, že z platnosti a | b a b | a plyne vlastnost a = b, a to pro všechna přirozenáčísla a, b.

Protože a | b, existuje přirozené číslo k tak, že platí b = k · a. S tímto číslem k můžeme dále pracovat.

Protože b | a, existuje přirozené číslo l tak, že platí a = l · b. S tímto číslem l můžeme dále pracovat.

Dostáváme tedy rovnostia = l · b = l · k · a (2.1)

V případě, že a 6= 0, můžeme rovnosti (2.1) číslem a vydělit a dostaneme tak rovnost l · k = 1. Protože ki l jsou přirozená čísla, musí platit k = l = 1. Proto a = l · b = b.

V případě, že a = 0, tak rovnost b = 0 okamžitě plyne z rovnosti b = k · a. Proto v tomto případě platía = b.

Další možnost nastat nemůže, důkaz antisymetrie je u konce.

Komentář. V tomto příkladu jsme ukázali, že 〈N, |〉 je poset. Viz také příklad 6.2.1.

�

2.1.5 Příklad Ukažte, že relace U na množině komplexních čísel C, definovaná vztahem

x U y právě když |x| = |y|

je relace ekvivalence a popište třídu ekvivalence čísla 1 + i.

Komentář. Připomeňme, že relace ekvivalence musí být reflexivní, symetrická a transitivní.

Řešení. Nejprve dokážeme, že U je relace ekvivalence:

1. Reflexivita: máme ukázat, že |x| = |x| pro všechna komplexní čísla x. To jistě platí.

Ukázali jsme, že U je reflexivní relace.

2. Symetrie: máme ukázat, že z platnosti |x| = |y| plyne platnost |y| = |x|, a to pro všechna komplexníčísla x, y. To je pravda díky vlastnostem rovnosti.

Ukázali jsme, že U je symetrická relace.

3. Transitivita: máme ukázat, že z platnosti |x| = |y| a |y| = |z| plyne platnost |x| = |z|, a to pro všechnakomplexní čísla x, y, z. To je pravda díky vlastnostem rovnosti.

Ukázali jsme, že U je transitivní relace.

Třída ekvivalence čísla 1 + i je množina

U [1 + i] = {z ∈ C | |1 + i| = |z|} = {z ∈ C |√2 = |z|},

což je kružnice v Gaussově rovině se středem v počátku a poloměrem√2.

Komentář. Zřejmě může být vůbec každá třída ekvivalence relace U příslušná komplexnímu číslu z chápána jakokružnice v Gaussově rovině se středem v počátku a poloměrem r = |z|.Tento popis tříd ekvivalence dává popis rozkladu C podle U : množina C/U „jeÿ množina nezáporných reálných čísel,protože každou třídu ekvivalence můžeme representovat nezáporným reálným číslem (poloměrem příslušné kružnice).

�



2.2 Práce s relacemi

2.2.1 Příklad Ať R, S a T jsou binární relace na množině A. Ať navíc platí R ⊆ S. Ukažte, že potom platíR;T ⊆ S;T .

Řešení. Chceme ukázat, že z platnosti vztahu a R;T b plyne platnost vztahu a S;T b, a to pro všechna a, bz A.Vezměme tedy libovolná a a b taková, že platí a R;T b.Vztah a R;T b znamená existenci c ∈ A tak, že platí a R c a současně c T b.Protože předpokládáme R ⊆ S, víme, že platí a S c. Celkově tedy platí a S c a současně c T b.Ukázali jsme, že a S;T b platí. �

2.2.2 Příklad Ukažte, že pro binární relaci R na množině A jsou následující podmínky ekvivalentní:

1. R je symetrická a antisymetrická současně.

2. R je koreflexivní, tj. platí R ⊆ ∆A.

Řešení. Máme dokázat, že z 1. plyne 2. a naopak.

1. Ať R je symetrická a antisymetrická současně. To znamená, že platí R = Rop (symetrie) a R ∩Rop ⊆ ∆A

(antisymetrie).

Potom platí R = R ∩R = R ∩Rop ⊆ ∆A. Relace R je koreflexivní, to jsme chtěli dokázat.

2. Ať platí R ⊆ ∆A. Potom zjevně platí R = Rop a relace R je tudíž symetrická.

Dále platí R = R ∩Rop ⊆ ∆A a relace R je antisymetrická.

�

2.2.3 Příklad Ať A je neprázdná množina. Ať R je binární relace na A, která splňuje x R y a současně y R xpro všechna x, y z množiny A. Ukažte, že potom platí R = A×A.

Řešení. Máme ukázat platnost R ⊆ A×A a platnost A×A ⊆ R současně.

1. Inkluse R ⊆ A×A samozřejmě platí, protože R je binární relace na množině A.

2. Dokážeme inklusi A×A ⊆ R. Zvolme libovolný prvek (x, y) ∈ A×A. Máme dokázat, že platí x R y.

To je ale triviální: podle našich předpokladů o relaci R víme, že platí x R y a současně y R x. Speciálnětedy platí x R y.

Dokázali jsme, že platí R = A×A. �

2.2.4 Příklad Řekneme, že binární relace R na množině A je funkcionální, pokud pro každé x ∈ A existujeprávě jedno y ∈ A tak, že platí x R y. Dokažte, že relace R je funkcionální právě tehdy, když platí ∆A ⊆ R;Rop

a současně Rop;R ⊆ ∆A.

Komentář. Máme tedy dokázat, že R je funkcionální právě tehdy, když R;Rop je reflexivní a Rop;R je koreflexivní(viz příklad 2.2.2).

Řešení.

1. Budeme předpokládat, že relace R je funkcionální. Chceme ukázat, že platí ∆A ⊆ R;Rop a současněRop;R ⊆ ∆A.


2.2. Práce s relacemi 17

(a) Budeme dokazovat platnost ∆A ⊆ R;Rop.

Zvolíme libovolné x ∈ A. Chceme dokázat, že platí x R;Rop x. Hledáme tudíž y ∈ A tak, že platíx R y a současně y Rop x. Jinými slovy: hledáme y ∈ A tak, že platí x R y a současně x R y. Toto yjistě existuje: relace R je totiž funkcionální.

Dokázali jsme, že ∆A ⊆ R;Rop platí.

(b) Budeme dokazovat platnost Rop;R ⊆ ∆A.

Zvolíme libovolná y a y′ tak, že platí y Rop;R y′. Chceme ukázat, že platí y ∆A y′, neboli, že platíy = y′.

Z platnosti y Rop;R y′ plyne existence x ∈ A tak, že platí y Rop x a současně x R y′. Neboli platíx R y a současně x R y′. Protože relace R je funkcionální, platí y = y′.

Dokázali jsme, že Rop;R ⊆ ∆A platí.

Ukázali jsme, že platí ∆A ⊆ R;Rop a současně Rop;R ⊆ ∆A.

2. Budeme předpokládat, že platí ∆A ⊆ R;Rop a současně Rop;R ⊆ ∆A. Chceme dokázat, že R je funkcio-nální relace.

Zvolme libovolné x ∈ A.

(a) Nejprve dokážeme, že existuje y ∈ A tak, že platí x R y. K tomu využijeme platnost inkluse ∆A ⊆R;Rop.

Platnost inkluse zaručuje, že platí x R;Rop x. Tudíž existuje y ∈ A tak, že platí x R y a současněy Rop x.

Speciálně jsme dokázali, že existuje y ∈ A tak, že platí x R y.

(b) Nyní dokážeme, že z platnosti x R y a současně x R y′ plyne y = y′.

Protože platí x R y a současně x R y′, platí y Rop x a současně x R y′. Neboli platí y Rop;R y′.

Protože platí Rop;R ⊆ ∆A, plyne z výše uvedeného, že y = y′. To jsme chtěli dokázat.

Relace R je funkcionální.

Komentář. Fukcionální binární relace R na množině A může být ztotožněna s funkcí fR : A −→ A takto: y = fR(x)platí právě tehdy, když platí x R y. Obráceně každá funkce f : A −→ A dává vznikout funkcionální binární relaci Rf

na množině A: definujte, že x Rf y platí právě tehdy, když platí y = f(x).

Samozřejmě, ne každá binární relace je funkcionální: buď

pro nějaké x existují různá y, y′ tak, že platí x R y a současně x R y′.

Příklad: A = {a, b}, R = {(a, a), (a, b)}. Existuje totiž x ∈ A (sice x = a) tak, že platí x R y a současně x R y′

pro různá y, y′, sice pro y = a a y′ = b.

nebo

pro nějaké x neexistuje žádné y tak, že platí x R y.

Příklad: A = {a, b}, R = {(a, a), (a, b)}. Existuje totiž x ∈ A (sice x = b) tak, že neexistuje žádné y tak, že platíx R y. Oba možní kandidáti, totiž y = a a y = b, selhávají.

Pojem relace je obecnější než pojem funkce!

�

2.2.5 Příklad Rozhodněte, zda průnik dvou symetrických relací na téže množině je opět symetrická relace.

Řešení. Označme jako S1 a S2 dvě symetrické na množině A. Dále označme P = S1 ∩ S2. Máme rozhodnout,zda P je opět symetrická relace.Protože S1 = Sop

1 (symetrie S1) a S2 = Sop2 (symetrie S2), platí S1 ∩ S2 = Sop

1 ∩ Sop2 = (S1 ∩ S2)op.

Protože S1 ∩ S2 = P , je symetrie P dokázána. �



2.2.6 Příklad Rozhodněte, zda sjednocení dvou antisymetrických relací na téže množině je opět antisymetrickárelace.

Řešení.Označme jako R1 a R2 dvě antisymetrické na množině A. Dále označme S = R1∪R2. Máme rozhodnout,zda S je opět antisymetrická relace.

Komentář. Protože nemáme nejmenší ponětí, zda tvrzení je pravdivé nebo ne, použijeme optimistickou metodu.Budeme se pokoušet tvrzení dokázat. Buď se nám to povede, nebo se důkaz na nějakém místě zadrhne. Toto místopak bude zdrojem protipříkladu, který tvrzení vyvrátí.

Víme, že platí R1∩Rop1 ⊆ ∆A (antisymetrie R1) a také platí R2∩Rop

2 ⊆ ∆A (antisymetrie R2). Chceme dokázat,že platí S ∩ Sop ⊆ ∆A (antisymetrie S).Protože S = R1 ∪R2, platí rovnosti

S ∩ Sop = (R1 ∪R2) ∩ (R1 ∪R2)op = (R1 ∪R2) ∩ (Rop

1 ∪Rop2 )

= (R1 ∩Rop1 ) ∪ (R1 ∩Rop

2 ) ∪ (R2 ∩Rop1 ) ∪ (R2 ∩Rop

2 )

První a čtvrtý člen pravé strany rovnosti jsou podmnožiny ∆A díky antisymetrii R1 a R2. Jsou i druhý a třetíčlen pravé strany rovnosti podmnožiny ∆A? Obecně se nezdá, že by tomu tak být mělo.

Komentář. To je místo, kde se důkaz zadrhává, začínáme konstruovat protipříklad. Pokud se podaří zařídit to tak,aby některý z prostředních dvou členů nebyl podmnožinou ∆A, bude protipříklad hotov.

Zvolme A = {a, b}, R1 = {(a, b)}, R2 = {(b, a)}. Potom R1 ∩ Rop2 = {(a, b)} a R2 ∩ Rop

1 = {(b, a)}, což jistěnejsou podmnožiny ∆A = {(a, a), (b, b)}.Jsou relace R1 a R2 antisymetrické? Jsou. Platí totiž R1 ∩ Rop

1 = ∅ a R2 ∩ Rop2 = ∅ a prázdná množina je

podmnožinou jakékoli množiny, tedy i množiny ∆A.Závěr: uvedené tvrzení neplatí. Nalezli jsme množinu A a dvě antisymetrické relace R1 a R2 na A takové,

že R1 ∪R2 není antisymetrická relace na A. �

2.2.7 Příklad Popište všechny relace ekvivalence na množině A = {a, b, c}.

Řešení. Stačí popsat nejrůznější možnosti „slepeníÿ prvků množiny A.

1. Slepí se všechny prvky a, b, c.

To odpovídá relaci E1, definované vztahem x E1 y právě když x, y ∈ A.

Relace E1 je zjevně relace ekvivalence.

2. Slepí se prvky a a b, prvkek c se slepí pouze sám se sebou.

To odpovídá relaci E2, definované vztahem x E2 y právě když x, y ∈ {a, b} nebo x, y ∈ {c}.Relace E2 je zjevně relace ekvivalence.

3. Slepí se prvky a a c, prvkek b se slepí pouze sám se sebou.

To odpovídá relaci E3, definované vztahem x E3 y právě když x, y ∈ {a, c} nebo x, y ∈ {b}.Relace E3 je zjevně relace ekvivalence.

4. Slepí se prvky b a c, prvkek a se slepí pouze sám se sebou.

To odpovídá relaci E4, definované vztahem x E4 y právě když x, y ∈ {b, c} nebo x, y ∈ {a}.Relace E4 je zjevně relace ekvivalence.

5. Každý z prvků a, b, c se slepí pouze sám se sebou.

To odpovídá relaci E5, definované vztahem x E5 y právě když x = y.

Relace E5 je zjevně relace ekvivalence.

Žádné další relace ekvivalence na množině {a, b, c}, než výše popsané relace E1 až E5, nejsou.

Komentář. Ukázali jsme užitečnou techniku: relaci ekvivalence na množině A můžeme popsat rozkladem množiny Ana disjunktní části. Tento rozklad jsou pak jednotlivé třídy ekvivalence. Například pro výše uvedenou relaci E3 platíE3[a] = E3[c] = {a, c} a E3[b] = {b}.

�


Kapitola 3

Počítání modulo číslo

V odstavci 3.1 jsou řešeny příklady ze základní teorie lineárních rovnic v Zm. Jádrem všech příkladů je bezpečnézvládnutí běhu rozšířeného Eukleidova algoritmu a sestavení příslušné Bezoutovy rovnosti.V odstavci 3.2 pak jsou řešeny příklady pomocí hlubších výsledků modulární aritmetiky: čínské věty o zbyt-

cích a Eulerovy věty.

3.1 Inverse, lineární rovnice a diofantické rovnice

3.1.1 Příklad Pokud existuje, nalezněte inversi k číslu 51 v Z501.

Řešení. Víme, že inverse existuje právě když gcd(501, 51) = 1. Největšího společného dělitele nalezneme rozší-řeným Eukleidovým algoritmem:

a b q r α2 α1 β2 β1501 51 1 0 0 1501 51 9 42 0 1 1 -951 42 1 9 1 -1 -9 1042 9 4 6 -1 35 10 -499 6 1 3 35 -36 -49 596 3 2 0

Spočetli jsme, že gcd(501, 51) = 3, inverse čísla 51 v Z501 neexistuje.

Komentář. Jako vedlejší produkt jsme rozšířeným Eukleidovým algoritmem získali příslušnou Bezoutovu rovnost3 = −36 · 501 + 59 · 51 v Z. Pro naši úlohu tato rovnost získá obrovský význam v případě, kdy nám vyjde největšíspolečný dělitel 1, viz příklad 3.1.2.

�

3.1.2 Příklad Pokud existuje, nalezněte inversi k číslu 17 v Z851.

Řešení. Víme, že inverse existuje právě když gcd(851, 17) = 1. Největšího společného dělitele nalezneme rozší-řeným Eukleidovým algoritmem:

a b q r α2 α1 β2 β1851 17 1 0 0 1851 17 50 1 0 1 1 -5017 1 17 0

Spočetli jsme, že gcd(851, 17) = 1, inverse čísla 51 v Z501 existuje.Rozšířený Eukleidův algoritmus nám dodal i příslušnou Bezoutovu rovnost:

1 = 1 · 851 + (−50) · 17 v Z


20 Kapitola 3. Počítání modulo číslo

Přečteme-li Bezoutovu rovnost v Z851, dostaneme 1 = (−50) · 17. Zjistili jsme, že inverse k číslu 17 v Z851 ječíslo −50 = 801. �

3.1.3 Příklad Vyřešte rovnici 51x = 36 v Z501.

Řešení. Způsobem, předvedeným v příkladu 3.1.1, nalezneme gcd(501, 51) = 3. Protože 3 | 36, má zadanárovnice právě tři různá řešení v Z501 podle věty o klasifikaci řešení lineárních rovnic.Danou rovnici nejprve „zkrátímeÿ třemi, tj. zaměříme se na rovnici 17x = 12 v Z167. Víme, že gcd(167, 17) =

1, a proto má rovnice 17x = 12 jednoznačné řešení v Z167. K nalezení tohoto řešení potřebujeme nalézt inversik 17 v Z167. Tuto inversi nalezneme rozšířeným Eukleidovým algoritmem:

a b q r α2 α1 β2 β1167 17 1 0 0 1167 17 9 14 0 1 1 -917 14 1 3 1 -1 -9 1014 3 4 2 -1 5 10 -493 2 1 1 5 -6 -49 592 1 2 0

Bezoutova rovnost má tedy tvar 1 = −6 · 167 + 59 · 17, proto je inverse k 17 v Z167 číslo 59. Řešení rovnice17x = 12 v Z167 je číslo x = 17−1 · 12 = 59 · 12 = 708 = 40 v Z167. Volbou k = 0, 1, 2 dostaneme pak tři různářešení xk = x+ k · 167 v Z501:

x0 = 40, x1 = 40 + 1 · 167 = 207, x2 = 40 + 2 · 167 = 374 v Z501

�

3.1.4 Příklad Vyřešte rovnici 15x+ 81y = 195 v Z.

Řešení. Jedná se o diofantickou rovnici. Nejprve zjistíme, zda řešení existuje. Spočteme gcd(15, 81) = 3 (roz-šířeným Eukleidovým algoritmem). Protože 3 | 195, řešení existuje. Původní rovnici číslem tři můžeme zkrátit:ekvivalentním problémem tedy je vyřešit rovnici 5x+ 27y = 65 v Z. Ta má tu výhodu, že gcd(5, 27) = 1.Hledání řešení rozdělíme do dvou kroků:

1. Partikulární řešení je jakákoli dvojice, která problém 5x+27y = 65 řeší. Můžeme jako partikulární řešenízvolit například dvojici (13, 0).

Komentář. Pokud se nám nepovede partikulární řešení uhodnout, pomůže opět rozšířený Eukleidův algoritmus,spuštěný na koeficienty 5 a 27:

a b q r α2 α1 β2 β127 5 1 0 0 127 5 5 2 0 1 1 -55 2 2 1 1 -2 -5 112 1 2 0

Proto má Bezoutova rovnost tvar 5 · 11 + 27 · (−2) = 1. Když ji vynásobíme 65, dostaneme rovnost 5 · 715 + 27 ·(−130) = 65. Získali jsme partikulární řešení (715,−130).

2. Řešení homogenní rovnice 5x+ 27y = 0 jsou dvojice t · (27,−5), kde t ∈ Z.

Celkové řešení je přímka (13, 0) + t · (27,−5), kde t ∈ Z. �

3.1.5 Příklad Dokažte, že v Zm platí: Jestliže mají a a b inversi, má inversi i součin a · b.


3.2. Čínská věta o zbytcích a Eulerova věta 21

Řešení. Hledáme číslo x v Zm, které jednoznačně řeší rovnici (a · b) · x = 1 v Zm.Nejprve ukážeme, že takové x je určeno jednoznačně. Předpokládejme, že platí (a · b) · u = 1 a (a · b) · v = 1

v Zm. Díky asociativitě násobení v Zm potom platí a · (b · u) = 1 a a · (b · v) = 1 v Zm. Protože a−1 existuje,platí i rovnosti b ·u = a−1 a b · v = a−1 v Zm. Protože b−1 existuje, platí i rovnosti u = b−1 · a−1 a v = b−1 · a−1v Zm. Dokázali jsme, že u = v v Zm.Nyní stačí ukázat, že číslo b−1 · a−1 je řešením rovnice (a · b) · x = 1 v Zm. Stačí za x dosadit: využijeme

asociativitu násobení a vlastnosti inversí:

(a · b) · (b−1 · a−1) = a · (b · b−1) · a−1 = a · a−1 = 1 v Zm

�

3.2 Čínská věta o zbytcích a Eulerova věta

3.2.1 Příklad Nalezněte řešení soustavy

x = 2 v Z6 x = 2 v Z7 x = 6 v Z25

Řešení. Protože gcd(6, 7) = gcd(6, 25) = gcd(7, 25) = 1, můžeme použít čínskou větu o zbytcích. Řešení budeurčeno jednoznačně v ZM , kde M = 6 · 7 · 25 = 1 050. Řešení napíšeme ve tvaru

x = 2 · +2 · +6 ·7 · 25·? 6 · 25·? 6 · 7·?

Čísla v jednotlivých obdélnících zajištují jejich nulovost: například první obdélník se anuluje při čtení v Z7 av Z25. Zbývá dopočítat otazníky: ty zajistí jedničkovost obdélníků.

1. První obdélník: spočteme 7 · 25 = 175 = 1 v Z6. Protože 1−1 = 1 v Z6, obsahuje první obdélník součin7 · 25 · 1.

2. Druhý obdélník: spočteme 6 · 25 = 150 = 3 v Z7. Protože 3−1 = 5 v Z7, obsahuje druhý obdélník součin6 · 25 · 5.

3. Třetí obdélník: spočteme 6 · 7 = 42 = 17 v Z25. Protože 17−1 = 3 v Z25, obsahuje třetí obdélník součin6 · 7 · 3.

Řešení je

x = 2 · 7 · 25 · 1 + 2 · 6 · 25 · 5 + 6 · 6 · 7 · 3 = 350 + 1 500 + 756 = 2 606 = 506 v Z1 050

�

3.2.2 Příklad Rozhodněte, zda 107 je prvočíslo.

Řešení. Stačí vyzkoušet dělitelnost čísla 107 všemi prvočísly ≤√107

.= 10, 34. Pokud vyjdou vždy nenulové

zbytky, bude číslo 107 prvočíslo.

Komentář. Tomuto postupu se říká Eratosthenovo síto. Jde vlastně o test prvočíselnosti hrubou silou. Pro lepší testyprvočíselnosti nemáme vybudovannou patřičnou teorii.

Takovými prvočísly jsou 2, 3, 5 a 7.Protože platí

107 = 2 · 53 + 1107 = 3 · 35 + 2107 = 5 · 21 + 2107 = 7 · 15 + 2

je číslo 107 prvočíslo. �


22 Kapitola 3. Počítání modulo číslo

3.2.3 Příklad Spočítejte ϕ(856).

Řešení. Pro zjištění hodnoty Eulerovy funkce potřebujeme znát prvočíselný rozklad čísla 856. Nemáme jinéprostředky než nalézt tento rozklad hrubou silou:

856 = 2 · 428 = 22 · 214 = 23 · 107

Protože 107 je podle příkladu 3.2.2 prvočíslo, nalezli jsme prvočíselný rozklad čísla 856.Protože gcd(23, 107) = 1, platí ϕ(856) = ϕ(23) · ϕ(107) = (23 − 22) · (107− 1) = 4 · 106 = 424. �

3.2.4 Příklad Spočtěte 28 457297 917 v Z856.

Řešení. Nejprve upravíme základ mocniny v Z856: 28 457 = 209. Víme tedy, že v Z856 platí 28 457297 917 =209297 917.Spočteme gcd(856, 209) rozšířeným Eukleidovým algoritmem:

a b q r α2 α1 β2 β1856 209 1 0 0 1856 209 4 20 0 1 1 -4209 20 10 9 1 -10 -4 4120 9 2 2 -10 21 41 -869 2 4 1 21 -94 -86 3852 1 2 0

Tudíž gcd(856, 209) = 1, můžeme použít Eulerovu větu, která nám říká, že 209ϕ(856) = 209424 = 1. (Hodnotuϕ(856) = 424 jsme spočetli v příkladu 3.2.3.) Spočteme exponent modulo ϕ(856): 297 917 = 424 · 702 + 269.Proto platí v Z856 následující rovnosti:

28 457297 917 = 209297 917 = 209424·702+269 = (209424)702 · 209269 = 1702 · 209269 = 209269

Dále musíme postupovat algoritmem opakovaných čtverců. Převedeme exponent 269 do binárního zápisu:

(269)2 = 100001101

což nám dá řídící slovo XSSSSSXSXSSX pro algoritmus opakovaných čtverců (následující výpočty jsouv Z856):

X 209 = 1 · 209 = 209S 2092 = 2092 = 43 681 = 25S 2094 = 252 = 625S 2098 = 6252 = 390 625 = 289S 20916 = 2892 = 83 521 = 489S 20932 = 4892 = 239 121 = 297X 20933 = 297 · 209 = 62 073 = 441S 20966 = 4412 = 194 481 = 169X 20967 = 169 · 209 = 35 321 = 225S 209134 = 2252 = 50 625 = 121S 209268 = 1212 = 14 641 = 89X 209269 = 89 · 209 = 18 601 = 625

Spočítali jsme 28 457297 917 = 209269 = 625 v Z856. �


Kapitola 4

RSA a lineární kódy

V odstavci 4.1 je spočteno několik příkladů na útok na protokol RSA. V každém z těchto příkladů se několikrátvyužívá rozšířený Eukleidův algoritmus, algoritmus opakovaných čtverců a čínská věta o zbytcích. Příklady nazvládnutí těchto technik jsou v kapitole 3.V odstavci 4.2 jsou řešeny příklady na nalezení kontrolní matice z generující matice a naopak. Na spočtení

složitějších příkladů z teorie lineárních kódů nebyla odpřednesena teorie.

4.1 Útoky na RSA

4.1.1 Příklad Dešifrujte hrubou silou zprávu 21 pro Alici, znáte-li Alicin veřejný klíč (703, 53) v protokoluRSA.

Řešení. Nejprve nalezneme faktorizaci Alicina modulu 703. Použijeme k tomu faktorizaci hrubou silou: musímevyzkoušet všechna prvočísla menší nebo rovna číslu

√703 ≤ 27. Dostaneme rozklad 703 = 19 · 37.

Komentář. Rozklad modulu RSA na prvočísla hrubou silou je nejslabším článkem útoku na RSA hrubou silou.Takový rozklad je totiž výpočetně velmi náročný: trvá exponenciálně dlouho.

Nyní potřebujeme najít Alicin dešifrovací exponent. K tomu potřebujeme spočítat ϕ(703) = 18 · 36 = 648 av Z648 invertovat šifrovací exponent 53. Spustíme rozšířený Eukleidův algoritmus:

a b q r α2 α1 β2 β1648 53 1 0 0 1648 53 12 12 0 1 1 -1253 12 4 5 1 -4 -12 4912 5 2 2 -4 9 49 -1105 2 2 1 9 -22 110 2692 1 2 0

Inverse k 53 v Z648 je tedy 269. Alicin soukromý klíč je (703, 269).Pro dešifrování zprávy je zapotřebí spočítat mocninu 21269 v Z703. Využijeme k tomu algoritmus opakovaných

čtverců a čínskou větu o zbytcích.

Komentář. Tato technika je rozumná: modul RSA máme rozložen na dvě (nesoudělná) prvočísla, která jsou řádověmenší než původní modul. Budeme tak pracovat s relativně malými čísly.

V každém případě musíme zjistit binární hodnotu exponentu:

(269)2 = 100001101

Řídící slovo pro algoritmus opakovaných čtverců tedy je XSSSSSXSXSSX.

1. Výpočet 21269 v Z19:


24 Kapitola 4. RSA a lineární kódy

X 21 = 1 · 21 = 2S 212 = 22 = 4S 214 = 42 = 16 = −3S 218 = (−3)2 = 9S 2116 = 92 = 81 = 5S 2132 = 52 = 25 = 6X 2133 = 6 · 21 = 126 = 12S 2166 = 122 = 144 = 11X 2167 = 11 · 21 = 231 = 3S 21134 = 32 = 9S 21268 = 92 = 81 = 5X 21269 = 5 · 21 = 105 = 10

Spočítali jsme, že 21269 = 10 v Z19.

2. Výpočet 21269 v Z37:

X 21 = 1 · 21 = 21 = −16S 212 = (−16)2 = 256 = 34 = −3S 214 = (−3)2 = 9S 218 = 92 = 81 = 7S 2116 = 72 = 49 = 12S 2132 = 122 = 144 = 33X 2133 = 33 · 21 = 693 = 27 = −10S 2166 = (−10)2 = 100 = 26 = −11X 2167 = (−11) · 21 = −231 = −9S 21134 = (−9)2 = 81 = 7S 21268 = 72 = 49 = 12X 21269 = 12 · 21 = 252 = 30

Spočítali jsme, že 21269 = 30 v Z37.

Připravíme si koeficienty pro čínskou větu o zbytcích. Potřebujeme 37−1 v Z19 a 19−1 v Z37.

1. Inverse 37 v Z19. Využijeme rovnosti 37 = −1 v Z19. Proto je 37−1 = −1 = 18 v Z19.

Komentář. Tento způsob nalezení inverse (všimnutí si speciálního vztahu) je samozřejmě legální. Pochopitelnětato cesta bývá nejrychlejší, nejde ale použít vždy.

2. Inversi k 19 v Z37 spočítáme opět rozšířeným Eukleidovým algoritmem:

a b q r α2 α1 β2 β137 19 1 0 0 137 19 1 18 0 1 1 -119 18 1 1 1 -1 -1 218 1 18 0

Spočetli jsme 19−1 = 2 v Z37.

Z čínské věty o zbytcích dostáváme rovnost

21269 = 10 · 37 · 18 + 30 · 19 · 2 = 6 660 + 1 140 = 7 800 = 67 v Z703

Dešifrovaná zpráva je 67. �

4.1.2 Příklad Dvěma účastníkům s veřejnými klíči (403, 13) a (403, 11) byla zaslána stejná zpráva z. Evezachytila c1 = 47 a c2 = 70. Nalezněte zprávu z metodou útoku outsidera.


4.1. Útoky na RSA 25

Řešení. Vidíme, že šifrovací exponenty obou účastníků jsou nesoudělné. Rozšířeným Eukleidovým algoritmemspočteme Bezoutovu rovnost:

a b q r α2 α1 β2 β113 11 1 0 0 113 11 1 2 0 1 1 -111 2 5 1 1 -5 -1 62 1 2 0

Bezoutova rovnost má tvar 1 = −5 · 13 + 6 · 11, neboli 1 + 5 · 13 = 6 · 11. Proto platí i rovnost

z · 475 = z · (z13)5 = z1+5·13 = z6·11 = (z11)6 = 706 v Z403

Protože platí 475 = 125 a 706 = 194 v Z403 (to spočteme algoritmem opakovaných čtverců jako v příkladu 4.1.1),máme vyřešit lineární rovnici

z · 125 = 194 v Z403 (4.1)

Zjistíme, zda existuje inverse k 125 v Z403. Opět rozšířeným Eukleidovým algoritmem:

a b q r α2 α1 β2 β1403 125 1 0 0 1403 125 3 28 0 1 1 -3125 28 4 13 1 -4 -3 1328 13 2 2 -4 2 13 -2913 2 6 1 2 -76 -29 1872 1 2 0

Inverse k 125 v Z403 je 187. Řešení rovnice (4.1) je z = 125−1 · 194 = 187 · 194 = 166 v Z403 a číslo 166 jepůvodně odeslaná zpráva. �

4.1.3 Příklad Dvěma účastníkům s veřejnými klíči (391, 17) a (391, 13) byla zaslána stejná zpráva z. Evezachytila c1 = 34 a c2 = 102. Nalezněte zprávu z metodou útoku outsidera.

Řešení. Protože evidentně platí gcd(17, 13) = 1, spočítáme rozšířeným Eukleidovým algoritmem Bezoutovurovnost:

a b q r α2 α1 β2 β117 13 1 0 0 117 13 1 4 0 1 1 -113 4 3 1 1 -3 -1 43 1 3 0

Bezoutova rovnost má tvar 1 = −3 · 17 + 4 · 13, neboli 1 + 3 · 17 = 4 · 13. Proto platí i rovnost

z · 343 = z · (z17)3 = z1+3·17 = z4·13 = (z13)4 = 1024 v Z391

Protože platí 343 = 204 a 1024 = 340 v Z391 (to spočteme algoritmem opakovaných čtverců jako v pří-kladu 4.1.1), máme vyřešit lineární rovnici

z · 204 = 340 v Z391 (4.2)

Zjistíme, zda existuje inverse k 204 v Z391. Opět rozšířeným Eukleidovým algoritmem:

a b q r α2 α1 β2 β1391 204 1 0 0 1391 204 1 187 0 1 1 -1204 187 1 17 1 -1 -1 2187 17 11 0



Zjistili jsme, že gcd(391, 204) = 17, tudíž inverse k 204 v Z391 neexistuje a rovnice (4.2) má přesně 17 různýchřešení, pokud navíc platí 17 | 340.

Komentář. Jedna možnost je nyní zjistit, zda 17 | 340 a pak případně 17 různých řešení rovnice (4.2) najít způsobempředvedeným v příkladu 3.1.3 a každé z těchto řešení vyzkoušet. Předvedeme jiný postup: právě jsme totiž nalezlidělitele čísla 391, sice číslo 17.

Protože jsme zjistili, že platí 17 | 391, můžeme modul 391 faktorizovat: 391 = 17 · 23. Zprávu z naleznemezpůsobem, popsaným v příkladu 4.1.1.

1. Platí ϕ(391) = 16 ·22 = 352. Nalezneme soukromý klíč účastníka s veřejným klíčem (391, 17). To znamenáspočítat inversi k 17 v Z352. Spustíme rozšířený Eukleidův algoritmus:

a b q r α2 α1 β2 β1352 17 1 0 0 1352 17 20 12 0 1 1 -2017 12 1 5 1 -1 -20 2112 5 2 2 -1 3 21 -625 2 2 1 3 -7 -62 1452 1 2 0

Zjistili jsme, že 17−1 = 145 v Z352. Proto je příslušný soukromý klíč (391, 145).

2. Hledaná zpráva je z = 34145 v Z391. Tuto mocninu spočítáme způsobem uvedeným v příkladu 4.1.1.

Protože (145)2 = 10010001, je řídící slovo pro algoritmus opakovaných čtverců XSSSXSSSSX. Spočí-táme 34145 v Z17 a Z23 a poté použijeme čínskou větu o zbytcích. Protože 34 = 0 v Z17, je 34145 = 0v Z17.

Výpočet 34145 = 11145 v Z23:

X 11 = 1 · 11 = 11S 112 = 121 = 6S 114 = 62 = 36 = 13S 118 = 132 = 169 = 8X 119 = 8 · 11 = 88 = 19 = −4S 1118 = (−4)2 = 16 = −7S 1136 = (−7)2 = 49 = 3S 1172 = 32 = 9S 11144 = 92 = 81 = 12X 21145 = 12 · 11 = 132 = 17

Spočetli jsme, že 34145 = 17 v Z23.

Podle čínské věty o zbytcích platí:

34145 = 0 · 23 · 3 + 17 · 17 · 19 = 5 491 = 17 v Z391

protože 23−1 = 6−1 = 3 v Z17 a 17−1 = (−6)−1 = −4 = 19 v Z23

Odeslaná zpráva je z = 17.

Komentář. Upozorněme, že časová složitost právě předvedeného útoku se podstatně liší od útoku hrubou silouz příkladu 4.1.1. V příkladu 4.1.1 jsme museli faktorizovat modul RSA hrubou silou, a to trvá exponenciálně dlouho.V právě dopočteném příkladu jsme faktorizaci modulu RSA zjistili z Eukleidova algoritmu, který má polynomiálnísložitost.

�


4.2. Generující a kontrolní matice 27

4.2 Generující a kontrolní matice

4.2.1 Příklad Víme, že generující matice G lineárního kódu nad Z11 je(5 4 3 2 77 6 4 0 1

)Nalezněte (nějakou) příslušnou kontrolní matici H.

Řešení.

Komentář. Danou úlohu můžeme vyřešit dvěma různými způsoby. Předvedeme oba způsoby.

1. První způsob řešení: spustíme GEM.(5 4 3 2 77 6 4 0 1

)∼(5 4 3 2 70 6 8 2 0

)R1R1 + 4 ·R2

Komentář. Používáme „zdravotní značeníÿ, abychom neztratili přehled o tom, co se děje.Všechny výpočty jsou samozřejmě v Z11. Značka R1 znamená: nový první řádek je opsaný starý první řádek.Značka R1 +4 ·R2 znamená: nový druhý řádek je starý první řádek, ke kterému jsme přičetli 4-násobek staréhodruhého řádku. To je totiž úprava, nulující první pozici na druhém řádku: v Z11 platí 5 + 4 · 7 = 33 = 0.

Gaussova eliminace skončila, hodnost matice G (tj. počet nenulových řádků po skončení Gaussovy elimi-nace) je 2.

V řádcích hledané matice H budou prvky fundamentálního systému homogenní rovnice(5 4 3 2 7 00 6 8 2 0 0

)(4.3)

Počet prvků tohoto fundamentálního systému je 5− 2 = 3, to plyne z Frobeniovy věty. Prvky fundamen-tálního systému nalezneme metodou organisovaného hádání.

Vektory fundamentálního systému mají tvar

(a1, a2, 1, 0, 0) (b1, b2, 0, 1, 0) (c1, c2, 0, 0, 1)

Volbou nul a jedniček v posledních třech položkách jsme totiž zajistili lineární nezávislost hledanýchvektorů a nyní dopočítáme v každém vektoru první dvě položky pomocí soustavy (4.3).

(a) První vektor: dosazení vektoru (a1, a2, 1, 0, 0) do druhé rovnice v (4.3) dává 6a2 + 8 = 0 v Z11 a povyřešení je a2 = 6.

Dosazení vektoru (a1, 6, 1, 0, 0) do první rovnice v (4.3) dává 5a1 + 24+ 3 = 0 v Z11 a po vyřešení jea1 = 10.

První vektor fundamentálního systému je (10, 6, 1, 0, 0).

(b) Druhý vektor: dosazení vektoru (b1, b2, 0, 1, 0) do druhé rovnice v (4.3) dává 6b2 + 2 = 0 v Z11 a povyřešení je b2 = 7.

Dosazení vektoru (b1, 7, 0, 1, 0) do první rovnice v (4.3) dává 5b1 + 28 + 2 = 0 v Z11 a po vyřešení jeb1 = 5.

Druhý vektor fundamentálního systému je (5, 7, 0, 1, 0).

(c) Třetí vektor: dosazení vektoru (c1, c2, 0, 0, 1) do druhé rovnice v (4.3) dává 6c2 + 0 = 0 v Z11 a povyřešení je c2 = 0.

Dosazení vektoru (b1, 0, 0, 0, 1) do první rovnice v (4.3) dává 5c1+7 = 0 v Z11 a po vyřešení je c1 = 3.

Třetí vektor fundamentálního systému je (3, 0, 0, 0, 1).

Kontrolní matice H je (například) 10 6 1 0 05 7 0 1 03 0 0 0 1



2. Druhý způsob řešení: původní matici budeme upravovat tak, abychom dostali na začátku jednotkovoumatici. (

5 4 3 2 77 6 4 0 1

)∼(5 4 3 2 70 6 8 2 0

)R1R1 + 4 ·R2

∼

(5 0 5 8 70 6 8 2 0

)R1 + 3 ·R2R2

∼(1 0 1 6 80 1 5 4 0

)9 ·R12 ·R2

Nyní použijeme větu z přednášky: generující matice je v blokovém tvaru(1 0 1 6 80 1 5 4 0

)a proto je příslušná kontrolní matice H −1 −5 1 0 0

−6 −4 0 1 0−8 −0 0 0 1

= 10 6 1 0 05 7 0 1 03 0 0 0 1

�

4.2.2 Příklad Víme, že kontrolní matice H lineárního kódu nad Z13 je(5 4 3 2 7

)Nalezněte (nějakou) příslušnou generující matici G.

Řešení. GEM končí po nula krocích, matice Hmá hodnost 1 a matice G bude obsahovat prvky fundamentálníhosystému homogenní rovnice (

5 4 3 2 7 0)

(4.4)

Počet vektorů ve fundamentálním systému je 5 − 1 = 4 podle Frobeniovy věty a my je nalezneme metodouorganizovaného hádání.Označme čtyři vektory fundamentálního systému následovně:

(a, 1, 0, 0, 0) (b, 0, 1, 0, 0) (c, 0, 0, 1, 0) (d, 0, 0, 0, 1)

Požadavky na jednotlivé první položky dostaneme dosazováním jednotlivých vektorů do homogenní rovnice (4.4):

5a+ 4 = 0 5b+ 3 = 0 5c+ 2 = 0 5d+ 7 = 0 v Z13

nebolia = 7 b = 2 c = 10 d = 9 v Z13

Generující matice G je (například) 7 1 0 0 02 0 1 0 010 0 0 1 09 0 0 0 1

�


Kapitola 5

Počítání modulo polynom

Počítání modulo polynom se řídí stejnými zákonitostmi jako počítání modulo číslo. Celá čísla jsou ovšem sys-tematicky nahrazena polynomy nad Zp, kde p je prvočíslo. Snad pomůže následující tabulka:

modulo číslo modulo polynom

základní množina „číselÿ Z Zp[x], p prvočíslo„prvočísloÿ prvočíslo ireducibilní polynommnožina „čísel moduloÿ Zm Zp[x]/m(x)

V odstavci 5.1 jsou vyřešeny základní úlohy lineární algebry modulo polynom a v odstavci 5.2 příklady týkajícíse konečných těles.

5.1 Lineární algebra modulo polynom

5.1.1 Příklad Pokud existuje, nalezněte řešení lineární rovnice p(x) · (x2 + 1) = (x+ 2) v Z3[x]/(x3 + 1).

Řešení. Nejprve zjistíme, zda má polynom x2+1 v Z3[x]/(x3+1) inversi. Použijeme k tomu rozšířený Eukleidůvalgoritmus pro polynomy. Všechny výpočty v tomto algoritmu jsou v Z3[x].

a(x) b(x) q(x) r(x) α2(x) α1(x) β2(x) β1(x)x3 + 1 x2 + 1 1 0 0 1x3 + 1 x2 + 1 x 2x+ 1 0 1 1 2xx2 + 1 2x+ 1 2x+ 2 2 1 x+ 1 2x 2x2 + 2x+ 12x+ 1 2 x+ 2 0

Zjistili jsme, že Bezoutova rovnost má tvar

(x+ 1) · (x3 + 1) + (2x2 + 2x+ 1) · (x2 + 1) = 2 v Z3[x]

neboli platí(2x+ 2) · (x3 + 1) + (x2 + x+ 2) · (x2 + 1) = 1 v Z3[x]

(vynásobili jsme celou v Bezoutovu rovnost číslem 2−1 = 2 v Z3).Zjistili jsme tedy, že gcd(x3 + 1, x2 + 1) = 1, proto (x2 + 1)−1 v Z3[x]/(x3 + 1) existuje a jde o polynom

x2 + x+ 2.Rovnice p(x) · (x2 + 1) = (x+ 2) má v Z3[x]/(x3 + 1) právě jedno řešení, a to

p(x) = (x2 + 1)−1 · (x+ 2) = (x2 + x+ 2) · (x+ 2) = x3 + x+ 1 = x v Z3[x]/(x3 + 1)

�

5.1.2 Příklad Pokud existuje, nalezněte řešení lineární rovnice p(x) · (2x+ 1) = (x+ 2) v R[x]/(x2 + 1).


30 Kapitola 5. Počítání modulo polynom

Řešení.

Komentář. Jsou možné dva způsoby řešení, ukážeme oba dva.

1. První způsob: nalezneme (pokud existuje) inversi k 2x+ 1 v R[x]/(x2 + 1). Protože polynom x2 + 1 jeireducibilní v R[x], je R[x]/(x2+1) těleso. Protože 2x+1 není nulový prvek, inverse k 2x+1 v R[x]/(x2+1)existuje.

K nalezení inverse k 2x + 1 použijeme rozšířený Eukleidův algoritmus pro polynomy. Všechny výpočtyv tomto algoritmu jsou v R[x].

a(x) b(x) q(x) r(x) α2(x) α1(x) β2(x) β1(x)x2 + 1 2x+ 1 1 0 0 1x2 + 1 2x+ 1 1

2x−14

54 0 1 1 − 12x+

14

2x+ 1 54

85x+

45 0

Bezoutova rovnost má tudíž tvar

1 · (x2 + 1) + (−12x+14) · (2x+ 1) = 5

4v R[x]

neboli45· (x2 + 1) + (−2

5x+15) · (2x+ 1) = 1 v R[x]

(původní Bezoutovu rovnost jsme vynásobili ( 54 )−1 = 4

5 v R[x]).

Zjistili jsme, že gcd(x2+1, 2x+1) = 1, proto (2x+1)−1 v R[x]/(x2+1) existuje a jde o polynom − 25x+15 .

Zadaná rovnice má tedy jediné řešení:

p(x) = (2x+ 1)−1 · (x+ 2) = (−25x+15) · (x+ 2) = −2

5x2 − 3

5x+25= −35x+45v R[x]/(x2 + 1)

2. Druhý způsob: z přednášky víme, že platí R[x]/(x2+1) je těleso, které je isomorfní tělesu C komplexníchčísel, tudíž jde o obyčejnou lineární rovnici p · (2i+ 1) = i+ 2 v komplexním oboru. Proto je řešení tvaru

p =i+ 22i+ 1

=i+ 22i+ 1

· −2i+ 1−2i+ 1

=−3i+ 45

= −35i+45v C

neboli (po ztotožnění i = x)

p(x) = −35x+45v R[x]/(x2 + 1)

�

5.1.3 Příklad Nad tělesem Z2[x]/(x2 + x+ 1) vyřešte (použitím GEM) soustavu lineárních rovnic:

ax1 + x2 + x3 + ax4 = bx1 + bx2 + ax3 + ax4 = 1

(5.1)

kde značíme a = x, b = x+ 1, tj. tabulky sčítání a násobení v Z2[x]/(x2 + x+ 1) vypadají takto:

+ 0 1 a b

0 0 1 a b1 1 0 b aa a b 0 1b b a 1 0

· 0 1 a b

0 0 0 0 01 0 1 a ba 0 a b 1b 0 b 1 a

(5.2)


5.1. Lineární algebra modulo polynom 31

Řešení. Přepíšeme soustavu do matice (a 1 1 a b1 b a a 1

)a matici upravujeme pomocí GEM:(

a 1 1 a b1 b a a 1

)∼(

a 1 1 a b0 0 a 1 1

)R1R2 − a ·R2

Komentář. Používáme „zdravotní značeníÿ, abychom neztratili přehled o tom, co se děje. Viz příklad 4.2.1. ZnačkaR1 znamená: nový první řádek je opsaný starý první řádek. Značka R1 − a ·R2 znamená: nový druhý řádek je starýprvní řádek, od kterého jsme odečetli a-násobek starého druhého řádku.

GEM skončila: hodnost matice soustavy je rovna hodnosti rozšířené matice soustavy (a je rovna 2). PodleFrobeniovy věty řešení soustavy (5.1) existuje.Nalezneme partikulární řešení a fundamentální systém.

1. Partikulární řešení je jakákoli čtveřice, která soustavu řeší. Použijeme zápis soustavy po skončení eliminace(a 1 1 a b0 0 a 1 1

)

Zvolíme-li (x1, 0, 0, 1), bude náš vektor jistě řešit druhou rovnici. První položku dopočítáme z první rovnice:musí platit ax1 + a = b, a tedy ax1 = b− a = 1, neboli x1 = b.

Partikulární řešení je čtveřice (b, 0, 0, 1).

2. Fundamentální systém musí mít 4 − 2 = 2 prvky, protože soustava má 4 neznámé a hodnost maticesoustavy je 2. Použijeme maticový zápis homogenní soustavy(

a 1 1 a 00 0 a 1 0

)(5.3)

První vektor ve fundamentálním systému napíšeme ve tvaru (x1, 0, x2, 1) a druhý vektor ve tvaru (y1, 1, y2, 0).Volba nul a jedniček ve druhé a čtvrté položce zajistí lineární nezávislost.

Komentář. Tvar soustavy (5.3) nám nedovoluje volit jedničky a nuly na posledních dvou položkách. Metodaorganizovaného hádání nám přikazuje pozici jedniček a nul posunout směrem doleva.

Další položky musíme dopočítat.

Dopočtení x2: ze druhé rovnice v (5.3) dostáváme požadavek ax2 + 1 = 0, neboli ax2 = −1 = 1, tudížx2 = b.

Dopočtení x1: z první rovnice v (5.3) dostáváme požadavek ax1+b+a = 0, neboli ax1 = −b−a = b+a = 1,tudíž x1 = b.

Dopočtení y2: ze druhé rovnice v (5.3) dostáváme požadavek ay2 + 0 = 0, neboli ay2 = 0, tudíž y2 = 0.

Dopočtení y1: z první rovnice v (5.3) dostáváme požadavek ay1 + 1 + 0 + 0 = 0, neboli ay1 = −1 = 1,tudíž y1 = b.

Fundamentální systém je tvořen vektory (b, 0, b, 1) a (b, 1, 0, 0).

Celkové řešení soustavy (5.1) je

(b, 0, 0, 1) + α · (b, 0, b, 1) + β · (b, 1, 0, 0)

kde α, β jsou libovolné prvky ze Z2[x]/(x2 + x+ 1). �


32 Kapitola 5. Počítání modulo polynom

5.2 Konečná tělesa

5.2.1 Příklad Označte jako Z3(i) množinu {a + bi | a, b ∈ Z3}. (Připomeňme, že i je komplexní jednotkasplňující i2 = −1.) Na množině Z3(i) definujte zřejmým způsobem sčítání a násobení:

(a+ bi) + (a′ + b′i) = (a+ a′) + (b+ b′)i, (a+ bi) · (a′ + b′i) = (aa′ − bb′) + (ab′ + a′b)i.

Je 〈Z3(i),+, ·〉 těleso?

Řešení.

Komentář. Existuje přímý způsob, jak příklad vyřešit, tj. ověřit axiomy tělesa. Předvedeme způsob jiný: množinaZ3(i) totiž připomíná komplexní čísla, takže by mohlo platit Z3(i) ∼= Z3[x]/(x2 + 1). Připomeňme, že prvky množinyZ3[x]/(x2 + 1) jsou všechny výrazy tvaru bx+ a, kde a, b jsou prvky množiny Z3. Tyto polynomy se sčítají a násobínásledovně: (bx+ a) + (b′x+ a′) = (b+ b′)x+ (a+ a′), (bx+ a) · (b′x+ a′) = (ab′ + a′b)x+ (aa′ − bb′).

Zobrazení f : Z3(i) −→ Z3[x]/(x2 + 1) definované předpisem f(a+ bi) = bx+ a je zřejmě bijekce:

1. Zobrazení f je prosté. Ať platí f(a+ bi) = f(a′ + b′i). Chceme dokázat, že platí a+ bi = a′ + b′i.

Jestliže bx+a = b′x+a′, potom platí b = b′ a současně a = a′. K tomu jsme použili fakta o rovnosti dvoupolynomů. Ukázali jsme, že rovnost a+ bi = a′ + b′i platí.

Dokázali jsme, že zobrazení f je prosté.

2. Zobrazení f je na. Ať bx+a je libovolný prvek Z3[x]/(x2+1). Hledáme prvek a′+ b′i v Z3(i) tak, že platíf(a′ + b′i) = bx+ a.

Stačí zvolit b = b′ a a = a′.

Dokázali jsme, že zobrazení f je na.

Komentář. Právě jsme ukázali, že množiny Z3(i) a Z3[x]/(x2 + 1) jsou z abstraktního hlediska stejné. Zobrazení fslouží jako „přemalováníÿ prvků množiny Z3(i) na prvky množiny Z3[x]/(x2 + 1).Na obou množinách je však definována jistá struktura sčítání a násobení. Musíme ukázat, že zobrazení f tuto struktururespektuje.

Zobrazení f respektuje sčítání a násobení.

1. Zobrazení f respektuje sčítání: máme dokázat, že platí f((a+ bi) + (a′ + b′i)) = f(a+ bi) + f(a′ + b′i), ato pro libovolné prvky a+ bi, a′ + b′i z množiny Z3(i).Levá, stejně jako pravá strana požadované rovnosti je (b+ b′)x+ (a+ a′), to jsme chtěli dokázat.

Dokázali jsme, že zobrazení f respektuje sčítání.

2. Zobrazení f respektuje násobení: máme dokázat, že platí f((a+ bi) · (a′ + b′i)) = f(a+ bi) · f(a′ + b′i), ato pro libovolné prvky a+ bi, a′ + b′i z množiny Z3(i).Levá, stejně jako pravá strana požadované rovnosti je (ab′ + a′b)x+ (aa′ − bb′), to jsme chtěli dokázat.

Dokázali jsme, že zobrazení f respektuje násobení.

Komentář. Právě jsme ukázali, že struktury 〈Z3(i),+, ·〉 a 〈Z3[x]/(x2 + 1),+, ·〉 jsou isomorfní. Isomorfismem jezobrazení f .

Zbývá dokázat, že Z3[x]/(x2 + 1) je těleso. K tomu je zapotřebí dokázat, že polynom x2 + 1 je ireducibilnív Z3[x]. Stačí vyzkoušet dělitelnost polynomu x2 + 1 všemi polynomy stupně přesně 1.

Komentář. To připomíná Eratosthenovo síto pro test prvočíselnosti, viz příklad 3.2.2. Chceme-li testovat ireducibilitupolynomu p(x) stupně n, stačí testovat dělitelnost všemi polynomy q(x) stupně alespoň 1 a nanejvýš n

2 .

Polynom nad Z3 stupně přesně 1 lze zakódovat dvojicí koeficientů (a1, a0), kde a1, a0 jsou prvky Z3 a a1 6= 0.Proto je polynomů stupně právě 1 přesně 2 · 3 = 6. Jsou to polynomy

x, 2x, x+ 1, x+ 2, 2x+ 1, 2x+ 2.

Po vydělení se zbytkem (všechny výpočty jsou v Z3[x]) dostáváme

x2 + 1 = x · x+ 1, x2 + 1 = 2x · 2x+ 1, x2 + 1 = (x+ 1) · (x+ 2) + 2, x2 + 1 = (2x+ 1) · (2x+ 2) + 2,


5.2. Konečná tělesa 33

proto je polynom x2 + 1 ireducibilní v Z3[x] a 〈Z3[x]/(x2 + 1),+, ·〉 je těleso.Protože 〈Z3(i),+, ·〉 a 〈Z3[x]/(x2 + 1),+, ·〉 jsou isomorfní, je těleso i 〈Z3(i),+, ·〉. �

5.2.2 Příklad Existuje těleso, které má přesně 76 různých prvků?

Řešení. Podle věty o klasifikaci konečných těles je každé konečné těleso (až na isomorfismus) některé Galoisovotěleso GF (pn), kde p je prvočíslo a n ≥ 1 je přirozené číslo. Navíc těleso GF (pn) pak má přesně pn různýchprvků.Protože číslo 76 nelze napsat ve tvaru pn, kde p je prvočíslo a n ≥ 1 je přirozené číslo (76 = 22 · 19), konečné

těleso s přesně 76 prvky neexistuje. �

5.2.3 Příklad Nalezněte těleso o 16 prvcích.

Řešení. Protože 16 = 24, hledáme podle věty o klasifikaci konečných těles Galoisovo těleso GF (24). K tomustačí najít ireducibilní polynom m(x) stupně 4 nad Z2. Hledané těleso GF (24) pak je Z2[x]/m(x).Polynom a4x

4 + a3x3 + a2x

2 + a1x + a0 stupně 4 nad Z2 můžeme zakódovat jako pětici (a4, a3, a2, a1, a0)jeho koeficientů, kde ai ∈ Z2 a a4 6= 0. Takových pětic je přesně 1 · 2 · 2 · 2 · 2 = 16.Jediná možnost je prohledat množinu 16 polynomů hrubou silou, protože žádný algoritmus hledající ire-

ducibilní polynomy nemáme k disposici. Přesto lze onu množinu zredukovat: žádný polynom kódovaný pěticí,která obsahuje sudý počet jedniček, není ireducibilní. Každý takový polynom totiž musí mít kořen 1 a proto jedělitelný příslušným kořenovým faktorem x + 1. Projdeme tedy pouze polynomy kódované pěticemi s lichýmpočtem jedniček. Navíc pro ireducibilitu stačí testovat dělitelnost polynomy x, x+ 1, x2, x2 + x, x2 + x+ 1 ax2 + 1.

1. Pětice (1, 0, 0, 0, 0): polynom x4 není ireducibilní, platí x4 = x2 · x2.

2. Pětice (1, 0, 0, 1, 1): polynom x4 + x+1 je ireducibilní. Není totiž dělitelný žádným z polynomů x (zbytek1), x+ 1 (zbytek 1), x2 (zbytek x+ 1), x2 + x (zbytek 1), x2 + x+ 1 (zbytek 1) a x2 + 1 (zbytek x).

Komentář. Tady bychom mohli příklad ukončit. Stačilo najít alespoň jeden ireducibilní polynom stupně 4. Jakuvidíme, je takových polynomů více.

3. Pětice (1, 0, 1, 0, 1): polynom x4 + x2 + 1 není ireducibilní, platí x4 + x2 + 1 = (x2 + x+ 1) · (x2 + x+ 1).

4. Pětice (1, 0, 1, 1, 0): polynom x4 + x2 + x není ireducibilní, platí x4 + x2 + x = x · (x3 + x+ 1).

5. Pětice (1, 1, 0, 0, 1): polynom x4+x3+1 je ireducibilní. Není totiž dělitelný žádným z polynomů x (zbytek1), x+ 1 (zbytek 1), x2 (zbytek 1), x2 + x (zbytek 1), x2 + x+ 1 (zbytek x) a x2 + 1 (zbytek x).

6. Pětice (1, 1, 0, 1, 0): polynom x4 + x3 + x není ireducibilní, platí x4 + x3 + x = x · (x3 + x2 + 1).

7. Pětice (1, 1, 1, 0, 0): polynom x4 + x3 + x2 není ireducibilní, platí x4 + x3 + x2 = x2 · (x2 + x+ 1).

8. Pětice (1, 1, 1, 1, 1): polynom x4 + x3 + x2 + x+ 1 je ireducibilní. Není totiž dělitelný žádným z polynomůx (zbytek 1), x + 1 (zbytek 1), x2 (zbytek x + 1), x2 + x (zbytek 1), x2 + x + 1 (zbytek x + 1) a x2 + 1(zbytek 1).

Nalezli jsme dokonce tři ireducibilní polynomy stupně 4 nad Z3.Hledané těleso je kterékoli ze tří těles Z2[x]/(x4 + x+ 1), Z2[x]/(x4 + x3 + 1), Z2[x]/(x4 + x3 + x2 + x+ 1).

Komentář. Tělesa Z2[x]/(x4+x+1), Z2[x]/(x4+x3+1) a Z2[x]/(x4+x3+x2+x+1) jsou (podle věty o klasifikacikonečných těles) navzájem isomorfní. To dokazovat nebudeme.

�


Kapitola 6

Abstraktní výpočty

V této kapitole jsou spočteny některé příklady z teorie jednoduchých algebraických struktur a rovnicovýchalgebraických specifikací. Nejde dát obecný návod, jak takové příklady řešit. Obecně platná je jediná rada:postupujte vždy formálně a používejte rovnicové vlastnosti jako přepisovací pravidla.Úlohy uvedené v odstavci 6.3 navíc vyžadují statečnou kreativitu: specifikovat můžeme téměř cokoli, měli

bychom ale umět napsanou specifikaci obhájit.

6.1 Grupoidy, pologrupy, monoidy a grupy

6.1.1 Příklad Na množině reálných čísel R je definována binární operace ? následovně:

x ? y = x+ y + x2y

Ukažte, že platí:

1. Operace ? má neutrální prvek e.

2. Pro každé x existuje právě jedno y tak, že x ? y = e. Tomuto jednoznačně určenému y říkáme praváinverse k x.

3. Existuje x tak, že rovnost y ? x = e neplatí pro žádné y. To znamená, že levá inverse k x obecně neexistuje.

Řešení. Vyřešíme jednotlivé body:

1. Neutrální prvek e: chceme najít reálné číslo e tak, aby platily rovnosti x ? e = x a e ? x = x, a to provšechna reálná čísla x.

V první rovnosti x ? e = x přepíšeme levou stranu pomocí definice ?: požadujeme rovnost x+e+x2e = x,neboli e+ x2e = e · (1 + x2) = 0. Proto e = 0.

Pokud ukážeme, že 0 ? x = x platí pro všechna x, ukážeme, že e = 0 je neutrální prvek operace ?.Přepíšeme levou stranu pomocí definice ?: dostáváme rovnost 0 + x+ 02x = x.

Ukázali jsme, že číslo 0 je neutrální prvek operace ?.

2. Zvolme libovolné x. Hledáme jednoznačně určené y tak, aby platilo x ? y = e. Tuto rovnost přepíšeme

pomocí definice ? a znalosti prvku e na x+y+x2y = 0. Ta má jednoznačné řešení vzhledem k y: y =−x

1 + x2.

3. Hledáme takové číslo x, aby rovnice y ? x = e neměla žádné řešení v R. Rozepišme rovnici y ? x = epodle definice ?: y + x + y2x = 0. Pro pevné x se zjevně jedná o kvadratickou rovnici pro y. Ta nebudemít řešení v R například pro x = 1, protože její diskriminant pak bude záporný.

Závěr: pro x = 1 neexistuje y tak, že y ? x = e.

�


6.1. Grupoidy, pologrupy, monoidy a grupy 35

6.1.2 Příklad Rozhodněte, zda 〈R, ?〉 je pologrupa, kde operace ? na množině reálných čísel R je definovánatakto: x ? y = x+ y + xy.

Řešení. Máme rozhodnout, zda rovnost (x ? y) ? z = x ? (y ? z) platí pro všechna reálná čísla x, y, z.Upravíme levou a pravou stranu požadované rovnice podle definice ?.

1. Levá strana: (x ? y) ? z = (x+y+xy) ? z = x+y+xy+z+(x+y+xy)z = x+y+z+xy+xz+yz+xyz.

2. Pravá strana: x ? (y ? z) = x ? (y+z+yz) = x+y+z+yz+x(y+z+yz) = x+y+z+xy+xz+yz+xyz.

Protože levá strana je rovna pravé straně, pro libovolná reálná čísla x, y, z, dokázali jsme asociativitu operace ?.Závěr: 〈R, ?〉 je pologrupa. �

6.1.3 Příklad Rozhodněte, zda 〈N, ?〉 je pologrupa, kde operace ? na množině přirozených čísel N je definovánatakto: x ? y = xy.

Řešení. Máme rozhodnout, zda rovnost (x ? y) ? z = x ? (y ? z) platí pro všechna přirozená čísla x, y, z.Upravíme levou a pravou stranu požadované rovnice podle definice ?.

1. Levá strana: (x ? y) ? z = (xy)z = xyz.

2. Pravá strana: x ? (y ? z) = x ? (yz) = x(yz).

Komentář. Nezdá se, že by (obecně) byla levá strana rovnosti byla stejná jako pravá strana. Tento pocit musímeospravedlnit svědky, kteří dosvědčí, že levá strana je různá od pravé strany.

Levá strana pro x = 3, y = 3, z = 3 je 39 = 19 683 a pravá strana pro x = 3, y = 3, z = 3 je 327 =7625 597 484 987.Asociativní zákon pro ? neplatí a proto 〈N, ?〉 není pologrupa. �

6.1.4 Příklad Označte jako t : {a, b} −→ {a, b} funkci t(a) = b, t(b) = a. Dále označte S = {t, t ◦ t}. Dokažte,že 〈S, ◦〉 je grupa.

Řešení. Především je ◦ skutečně operace na S: to plyne z toho, že t ◦ t = id (identická funkce), takže platírovnosti

id ◦ id = id id ◦ t = t t ◦ id = t t ◦ t = id

Ukázali jsme, že 〈S, ◦〉 je grupoid.

1. Asociativita ◦: skládání funkcí je vždy asociativní.Ukázali jsme, že 〈S, ◦〉 je pologrupa.

2. Neutrální prvek: označíme e = id. Potom platí rovnosti e ◦ f = f ◦ e = f , a to pro všechna f ∈ S.

Ukázali jsme, že 〈S, ◦, e〉 je monoid.

3. Inverse: definujeme t−1 = t a id−1 = id. Definovali jsme unární operaci a zjevně platí rovnosti f−1 ◦ f =f ◦ f−1 = e, a to pro všechna f ∈ S.

Ukázali jsme, že 〈S, ◦, e, (−)−1〉 je grupa.

�

6.1.5 Příklad Centrum grupy 〈G, ?, e, (−)−1〉 je množina

Z(G) = {a ∈ G | a ? g = g ? a pro všechna g ∈ G}.

Ukažte, že množina Z(G) je v G uzavřena na všechny operace, a tvoří tudíž podgrupu grupy 〈G, ?, e, (−)−1〉.


36 Kapitola 6. Abstraktní výpočty

Řešení. Máme dokázat uzavřenost centra na binární operaci, neutrální prvek a inversi.

1. Uzavřenost na binární operaci: máme dokázat, že a1 ? a2 ∈ Z(G), a to pro všechna a1, a2 ze Z(G).

Zvolíme libovolný prvek g ∈ G. Chceme ukázat, že platí rovnost

(a1 ? a2) ? g = g ? (a1 ? a2). (6.1)

Budeme přepisovat levou stranu požadované rovnosti a budeme při tom využívat axiomů grupy:

(a1 ? a2) ? g = a1 ? (a2 ? g) (asociativita ?)= a1 ? (g ? a2) (protože a2 ∈ Z(G))= (a1 ? g) ? a2 (asociativita ?)= (g ? a1) ? a2 (protože a1 ∈ Z(G))= g ? (a1 ? a2) (asociativita ?)

Levou stranu rovnosti (6.1) jsme přepsali na pravou, proto je množina Z(G) uzavřena na operaci ?.

2. Uzavřenost na neutrální prvek: máme dokázat, že e ∈ Z(G).

Zvolíme libovolný prvek g ∈ G. Chceme ukázat, že platí e ? g = g ? e. Tato rovnost ale platí, protože e jeneutrální prvek grupy 〈G, ?, e, (−)−1〉.

3. Uzavřenost na inversi: máme dokázat, že a−1 ∈ Z(G), a to pro všechna a ze Z(G).

Zvolíme libovolný prvek g ∈ G. Chceme ukázat, že platí rovnost

a−1 ? g = g ? a−1. (6.2)

Stačí dokázat, že platí rovnostg = a ? (g ? a−1), (6.3)

protože z (6.3) plyne (6.2) vynásobením zleva prvkem a−1. Budeme upravovat pravou stranu rovnosti (6.3)a využívat při tom axiomů grupy:

a ? (g ? a−1) = (a ? g) ? a−1 (asociativita ?)= (g ? a) ? a−1 (protože a ∈ Z(G))= g ? (a ? a−1) (asociativita ?)= g ? e (axiom pro (−)−1)= g (axiom pro e)

Pravou stranu rovnosti (6.3) jsme přepsali na levou, proto je množina Z(G) uzavřena na operaci (−)−1.

�

6.1.6 Příklad Ať 〈X, /〉 je grupoid a e ∈ X je prvek takový, že platí následující čtyři axiomy

(i) x/e = x (ii) x/x = e (iii) e/(x/y) = y/x (iv) (x/z)/(y/z) = x/y

pro všechny prvky x, y, z z X.Definujte x ? y = x/(e/y) a x−1 = e/x. Dokažte, že e je neutrální prvek operace ? a že x−1 je inverse k x.

Řešení. Nejprve si uvědomme, že ? a (−)−1 jsou skutečně operace. To plyne z toho, že 〈X, /〉 je grupoid. Žádanéaxiomy ověříme v tomto pořadí:

1. Neutralita e: máme ověřit rovnosti x ? e = e ? x = x, a to pro libovolné x ∈ X.

Rovnost x ? e = x dokážeme tak, že budeme přepisovat její levou stranu a budeme při tom využívatdefinici ? a axiomy (i)–(iv):

x ? e = x/(e/e) (definice ?)= x/e (axiom (ii), aplikovaný na e)= x (axiom (i))


6.2. Posety, svazy a Booleovy algebry 37

Rovnost e ? x = x dokážeme tak, že budeme přepisovat její levou stranu a budeme při tom využívatdefinici ? a axiomy (i)–(iv):

e ? x = e/(e/x) (definice ?)= x/e (axiom (iii))= x (axiom (i))

Ukázali jsme, že e je neutrální prvek operace ?.

2. Axiomy pro inverse: máme dokázat, že platí rovnosti x−1 ? x = x ? x−1 = e, a to pro libovolné x ∈ X.

Rovnost x−1 ? x = e dokážeme tak, že budeme přepisovat její levou stranu a budeme při tom využívatdefinici ?, (−)−1 a axiomy (i)–(iv):

x−1 ? x = (e/x)/(e/x) (definice ? a (−)−1)= e (axiom (ii), aplikovaný na e/x)

Rovnost x ? x−1 = e dokážeme tak, že budeme přepisovat její levou stranu a budeme při tom využívatdefinici ?, (−)−1 a axiomy (i)–(iv):

x ? x−1 = x/(e/(e/x)) (definice ? a (−)−1)= x/(x/e) (axiom (iii), aplikovaný na e/x)= x/x (axiom (i))= e (axiom (ii))

Komentář. Povšimněme si, že pro důkaz požadovaných tvrzení jsme nepoužili axiom (iv). Podobnou technikou všaklze dokázat, že operace ? je asociativní, a tudíž, že 〈X, ?, e, (−)−1〉 je grupa. To ale není úplně triviální, je zapotřebídokázat řadu pomocných tvrzení. Zde už axiom (iv) budeme skutečně pořebovat.

�

6.2 Posety, svazy a Booleovy algebry

6.2.1 Příklad Označte jako X množinu všech dělitelů čísla 40. Pro x, y z množiny X definujte x v y právětehdy, když číslo y je dělitelné číslem x. Ukažte, že 〈X,v〉 je poset, ve kterém existují suprema a infima všechdvojic.

Řešení. Protože platí 40 = 23 · 5, má množina X celkem (3 + 1) · (1 + 1) = 8 různých prvků. Platí X ={1, 2, 4, 5, 8, 10, 20, 40}.K tomu, že 〈X,v〉 je poset, stačí ukázat, že relace v je reflexivní, transitivní a antisymetrická. To se dokáže

analogicky jako v příkladu 2.1.4.Nakreslíme Hasseho diagram 〈X,v〉:

1

2 5

4 10

8 20

40

////��

��

��

��

////

(6.4)

Z tohoto obrázku je vidět, že suprema a infima všech dvojic existují: supv{x, y} = lcm(x, y) (nejmenší společnýnásobek x a y) a infv{x, y} = gcd(x, y) (největší společný dělitel x a y). �



6.2.2 Příklad Rozhodněte, zda v obecném svazu 〈X,∧,∨〉 platí nerovnost x ∧ y v x ∧ (y ∨ z).

Řešení.

Komentář. Připomínáme, že svazy jsou přesně posety, ve kterých existují suprema a infima všech dvojic. Přitomplatí x ∧ y = infv{x, y} a x ∨ y = supv{x, y} pro všechna x a y. Této korespondence budeme využívat.

Nerovnost x ∧ y v x ∧ (y ∨ z) platí přesně když platí

x ∧ y v x a současně x ∧ y v y ∨ z (6.5)

pro všechna x, y, z. To plyne z toho, že x ∧ (y ∨ z) je infimum x a y ∨ z v uspořádání v.Levá část požadavku (6.5) je splněna pro všechna x, y: platí totiž infv{x, y} v x.Pravá strana požadavku (6.5) je splněna díky transitivitě uspořádání v. Platí totiž

x ∧ y v y a současně y v y ∨ z (6.6)

a to pro všechna x, y, z.Levá strana požadavku (6.6) je splněna pro všechna x, y: platí totiž infv{x, y} v y.Pravá strana požadavku (6.6) je splněna pro všechna y, z: platí totiž y v supv{y, z}.Závěr: nerovnost x ∧ y v x ∧ (y ∨ z) platí pro všechna x, y, z v libovolném svazu 〈X,∧,∨〉. �

6.2.3 Příklad Ukažte, že poset 〈X,v〉 z příkladu 6.2.1 není Booleova algebra.

Řešení. Připomeňme, že X = {1, 2, 4, 5, 8, 10, 20, 40}. Množina X má tudíž 8 prvků. Podle věty o klasifikacikonečných Booleových algeber by poset 〈X,v〉 z příkladu 6.2.1 musel být isomorfní Booleově algebře

〈exp{a, b, c},∩,∪, ∅, {a, b, c}, {a, b, c} \ (−)〉,

která má 23 = 8 prvků. Hasseho diagram takové Booleovy algebry vypadá následovně:

∅

{a} {b} {c}

{a, b} {a, c} {b, c}

{a, b, c}

?????????????

��

��

????????????

��

????????????

��

????????????

což je Hasseho diagram, který není isomorfní s Hasseho diagramem z obrázku (6.4). Proto 〈X,v〉 z příkladu 6.2.1není Booleova algebra. �

6.2.4 Příklad Ať 〈X,∧,∨,>,⊥, (−)′〉 je Booleova algebra. Definujte x ⇒ y jako zkratku za x′ ∨ y. Dokažte,že x ∧ y v z platí právě tehdy, když platí x v y ⇒ z, a to pro všechna x, y, z z množiny X.

Řešení.

Komentář. Využijeme faktu, že Booleova algebra je přesně distributivní, komplementární svaz s největším a nejmen-ším prvkem. Zvlášť budeme používat definice uspořádání: x v y platí právě tehdy, když x ∨ y = y, což platí právětehdy, když x ∧ y = x, a to pro všechna x a y.


6.3. Jednoduché rovnicové specifikace 39

1. Předpokládejme, že platí x∧ y v z, čili (x∧ y)∨ z = z. Chceme dokázat platnost x v y ⇒ z, neboli platnostrovnosti x ∨ (y′ ∨ z) = y′ ∨ z. Budeme přepisovat y′ ∨ z pomocí zákonů Booleovy algebry:

y′ ∨ z = y′ ∨ ((x ∧ y) ∨ z) (platí (x ∧ y) ∨ z = z)= y′ ∨ ((x ∨ z) ∧ (y ∨ z)) (distributivní zákon)= (y′ ∨ (x ∨ z)) ∧ (y′ ∨ (y ∨ z)) (distributivní zákon)= (y′ ∨ (x ∨ z)) ∧ ((y′ ∨ y) ∨ z) (asociativní zákon)= (y′ ∨ (x ∨ z)) ∧ (> ∨ z) (vlastnost doplňku)= (y′ ∨ (x ∨ z)) ∧ > (axiom pro největší prvek)= y′ ∨ (x ∨ z) (axiom pro největší prvek)= (y′ ∨ x) ∨ z (asociativní zákon)= (x ∨ y′) ∨ z (komutativní zákon)= x ∨ (y′ ∨ z) (asociativní zákon)

2. Předpokládejme, že platí x v y ⇒ z, čili x∧(y′∨z) = x. Chceme dokázat platnost x∧y v z, čili (x∧y)∨z = z.Budeme upravovat výraz (x ∧ y) ∨ z a využívat při tom zákonů Booleovy algebry:

(x ∧ y) ∨ z = ((x ∧ (y′ ∨ z)) ∧ y) ∨ z (platnost x ∧ (y′ ∨ z) = x)= (x ∧ ((y′ ∨ z) ∧ y)) ∨ z (asociativní zákon)= (x ∧ ((y′ ∧ y) ∨ (z ∧ y)) ∨ z (distributivní zákon)= (x ∧ (⊥ ∨ (z ∧ y)) ∨ z (vlastnost doplňku)= (x ∧ (z ∧ y)) ∨ z (vlastnost nejmenšího prvku)= (x ∧ (y ∧ z)) ∨ z (komutativní zákon)= ((x ∧ y) ∧ z) ∨ z (asociativní zákon)= ((x ∧ y) ∨ z) ∧ (z ∨ z) (distributivní zákon)= ((x ∧ y) ∨ z) ∧ z (idempotence)= z (absorpce)

�

6.3 Jednoduché rovnicové specifikace

6.3.1 Příklad Napište rovnicovou specifikaci komutativních pologrup. Jednotlivé části specifikace krátce oko-mentujte.

Řešení. Naše specifikace bude jednosortová (komutativní pologrupa je totiž množina s jednou asociativní akomutativní binární operací).Specifikace tedy může vypadat následovně:

1 spec KOM_POLOGRUPA is2 sorts: elt3 operations: _*_ : elt,elt --> elt4 variables: x,y, z: elt5 equations: (x*y)*z=x*(y*z)6 x*y=y*x7 endspec

Komentář:

1. Řádky 1 a 7 jsou otevírací a zavírací příkazy specifikace.

2. Na řádku 2 specifikujeme jedinou sortu: sorta elt representuje prvky naší komutativní pologrupy.

3. Na řádku 3 specifikujeme _*_ jako binární operaci, psanou infixně.

4. Na řádku 4 deklarujeme proměnné: x, y a z.



5. Na řádku 5 specifikujeme asociativní zákon a na řádku 6 specifikujeme komutativní zákon.

�

6.3.2 Příklad Dejte příklad confusion modelu specifikace

1 spec POLOGRUPA is2 sorts: elt3 operations: _*_ : elt,elt --> elt4 variables: x,y, z: elt5 equations: (x*y)*z=x*(y*z)6 endspec

Komentář. Confusion model je takový model dané specifikace, ve kterém jsou splněny některé rovnice, které nejsouspecifikací vynuceny.

Řešení. Struktura 〈N,+〉 je modelem specifikace POLOGRUPA, protože sčítání přirozených čísel splňuje asociativnízákon. V 〈N,+〉 ovšem platí i rovnice x+ y = y + x pro všechna x, y z množiny N. Komutativní zákon ovšemobecně asociativním zákonem vynucen není. �

6.3.3 Příklad Dejte příklad junk modelu specifikace

1 spec POINTED is2 sorts: elt3 operations: p : --> elt4 endspec

Komentář. Junk model je takový model dané specifikace, ve kterém se vyskytují některé prvky, které nejsou speci-fikací vynuceny.

Řešení. Struktura 〈N, 0〉 je modelem specifikace POINTED, kde nulární operace p je interpretována jako číslo 0.Protože množina N obsahuje i jiné prvky (například číslo 12), jde o junk model. �

6.3.4 Příklad Specifikujte konstrukci if _ then _ else _ fi nějakého imperativního programovacího ja-zyka jako vícesortovou operaci a dejte příklad jedné rovnice, kterou by tato operace měla splňovat. Každoudeklarovanou sortu, operaci a rovnici krátce okomentujte.

Řešení. Hledaná specifikace bude vícesortová: do operace if _ then _ else _ fi totiž jako první operandvstupuje Booleovský výraz a další dva operandy jsou příkazy.Specifikace tedy může vypadat následovně:

1 spec IF is2 sorts: bexp, comm3 operations: if _ then _ else _ fi : bexp,comm,comm --> comm4 variables: e: bexp, c: comm5 equations: if e then c else c fi = c6 endspec

Komentář:

1. Řádky 1 a 6 jsou otevírací a zavírací příkazy specifikace.

2. Na řádku 2 specifikujeme dvě sorty: sorta bexp jsou Booleovské výrazy a sorta comm jsou příkazy.

3. Na řádku 3 specifikujeme if _ then _ else _ fi jako operaci, která má vstupní argumenty po řaděsort bexp, comm, comm a výstupní sortu comm.


6.3. Jednoduché rovnicové specifikace 41

4. Na řádku 4 deklarujeme proměnné: e sorty bexp a c sorty comm.

5. Konečně na řádku 5 specifikujeme rovnici, která říká, že pokud napíšeme stejný (ale libovolný) příkaz doobou větví, pak je to totéž jako napsat pouze tento příkaz, a to nezávisle na testovaném (libovolném)Booleovském výrazu.

Komentář. Je pochopitelně možné napsat celou řadu jiných specifikací, které vyhovují zadání. Jiná možnost jenapříklad

1 spec IF2 is2 sorts: bexp, comm3 operations: if _ then _ else _ fi : bexp,comm,comm --> comm4 true: --> bexp6 not _ : bexp --> bexp7 variables: e: bexp, c1, c2: comm8 equations: if not e then c1 else c2 fi = if e then c2 else c1 fi9 endspec

Specifikace IF2 je ovšem složitější než specifikace IF a obhajoba specifikace IF2 bude jistě složitější než obhajobaspecifikace IF.

�


Date post:	05-Mar-2018
Category:	Documents
Upload:	lebao
View:	220 times
Download:	3 times

Diskrétní matematika --- sbírka · PDF fileÚvod Text, který...

Documents