Matematické Fórum

Peroplesk · 27. 11. 2018 15:41

Budu moc rád za vysvětlení postupu, jak řešit tento typ úloh. Snažil jsem se to řešit tak, že jsem si nakreslil graf relace, kdy jsem každému místu dal proměnnou a-i. Když jsem pak k tomu měl nakreslit ještě tranzitivní uzávěr, tak jsem se do toho zamotal úplně. Asi je k tomu jiná cesta, která je však pro mě bohužel skrytá. A druhou otázku nechápu už vůbec.

Mezi všemi studenty sedícími v jedné posluchárně definujeme binární relaci R následovně. Student A je v relaci se studentem B, formálně $(A,B)\in R$ , právě když

"oba sedí ve stejné řadě a B není nalevo od A"
nebo
"B sedí jednu řadu před A (tj. není mezi nimi další řada)".

Nechť T je tranzitivní uzávěr relace R. Předpokládejte dále, že posluchárna má alespoň 3 řady a 3 sloupce a všechna místa v ní jsou obsazená studenty.

Určete, které z následujících vlastností popsaná relace T za uvedených předpokladů vždy splňuje:

reflexivní (správná odpověď: ano)
symetrická (správná odpověď: ne)
antisymetrická (správná odpověď: ano)

Vedle toho rozhodněte následující dvě otázky (s tímto společným popisem);
zda v posluchárně za uvedených předpokladů vždy existuje student D takový, že pro všechny studenty C v posluchárně různé od D
platí $(D,C)\in T$ (správná odpověď: ano)
platí $(C,D)\in T$ (správná odpověď: ano)

vlado_bb · 27. 11. 2018 16:54

↑ Peroplesk: Doteraz si zadal dve otazky, v oboch pripadoch sa nasli ludia, ktori ti poradili, v oboch pripadoch si nijako nereagoval, nespolupracoval pri rieseni. Toto nie velmi motivuje ludi pomahat.

Peroplesk · 27. 11. 2018 17:25

↑ vlado_bb:
Nepsaná pravidla tohoto fóra zatím neznám. V obou případech jsem díky feedbacku od lidí, kteří mi poradili, dospěl ke správnému řešení. Proto jsem nepovažoval za nutné téma dále rozvíjet. Pro příště ale budu vědět. Jednomu z odpovídajících jsem teď zpětně dal + (u druhého to nelze) a téma jsem označil jako vyřešené. Děkuji za upozornění.

vlado_bb · 27. 11. 2018 20:05

↑ Peroplesk: Tu nejde o nepisane pravidla fora, ale akejkolvek ludskej komunikacie. No a teraz k ulohe. Predpokladam, ze relacia $R$ je jasna. Problem moze nastat s jej tranzitivnym uzaverom $T$ . Tu je dobre uvedomit si, ze v tomto pripade najst tranzitivny uzaver znamena doplnit k dvojiciam v $R$ vsetky dvojice, ktore su nevyhnutne na to, aby takto vytvorena relacia bola tranzitivna. Ak budeme mat $T$ , zvysok ulohy uz bude jasny.

Peroplesk

↑ vlado_bb:
Řešil jsem si to tak, že jsem si udělal tabulku
levo---pravo
| 1 | 2 | 3 | vpřed
| 4 | 5 | 6 |
| 7 | 8 | 9 | za

Oba sedí ve stejné řadě a B není nalevo od A jsem si vypsal jako:
(1,2), (1,3),
(2,3),
(4,5), (4,6),
(5,6),
(7,8), (7,9),
(8,9)

B sedí jednu řadu před A (není mezi nimi žádná řada) jsem si vypsal jako:
(4,1), (4,2), (4,3),
(5,1), (5,2), (5,3),
(6,1), (6,2), (6,3),
(7,4), (7,5), (7,6),
(8,4), (8,5), (8,6),
(9,4), (9,5), (9,6)

Vzhledem k tomu, že je tam „nebo“, tak jsem to sjednotil a vypadá to následovně:
(1,2), (1,3),
(2,3),
(4,1), (4,2), (4,3), (4,5), (4,6),
(5,1), (5,2), (5,3), (5,6),
(6,1), (6,2), (6,3),
(7,4), (7,5), (7,6), (7,8), (7,9),
(8,4), (8,5), (8,6), (8,9)
(9,4), (9,5), (9,6)

Pro to, aby relace byla tranzitivní, je potřeba přidat následující:
(7,1), (7,2), (7,3)
(8,1), (8,2), (8,3),
(9,1), (9,2), (9,3)

Špatně mám však už hnedka reflexivitu. Chybí tam totiž
(1,1), (2,2), (3,3), (4,4), (5,5), (6,6), (7,7), (8,8), (9,9).
Tedy nemůže být, podle mého řešení, reflexivní.

Už od počátku to tedy nejspíš řeším špatně.

A ty následující dvě otázky tím pádem nezvládám vůbec.

Stýv · 27. 11. 2018 21:50

↑ Peroplesk: ad reflexivita: Sedí x ve stejné řadě jako x? Sedí x vlevo od x?

Doufám, že si jenom nevypisuješ ty čísla, ale že si to nějak smysluplně kreslíš do tý tabulky, abys z toho něco viděl.

Peroplesk

↑ Stýv:
Aha, nenapadlo mě, že to mohou být i stejní studenti.
A jestli to chápu správně, tak asymetričnost je pak splněná proto, že pro $(1,1) \wedge (1,1)$ etc... zároveň platí, že A je stejné jako B.
A symetričnost není splněna proto, že např. pro (4,1) (ale i ostatních dvojice, kromě těch, které tvoří reflexivitu) neexistuje přehozená dvojice (v tomto případě ((1,4)).

Nenapadá mě, jak si to zakreslit nějak přehledně. Jedině 9x9 matici.

Matematické Fórum

#1 27. 11. 2018 15:41

Relace mezi studenty v posluchárně

#2 27. 11. 2018 16:54

Re: Relace mezi studenty v posluchárně

#3 27. 11. 2018 17:25

Re: Relace mezi studenty v posluchárně

#4 27. 11. 2018 20:05

Re: Relace mezi studenty v posluchárně

#5 27. 11. 2018 21:38 — Editoval Peroplesk (27. 11. 2018 21:45)

Re: Relace mezi studenty v posluchárně

#6 27. 11. 2018 21:50

Re: Relace mezi studenty v posluchárně

#7 27. 11. 2018 22:22 — Editoval Peroplesk (27. 11. 2018 22:40)

Re: Relace mezi studenty v posluchárně

Zápatí