Pisomka

Diskrétna matematika II.

A

 

Príklady si prečítajte pozorne. Riešenia píšte podrobne, každý príklad na zvláštny papier (kvôli opravovaniu). Prehľadne uveďte všetky argumenty.

 

1. (15b.)

Nech R je relácia z A do B. Dokážte, že R je jednoznačná práve vtedy, keď

 

2. (15b.)

Nech A je 5-prvková množina. Koľko je takých rôznych relácií ekvivalencie na A, ktoré majú

a) presne jednu 3-prvkovú triedu ekvivalencie;

b) jednu 4-prvkovú triedu ekvivalencie;

c) aspoň jednu triedu ekvivalencie s troma alebo viac prvkami?

 

3. (10b.)

Nech A je neprázdna množina. Nech B je pevne zvolená podmnožina A. Definujme na P(A) reláciu R nasledovne: Pre .

a) Overte, že R je ekvivalencia na P(A).

b) Ak A = {1, 2, 3, 4, 5} a B = {1, 2, 3} nájdite triedu ekvivalencie [X], ak X = {1, 3, 5}.

 

4. (15 b.)

Uveďte príklady konečnej čiastočne usporiadanej množiny (A,) a jej podmnožiny B takých, že :

a) B má najväčší prvok

b) B nemá najväčší prvok, ale má supremum

c) B nemá supremum

 

5. (20 b.)

Nech (A, ) je usporiadaná množina a nech .

a) Dokážte, že ak B je reťazec, tak každý minimálny prvok B je zároveň aj najmenší.

b) Ukážte, že vo všeobecnosti minimálny prvok B nemusí byť najmenší.

 

6. (15b.)

Koľko existuje

a) rôznych relácii ekvivalencie na 4-prvkovej množine?

b) neizomorfných usporiadaní na 4-prvkovej množine?

c) rôznych usporiadaní s najväčším prvkom na 4-prvkovej množine?

 

7. (10 b.)

Uveďte príklad relácie, ktorá je

a) reflexívna a symetrická, ale nie je tranzitívna.

b) symetrická a tranzitívna, ale nie je reflexívna.