Skusky 3

Diskr´

etna matematika I.

Sk´

uˇska.

12.1.2005

Pr´ıklady si preˇc´ıtajte pozorne. Rieˇsenia p´ıˇste podrobne, uveˇ

dte vˇsetky argumenty.

Kaˇzd´

y pr´ıklad p´ıˇste na samostatn´

y papier (kvˆoli opravovaniu). Nezabudnite kaˇzd´

y

papier podp´ısaˇt.

1. (15b.) Nech mnoˇzina M m´a n prvkov, kde n je prirodzen´e ˇc´ıslo. Dok´aˇzte, ˇze potenˇcn´a

mnoˇzina

P (M) mnoˇziny M m´a pr´ave 2

n prvkov.

2. (15b.) Nech A, B s´

u mnoˇziny.

Dok´aˇzte: A aB s´

u disjunktn´e pr´ave vtedy, keˇ

d (A

× B) ∩ (B × A) = ∅.

3. (15b.) Uk´aˇzte, ˇze

|P(A) ∩ P(B)| > 1 pr´ave vtedy, keˇd A ∩ B 6= ∅.

4. (15b.) Nech R je rel´acia z A do B. Pripomeˇ

nme, ˇze IA oznaˇcuje identick´u rel´aciu na

A. Dok´aˇzte: R je vˇsade definovan´a pr´ave vtedy, keˇ

d IA

⊆ R ◦ R−

1.

vskip 5mm

5. (20b.) Nech n a r s´

u kladn´e cel´e ˇc´ısla, priˇcom n

≥ r.

a) Koˇlko rieˇsen´ı m´a rovnica

x1 + x2 +

· · · + xr = n,

kde kaˇzd´e xi je kladn´e cel´e ˇc´ıslo, 1

≤ i ≤ r?

b) Koˇlk´

ymi spˆosobmi sa d´a kladn´e cel´e ˇc´ıslo n zap´ısaˇt ako s´

uˇcet r kladn´

ych

sˇc´ıtancov (1

≤ r ≤ n), ak na porad´ı sˇc´ıtancov z´aleˇz´ı ?

6. (30b.) Nech abeceda

P

=

{w, x, y, z}.

a) Urˇcite poˇcet reˇtazcov v

P∗

d´lˇzky 5, ktor´e zaˇc´ınaj´

u w.

b) Urˇcite poˇcet reˇtazcov v

P∗

d´lˇzky 5, ktor´e obsahuj´

u presne dve w.

c) Urˇcite poˇcet reˇtazcov v

P∗

d´lˇzky 5, ktor´e neobsahuj´

u w.

7. (10b.) Dok´aˇzte: Pre ˇlubovoˇln´e prirodzen´e ˇc´ısla n a k plat´ı:

n
k

=

n

− 1

k

− 1

+

n

− 1

k

.

P´ısomka pokraˇ

cuje na druhej strane

8. (15b.) Nech A a B s´

u mnoˇziny a nech

|B| = 3. Ak je 4096 rˆoznych rel´acii z A do B,

ˇco je

|A|?

9. (25b.) Nech p(x) a q(x) s´

u v´

yrokov´e funkcie s premennou x s dan´

ym definiˇcn´

ym

oborom.

a) Dok´aˇzte, ˇze

∀x p(x) ∨ ∀x q(x) ⇒ ∀x[p(x) ∨ q(x)].

b) N´ajdite protipr´ıklad pre opaˇcn´

u implik´aciu.

(t.j. Uk´aˇzte, ˇze

∀x p(x) ∨ ∀x q(x) ⇐ ∀x[p(x) ∨ q(x)] neplat´ı.)