Matematické Fórum

Majkl9102 · 03. 10. 2010 16:19

zdravím,

mám menší zádrhel u příkladu:

Dokažte, že pro libovolné tři binární relace R,S,T platí: (T o S) o R = T o (S o R).

Pořádně nevím jak se má řešit příklad tohoto typu.

Předem děkuji.

Olin · 03. 10. 2010 16:30

Nazdar, tady jsem dokazoval podobné tvrzení, zde bude postup analogický - budeme chtít pro libovolně zvolené x, y dokázat, že $(x, y) \in (T \circ S) \circ R \, \Leftrightarrow \, (x, y) \in T \circ (S \circ R)$ . Půjde o to, že si čtyřikrát po sobě uvědomíme, jak je definováno skládání relací.

andres1 · 03. 10. 2010 19:09

Řešil jsem stejný příklad. A už asi hodinu nemůžu přijít, jak na něj. Počítání skládání relací s konkrétními čísly rozumím, ale nevím, jak vytvořit důkaz. Respektive nevím, postup, jak ho vytvořit. Můžeš mi prosím pomoct s tímto algoritmem? Prosím o rychlou odpověď. Děkuji.

Oxyd · 03. 10. 2010 19:19

V zásadě de skutečně jenom o rozepsání definic.

$(x, y) \in T \circ S \Leftrightarrow \left( \exists z \right)\left( (x, z) \in T & (z, y) \in S \right)$
$(x, y) \in (T \circ S) \circ R \Leftrightarrow (\exists w)\left( (x, w) \in (T \circ S) & (w, y) \in R \right)$

Teďka akorát rozepsat $(x, w) \in (T \circ S)$ v posledním řádku, a zase od definic se dopracovat zpátky ke kolečkům tentokrát ale tak, abychom z toho měli T o (S o R).

Těžko se tady napovídá, aniž bych vyřešil celý příklad. Stačí to takhle?

mlickko · 03. 10. 2010 20:52

↑ Oxyd:

dobry vecer, riesim tento isty priklad a hoci je to vysvetlene dobre, tak stale nerozumiem ako mam rozpisat to (x, w) \in (T \circ S) , dakujem za trpezlivost.

Oxyd · 03. 10. 2010 21:02

↑ mlickko:

No zase podle definice, kterou jsem napsal na prvním řádku. Vznikne z toho tohle:

$(x, y) \in (T \circ S) \circ R \Leftrightarrow (\exists w)\left( \left[ (\exists z) \left( (x, z) \in T & (z, w) \in S \right) \right] & (w, y) \in R \right)$

Teď se to akorát upraví na ekvivalentní formuli (hejbnu kvantifikátory a přezávorkuju) a pak jdeme zase od téhle formule pomocí definic k skládání relací.

mlickko · 03. 10. 2010 21:25

Takze dalsi krok bude vyzerat takto?
$(x, y) \in (T \circ S) \circ R \Leftrightarrow (\exists w,z)\left( \left( (x, z) \in T & (z, w) \in S & (w, y) \in R \right)$

Oxyd · 03. 10. 2010 21:33

↑ mlickko:

Ano, přesně tak.

mlickko · 03. 10. 2010 22:13

↑ Oxyd:

Dakujem, konecne som sa nejako dopracoval k finalnemu vysledku.

andres1 · 03. 10. 2010 22:29

v druhe casti musim prepsat promenne, aby to odpovidalo predchozi casti? nebo to muze byt takhle?
$(x, y) \in S \circ R \Leftrightarrow \left( \exists z \right)\left( (x, z) \in S & (z, y) \in R \right)$

...

Oxyd · 03. 10. 2010 22:34

↑ andres1:

To, cos napsal, je naprosto správně. Jak si tu "prostřední" proměnnou pojmenuješ, to je jedno. Jenom si dej pozor, abys nepoužil stejné písmenko ve dvou různých významech. Proto jsem tam jednou použil z a podruhé w -- jsou to dvě různé proměnné a nemůžu je označit stejně.

andres1 · 03. 10. 2010 22:39

Jasně :) Díky. Právě mi nebylo jasné, jak si můžu proměnné pojmenovat. Takže vlastně jenom upravím předchozí část a mám to. Jdu na to.

andres1 · 03. 10. 2010 22:56

takhle by to slo, ta druha cast?
$(x, y) \in S \circ R \Leftrightarrow \left( \exists z \right)\left( (x, z) \in S & (z, y) \in R \right)$
$(x, y) \in T\circ (S \circ R) \Leftrightarrow (\exists w)\left( (x, w) \in T & (w, y) \in (S \circ R) \right)$
$(x, y) \in T\circ (S \circ R) \Leftrightarrow (\exists w) \left( (x, w) \in T & [(\exists z) (w,z) \in S & (z,y) \in R)] \right)$
$(x, y) \in T\circ (S \circ R) \Leftrightarrow (\exists w,z) \left( (x, w) \in T & (w, z) \in S & (z, y) \in R \right)$

Oxyd · 03. 10. 2010 23:11

↑ andres1:

Ano, to je správně.

andres1 · 03. 10. 2010 23:19

Díky moc :)

Majkl9102 · 04. 10. 2010 16:22

Taky díky moc
včera jsem to dal dohromady a potěšilo mě že jste to pak tady ještě řešili páč jsem si to pak aspoň zkontroloval :o)

petrkovar

↑ Oxyd:My se učili, že $R \circ S$ je "R po S", tedy pořadí relací je nejprve S a potom R.
To znamená, že je-li $(x,y) \in R \circ S$ , tak
$(\exist w): (x,w) \in S \& (w,y) \in R$ a nikoliv
$(\exist w): (x,w) \in R \& (w,y) \in S$ .

Oxyd · 04. 10. 2010 21:26

↑ petrkovar:

To je dost dobře možné. Myslím ale, že ta definice, kterou jsem použil já, je častější.

Často se definuje -- aspoň v těch zdrojích, které znám -- skládání relací R o S jako "nejdřív R, pak S". Naproti tomu ale skládání funkcí je naopak: f o g je "nejdřív g, potom f" -- pak totiž platí celkem hezká formulka (f o g)(x) = f(g(x)). Dokážu si představit, že jste si definovali skládání v tomhle "obráceném" pořadí, abyste pak měli stejné pořadí u skládání relací jako u skládání funkcí.

Jak říkám, myslím, že R o S ve významu "nejdřív R, pak S" je častější. Samozřejmě je ale vhodné, aby si každý tazatel pečlivě ověřil své vlastní poznámky, jestli je tohle to správné pořadí, které se na jeho škole očekává.

Nich · 05. 10. 2010 21:12

Takže řešením zadaného příkladu by bylo?

$(x, y) \in (T \circ S) \circ R \, \Leftrightarrow \, (x, y) \in T \circ (S \circ R)$
$(x, y) \in S \circ R \Leftrightarrow \left( \exists z \right)\left( (x, z) \in S & (z, y) \in R \right)$
$(x, y) \in T\circ (S \circ R) \Leftrightarrow (\exists w)\left( (x, w) \in T & (w, y) \in (S \circ R) \right)$
$(x, y) \in T\circ (S \circ R) \Leftrightarrow (\exists w) \left( (x, w) \in T & [(\exists z) (w,z) \in S & (z,y) \in R)] \right)$
$(x, y) \in T\circ (S \circ R) \Leftrightarrow (\exists w,z) \left( (x, w) \in T & (w, z) \in S & (z, y) \in R \right)$

Oxyd · 05. 10. 2010 21:40 — Editoval Oxyd (05. 10. 2010 21:42)

To je půlka řešení. Celé by to mohlo vypadat třeba takhle:

$(x, y) \in (T \circ S) \circ R \nl \Leftrightarrow (\exists w) \left( (x, w) \in (T \circ S) & (w, y) \in R \right) \nl \Leftrightarrow (\exists w)\left( \left[ (\exists z)\left( (x, z) \in T & (z, w) \in S \right) \right] & (w, y) \in R \right) \nl \Leftrightarrow (\exists w)(\exists z)\left( (x, z) \in T & (z, w) \in S & (w, y) \in R \right) \nl \Leftrightarrow (\exists z)\left( (x, z) \in T & \left[ (\exists w) \left( (z, w) \in S & (w, y) \in R \right) \right] \right) \nl \Leftrightarrow (\exists z)\left( (x, z) \in T & (z, y) \in (S \circ R) \right) \nl \Leftrightarrow (x, y) \in T \circ (S \circ R)$

A tedy $(x, y) \in (T \circ S) \circ R \Leftrightarrow (x, y) \in T \circ (S \circ R)$ pro všechna (x, y), z čehož plyne, že (T o S) o R = T o (S o R).

Matematické Fórum

#1 03. 10. 2010 16:19

Důkaz vlastností binárních relací

#2 03. 10. 2010 16:30

Re: Důkaz vlastností binárních relací

#3 03. 10. 2010 19:09

Re: Důkaz vlastností binárních relací

#4 03. 10. 2010 19:19

Re: Důkaz vlastností binárních relací

#5 03. 10. 2010 20:52

Re: Důkaz vlastností binárních relací

#6 03. 10. 2010 21:02

Re: Důkaz vlastností binárních relací

#7 03. 10. 2010 21:25

Re: Důkaz vlastností binárních relací

#8 03. 10. 2010 21:33

Re: Důkaz vlastností binárních relací

#9 03. 10. 2010 22:13

Re: Důkaz vlastností binárních relací

#10 03. 10. 2010 22:29

Re: Důkaz vlastností binárních relací

#11 03. 10. 2010 22:34

Re: Důkaz vlastností binárních relací

#12 03. 10. 2010 22:39

Re: Důkaz vlastností binárních relací

#13 03. 10. 2010 22:56

Re: Důkaz vlastností binárních relací

#14 03. 10. 2010 23:11

Re: Důkaz vlastností binárních relací

#15 03. 10. 2010 23:19

Re: Důkaz vlastností binárních relací

#16 04. 10. 2010 16:22

Re: Důkaz vlastností binárních relací

#17 04. 10. 2010 21:19 — Editoval petrkovar (04. 10. 2010 21:26)

Re: Důkaz vlastností binárních relací

#18 04. 10. 2010 21:26

Re: Důkaz vlastností binárních relací

#19 05. 10. 2010 21:12

Re: Důkaz vlastností binárních relací

#20 05. 10. 2010 21:40 — Editoval Oxyd (05. 10. 2010 21:42)

Re: Důkaz vlastností binárních relací

Zápatí