Matematické Fórum

jterrry

Zdravim, mel bych par veci z diskretni matematiky se kterymi si nevim rady. Predem diky za jakykoliv poznatek k reseni.

1)Uvažujme binární relaci R = {(a,b), (b,c), (c,a)} na množině X = {a,b,c}. Určete, která z následujících relací je ekvivalencí na X.

správně to být R doplněná o tranzitivní uzávěr, ekvivalenci vím jak udělat, ovšem nejsem si jistý jaké všechny dvojice tam tranzitivní uzávěr přidá

2)Uvažujme zobrazení f(n)= n+1 (mod m) na množině X={0,1,2,...,m-1}. Určete hodnotu f^-3(2) (f^-3 je třikrát složené inverzní zobrazení f^-1, tedy f^-1 ° f^-1 ° f^-1).

OiBobik

↑ jterrry:
ahoj,
nejprve si, prosim, zkus přečíst pravidla fora.

// ok, takže k 1) - jestli správně chápu, jde ti o to, rozhodnout, zda relace $R\cup \tau(R)$ je ekvivalence. K tomu zřejmě stačí si rozmyslet, co to ten tranzitivni uzávěr je. Jedna možnost, jak jej vytvořit (pro konečné relace), je následující algoritmus:
na začátku máme relaci T=R.
Kdykoli najdeme v relaci T dvojici navazujících prvků, tj dvojice tvaru (x,y),(y,z), pak do T přidáme (x,z).
Pokud je T tranzitivni, končíme.

Na základě toho zkus zjistit, jak teda vypadá $R \cup \tau(R)$ a podle toho rozhodni, je-li to ekvivalence, či ne.

jterrry · 19. 12. 2011 21:38

↑ OiBobik:

tak vim ze tam doplnim urcite (a,c), podle toho co jsem tak pochopil by ale mela dvojice (c,a) rozvinout celou relaci o (c,b), (b,a), (c,c), (b,b), (c,c), ale u tohoto nevim jak to, protoze mi prijde ze kdybych to o tyhle prvky nerozsiroval, tak by to uz bylo tranzitivni.

OiBobik · 19. 12. 2011 22:19

↑ jterrry:
píšeš to tak nějak přibližně-nepřesně, že těžko říct, jak to myslíš. Ale tak určitě je pravda, že ten tranzitivni uzávěr nám doplní dvojici (a,c) vzhledem ke dvojicím (a,b) a (b,c), obsaženým v R. Zkus analogicky uvážit dvojice (b,c),(c,a) a (c,a),(a,b).
No a co se zbylých dvojic týče: je potřeba si uvědomit, že aby relace byla tranzitivni, nestačí pouze takto "jednorázově" doplnit nějaké dvojice ke dvojicím, které již jsou v relaci. Přidané dvojice by mi mohly tranzitivítu take "kazit" - je třeba ten postup tedy opakovat. Konkrétně: v R je dvojice (c,a) a již jsme zjistili, že v uzávěru bude (a,c). Z toho již plyne, že v uzávěru nutné musí být i (a,a). Atd.

jterrry · 20. 12. 2011 00:10

↑ OiBobik:

diky za vysvetleni, uz mi to doslo..nevedel bys jeste co s tou dvojkou?

OiBobik · 20. 12. 2011 21:20

↑ jterrry:
příště si v souladu s pravidly na další, naprosto nenavazující příklad založ extra téma.
Tady to stačí snad jen přeformulovat: hledáš takové číslo, na které když třikrát použiješ f, tj. přičteš k němu 1 a "zmodulíš", dostaneš 2. ; ))

Matematické Fórum

#1 18. 12. 2011 19:22 — Editoval jterrry (19. 12. 2011 20:52)

Pár věcí z diskrétní matematiky

#2 19. 12. 2011 10:55 Příspěvek uživatele jterrry byl skryt uživatelem jterrry.

#3 19. 12. 2011 19:53 Příspěvek uživatele jterrry byl skryt uživatelem jterrry.

#4 19. 12. 2011 20:19 — Editoval OiBobik (19. 12. 2011 21:26)

Re: Pár věcí z diskrétní matematiky

#5 19. 12. 2011 21:38

Re: Pár věcí z diskrétní matematiky

#6 19. 12. 2011 22:19

Re: Pár věcí z diskrétní matematiky

#7 20. 12. 2011 00:10

Re: Pár věcí z diskrétní matematiky

#8 20. 12. 2011 21:20

Re: Pár věcí z diskrétní matematiky

Zápatí