Diskr´etn´ı matematika

(1)

1 / 82

Diskr´ etn´ı matematika

Petr Kov´aˇr petr.kovar@vsb.cz

Vysoká ˇskola báˇnská – Technická univerzita Ostrava

zimn´ı semestr 2021/2022

DiM 470-2301/01, 470-2301/03*, 470-2301/05

(2)

O tomto souboru

Tento soubor je zam´yˇslen pˇredevˇs´ım jako pom˚ucka pro pˇredn´aˇsej´ıc´ıho.

Radu d˚ˇ uleˇzitých informac´ı v souboru nenajdete, protoˇze pˇrednáˇsej´ıc´ı je ˇr´ıká, ukazuje, pˇr´ıpadnˇe maluje na tabuli. Pˇrednáˇsky jsou na webu k dispozici, aby studenti mohli snadno dohledat prob´ıraná témata z pˇrednáˇsek, které zameˇskali.

Pro samostatn´e studium doporuˇcuji skripta:

M. Kubesa: Základy diskrétn´ı matematiky, výukový text P. Kováˇr: Úvod do teorie graf˚u, výukový text

Pro pˇr´ıpravu ke zkouˇsce a p´ısemk´am doporuˇcuji cviˇcebnici:

P. Kov´aˇr: Cviˇcen´ı z diskr´etn´ı matematiky, sb´ırka pˇr´ıklad˚u Vˇse na http://homel.vsb.cz/~kov16/predmety dm.php

(3)

3 / 82

Pˇrehled pˇredn´aˇsky

Kapitola 0. Opakov´ an´ı

mnoˇziny, podmnoˇziny a operace s nimi princip inkluze a exkluze

relace

d˚ukazov´e techniky

(4)

Mnoˇziny a mnoˇzinov´e operace

Mnoˇzina

je soubor r˚uzných (rozliˇsitelných) objekt˚u. Obvykle znaˇc´ıme velkými p´ısmeny A,B,X,M, . . .

Prvky mnoˇzin znaˇc´ıme malými p´ısmenya,b,x, . . . Prázdná mnoˇzina ∅ nikoli{∅}!

Mnoˇziny zad´av´ame

v´yˇctem prvk˚u (taxativnˇe): M ={a,b,c,d}, plat´ıa∈M,d ∈M, alee 6∈M

charakteristickou vlastnost´ı: N={x:x ∈N,x>5}.

Mohutnost mnoˇziny M

ud´av´a poˇcet prvk˚u v mnoˇzinˇe M, znaˇc´ıme |M|.

Podmnoˇzina

(5)

5 / 82

Mnoˇzinov´e operace

Sjednocen´ımnoˇzin A∪B={x :x∈Anebox ∈B} Pr˚unik mnoˇzin A∩B ={x:x ∈A a souˇcasnˇe x∈B}

Rozd´ıl mnoˇzin A\B ={x :x∈Aa souˇcasnˇe x 6∈B}

Symetrick´y rozd´ıl mnoˇzin A∆B= (A\B)∪(B\A) Pˇr´ıklady

A={a,b,c}, B ={c,d}

A∪B ={a,b,c,d}, A∩B={c}, A\B ={a,b}, A∆B ={a,b,d} Ot´azky

Najdete takov´e dvˇe mnoˇzinyA,B, ˇze A\B=B\A?

Najdete takov´e dvˇe r˚uzn´emnoˇziny A,B, ˇze A\B =B\A?

(6)

Rozˇs´ıˇren´e sjednocen´ı a pr˚unik mnoˇzin Rozˇs´ıˇren´e sjednocen´ı

n

[

i=1

Xi a pr˚unik

n

\

i=1

Xi mnoˇzin.

Mˇejme mnoˇzinuJ, lze pouˇz´ıt i [

j∈J

X_j a \

j∈J

X_j.

Pˇr´ıklady

Ai ={1,2, . . . ,i}

5

[

i=1

A_i ={1,2,3,4,5},

5

\

i=1

A_i ={1},

∞

\

i=1

A_i ={1}

Ot´azky Jak vypad´a \

j∈J

Aj proJ ={2,5}?

(7)

7 / 82

Kartézský souˇcin a kartézská mocnina

Kart´ezsk´y souˇcinmnoˇzin A×B ={(a,b) :a∈A, b ∈B}

je mnoˇzina vˇsech uspoˇrádaných dvojic prvk˚u vybraných po sloˇzkách z mnoˇzin AaB v daném poˇrad´ı.

A1×A2× · · · ×An={(a₁,a2, . . . ,an) :ai ∈Ai, i = 1,2, . . . ,n}

Pro A₁ =A₂=. . .=A_ndostaneme kart´ezskou mocninu Aⁿ. Definujeme A⁰ ={∅},A¹=A.

Pˇr´ıklad

A={a,b}, B={♣,♥,♠}

A×B={(a,♣),(a,♥),(a,♠),(b,♣),(b,♥),(b,♠)}

Typick´y pˇr´ıklad

Kart´ezsk´e souˇradnice (x,y) v R²=R×Ra (x,y,z) v R³=R×R×R.

(8)

A

B A×B a

b

♣ ♥ ♠

(a,♣) (b,♣)

(a,♥) (b,♥)

(a,♠) (b,♠)

Kart´ezsk´y souˇcinu mnoˇzin A×B ={a,b} × {♣,♥,♠}.

r b

g y

g r

b y

(9)

9 / 82

Potenˇcn´ı mnoˇzina

je mnoˇzina obsahuj´ıc´ı vˇsechny podmnoˇziny mnoˇziny A 2^A ={X :X ⊆A}.

Mnoˇzinov´y syst´em nad A

nebo také systém mnoˇzinnad Aje nˇejaká mnoˇzina T ⊆2Â. Dáváme pˇrednost term´ınu

”syst´em mnoˇzin“ pˇred

”mnoˇzina mnoˇzin“.

Pˇr´ıklady

A={a,b} 2^A ={∅,{a},{b},{a,b}}

2^A

= 2^|A|

Doplnˇek mnoˇziny na univerzu

Univerzumobsahuje vˇsechny moˇzn´e prvky.

Pro dané Aobsahuje doplnˇek Aprávˇe ty prvky, které nepatˇr´ı do A.

(10)

Ot´azky

B×A×B =?, A× ∅=?, ∅ × ∅=?, ∅⁰=?, ∅^∅=?

Kter´e mnoˇzinov´e operace jsou komutativn´ı?

asociativn´ı?

Ot´azky

|A×B|=?, |2Â|=^? |A²|, |2Â|<^? |A²|, |2Â|≤ |A^? ²|

Ot´azky

Mnoˇzina S obsahuje vˇsechna sud´a ˇc´ısla.

Jak vypad´a S pro univerzumZ? Jak vypad´aS pro univerzum R?

(11)

11 / 82

C´ıseln´ˇ e obory a celoˇc´ıseln´y interval

Pˇrirozen´a a cel´a ˇc´ısla

pˇrirozen´a ˇc´ısla znaˇc´ıme N={1,2,3,4,5, . . .} neobsahuj´ıˇc´ıslo 0 pˇrirozen´a ˇc´ısla vˇcetnˇe nuly znaˇc´ıme N0 ={0,1,2,3,4,5, . . .}

cel´a ˇc´ısla znaˇc´ıme Z={. . . ,−3,−2,−1,0,1,2,3,4, . . .}

Interval cel´ych ˇc´ısel od a do b je mnoˇzina {a,a+ 1, . . . ,b−1,b}

znaˇc´ıme: [a,b] ={a,a+ 1, . . . ,b−1,b}

srovnejte s intervalem re´aln´ych ˇc´ısel (a,b) Pˇr´ıklady

[3,7] ={3,4,5,6,7} [−2,−2] ={−2}

[5,0] =∅ (pr´azdn´a mnoˇzina)

(12)

Princip inkluze a exkluze Nazýván také

”princip zapojen´ı a vypojen´ı“, nebo

”zahrnut´ı a vylouˇcen´ı“.

Pro mal´an jej ˇcasto intuitivnˇe pouˇz´ıv´ame:

Vˇeta

Poˇcet prvk˚u ve sjednocen´ı dvou mnoˇzin je:

|A∪B|=|A|+|B| − |A∩B|.

A B

Poˇcet prvk˚u ve sjednocen´ı tˇr´ı je:

|A∪B∪C|=|A|+|B|+|C| − |A∩B| − |B∩C| − |A∩C|+|A∩B∩C|.

C

(13)

13 / 82

Obecn´y tvar principu inkluze a exkluze Poˇcet prvk˚u ve sjednocen´ın mnoˇzin je:

n

[

i=1

A_i

= X

J⊆{1,...,n}

J6=∅

(−1)^|J|−1·

\

i∈J

A_i .

Abychom zjistili, kolik prvk˚u m´a sjednocen´ı seˇcteme velikosti jednotliv´ych mnoˇzin, odeˇcteme velikosti pr˚unik˚u vˇsech dvojic, pˇriˇcteme velikosti pr˚unik˚u vˇsech trojic, odeˇcteme velikosti pr˚unik˚u vˇsech ˇctveˇric, . . .

(14)

Velikost sjednocen´ı tˇr´ı mnoˇzin

Napˇr´ıklad pro n= 3 dost´av´ame

3

[

i=1

Ai

= X

J⊆{1,2,3}

J6=∅

(−1)^|J|−1·

\

i∈J

Ai

=

= |A₁|+|A₂|+|A₃| −

− |A₁∩A₂| − |A₁∩A₃| − |A₂∩A₃|+ +|A₁∩A2∩A3|.

A1 A2

A₃

(15)

15 / 82

Velikost sjednocen´ı ˇctyˇr mnoˇzin pro n= 4 dost´av´ame

4

[

i=1

A_i

= X

J⊆{1,2,3,4}

J6=∅

(−1)^|J|−1·

\

i∈J

A_i

=

= |A₁|+|A₂|+|A₃|+|A₄| −

− |A₁∩A2| − |A₁∩A3| − |A₂∩A3| − |A₁∩A4| − |A₂∩A4| − |A₃∩A4|+ + |A₁∩A2∩A3|+|A₁∩A2∩A4|+|A₁∩A3∩A4|+|A₂∩A3∩A4| −

− |A₁∩A2∩A3∩A4|.

A1 A2

A3

A4

(16)

Speci´aln´ı tvar principu inkluze a exkluze

Jednoduˇsˇs´ı tvar (s m´enˇe sˇc´ıtanci), maj´ı-li mnoˇziny a pr˚uniky i mnoˇzin stejn´e velikosti:

n

[

i=1

Ai

=

n

X

k=1

(−1)^k−1· n

k

·

k

\

j=1

Aj

.

Abychom zjistili, kolik prvk˚u m´a sjednocen´ı poˇcet jednoprvkov´ych mnoˇzin mnoˇzin,

odeˇcteme poˇcet dvouprvkových pr˚unik˚u ×velikost pr˚unik˚u dvojic, pˇriˇcteme poˇcet tˇr´ıprvkových pr˚unik˚u ×velikost pr˚unik˚u trojic, odeˇcteme poˇcet ˇctyˇrprvkových pr˚unik˚u ×velikost pr˚unik˚u ˇctveˇric, . . .

(17)

17 / 82

Velikost sjednocen´ı tˇr´ı mnoˇzin maj´ı-li mnoˇziny i pr˚uniky mnoˇzin stejn´e velikosti

Pro n= 3 dost´av´ame

3

[

i=1

A_i

=

3

X

k=1

(−1)^k⁻¹· 3

k

·

k

\

j=1

A_j

=

= 3

1

· |A₁| − 3

2

· |A₁∩A₂|+ 3

3

· |A₁∩A₂∩A₃|.

A1 A2

A3

(18)

Velikost sjednocen´ı ˇctyˇr mnoˇzin maj´ı-li mnoˇziny i pr˚uniky mnoˇzin stejn´e velikosti

Pro n= 4 dost´av´ame

4

[

i=1

A_i

=

n

X

k=1

(−1)^k−1· n

k

·

k

\

j=1

A_j

=

= 4

1

· |A₁| − 4

2

· |A₁∩A₂|+ +

4 3

· |A₁∩A2∩A3| − 4

4

|A₁∩A2∩A3∩A4|.

A1 A2

A3

(19)

19 / 82

Venn˚uv diagram pro sedm mnoˇzin – Adelaide

(20)

Pˇr´ıklad

Ve tˇr´ıdˇe je 25 ˇz´ak˚u. 17 z nich se uˇc´ı anglicky a 10 nˇemecky. 4 se uˇc´ı anglicky a nˇemecky, 4 anglicky a francouzsky, 2 nˇemecky a francouzsky a jeden studuje vˇsechny tˇri jazyky. Kolik student˚u se uˇc´ı jen francouzsky?

Mnoˇziny oznaˇc´ıme A,N aF. Zap´ıˇseme si

|A|= 17, |N|= 10, |A∩N|=|A∩F|= 4, |N∩F|= 2, |A∩N∩F|= 1 Z rovnice

|A∪N∪F|=|A|+|N|+|F| − |A∩N| − |N∩F| − |A∩F|+|A∩N∩F| dostaneme

|F|=|A∪N∪F| − |A| − |N|+|A∩N|+|N∩F|+|A∩F| − |A∩N∩F|

|F|= 25−17−10 + 4 + 4 + 2−1 = 7.

F

(21)

21 / 82

Pˇr´ıklad (pokraˇcov´an´ı)

Ale nˇekteˇr´ı z tˇechto 7 student˚u se uˇc´ı i jin´e jazyky!

A N

F

Jen francouzsky

x =|F| − |A∩F| − |N∩F|+|A∩N∩F| x = 7−4−2 + 1 = 2 ˇz´aci.

Jen francouzsky se uˇc´ı 2 ˇz´aci.

(22)

0.3. Relace a zobrazen´ı

Pˇri studiu diskr´etn´ı matematiky nevystaˇc´ıme s naivn´ım pˇr´ıstupem

k pojm˚um funkce,uspoˇrádán´ınebo být ekvivalentn´ı, je potˇreba tyto pojmy korektnˇe definovat. Vˇsechny vycházej´ı ze spoleˇcného základu – relace.

Význam pojm˚u ekvivalence afunkce pˇrekraˇcuje rámec pˇredmˇetu Diskrétn´ı matematiky.

Pˇrehled

pojem relace

uspoˇrádán´ı a ekvivalence funkce a zobrazen´ı skládán´ı zobrazen´ı princip inkluze a exkluze

(23)

23 / 82

0.3.1. Binárn´ı an-árn´ı relace (na mnoˇzinˇe a mezi mnoˇzinami) Pˇripomeˇnme:Kartézský souˇcinmnoˇzin A×B ={(a,b) :a∈A,b∈B}

je mnoˇzina vˇsech uspoˇrádaných dvojic prvk˚u vybraných po sloˇzkách z mnoˇzin AaB (v daném poˇrad´ı).

Definice

(Heterogenn´ı) binárn´ı relace R mezi mnoˇzinami A,B je libovolné podmnoˇzina kartézského souˇcinu A×B, tj.

R ⊆A×B.

R´ık´ˇ ame, ˇze

”prvek x ∈A je v relaci sy ∈B“ (v tomto poˇrad´ı).

P´ıˇseme (x,y)∈R nebo (x,y)∈/R, ˇcasto jen xRy.

(napˇr. x =y,x <y m´ısto (x,y)∈=, (x,y)∈<) Definice – obecnˇejˇs´ı

(Heterogenn´ı) n-árn´ı relace S mezi mnoˇzinami A₁,A₂, . . . ,A_n je libovolné podmnoˇzina kartézského souˇcinu A₁×A₂× · · · ×A_n, tj.

S ⊆A₁×A₂× · · · ×A_n.

(24)

A

B A×B x

y z

a b c d

(x, a) (y, a) (z, a)

(x, b) (y, b) (z, b)

(x, c) (y, c) (z, c)

(x, d) (y, d) (z, d)

Kart´ezsk´y souˇcinu mnoˇzin A×B ={x,y,z} × {a,b,c,d}.

(25)

25 / 82

Pˇr´ıklad

Záznam v databázi odpov´ıdá jednomu prvku relace. Napˇr´ıklad výsledek zkouˇsky v Edisonu:

(jm´eno, osobn´ı ˇc´ıslo, datum, bodov´e hodnocen´ı) Prvek souˇcinuJmeno×OsCis×Datum×Body

V databázi m˚uˇzeme vyhledat vˇsechny záznamy s pˇredepsanými vlastnostmi:

studenti, kteˇr´ı vykonali zkouˇsku ve zvolený den, studenti, kteˇr´ı pˇriˇsli na zkouˇsku spoleˇcnˇe, bodové výsledky v daném term´ınu, . . .

V´ysledek m˚uˇze urˇcovat vztah (relaci) mezi prvkystejn´emnoˇziny souˇcinu:

vztah (relaci) mezi studenty, relaci mezi body za p´ısemku.

(26)

Definice

(Homogenn´ı) binárn´ı relaceR na mnoˇzinˇeA je libovolné podmnoˇzina kartézského souˇcinuA×A=A², tj.

R⊆A².

Definice

(Homogenn´ı) n-árn´ı relace S na mnoˇzinˇe Aje libovolné podmnoˇzina kartézské mocniny A×A× · · · ×A=Aⁿ, tj.

S ⊆Aⁿ.

Pˇr´ıklad

Relace mezi studenty, kteˇr´ı z´ıskali stejnou zn´amku z DiM.

Relace mezi dvojicemi student˚u, kdo m´a vyˇsˇs´ı sk´ore z p´ısemky.

Relace mezi dokumenty s podobn´ymi pojmy (plagi´aty). . .

(27)

27 / 82

Definice

(Bin´arn´ı) relaceR na mnoˇzinˇeA je

reflexivn´ıpokud (x,x)∈R pro vˇsechna x∈A,

symetrick´apokud (x,y)∈R ⇔(y,x)∈R pro vˇsechna x,y ∈A, antisymetrick´apokud (x,y),(y,x)∈R⇒x =y pro vˇsechna x,y ∈A,

tranzitivn´ıpokud (x,y),(y,z)∈R ⇒(x,z)∈R pro vˇsechna x,y,z ∈A.

lineárn´ı(úplná) pokud (x,y)∈R nebo (y,x)∈R pro kaˇzdéx,y ∈A Pˇr´ıklady

relace rovnosti

”=“ je reflexivn´ı, tranzitivn´ı, symetrick´a i antisymetrick´a

relace menˇs´ı

”<“ je tranzitivn´ı a antisymetrick´a,

”≤“ je i reflexivn´ı relace dˇelitelnosti

”|“ naN(i N0) je reflexivn´ı, tranzitivn´ı a antisymetrick´a

relace

”být pˇr´ıbuzný“ je jistˇe symetrická, tranzitivn´ı a reflexivn´ı relace

”podˇr´ızený/nadˇr´ızený“ je antisymetrická a tranzitivn´ı relace

”dorozumˇen´ı se“ je obvykle symetrick´a, nemus´ı b´yt tranzitivn´ı

(28)

0.3.2. Relace ekvivalence Definice

Ekvivalence na mnoˇzinˇeA jereflexivn´ı, symetrick´a a tranzitivn´ıbin´arn´ı relace na mnoˇzinˇe A. Znaˇc´ıme '.

Definice

Mˇejme relaci ekvivalence'na mnoˇzinˇe A.Tˇr´ıdou ekvivalence prvkux (znaˇc´ıme ['x]) rozum´ıme podmnoˇzinu ['x] ={z ∈A:z 'x}.

['a]

['b]

['c]

['d]

Relace ekvivalence vyjadˇruje vztah

”m´ıt stejnou vlastnost“.

Pˇr´ıklady

relace kongruence(m´ıt stejn´y zbytek po dˇelen´ı ˇc´ıslemn); znaˇc´ı se ≡

(29)

29 / 82

Definice rozkladu mnoˇziny Y

R´ık´ˇ ame, ˇze podmnoˇziny X1,X2, . . . ,Xm mnoˇzinyY tvoˇr´ırozkladY, jestliˇze

X₁,X₂, . . . ,X_m jsou po dvou disjunktn´ı: X_i∩X_j =∅pro ∀i 6=j jejich sjednocen´ı je ´upln´e: X₁∪X₂∪ · · · ∪X_m =Y

Ot´azky

pˇr´ıklad rozkladu, který má koneˇcnˇe mnoho nekoneˇcných tˇr´ıd rozkladu pˇr´ıklad rozkladu, který má nekoneˇcnˇe mnoho tˇr´ıd rozkladu

pˇr´ıklad rozkladu, který má nekoneˇcnˇe mnoho nekoneˇcných tˇr´ıd rozkladu

Mezi relac´ı ekvivalence na mnoˇzinˇe Aa rozkladem mnoˇziny Aje ´uzk´y vztah:

Vˇeta

R˚uzn´e tˇr´ıdy ekvivalence' na mnoˇzinˇe Atvoˇr´ı rozklad A.

Plat´ı i opaˇcn´e tvrzen´ı: rozklad mnoˇziny A urˇcuje relaci ekvivalence na A.

(30)

Vˇeta

R˚uzn´e tˇr´ıdy ekvivalence' na mnoˇzinˇe Atvoˇr´ı rozklad A.

D˚ukaz Vˇsimneme si, ˇze pro kaˇzdou dvojici a'b se tˇr´ıdy ekvivalence rovnaj´ı ['a] = ['b] i kdyˇz maj´ı jin´e oznaˇcen´ı, nebot’ pro kaˇzd´e x∈['a]

jex 'a, z tranzitivityx 'b a tedy x∈['b]. D´ale ovˇeˇr´ıme:

S

x∈A['x] =A

Je zˇrejm´e z reflexivity relace', nebot’x∈['x].

['x]∩['y] =∅ pro kaˇzd´ex 6'y

Uk´aˇzeme nepˇr´ımo, tj. ['x]∩['y]6=∅, potom ['x] = ['y].

Mˇejme u∈['x]∩['y]. Pak podle definice tˇr´ıdy rozkladu jeu'x a u 'y, coˇz z tranzitivity a symetrie dáváx 'y. To ale znamená, ˇze kaˇzdý prvek u ∈['x] je také v ['y] a naopak, tj. ['x] = ['y].

Pˇr´ıklady

rozklad mnoˇziny pˇrirozen´ych ˇc´ısel podle relace kongruence pˇri dˇelen´ın rozklad mnoˇziny student˚u podle relace m´ıt stejnou zn´amku z DIM“

(31)

31 / 82

0.3.3. Relace ˇcásteˇcného uspoˇrádán´ı

Uspoˇr´ad´an´ı a ekvivalence jsou nejbˇeˇznˇejˇs´ı typy relac´ı.

Definice

C´ˇasteˇcné uspoˇrádán´ıjereflexivn´ı, antisymetrická a tranzitivn´ıbinárn´ı relace na mnoˇzinˇe A. Mnoˇzina s relac´ıse nazýváposet.

Slovoˇcásteˇcné zd˚urazˇnuje, ˇze se nemus´ı jednat oúplnou relaci naA, tj. ne kaˇzdá dvojice prvk˚u mus´ı být v relacixRy nebo yRx.

C´ˇasteˇcné uspoˇrádán´ı m˚uˇzeme znázornit pomoc´ıhasseovského diagramu je-lix y, bude prveky zakreslen výˇs neˇz prvek x,

prvkyx ay spoj´ıme ˇcárkou, jestliˇze xy; vynecháme vˇsechny spojnice, které vyplynou z tranzitivity.

1

2 3

4

5 6

7 8

9 10

1 2

3

4 5

6

(32)

Pˇr´ıklady

relace inkluze⊆(být podmnoˇzinou). Dvˇe mnoˇziny mohou snadno být neporovnatelné inkluz´ı, tˇreba{1,2} a{1,3,4}.

relace dˇelitelnosti |naN (pˇredchoz´ı obr´azek)

rozehraný turnaj po prvn´ım kole — nˇekteré týmy spolu jeˇstˇe nehrály, nev´ıme kdo je

”lepˇs´ı“

Definice

Je-li ab, ˇr´ıkáme, ˇzea jemenˇs´ıneˇz prvekb v ˇcásteˇcném uspoˇrádán´ı. Dále prvky a,b jsouneporovnatelné, jestliˇze nen´ı aniab, anib a.

R´ık´ˇ ame, ˇze posloupnosta1,a2, . . . ,an tvoˇr´ıˇretˇezec v ˇcásteˇcném uspoˇrádán´ı, jestliˇze a₁a₂ · · · a_n.

Prvek mnazvememaximáln´ıv ˇcásteˇcném uspoˇrádán´ımnoˇzinyA, jestliˇze neexistuje prvek x∈Avˇetˇs´ı neˇz m, tj. ∀x∈A:mx ⇒x=m.

Prvek mje nejvˇetˇs´ıv ˇcásteˇcném uspoˇrádán´ı mnoˇziny A, pokud je kaˇzdý

(33)

33 / 82

Pˇr´ıklady

1 je nejmenˇs´ı pˇrirozené ˇc´ıslo (bez nuly) v uspoˇrádán´ı podle velikosti mnoˇzina {2,3,4,5,6}uspoˇrádaná dˇelitelnost´ı nemá nejmenˇs´ı prvek, minimáln´ı prvky jsou 2, 3, a 5; prvky 4 ani 6 nejsou minimáln´ı prvky, protoˇze 2|4 a 2|6, (tj.

”2 je menˇs´ı neˇz 4 a 6“)

pˇrirozená ˇc´ısla nemaj´ı nejvˇetˇs´ı ani maximáln´ı prvek v klasickém uspoˇrádán´ı podle velikosti

kladná racionáln´ı ˇc´ısla nemaj´ı nejmenˇs´ı ani minimáln´ı prvek nezáporná racionáln´ı ˇc´ısla maj´ı nejmenˇs´ı prvek 0 (je i minimáln´ı) C´ˇasteˇcné uspoˇrádán´ıse nazýválineárn´ı uspoˇrádán´ı na mnoˇzinˇe A (zkrácenˇe uspoˇrádán´ı naA), pokud nemá neporovnatelné prvky.

Máme-li uspoˇrádán´ı na A, tak m˚uˇzeme prvky Auspoˇrádat do jednoho ˇretˇezce.

Pˇr´ıklady

klasické uspoˇrádán´ı celých, racionáln´ıch ˇci reálných ˇc´ısel podle velikosti

abecedn´ı (lexikografické) uspoˇrádán´ı slov – vˇzdy um´ıme rozhodnout

(34)

Pˇr´ıklad

Závodu se úˇcastnila ˇctyˇri auta: ˇcervené, modré, zelené a fialové.

Cerven´ˇ e auto pˇrijelo do c´ıle dˇr´ıve neˇz fialov´e. Zelen´e auto pˇrijelo dˇr´ıve neˇz ˇ

cervené. Fialové auto pˇrijelo dˇr´ıve neˇz modré. Zelené auto pˇrijelo dˇr´ıve neˇz fialové. Které auto pˇrijelo posledn´ı?

Zavedeme relaci na mnoˇzinˇe aut. Auto x je v relaci s autemy (v tomto poˇrad´ı), pokud auto x pˇrijelo pozdˇeji neˇz autoy.

Jedná se o relaci ˇcásteˇcného uspoˇrádán´ı: je tranzitivn´ı a antisymetrická, ale nen´ı reflexivn´ı. Bez újmy na platnosti ˇreˇsen´ı m˚uˇzeme doplnit relaci o triviáln´ı dvojice

”auto x dorazilo dˇr´ıve nebo souˇcasnˇe jako autoy“.

M˚uˇzeme nakreslit hasseovský diagram, ve kterém jsou auta, které pˇrijela dˇr´ıve, zakreslena výˇse. _Z

C

(35)

35 / 82

0.3.4. Zobrazen´ı (funkce)

Definice

Mˇejme binárn´ı relacif ⊆A×B, pro kterou plat´ı, ˇze ke kaˇzdémux ∈A existuje právˇe jedna uspoˇrádaná dvojice (x,y)∈f, kdey ∈B. Potom relaci f nazýváme zobrazen´ımnoˇziny Ado mnoˇzinyB; zapisujeme f :A→B.

Zobrazen´ı mnoˇzinyA do mnoˇziny B v DiM ˇr´ık´amefunkce.

Druh´y (jedin´y) prvek dvojice zapisujeme jednoduˇse jako y =f(x) m´ısto (x,y)∈f.

Pozn´amka

Obvykle je pojem funkce chápán jako speciáln´ı pˇr´ıpad zobrazen´ı, kdy A,B⊆R(pˇr´ıpadnˇe C). V tomto kurzu budeme pojmyfunkce azobrazen´ı povaˇzovat za synonyma.

Pˇr´ıklady

v analýzef :R→R, pˇr´ıpadnˇe funkce v´ıce promˇennýchf :R×R→R zobrazen´ıf :A→B, které pointer˚umA pˇriˇrazuje pamˇet’ové adresyB

(36)

Nˇekteré vlastnosti zobrazen´ı jsou natolik významné, ˇze maj´ı jména:

Definice

Funkce f :A→B se naz´yv´a

prostá (injektivn´ı) jestliˇze r˚uzné prvky z Ase zobraz´ı na r˚uzné prvky B tj.x 6=y ⇒f(x)6=f(y), totéˇz jakof(x) =f(y)⇒x =y

na (surjektivn´ı) jestliˇze na kaˇzd´y prvek B se zobraz´ı nˇejak´y prvek A tj.∀y ∈B existuje x ∈Atak, ˇze f(x) =y

vz´ajemnˇe jednoznaˇcn´a (bijektivn´ı) je-lif

”prost´a“ i

”na“

A B A B A B

Pˇr´ıklady

je-lif :R→R, takf(x) =x² nen´ı ani prost´a ani na

(37)

37 / 82

V pˇredmˇetu UTI budete rozliˇsovat:

tot´aln´ı funkci

Binárn´ı relaci f ⊆A×B, pro kterou plat´ı, ˇze ke kaˇzdémux∈A existuje právˇe jedna uspoˇrádaná dvojice (x,y)∈f, kdey ∈B. parciáln´ı funkci

Binárn´ı relaci f ⊆A×B, pro kterou plat´ı, k ˇzádnémux ∈A neexistujenejvýˇse jedna uspoˇrádaná dvojice (x,y)∈f, kdey ∈B.

A B A B A B

Zobrazen´ı a funkce zavedené na pˇredchoz´ıch slidech odpov´ıdaj´ı totáln´ı funkci. Parciáln´ı funkce nen´ı

”funkce“ ve smyslu pˇredchoz´ı definice.

Pozor: Bijektivn´ı zobrazen´ı definov´ano pouze pro tot´aln´ı zobrazen´ı, nestaˇc´ı injektivn´ı a surjektivn´ı zobrazen´ı.

(38)

Skl´ad´an´ı zobrazen´ı

Definice skl´ad´an´ı zobrazen´ı

Mˇejme dvˇe zobrazen´ı (funkce) f :A→B a g :B →C. Jejich sloˇzen´ımrozum´ıme zobrazen´ı (g◦f) :A→C (ˇcti

”g pof“) definovan´e vztahem

(g◦f)(x) =g(f(x)).

Ve sloˇzen´em zobrazen´ı (g◦f) :A→C pˇriˇrad´ı nejdˇr´ıve zobrazen´ıf vzoru x ∈A jeho obraz f(x)∈B a pak zobrazen´ıg pˇriˇrad´ı vzoruf(x)∈B jeho obraz g(f(x))∈C.

Pozn´amka

Vˇsimnˇete si: mnoˇzina obraz˚u prvn´ıho zobrazen´ıf mus´ı b´yt podmnoˇzinou mnoˇziny vzor˚u druh´eho zobrazen´ıg.

(39)

39 / 82

Isomorfismus

Casto se setk´ˇ aváme s diskrétn´ımi strukturami, které jsou sice jinak pojmenované, jinak znaˇcené i jinak definované, ale ve své podstatˇe jsou analogické. Prvky jedné lze pˇrevést bijekc´ına prvky druhé, pˇriˇcemˇz

”vlastnosti“ se zachovaj´ı. Tuto vlastnost vyjadˇrujeme slovem b´ytisomorfn´ı. Pˇr´ıklady

potenˇcn´ı mnoˇzina mnoˇziny{a,b} s relac´ı

”b´yt podmnoˇzinou“ je isomorfn´ı mnoˇzinˇe{1,2,3,6} s relac´ı dˇelitelnosti

mnoˇzina {1,2, . . . ,n} m´a stejnˇe mnoho podmnoˇzin jako mnoˇzina {n+ 1,n+ 2, . . . ,2n}; mezi prvky existuje snadn´a bijekceb(i) =i+n;

také ˇcásteˇcná uspoˇrádán´ı tˇechto systém˚u podmnoˇzin inkluz´ı jsou si isomorfn´ı pˇres rozˇs´ıˇrenou bijekcib^∗(X) ={i+n:i ∈X}

relace dˇelitelnosti na mnoˇzinˇe {1,2,3,4,6,9,12,18,36}je isomorfn´ı s dˇelitelnost´ı na mnoˇzinˇe{1,2,4,5,10,20,25,50,100}; bijekcip v prvoˇc´ıseln´em rozkladu nahrad´ı prvoˇc´ıslo 3 prvoˇc´ıslem 5, tj.p(1) = 1, p(3) = 5, p(6) = 10, p(9) = 25, . . .

Mˇejme (A, ρ), (B, σ). (A, ρ)'(B, σ) jestliˇze existuje bijekce f :A→B kde xρy ⇔f(x)σf(y)

(40)

0.3.5. Bijekce koneˇcn´e mnoˇziny, permutace

Permutaci (bez opakov´an´ı) na mnoˇzinˇe Alze ch´apat jako bijektivn´ı zobrazen´ıπ :A→A.

Mˇejme mnoˇzinuA= [1,n].

Permutace na A je urˇcena poˇrad´ım prvk˚u (p₁,p₂, . . . ,p_n). Zobrazen´ıπ definujeme pˇredpisem π(i) =pi.

Pˇr´ıklady

Permutace zapisujeme napˇr´ıklad

π=

1 2 3 4 5 6

3 1 5 4 2 6

, σ=

1 2 3 4 5 6

2 5 4 3 1 6

.

Nyn´ı m˚uˇzeme permutace skl´adat

σ◦π=

1 2 3 4 5 6

4 2 1 3 5 6

, π◦σ =

1 2 3 4 5 6

1 2 4 5 3 6

.

(41)

41 / 82

Pozn´amky

Vˇsechny permutace mnoˇziny [1,n] spolu s operac´ı skládán´ı tvoˇr´ı grupu, které ˇr´ıkáme symetrickánebopermutaˇcn´ı grupa. Znaˇc´ı se Sn. Kaˇzdá grupa je isomorfn´ı nˇekteré grupˇe (podgrupˇe) permutac´ı.

Pozor!Pouˇz´ıvaj´ı se i jiná znaˇcen´ı pro skládán´ı permutac´ı.

Pˇri zápisu permutace vynecháváme (uspoˇrádaný) prvn´ı ˇrádek 1,2, . . . ,n.

Zavedeme si jiný v praxi pouˇz´ıvaný zápis permutac´ı, pomoc´ı jejichcykl˚u.

Definice

Necht’ π je permutace na mnoˇzinˇe A.Cyklem permutace π rozum´ıme takovou posloupnost (a1,a2, . . . ,ak) r˚uzn´ych prvk˚u A, ˇze

π(a_i) =a_i+1 proi = 1,2, . . . ,k−1 a π(a_k) =a₁. Pˇr´ıklady

π =

1 2 3 4 5 6

3 1 5 4 2 6

zap´ıˇseme jakoπ = (1,3,5,2)(4)(6)

σ =

1 2 3 4 5 6

2 5 4 3 1 6

zap´ıˇseme jakoσ = (1,2,5)(3,4)(6)

(42)

Z´apis permutace pomoc´ı cykl˚u

Nen´ı d˚uleˇzité, kterým prvkem zápis permutace zaˇc´ınáme, avˇsak obvykle se snaˇz´ıme zaˇc´ınat

”od nejmenˇs´ıho“ prvku.

Vˇeta

Kaˇzdou permutaci koneˇcn´e mnoˇziny Alze zapsat jako sloˇzen´ı cykl˚u na disjunktn´ıch podmnoˇzin´achA.

D˚ukaz Vezmeme libovolný (napˇr. nejmenˇs´ı) prvek a₁∈Aa iterujeme zobrazen´ıa₂ =π(a₁), a₃=π(a₂) atd., aˇz dostaneme a₁ (postup je koneˇcný, protoˇze Aje koneˇcná). Tak z´ıskáme prvn´ı cyklus (a1, . . . ,a_k).

Pokraˇcujeme v sestavov´an´ı cykl˚u ve zbyl´e mnoˇzinˇe A\ {a₁, . . . ,a_k} (napˇr.

od nejmenˇs´ıho prvku), dokud prvky Anevyˇcerp´ame.

nevýhodou zápisu permutac´ı pomoc´ı cykl˚u je sloˇzitˇejˇs´ı skládán´ı výhodou zápisu permutac´ı pomoc´ı cykl˚u je snadné urˇcen´ıˇrádu (délky) permutace, tj. poˇctu kolikrát sloˇz´ıme permutaci samu se sebou,

(43)

43 / 82

Definice

Necht’ n∈N. Pakn-tou mocninu permutaceπ budeme definovat rekurentnˇe:

π¹ =π pron= 1 aπⁿ=πⁿ⁻¹◦π=π◦πⁿ⁻¹ pron>1.

Definice

Mˇejme nejmenˇs´ı moˇzné k ∈N takové, ˇze π^k =id, kdeπ je nˇejaká permutace. Potom ˇc´ıslok nazývámeˇrád permutaceπ.

Pˇr´ıklad

Permutaceτ =

1 2 3 4 5

3 1 2 5 4

m´a ˇr´ad 6.

Snadno ovˇeˇr´ıme τ◦τ ◦τ ◦τ ◦τ ◦τ =ida menˇs´ı poˇcet sloˇzen´ı ned´a identick´e zobrazen´ı.

Vˇeta

R´ˇad permutace je nejmenˇs´ım spoleˇcným násobkem délek jednotlivých disjunktn´ıch cykl˚u v cyklickém zápisu permutace.

(44)

Pˇr´ıklad

Skládán´ı permutac´ı zadaných pomoc´ı cykl˚u Máme dány permutace

π=

1 2 3 4 5 6

3 1 5 4 2 6

= (1,3,5,2)(4)(6),

σ=

1 2 3 4 5 6

2 5 4 3 1 6

= (1,2,5)(3,4)(6).

V´ıme

σ◦π=

1 2 3 4 5 6

4 2 1 3 5 6

, π◦σ =

1 2 3 4 5 6

1 2 4 5 3 6

. Sloˇz´ıme permutace jako cykly:

σ◦π= (1,2,5)(3,4)(6)◦(1,3,5,2)(4)(6) = (1,4,3)(2)(5)(6).

(45)

45 / 82

Pˇr´ıklad

M´ame automat na m´ıch´an´ın karet.

Pokaˇzd´e provede stejnou permutaci mnoˇziny karet{1,2, . . . ,n}.

pouˇzijeme-lik-krát (k je ˇrád permutace), seˇrazen´ı bude jako pˇred m´ıchán´ım

lze uk´azat, ˇze jedn´ım strojem nem˚uˇzeme pron >2 z´ıskat vˇsechny permutace (vˇsechna rozm´ıch´an´ı)

Pˇr´ıklad

Elegantn´ı zd˚uvodnˇen´ı, ˇze nen´ı moˇzno vyˇreˇsit hlavolam Loydova patn´actka s vyuˇzit´ım permutac´ı.

(46)

Pˇr´ıklad

Nˇemecký ˇsifrovac´ı stroj Enigma byl rozluˇstˇen spojenci. Kl´ıˇcovým krokem byla analýza, kterou v roce 1932 udˇelal Polský matematik Marian Rejewski rozborem grupy permutac´ı. Byl schopen odhalit spoje jednotlivých kotouˇc˚u aniˇz stroj kdy vidˇel.

Pˇr´ıklad

Deˇsifrovac´ı kl´ıˇc pro nápovˇedu ve hˇre geocaching je popsán schématem A|B|C|D|E|F|G|H|I|J|K|L|M

--- N|O|P|Q|R|S|T|U|V|W|X|Y|Z

(47)

47 / 82

Pˇr´ıklad

Generátor náhodných ˇc´ısel v programovac´ıch jazyc´ıch obvykle nen´ı náhodný, ale dává prvky permutace s velkým ˇrádem.

Na prvn´ı pohled nen´ı zˇrejmé, protoˇze obvykle vypisujeme ˇc´ısla zaokrouhlená z pˇredepsané mnoˇziny ˇc´ısel.

Ot´azky

Jak´y je rozd´ıl mezi bijekc´ı a surjekc´ı?

Jak uk´aˇzete, ˇze jsou mnoˇziny stejnˇe velk´e?

Jak uk´aˇzete, ˇze jsou mnoˇziny s operac´ı stejn´e?

Jak porovn´avat velikosti koneˇcn´ych mnoˇzin pomoc´ı zobrazen´ı?

Jak porovn´avat velikosti nekoneˇcn´ych mnoˇzin pomoc´ı zobrazen´ı?

Kolik nejv´ıce r˚uzn´ych rozm´ıch´an´ı um´ı automat pro 10 karet?

Kolik nejv´ıce r˚uzn´ych rozm´ıch´an´ı um´ı automat pro 32 karet?

(48)

0.4. D˚ ukazov´ e techniky v diskr´ etn´ı matematice

Matematika se jako vˇedn´ı discipl´ına vyznaˇcuje svou exaktnost´ı. Rozum´ıme t´ım schopnostdok´azattvrzen´ı nade vˇs´ı pochybnost.

Pojem matematického d˚ukazu se vyv´ıjel nˇekolik stolet´ı. K nejznámˇejˇs´ım historicky doloˇzeným d˚ukaz˚um patˇr´ı:

grafick´e d˚ukazy Pythagorovy vˇety (tvrzen´ı: Babylonsk´a tabulka cca. 1900–1600 pˇr.n.l.,

”Rhind˚uv Papyrus“ z Egypta 1788–1580 pˇr.n.l.,

d˚ukaz: Pythagorejsk´a ˇskola cca. 560–480 pˇr.n.l., v ˇC´ınˇe cca. 500–200 pˇred n.l.)

Euklidovy

”Z´aklady“ cca. 300 pˇr.n.l.

V modern´ı matematice: pojem matematického d˚ukazu je posloupnost elementárn´ıch ovˇeˇritelných krok˚u vedouc´ıch od známých/pˇredpokládaných fakt˚u k novému/poˇzadovanému tvrzen´ı.

V diskr´etn´ı matematice jsou z´akladn´ı pˇredpoklady tvoˇrenyaxiomy

(49)

49 / 82

0.4.1. Základn´ı logické symboly Známé pojmy:

Tvrzen´ıje výrok, o kterém má smysl rozhodnout, zda jepravdivéˇci nepravdivé

Logick´e hodnoty: 1/0, True/False, Pravda/Nepravda Logick´e spojky:

”NOT“¬X,

”AND“ X ∧Y,

”OR“ X∨Y Implikace:

”jestliˇze (je pravda)X, pak (mus´ı b´yt) Y“ X ⇒Y Ekvivalence:

”X (je pravda), právˇe kdyˇzY (je pravda)“ X ⇔Y Negace ¬ jeunárn´ıoperátor,∧,∨,⇒,⇔ jsoubinárn´ı operátory.

Dalˇs´ı oper´atory jsou kombinac´ı:

A XORB je tot´eˇz jako¬(A⇔B).

Ot´azky

Kolik existuje logických binárn´ıch operátor˚u?

Je ”? : “ plnohodnotný ternárn´ı operátor?

(50)

Kvantifik´atory vˇseobecn´y

”Pro kaˇzd´ex ∈M plat´ı tvrzen´ıP(x)“

p´ıˇseme: ∀x∈M :P(x) existenˇcn´ı

”Existuje x∈M, pro kter´e plat´ı tvrzen´ıP(x)“

p´ıˇseme: ∃x∈M :P(x)

Mnoˇzinu M m˚uˇzeme vynechat, pokud je zˇrejm´e o jakouM se jedn´a.

Jak vypadá negace obecného výroku s kvantifikátorem?

Pˇr´ıklad

Vyslovte negaci v´yroku ∀x∈M :P(x)?

∃x ∈M :¬P(x) Pˇr´ıklad

Vyslovte negaci v´yroku ∃x∈M :P(x)?

∀x ∈M :¬P(x)

(51)

51 / 82

0.4.2. Pojem matematick´eho d˚ukazu

Struktura vˇety (tvrzen´ı) v matematice: P ⇒D

Pˇresnˇe formulované pˇredpokladyP, za kterých plat´ıtvrzen´ı vˇetyD. Podrobný postup, jak z pˇredpoklad˚u odvodit tvrzen´ı vˇety nazýváme d˚ukaz.

Matematick´y d˚ukaz

nˇejakého tvrzen´ıD je koneˇcná posloupnost krok˚u/výrok˚u, kde kaˇzdý krok je:

axiom– obecnˇe platný ˇci pˇredpokládaný fakt (volba axiom˚u závis´ı na matematické teorii^∗), pˇredpoklad P je podm´ınka, na kterou se omez´ıme,

výrok odvozenýz pˇredchoz´ıch krok˚u uˇzitém nˇekterého z platných odvozovac´ıch pravidel (závis´ı na pouˇzité logice).

Posledn´ı krok obsahuje jako v´yrok tvrzen´ı D.

∗R˚uzná odvˇetv´ı matematiky vycház´ı z r˚uzných axiom˚u. Zat´ımco diskrétn´ı matematika vycház´ı z Peanových axiom˚u, napˇr´ıklad geometrie (nejstarˇs´ı exaktnˇe budovaná matematická discipl´ına) vycház´ı z pˇetiEuklidových axiom˚u.

(52)

K ˇcemu to budu jako absolvent potˇrebovat?

”K ˇcemu je novorozenˇe?“

správné pochopen´ı omezen´ı pouˇzitých metod argumentace pro a proti navrˇzenému ˇreˇsen´ı srovnán´ı kvality r˚uzných ˇreˇsen´ı

100% korektnost metody/algoritmu je nˇekdy vyˇzadov´ana (autopilot, jednotka intenzivn´ı p´eˇce, ˇr´ızen´ı satelit˚u)

(53)

54 / 82

Pˇr´ıklad

Abstraktn´ı o inverzn´ım prvku

Dokáˇzeme, ˇze v libovolné (i nekomutativn´ı!) algebraické grupˇe plat´ı komutativita operace vzhledem k

”n´asoben´ı inverzn´ım prvkem“. Tj. jestliˇze A·B =E, potom tak´e B·A=E.

Vzpomeˇnte na násoben´ı regulárn´ıch matic: jednotková matice m˚uˇze vyj´ıt pouze pro regulárn´ı matice, nebot’ existuje inverzn´ı matice.

Grupa (G,·) je mnoˇzina prvk˚u s jednou operac´ı, pro kterou plat´ı nˇejak´e vlastnosti, tzv. axiomy grupy. N´as zaj´ımaj´ı tˇri

1 operace je asociativn´ı

2 v grupˇe existuje

”jedniˇcka“ (neutr´aln´ı prvek)

3 ke kaˇzd´emu prvku existuje prvek inverzn´ı Pozn´amka

Pˇri psan´ı d˚ukaz˚u m˚uˇzeme nˇekteré elementárn´ı kroky vynechat, pˇr´ıpadnˇe zkrátit. Nesm´ı vˇsak být poruˇsena korektnost tvrzen´ı (vynechat nˇekterý pˇredpoklad). M´ıra

”zkratky“ závis´ı i na oˇcekávaném

”pr˚umˇern´em ˇcten´aˇri“.

(54)

Grupa (G,·) je mnoˇzina prvk˚u s jednou operac´ı, pro kterou plat´ı tzv.

axiomy grupy. Vyuˇzijeme n´asleduj´ıc´ı tˇri axiomy

1 operace je asociativn´ı:

∀A,B,C ∈G : (A·B)·C =A·(B·C)

2 v grupˇe existuje

”jedniˇcka“:

∃E ∈G :E ·A=A·E =Apro ∀A∈G

3 ke kaˇzd´emu prvku existuje prvek inverzn´ı:

∀A∈G ∃A⁻¹ :A·A⁻¹=E ∧ A⁻¹·A=E.

D˚ukaz tvrzen´ı:

A·B = E pˇredpoklad

A⁻¹·(A·B) = A⁻¹·E z axiomu 3. existuje A⁻¹ (A⁻¹·A)·B = A⁻¹ z axiomu 1. a axiomu 2.

E·B = A⁻¹ z axiomu 3.

B = A⁻¹ z axiomu 2.

· ⁻¹·

(55)

57 / 82

0.4.3.Základn´ı d˚ukazové techniky pˇr´ımý d˚ukaz:A⇒B

nepˇr´ım´y d˚ukaz:¬B ⇒ ¬A

d˚ukaz sporem:A∧ ¬B ⇒spor (sporje souˇcasná platnost T a¬T) d˚ukaz matematickou indukc´ı (slabáa silná)

Pˇr´ıklad

Kaˇzd´e lich´e ˇc´ıslo je moˇzno napsat jako rozd´ıl dvou ˇctverc˚u.

Uk´aˇzeme pˇr´ımo. Mˇejme lich´e ˇc´ıslo 2k+ 1, kde k ∈Z, potom 2k+ 1 =k²+ 2k+ 1−k² = (k+ 1)²−k².

Pˇr´ıklad

Prvoˇc´ısel je nekoneˇcnˇe mnoho.

V´ıme, ˇze kaˇzdé kladné pˇrirozené ˇc´ıslo je moˇzno napsat jako souˇcin prvoˇc´ısel. Sporem:

Pˇredpokl´ad´ame, ˇze prvoˇc´ısel je koneˇcnˇe mnoho, oznaˇc´ıme jep1,p2, . . . ,pn

(jsou vˇsechna). Ale ˇc´ıslox=p₁·p₂· · ·p_n+ 1 nen´ı dˇelitelné ani jedn´ım z prvoˇc´ısel! Máme spor (= má souˇcasnˇe platit nˇejaké tvrzen´ı i jeho negace), proto pˇredpoklad nepravdivý, tj. prvoˇc´ısel je nekoneˇcnˇe mnoho.

(56)

0.4.4. Princip matematick´e indukce

Princip matematické indukceje jedna z nejˇcastˇeji pouˇz´ıvaných d˚ukazových technik pro tvrzen´ı (výrokové formy) závislé na pˇrirozeném parametru n (oznaˇcujemeP(n)).

Matematick´a indukce

Mˇejme tvrzen´ıP(n) s celoˇc´ıseln´ym parametrem n. Necht’ plat´ı:

Z´aklad indukce:

Tvrzen´ıP(n₀) je pravdivé, kde n₀ = 0 nebo 1, nebo obecné celén₀. Indukˇcn´ı krok:

Vyslov´ımeindukˇcn´ı pˇredpoklad: Pro nˇejak´e n tvrzen´ıP(n) plat´ı.

Uk´aˇzeme, ˇze pro kaˇzd´e n>n₀ z platnosti P(n) plyne platnost P(n+ 1).

Pak P(n)plat´ı pro vˇsechna pˇrirozen´a n≥n₀.

Matematickou indukci lze úspˇeˇsnˇe vyuˇz´ıvat pˇri dokazován´ı správnosti

(57)

59 / 82

Poˇckat!

Ale. . .

uk´aˇzeme z´aklad indukce,

uk´aˇzeme platnost indukˇcn´ıho kroku (s vyuˇzit´ım indukˇcn´ıho pˇredpokladu),

. . . nicm´enˇe tvrzen´ı m´a platit pronekoneˇcnˇe mnohohodnot!?!

Pˇr´ıklad

Jak vysoko lze vystoupat na ˇzebˇr´ık?

Pˇredpokl´adejme, ˇze um´ıme vstoupit na prvn´ı pˇr´ıˇcku,

z kaˇzd´e pˇr´ıˇcky n vystoupit na pˇr´ıˇckun+ 1.

. . . tak um´ıme vystoupat libovolnˇe vysoko!

(58)

Vˇeta

Souˇcet prvn´ıch n sud´ych ˇc´ısel jen(n+ 1).

2 + 4 + 6 = 12 = 3·4

2 + 4 + 6 + 8 + 10 + 12 + 14 + 16 + 18 + 20 = 110 = 10·11 D˚ukaz matematickou indukc´ı vzhledem k n:

Dokazujeme, ˇze ∀n∈Nplat´ıPn

i=12i =n(n+ 1).

Z´aklad indukce: Pro n= 1 tvrzen´ı P(1) zn´ı

”2 = 1·2“.

Indukˇcn´ı krok: Plyne z platnostiP(n) platnostP(n+ 1)?

Tj. pokudPn

i=12i =n(n+ 1), takPn+1

i=1 2i = (n+ 1)(n+ 2)?

Vyslov´ımeindukˇcn´ı pˇredpoklad P(n):

Pˇredpokl´adejme, ˇze ∃n∈N:Pn

i=12i =n(n+ 1).

Nyn´ı Pn+1

i=1 2i = Pn

i=12i+ 2(n+ 1)^IP=n(n+ 1) + 2(n+ 1) = (n+ 1)(n+ 2).

Uk´azali jsme ˇze s vyuˇzit´ım znalosti vztahu pro souˇcet prvn´ıch n

(59)

61 / 82

Struktura d˚ukazu matematickou indukc´ı

Lze postupovat podle n´asleduj´ıc´ıho sch´ematu:

1 Rozpoznáme, ˇze se jedná o tvrzen´ı dokazovatelné matematickou indukc´ı:

”∀n∈N,n≥n₀ plat´ı P(n).“

2 UkáˇzemeZáklad indukce: Dokáˇzeme platnost P(n₀).

3 Zformulujeme indukˇcn´ı pˇredpoklad:∃n∈N,n≥n0 aby platilo P(n).

4 Uk´aˇzemeIndukˇcn´ı krok:

S vyuˇzit´ım indukˇcn´ıho pˇredpokladu odvod´ıme platnost P(n+1).

(V´ıme, jak m´a tvrzen´ı nebo vztah P(n+1) vypadat!)

5 Shrneme, ˇze platnost tvrzen´ı P(n) pro vˇsechna n≥n₀ plyne z principu matematick´e indukce.

(60)

Dalˇs´ı vzorov´y d˚ukaz (dˇelitelnost ˇc´ısel):

Vˇeta

Pro kaˇzdé pˇrirozené ˇc´ıslon je výrazn³+ 2n dˇelitelný 3.

Rekneme, ˇˇ ze ˇc´ısloa dˇel´ı ˇc´ıslob, jestliˇze ∃k ∈Z:b=ka. P´ıˇseme a|b.

D˚ukaz matematickou indukc´ı vzhledem k n:

Dokazujeme, ˇze ∀n∈Nplat´ı, ˇze 3 dˇel´ın³+ 2n.

Z´aklad indukce: Pro n= 1 tvrzen´ı P(1) zn´ı

”3 dˇel´ı 1³+ 2·1“.

Tj. pokud 3 dˇel´ın³+ 2n, tak 3 dˇel´ı (n+ 1)³+ 2(n+ 1).

Vyslov´ımeindukˇcn´ı pˇredpoklad P(n):

Pˇredpokl´adejme, ˇze ∃n∈N: 3|n³+ 2n, tj.∃k ∈Z:n³+ 2n= 3k.

Nyn´ı (n+ 1)³+ 2(n+ 1) = (n³+ 3n²+ 3n+ 1) + (2n+ 2) = (n³+ 2n) + (3n²+ 3n+ 3)^IP= 3k+ 3(n³+n+ 1).

(61)

63 / 82

Dalˇs´ı vzorov´y d˚ukaz (nerovnost):

Vˇeta

Pro kaˇzd´e pˇrirozen´e ˇc´ıslon≥4 plat´ın!>2ⁿ.

Velikost faktori´alu n! roste (super)exponenci´alnˇe vzhledem kn.

D˚ukaz matematickou indukc´ı vzhledem k n:

Dokazujeme, ˇze ∀n∈N,n≥4 plat´ın!>2ⁿ. Z´aklad indukce: Pron= 4 tvrzen´ı P(4) zn´ı

”4!>2⁴“, tj. 24>16.

Tj. uk´aˇzeme, ˇze pokudn!>2ⁿ, tak tak´e (n+ 1)!>2ⁿ⁺¹. Vyslov´ımeindukˇcn´ı pˇredpoklad P(n):

Pˇredpokládejme, ˇze ∃n∈N,n≥4, pro které plat´ın!>2ⁿ. Nyn´ı (n+ 1)! = (n+ 1)·n!ÎP>(n+ 1)2ⁿ>2·2ⁿ= 2ⁿ⁺¹.

Uk´azali jsme s vyuˇzit´ım indukˇcn´ıho pˇredpokladu, ˇze (n+ 1)!>2ⁿ⁺¹. Podle principu matematick´e indukce tvrzen´ı plat´ı∀n∈N,n≥4.

(62)

Dalˇs´ı pˇr´ıklady:

Vˇeta

Vˇsech zobrazen´ı libovolné b-prvkové mnoˇziny doa-prvkové mnoˇziny jea^b. D˚ukaz matematickou indukc´ı podleb ∈N0:

Z´aklad indukce:

Pro b= 0 m´ame jedinou moˇznost (jak nic nepˇriˇradit:a^b =a⁰ = 1).

Pro b= 1 máme amoˇzných obraz˚u pro jediný prvek (a^b =a¹=a).

Indukˇcn´ı krok:

IP: pro nˇejaké b je poˇcet r˚uzných zobrazen´ıB →Arovena^b. Mˇejme libovolnou mnoˇzinu B ob+ 1>0 prvc´ıch. Zvolme nˇejaký prvek x ∈B (takový existuje) a oznaˇcmeB⁰ =B\ {x},|B⁰|=b.

Vˇsech zobrazen´ı zB⁰ doA je podle indukˇcn´ıho pˇredpokladua^b. Pro prvek x máme nav´ıc nezávislý výbˇer z amoˇzných obraz˚u. Celkem je dle principu nezávislých výbˇer˚u a·a^b=a^b+1 r˚uzných zobrazen´ı zB doA.

(63)

66 / 82

Silná matematická indukce (ve srovnán´ı s matematickou indukc´ı)

Matematick´a indukce

Mˇejme tvrzen´ıP(n) s celoˇc´ıseln´ym parametrem n. Necht’ plat´ı:

Z´aklad indukce:

Tvrzen´ıP(n₀) je pravdivé, kde n₀ = 0 nebo 1, nebo obecné celén₀. Indukˇcn´ı krok:

Vyslov´ımeindukˇcn´ı pˇredpoklad: Pro nˇejak´e n tvrzen´ıP(n) plat´ı.

Uk´aˇzeme, ˇze pro kaˇzd´e n>n₀ z platnosti P(n) plyne platnost P(n+ 1).

Pak P(n)plat´ı pro vˇsechna pˇrirozená n≥n₀. Silná matematická indukce

Z´aklad indukce: Tvrzen´ıP(n0) je pravdiv´e.

Indukˇcn´ı krok:

Indukˇcn´ı pˇredpoklad: Tvrzen´ıP(k) plat´ı pro vˇsechnan₀≤k <n.

Uk´aˇzeme, ˇze pak plat´ı tak´eP(n).

Pak P(n)plat´ı pro vˇsechna pˇrirozen´a n≥n₀.

(64)

Pˇr´ıklad

Pro nalámán´ı ˇcokolády rozmˇeru p×r d´ılk˚u je vˇzdy potˇrebapr−1 zlom˚u.

D˚ukaz silnou matematickou indukc´ı podle n=pr:

Z´aklad indukce:

Pro n₀ = 1 m´ame jeden d´ılek a je tˇreba pr−1 = 0 zlom˚u.

Indukˇcn´ı krok:

Necht’ nyn´ı tvrzen´ı plat´ı pro vˇsechny ˇcokol´ady o m´enˇe neˇz n d´ılc´ıch.

Mˇejme libovolnou tabulku o n d´ılc´ıch. Tabulku rozlom´ıme a dostaneme dvˇe menˇs´ı tabulky o s,t d´ılc´ıch, kde 1≤s,t<n a s+t=n. Kaˇzdou z nich um´ıme podle pˇredpokladu nal´amat pomoc´ı s−1 resp.t−1 zlom˚u. Celkem je tˇreba

(s −1) + (t−1) + 1 =s+t−1 =n−1 zlom˚u.

Podle principu siln´e matematick´e indukce tvrzen´ı plat´ı∀p,r ∈N.

(65)

68 / 82

Pˇr´ıklad

Máme sloupeˇcekn krabic. Budeme hrát následuj´ıc´ı hru (pro jednoho/libovolný poˇcet hráˇc˚u):

Z jednom kroku vˇzdy rozdˇel´ıme nˇejaký sloupec z krabic (z ≥2) na dva menˇs´ı sloupce s x ay krabicemi. Za tento krok z´ıskáme poˇcet bod˚u, který je dán souˇcinemx·y.

Hra konˇc´ı, jakmile máme n sloupc˚u kaˇzdý s jedinou krabic´ı. Zaˇc´ınáme s nulovým poˇctem bod˚u a chtˇeli bychom dosáhnout co nejvˇetˇs´ıho poˇctu bod˚u. Hráˇc s nejvˇetˇs´ım poˇctem bod˚u vyhrál.

Jakou strategii zvolit, abychom z´ıskali co nejvˇetˇs´ı sk´ore?

Dokaˇzte, ˇze ˇzádná jiná strategie nevede k vyˇsˇs´ımu skóre.

(66)

0.4.5. D˚ukazy vztah˚u s kombinaˇcn´ımi ˇc´ısly

Pro kombinaˇcn´ı ˇc´ısla m˚uˇzeme dok´azat celou ˇradu zaj´ımav´ych vztah˚u.

Zabývá se jimi dokonce celá samostatná ˇcást diskrétn´ı matematiky.

Fakt (na prvn´ı pohled zˇrejm´e tvrzen´ı) Pro vˇsechna n≥0 plat´ı

n 0

= n

n

= 1.

Lemma (pomocn´e tvrzen´ı) Pro vˇsechna n≥k ≥0 plat´ı

n k

= n

n−k

.

Tvrzen´ı, jejichˇz d˚ukaz spoˇc´ıv´a v dosazen´ı do definice (jedna/dvˇe

(67)

70 / 82

Lemma

Pro vˇsechna n≥k ≥0 plat´ı n+ 1

k+ 1

= n

k

+ n

k+ 1

.

Pˇr´ım´y (dosazen´ım a ´upravou) n

k

+ n

k+ 1

= n!

k!·(n−k)!+ n!

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

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

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

= (n+ 1)!

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

n+ 1 k+ 1

.

Vztahy mohou slouˇzit jako alternativn´ı definice kombinaˇcn´ıch ˇc´ısel.

n 0

= n

n

= 1

n k

= n

n−k

n+ 1 k+ 1

= n

k

+ n

k+ 1

.

(68)

Pascal˚uv troj´uheln´ık

0 0

= 1 1

0

= 1 1

1

= 1 2

0

= 1 2

1

= 2 2

2

= 1 3

0

= 1 3

1

= 3 3

2

= 3 3

3

= 1 4

0

= 1 4

1

= 4 4

2

= 6 4

3

= 4 4

4

= 1 5

0

= 1 5

1

= 5 5

2

= 10 5

3

= 10 5

4

= 5 5

5

= 1 . . . .

(69)

72 / 82

Binomick´a vˇeta Pro vˇsechna n>0 plat´ı

(1 +x)ⁿ= n

0

+ n

1

x+ n

2

x²+· · ·+ n

n−1

xⁿ⁻¹+ n

n

xⁿ.

D˚ukazTvrzen´ı je moˇzno dokázat indukc´ı (skripta). Avˇsak moˇzný je i d˚ukaz jednoduchou úvahou (s vyuˇzit´ım lemmatu):

Algebraick´em rozvoji souˇcinu pouˇz´ıv´ame pravidlo

”vynásobit kaˇzdý ˇclen s kaˇzdým“. Proto se v rozvoji vztahu (1 +x)(1 +x). . .(1 +x)

| {z }

n

ˇclenx^k objev´ı tolikrát, kolik je moˇznost´ı (neuspoˇrádanˇe) vybratk z n ˇcinitel˚u – závorek. To je právˇe ⁿ_k

kr´at = poˇcetk prvkov´ych podmnoˇzin z nprvk˚u.

Z binomické vˇety ihned plyne (pro pˇrirozená n≥0 a druhé pro n>0) n

0

+ n

1

+ n

2

+ n

3

+· · ·+ n

n−1

+ n

n

= 2ⁿ, n

0

− n

1

+ n

2

− n

3

+. . .−(−1)ⁿ n

n−1

+ (−1)ⁿ n

n

= 0.

(70)

0.4.6. D˚ukazy vztah˚u pro kombinatorick´e v´ybˇery

Pˇri d˚ukazech vyuˇzijeme matematickou indukci a metodu dvoj´ıho poˇc´ıt´an´ı.

Vˇeta

Poˇcet vˇsech permutac´ın-prvkov´e mnoˇziny je n!, pro kaˇzd´e n≥0.

Indukc´ı podle n:

Základ indukce: Tvrzen´ı plat´ı pron = 0, protoˇze ˇzádné prvky lze uspoˇrádat jen jedn´ım zp˚usobem. (Stejnˇe jednoprvkové mnoˇziny.) Indukˇcn´ı krok: Mˇejme nyn´ın≥0 a mnoˇzinuP o n+ 1 prvc´ıch, pˇredpokládejme pro jednoduchost P ={1,2, . . . ,n+ 1}. Zvolme prvn´ı prvek p ∈P (existuje!) permutace zn+ 1 moˇznost´ı. Nezávisle na volbˇe prvn´ıho prvku pak sestavujeme permutace mnoˇziny P\ {p}.

(Jedn´a se sice o permutacijin´e mnoˇziny, ale vˇzdy m˚uˇzeme prvky P\ {p}

oindexovat/

”pˇreˇc´ıslovat“ na{1,2, . . . ,n}, coˇz neovlivn´ı poˇcet moˇznost´ı.) Potom n-prvkov´a mnoˇzina{1,2, . . . ,n} m´a podle indukˇcn´ıho pˇredpokladu

(71)

74 / 82

Vˇeta

Poˇcet vˇsechk-prvkov´ych variac´ı zn-prvkov´e mnoˇziny je n!

(n−k)!, pro kaˇzd´en ≥k ≥0.

Metodou dvoj´ıho poˇc´ıt´an´ı:

Dvˇema zp˚usoby spoˇc´ıt´ame poˇcet permutac´ın-prvkov´e mnoˇziny:

Uˇz v´ıme, ˇze tyto permutace lze vybratn! r˚uzn´ymi zp˚usoby.

Souˇcasnˇe lze vz´ıt nˇekterouk-prvkovou variaci, jej´ı prvky zapsat na zaˇcátek permutace (dodrˇz´ıme poˇrad´ı) a zbývaj´ıc´ıch n−k prvk˚u seˇrad´ıme za nimi jedn´ım z (n−k)!r˚uzných zp˚usob˚u. Z r˚uzných variac´ı t´ımto postupem z´ıskáme r˚uzné permutace, a pˇritom kaˇzdou permutaci lze z´ıskat z variace vyb´ıraj´ıc´ı jej´ıch prvn´ıch k prvk˚u.

Oznaˇc´ıme x neznámý poˇcet vˇsech k-prvkových variac´ı zn-prvkové mnoˇziny. Výˇse popsaným postupem vytvoˇrit právˇe x·(n−k)! vˇsech r˚uzných permutac´ın-prvkové mnoˇziny. Proto plat´ı

x·(n−k)! = n!

x = n!

(n−k)!.

(72)

Vˇeta

Poˇcet vˇsechk-prvkov´ych kombinac´ı zn-prvkov´e mnoˇziny je n

k

, pro kaˇzd´e n≥k ≥0.

Metodou dvoj´ıho poˇc´ıt´an´ı:

Nyn´ı budeme dvoj´ım zp˚usobem poˇc´ıtat vˇsechnyk-prvkov´e variace z n-prvkov´e mnoˇziny:

Na jednu stranu uˇz v´ıme, ˇze jich je _(n−k)!^n! , na druhou stranu m˚uˇzeme z jedné k-prvkové kombinace z´ıskat celkemk! r˚uzných variac´ı uspoˇrádán´ım prvk˚u této kombinace. Oznaˇc´ımex neznámý poˇcet vˇsechk-prvkových kombinac´ı z n-prvkové mnoˇziny a dostaneme, obdobnˇe jako v pˇredchoz´ım d˚ukazu,

x·k! = n!

(n−k)!

x = n!

k!·(n−k)!

n

(73)

76 / 82

0.4.7. D˚ukazy

”metodou poˇc´ıt´an´ı moˇznost´ı“

Nˇekdy máme ukázat existenci nˇejakého objektu nebo vlastnosti, aniˇz jsme schopni objekt zkonstruovat nebo jinak specifikovat. Takovým d˚ukaz˚um ˇr´ıkámenekonstruktivn´ı, nˇekdy také existenˇcn´ı.

M´ısto abychom ˇreˇsen´ı

”zkonstruovali“, tak se n´am podaˇr´ı

”spoˇc´ıtat“, ˇze ˇreˇsen´ı mus´ı existovat.

Dirichlet˚uv princip (the pigeon-hole principle)

Rozm´ıst´ıme-li `+ 1 (nebo v´ıce) objekt˚u do` pˇrihrádek, v nˇekteré pˇrihrádce mus´ı být alespoˇn dva objekty.

(74)

D˚ukazy poˇc´ıt´an´ım moˇznost´ı

Existenci konkrétn´ı moˇznosti (ze známé mnoˇziny) ukáˇzeme, pokud poˇcet moˇznost´ı, které nemohou nastat je menˇs´ı neˇz celkový poˇcet moˇznost´ı.

Pˇr´ıklad

Vid´ıme, jak do tunelu vjedou tˇri auta a jen dvˇe vid´ıme vyjet ven. To znamen´a, ˇze jedno auto v tunelu z˚ustalo (pˇrestoˇze ho nyn´ı nevid´ıme).

Pˇr´ıklad

8 kamarád˚u jelo na 9 dn´ı dovolené. Kaˇzdý den nˇekterá (jedna) trojice z nich ˇsla na výlet. Dokaˇzte, ˇze nˇekteˇr´ı dva z nich ani jednou nebyli spolu na výletˇe.

D˚ukaz rozeb´ır´an´ı moˇznost´ı by asi k niˇcemu nevedlo. . .

D˚ukaz poˇc´ıtán´ım je vˇsak snadný: Jedna trojice má celkem 3 dvojice, proto po 9 dnech se mohlo vystˇr´ıdat nejvýˇse r˚uzných 9·3 dvojic, ale

9·3 = 27< ⁸₂

= 28, jedna dvojice n´am zde sch´az´ı.

(75)

80 / 82

Pˇr´ıklad

V ˇsupl´ıku je (poházeno) 30 pár˚u ˇcerných ponoˇzek, 10 pár˚u hnˇedých ponoˇzek a 3 páry b´ılých ponoˇzek. Kolik mus´ıme potmˇe vytáhnout ponoˇzek, abychom mˇeli jistotu, ˇze máme alespoˇn jeden pár stejné barvy?

”Pˇrihrádky“ Dirichletova principu budou odpov´ıdat tˇrem r˚uzným barvám.

Vytáhneme-li ˇctyˇri ponoˇzky (nerozliˇsujeme pravou a levou ponoˇzku), mus´ı být alespoˇn dvˇe ponoˇzky stejné barvy.

Ot´azka

Máme 4 pˇrirozená ˇc´ısla. Ukaˇzte, ˇze mezi nimi vˇzdy najdete dvˇe ˇc´ısla tak, aby jejich rozd´ıl dˇelitelný ˇc´ıslem 3.

Ot´azka

Máme 3 pˇrirozená ˇc´ısla. Ukaˇzte, ˇze mezi nimi vˇzdy najdete dvˇe ˇc´ısla tak, aby jejich souˇcet byl dˇelitelný nˇejakým prvoˇc´ıslem.

(76)

Handshaking problem

V m´ıstnosti je n lid´ı, nˇekteˇr´ı si podali ruce. Ukaˇzte, ˇze alespoˇn dva lid´e podali ruku stejn´emu poˇctu lid´ı.

Pˇr´ıklad

Máme 5 pˇrirozených ˇc´ısel. Ukaˇzte, ˇze mezi nimi vˇzdy najdeme dvˇe ˇc´ısla tak, ˇze jejich souˇcet je dˇelitelný 9.

D˚ukaz (chybný!) Celkem máme 9 r˚uzných zbytkových tˇr´ıd po dˇelen´ı ˇc´ıslem 9. Z pˇeti ˇc´ısel m˚uˇzeme z´ıskat 10 r˚uzných souˇct˚u. Jistˇe bude v kaˇzdé zbytkové tˇr´ıdˇe alespoˇn jeden souˇcet, v nˇekteré budou dokonce dva souˇcty.

Proto dvojice ˇc´ısel, jejichˇz souˇcet odpov´ıdá zbytkové tˇr´ıdˇe 0, má souˇcet ˇ

c´ısel dˇeliteln´y dev´ıti.

Ot´azka

Co je ˇspatnˇe v uveden´em d˚ukazu pˇredchoz´ıho tvrzen´ı?

(77)

82 / 82

Pˇr´ıˇstˇe

Kapitola 1. Posloupnosti

posloupnosti sumy a produkty aritmetická posloupnost geometrická posloupnost horn´ı a doln´ı celá ˇcást