Matematické Fórum

↑ r0b1nh0:
Ahoj, nemám moc zkušeností z diskrétní matematiky, takže mé postupy nemusí být zrovna výhodné.
Nicméně zkusím poradit aspoň s reflexivitou.
Předpokládejme, že třída ma řad a sloupců, které očíslujeme obyčejně, podle pořadí, zleva doprava, resp. zepředu dozadu.
Zajímá nás množina . Tedy předpokládáme, že třída je plně obsazená (není řečeno jinak).
Pak relace vypadá takto:
pro je .
Zkus zapsat relaci .
Edit: Ráda přenechám problém kolegovi. Kdybys měl ale dotaz na mě, budu se snažit odpovědět.
Edit2: hezčí znaky

↑ Andrejka3:

Díky moc, ale neměly by se první složit relace S o R a az potom posuzovat ty podminky?

Já se v tom úplně ztrácím, ale možná se postupnými otázkami dopracuji k cíli :-D

co mi zatím došlo:

Z relace S mi vyplývá, že X nesmí sedět v posledních dvou řadách (druhá složka relace S)
a Y nesmí sedět v prvních dvou řadách (první složka relace S)

chápu to správně?

Tu reflexivitu jsem pochopil tak, že prvek nemůže být v relaci sam se sebou, protože je dané, že Y musí být před X. Asi to je špatně napsané, ale zda to chápu dobře, tak třeba relace R je reflexivní.

Ale stejně tomu vůbec nerozumím, mám pocit, že mi uniká něco důležitého, co zatím nechápu abych to mohl řešit. :(

↑ r0b1nh0:
Abys tomu rozumnel z hlediska formalniho, je nutne vedet, co to je slozena relace.
Budte A,B,C mnoziny. R relace mezi A,B. S relace mezi B,C.
Pak slozena relace
, takže je to relace mezi A a C.
Každou relaci si lze představit jako šipky. Složená relace je taky ze šipek. Šipka od a k c existuje, když je k dispozici b takové, že od a k b přejdeš šipkou první relace a od b k c šipkou druhé relace.

Edit: hezčí znaky

↑ Andrejka3:

Na začátek bych chtěl mnohokrát poděkovat za několik pohledá jak to vysvětlit a taky za trpělivost. :-)

Pomocí těch šipek to možná chápu. Když si vezmu tu symetrii tak sipkou relace S se dostanu od prvku studenta1 ke studentovi2 sediciho o dve rady pred nim a sipkou relace R se mohu zase dostat zpet ke studentovi1, protoze sedi ve stejnem sloupci. Ale zase kdyby student1 sedel v prvnich dvou radach tak od neho nevede zadna sipka.

Pokud bych pocital se psravnosti symetrie tak mam splnenou prvni podminku antisymetrie ale nebude platit ze student1 = student2 takze to podle me neni antisymentricke

A co se tyka tranzitivity, tak zkusím takhle: sipkami relace S pojedu od studenta1 ke studentovi2 a pak od studenta2 ke studentovi3 a pak pomoci sipky relace R muzu od studenta1 ke studentovi3. Takze by mela byt tranzitivni.


Snad jsem dobře popsal jak jsem nad tim premyslel, ale se správností to bude horsi :-D

Nejvíce pomůže si to kreslit :)
Skládání relací je jako jízda na dovolenou s přestupem.
Transitivita (jednoduché) relace
Letecká společnost je tranzitivní, když pokud z místa A mohu letět přímo do místa B a z místa B mohu přímým spojem letět do místa C, pak taky existuje přímý spoj z A do C.
Ale nejdřív by bylo fajn dořešit tu symetrii.

↑ r0b1nh0:
Výborně!
"Takze cesta tam je (s1,s2) \in S o R a musime dokazat cestu zpet (s2,s1) \in S o R. Pokud ale pri ceste tam student2 sedel v prvni lavici tak od neho nemuze vest cesta zpet ne? Tedy od studenta v prvnich dvou lavicich nevedou zadne sipky relace S."

Vzad skutečně jít nemůžeme.

Takže pokud má třída aspoň tři řady, není složená relace symetrická. Pak totiž najdem dvojici studentů takovou, že od jednoho vede šipka k druhému ale zpět ne.

Pojďme na antisymetrii.
Relace je antisymetricka, pokud plati: je -li (a,b) v relaci a  též (b,a) v relaci, pak a = b.
Je naše složená relace antisymetrická?

↑ r0b1nh0:
Z toho, že relace není symetrická obecně neplyne, že je / není antisymetrická.
Porovnejme nejprve tyto dvě vlastnosti.
Symetrie. Pokud je (a,b) v relaci, pak (b,a) je v relaci.
Antisymetrie. Pokud je (a,b) v relaci a (b,a) v relaci, pak...
Takže předpoklad implikace u symetrie je o něco kratší. Když chci dokázat, že relace je antisymetrická, vypíšu si všechny dvojičky, takové, že z prvního z té dvojičky jde šipka k druhému a taky z druhého jde šipka k prvému. Jakmile mám tento seznam, podívám se, zda se mi tam vyskytla dvojička (a,b) kde .
Pokud ne, je relace antisymetrická. Pokud tam taková je, není antisymetrická.
Pokud je seznam prázdný, je antisymetrická (proč? ukaž že není pravda, že relace není antisymetrická - tj. existuje prvek prázdné množiny... a je hotovo...)

Ta naše relace je ošklivá, takže nepřekvapí, pokud nebude mít žádnou z těch vlastností, které máme prověřit.
Náš cíl je: buďto
a) Napsat seznam zmíněných dvojiček ;)
b) Najít jednu dvojičku .
Pomohu začátkem. Pokud má učebna nejvýše dvě řady, je naše relace prázdná a tedy antisymetrická.
Tvůj úkol:
Pokud má učebna aspoň tři řady, pak...
Co když má tři řady a jen jeden sloupec?
3 řady a více sloupců?

Vím, je to asi frustrující, ale myslím, že popocházíme.

Edit: oprava: místo antisymetrická bylo asymetrická

↑ r0b1nh0:
Trochu máš problémy s formulací logickou, konkrétně s implikací.
Implikace se skládá ze dvou částí - z předpokladu (výrok A), a závěru (výrok B)

Mějme konkrétní výroky A,B. Výrok
je pravdivý v následujícíh situacích:
A je pravda, B je pravda
A není pravda, B je pravda
A není pravda, B není pravda.
Jediná situace, kdy implikace je nepravdivá je v případě, kdy je pravdivý předpoklad, ale nepravdivý závěr!
U tranzitivity máme přesně toto:
R je tranzitivní
Takhle se vyhneme implikaci a stačí nám jen obecný kvantifikátor. Za ekvivalencí je...
Pro každé a,b,c z M takové, že blabla ... ":" znamená "platí, že".
Podobně antisymetrie:
R je antisymetrická

↑ r0b1nh0:
Ať má učebna tři řady a jeden sloupec.
Jediný student, ze kterého jde šipka relace složené, je ten v té třetí řadě (Pepa). Začneme u něj. Kam můžeme jít?
Vždycky si odpověz předtím, než si to přečteš...
Šipka S nás dovede k studentovi v první lavici. Z něj chceme nastoupit na šipku relace R. Máme tři možnosti. Nastoupíme na šipku R, která vede ke studentovi v třetí řadě. Čímž, jsme absolvovali cestu po šipce složené relace. Dostali jsme se od Pepy, k Pepovi po složené šipce. Můžeme se dostat zpět, tj. od Pepy k Pepovi po složené šipce? samozřejmě, je to ta samá cesta, takže:
(Pepa, Pepa) je v relaci a obráceně taky : (Pepa, Pepa), akorát Pepa = Pepa. Takže jsme zatím nenašli dvojici, která by nesplňovala antisymetrii.
Co kdybychom nastoupili na jinou R šipku? (Tj. Pepa -> student v 1. lavici), ale ted student v prvni lavici sikpou R student v prvni nebo v druhe lavici. Tj, absolvovali jsme jednu cestu slozenou sipkou. Muzeme se dostat zpet?
Nemuzeme :)
Nas seznam vsech dvojicek, ze z prvniho te dvojicky se slozenou dostanem k druhemu a jde to i zpatky je tento:
Seznam: (Pepa, Pepa)
Zaver: Takove relace je antisymetricka.

Ať má učebna tři řady ale aspoň dva sloupce.
Co se změní? Od Pepy vede více S šipek (do jiných sloupců). Můžeme se dostat k sousedovi Pepy po pravé ruce  a též naopak. Soused Pepy Pepa a tedy tato relace je/neni...
Kazdopadne seznam se rozsiril.
Posledni moznost: Ucebna ma aspoň čtyři řady...

↑ r0b1nh0:
Měj se, dobrou.

Zdravím, jako kolega řeším podobné zadání, které však zní takto:

Student A je v relaci R se studentem B , formálně (X, Y ) ∈ R, právě když
A sedí alespoň o dvě řady před B (tj. mezi nimi je další řada) .
• Student A je v relaci S se studentem B , formálně (X, Y ) ∈ S, právě když
A a B sedí ve stejné řadě a mezi nimi je alespoň jeden další student .

Pokud udělám složení relací S o R tak mi vznikne toto:
A a B nesedí ve stejné řadě a A sedí alespoň o dvě řady před B

Pokud to vezmu logicky (čili bez nějakých formálních matematických důkazů), zjistím následující:

REFLEXIVNÍ - Student A nesedí ve stejné řadě jako on sám a A sedí alespoň o dvě řady před sebou samým, čili reflexivní NENÍ

SYMETRICKÁ - pokud A sedí alespoň o dvě řady před B, tak to však neplatí opačně, že B sedí alespoň o dvě řady před A, symetrická tedy také NENÍ

TRANZITIVNÍ - pokud A je o dvě řady před B a zároveň B o dvě řady před C, tak A a C nejsou v relaci.

znázornění:

A
-
-
B
-
-
C

Poprosil bych o zhodnocení mých odpovědí a následné vysvětlení proč je to špatně (nepředpokládám, že bych to měl dobře :-D). Dále nevím jak zjistit a oddůvodnit zda-li je relace ANTISYMETRICKÁ. Byl by někdo tak hodný? Děkuju moc :-)