Matematické Fórum

myrek · 19. 10. 2010 20:10 — Editoval myrek (19. 10. 2010 20:12)

1) Necht X je n-prvkova mnozina
a) kolik je vsech reflexivnich relaci R nad X?
b) kolik je vsech antisymetrickych relaci R nad X?

2) Necht R a S jsou nejake dve ekvivalence na mnozine X. Rozhodnete zda nasledujici mnoziny jsou nutne opet ekvivalence na X nebo existuje protipriklad (pokud existuje tak ho popiste jinak napiste dukaz ze vysledna mnozina je ekvivalence
a) $R \cap S$
b) $R \cup S$
c) $R \backslash S$
d) $R \circ S$

Fauſt · 19. 10. 2010 20:35

A kde je problém? Sepiš si všechny definice, nakresli si pár příkladů pro menší n a koukej do toho než na to přijdeš. Až budeš alespoň půl hodiny koukat bezvýsledně, tak napiš kde jsi skončil.

Kondr · 19. 10. 2010 20:50

Mimochodem přesně tyto problémy se na fóru řešily, stačí vyzkoušet pár klíčových slov jako "relace", "počet relací", ...

Namátkou http://forum.matweb.cz/viewtopic.php?id=6271

myrek · 24. 10. 2010 21:31 — Editoval myrek (24. 10. 2010 21:31)

relaci celkem je $2^{n^2}$
1) a) pocet reflexivnich je $2^{n^2 -n}$
b) pocet slabe antisymetrickzch relaci je $2^{n}3^{\frac{n^2 -n}{2}$
a pocet antisymetrickych je $3^{\frac{n^2 -n}{2}$

Kondr · 24. 10. 2010 21:35

↑ myrek: Přesně tak.

myrek · 24. 10. 2010 21:47

co se tyce 2) rekl bych ze sjednoceni dvou ekvivalenci je urcite ekvivalence
prunik zrejme taky
rozdil to uz bych rekl ze ne
a to posledni to je skladani?

jinak nevim jak to formalne dokazat

Pavel Brožek · 24. 10. 2010 21:56

↑ myrek:

Ano, to poslední je skládání. Proč bys řekl, že rozdíl není ekvivalence? Pokud pro to máš nějaký důvod, zkus ho využít k tomu, abys sestavil protipříklad.

myrek · 24. 10. 2010 22:06

↑ BrozekP:
aha tak zrejme bude ptz kdyz vezmu nejake prvky dostanu prvky ekvivalence A a ktere nejsou v ekvivalenci B cimz me vznika opet ekvivalence techto prvku
tak a jak na to formalne?

Pavel Brožek · 24. 10. 2010 22:57

↑ myrek:

Aby byla relace ekvivalencí, musí být reflexivní. Zkus ověřit, jestli je relace $R \backslash S$ reflexivní.

Mr.Pinker · 24. 10. 2010 23:27

↑ BrozekP:
promin že tě opravuju ale není reflexivnost jen jednou podmínkou ?

btw: jak dokážu že relace je tranzitivní ?

Pavel Brožek · 24. 10. 2010 23:31

↑ Mr.Pinker:

Je, ale pokud ta není splněna, nemůže být relace ekvivalencí. Bylo to tedy myšleno ve smyslu „musí být nutně reflexivní“. Na protipříklady to stačí. Pokud chceme dokázat, že nějaká relace je ekvivalencí, pak musíme dokazovat reflexivitu, symetrii i tranzitivnost.

K druhé otázce: předpokládáš aRb, bRc a snažíš se dokázat aRc.

myrek · 24. 10. 2010 23:34

a co ten formalni zapis dukazu?

Pavel Brožek · 24. 10. 2010 23:37

↑ myrek:

Nechci řešit víc věcí dohromady. Začal jsem tedy s případem c). Ještě ses k tomu nevyjádřil.

myrek · 25. 10. 2010 00:03

↑ BrozekP:
aha takze bych rekl ze c neni reflexivni protoze by v rozdilu mohlo R prijit o prvky z "uhlopricky"

Pavel Brožek · 25. 10. 2010 00:19

↑ myrek:

Ano. Jen bych netvrdil, že by mohlo, ale že o ně přijde :-). Pro nějaký prvek x jistě platí xRx a xSx. Neplatí pro něj tedy $xR\setminus S x$ . To ale znamená, že $R\setminus S$ není reflexivní a tudíž to není ekvivalence (takhle je to formálně rozvedeno).

Zaměřme se na bod a). Tam čekáš, že to bude ekvivalence. Zkus pro začátek dokázat, že je to reflexivní relace.

myrek · 25. 10. 2010 00:35

no tak u acka bude vzdycky uhlopricka takze bude reflexivni

Pavel Brožek

↑ myrek:

No, zkus to trochu formálněji :-). Představ si, že já tomu nerozumím, proč by tam ta úhlopříčka měla být. A ty mi to vysvětli tak, abych tomu porozumněl.

myrek · 25. 10. 2010 12:27

↑ BrozekP:
R a S jsou ekvivalence, tedy jsou reflexivni, v jejich pruniku budou zcela urcite reflexivni prvky (uhlopricka) kdyz tam budou i jine prvky tak ty musi byt nutne symetricke

myrek · 26. 10. 2010 00:21

toz co?
je to spravne?

a co se tyce skladani? me se zda ze skladani nemusi byt tranzitivni
a jak formalne a) a b) a d)?

Kondr · 26. 10. 2010 02:06

↑ myrek: Sjednocení poruší tranzitivitu, skládání symetrii (stačí najít protipříklady na malých množinách). Stejně tak stačí najít protipříklad pro rozdíl -- napž. říct, že za R, S zvolíme rovnost, jejich rozdíl je prázdná relace a ta není reflexivní.

Jediné, co je třeba dokazovat, je ten průnik. Z definice průniku to lze ale snadno.

myrek · 26. 10. 2010 09:02

a jak popsat protipriklady?

co se tyce pruniku myslite neco ve smyslu
$x \in R \cap S \equiv x \in R & x \in S$

myrek · 31. 10. 2010 00:32

jo tak tomu dukazu pruniku uz chapu stejne tak chapu protiprikladu skladani kde jsem si nakreslil sipky a tecky
protipriklad rozdilu jsem uz mel

ale porad jeste nevim proc by sjednoceni nemelo byt ekvivalenci

Matematické Fórum

#1 19. 10. 2010 20:10 — Editoval myrek (19. 10. 2010 20:12)

diskretni matematika ukoly

#2 19. 10. 2010 20:35

Re: diskretni matematika ukoly

#3 19. 10. 2010 20:50

Re: diskretni matematika ukoly

#4 24. 10. 2010 21:31 — Editoval myrek (24. 10. 2010 21:31)

Re: diskretni matematika ukoly

#5 24. 10. 2010 21:35

Re: diskretni matematika ukoly

#6 24. 10. 2010 21:47

Re: diskretni matematika ukoly

#7 24. 10. 2010 21:56

Re: diskretni matematika ukoly

#8 24. 10. 2010 22:06

Re: diskretni matematika ukoly

#9 24. 10. 2010 22:57

Re: diskretni matematika ukoly

#10 24. 10. 2010 23:27

Re: diskretni matematika ukoly

#11 24. 10. 2010 23:31

Re: diskretni matematika ukoly

#12 24. 10. 2010 23:34

Re: diskretni matematika ukoly

#13 24. 10. 2010 23:37

Re: diskretni matematika ukoly

#14 25. 10. 2010 00:03

Re: diskretni matematika ukoly

#15 25. 10. 2010 00:19

Re: diskretni matematika ukoly

#16 25. 10. 2010 00:35

Re: diskretni matematika ukoly

#17 25. 10. 2010 00:41 — Editoval BrozekP (25. 10. 2010 00:44)

Re: diskretni matematika ukoly

#18 25. 10. 2010 12:27

Re: diskretni matematika ukoly

#19 26. 10. 2010 00:21

Re: diskretni matematika ukoly

#20 26. 10. 2010 02:06

Re: diskretni matematika ukoly

#21 26. 10. 2010 09:02

Re: diskretni matematika ukoly

#22 31. 10. 2010 00:32

Re: diskretni matematika ukoly

Zápatí