Relacja skierowana

[bemekw]

Mam tak zdefiniowaną relację skierowaną \(\displaystyle{ r \subseteq A\times A}\):
\(\displaystyle{ \bigwedge_{x,y,z}[\langle x,y\rangle \in r \wedge \langle x,z \rangle \in r \rightarrow \bigvee_t( \langle y,t \rangle \in r \wedge \langle z,t \rangle \in r)]}\)

mam pokazać, że \(\displaystyle{ r \cup r^{-1}}\) jest skierowana.

Czy relacja odwrotna \(\displaystyle{ r^{-1}}\) to:
\(\displaystyle{ \bigwedge_{x,y,z}[\langle y,z \rangle \in r \wedge \langle z,x \rangle \in r \rightarrow \bigvee_t( \langle t,y \rangle \in r \wedge \langle t,z \rangle \in r)]}\)
Czy jakaś inna? Należy też odwrócić implikację? czyli jeśli istnieje takie \(\displaystyle{ t,y,z}\) takie że.. to wtedy dla kazdego \(\displaystyle{ x}\)...?

\(\displaystyle{ \bigwedge_{a,b,c}[\langle a,b\rangle \in r \cup r^{-1} \wedge \langle a,c \rangle \in r \cup r^{-1} \rightarrow \bigvee_d( \langle b,d \rangle \in r \cup r^{-1} \wedge \langle c,d \rangle \in r\cup r^{-1} )]}\)

[Qń]

Relacja odwrotna zdefiniowana jest:
\(\displaystyle{ (x,y)\in r^{-1} \Leftrightarrow (y,x)\in r}\)

Q.

[bemekw]

Czyli ta pierwsza wersja jest dobra? Zadnych zmian kwantyfikatorów nie trzeba?

bo ogólnie mam - skoro
\(\displaystyle{ \langle x,y \rangle \in r \wedge \langle x,z \rangle \in r \wedge \langle y,t \rangle \in r \wedge \langle z,t \rangle \in r \Leftrightarrow}\)
\(\displaystyle{ \langle y,x \rangle \in r^{-1} \wedge \langle z,x \rangle \in r^{-1} \wedge \langle y,t \rangle \in r^{-1} \wedge \langle t,z \rangle \in r^{-1}}\)

Jak udowodnić, że \(\displaystyle{ r^{-1}}\) jest skierowana? To chyba widać, bo wtedy funkcję naszego \(\displaystyle{ x}\) z definicji pełni \(\displaystyle{ t}\), a \(\displaystyle{ t}\) pełni \(\displaystyle{ x}\) itd.. To wartości chyba dowodowej nie ma żadnej.

[Qń]

Pomijając literówkę, napisałeś tam co znaczyłoby, że relacja \(\displaystyle{ r^{-1}}\) jest skierowana. Ale przecież nie ma to specjalnego związku z tym co mamy wykazać.

Q.

[bemekw]

Myślałem że jeśli udowodniłbym, że relacja \(\displaystyle{ r^{-1}}\) jest skierowana tak jak \(\displaystyle{ r}\), to tym bardziej relacja \(\displaystyle{ r \cup r^{-1}}\). Jednak wychodzi na to, że ten pomysł raczej nie wypali.

[Qń]

Ale przecież o \(\displaystyle{ r}\) nie zakładamy, że jest skierowana. Masz pokazać, że dla dowolnej relacji \(\displaystyle{ r}\) relacja \(\displaystyle{ r \cup r^{-1}}\) jest skierowana.

Możesz spróbować zacząć od wykazania, że dowolna relacja symetryczna jest skierowana.

Q.

[bemekw]

Wiemy, że \(\displaystyle{ r}\) jest skierowana - w pierwszym poście relacja \(\displaystyle{ r}\) jest dana jako skierowana, której definicja brzmi właśnie jak w pierwszym poście. [o to mi chodziło - tu mój błąd, może źle się wyraziłem na początku]
Tak więc mamy de facto udowodnić, że jeśli \(\displaystyle{ r}\) jest skierowana, to relacja \(\displaystyle{ r \cup r^{-1}}\) też jest skierowana.

Tak więc myślę, że wystarczy udowodnić, że \(\displaystyle{ r^{-1}}\) jest skierowana.

[Qń]

Nie chce mi się wierzyć, żeby tezę trzeba było pokazać dla \(\displaystyle{ r}\) skierowanej, skoro ta teza jest prawdziwa \(\displaystyle{ r}\) dowolnej. Zgaduję, że coś źle przepisałeś z tablicy.

W każdym bądź razie nie jest prawdą, że jeśli \(\displaystyle{ r}\) jest skierowana to \(\displaystyle{ r^{-1}}\) też.

Proponuję też żebyś jednak zechciał skorzystać ze wskazówki i wykazał, że relacja symetryczna jest zawsze skierowana.

Q.

[bemekw]

Spróbuję.
Co do zadania - na pewno jest dobrze, brzmi ono:
Jeśli \(\displaystyle{ r}\) jest skierowana, to czy \(\displaystyle{ r \cup r^{-1}}\) jest również skierowana?
Oczywiście jakiś kawałek sensownego dowodu należy pokazać, lub kontrprzykład.

a \(\displaystyle{ r^{-1}}\) nie jest skierowana? Można jakiś kontrprzykład?

Na pierwszy rzut oka:
\(\displaystyle{ r = \left\{ \left\langle 1,2 \right\rangle,\left\langle 1,3 \right\rangle,\left\langle 2,5 \right\rangle,\left\langle 3,5 \right\rangle,\left\langle 2,6 \right\rangle,\left\langle 3,6 \right\rangle \right\}}\) (tutaj akurat istnieją dwa takie \(\displaystyle{ t}\).
\(\displaystyle{ r^{-1} = \left\{ \left\langle 2,1 \right\rangle,\left\langle 3,1 \right\rangle,\left\langle 5,2 \right\rangle,\left\langle 5,3 \right\rangle,\left\langle 6,2 \right\rangle,\left\langle 6,3 \right\rangle \right\}}\) - Czy to nie jest skierowaną relacją? (teraz nasze \(\displaystyle{ t}\) definicyjne jest równe 1. Cała jednak relacja odwrotna wydaje się być skierowana.

[Qń]

Rozważ relację skierowaną \(\displaystyle{ \{ (1,3),(2,3),(3,3)\}}\) i zastanów się czy relacja odwrotna jest skierowana.

Q.

[bemekw]

Ale to aby na pewno jest relacja skierowana?
weźmy to w postaci takiej, że \(\displaystyle{ r = \{(x,t),(y,t)(z,t)\}}\) - jak widać, poprzednik jest fałszywy, a następnik prawdziwy. Wtedy cała implikacja powinna być fałszywa, więc relacja nie skierowana. Czy się mylę?

[Qń]

Nie rozumiem co próbujesz powiedzieć. Jeśli twierdzisz, że ta relacja nie jest skierowana, to wskaż takie \(\displaystyle{ x,y,z}\) dla których implikacja z definicji nie jest prawdziwa, to znaczy takie dla których nie istnieje żądane \(\displaystyle{ t}\).

Q.

[dmjeh]

moze podepne sie pod ten temat bo jest czesciowo powiazany z moim, mysle, ze dla Was dosc prostym dylamatem, bez rozwiazania ktorego zadanie wydaje mi sie podejrzanie za proste.
Zgodnie z tym, iz gdy poprzednik implikacji jest falszywy to cala implikacja jest prawdziwa mamy, ze
relacja \(\displaystyle{ \left\{(1,2),(2,3) \right\}}\) jest skierowana?:>

Czy zlozenie relacji skierowanych r,s jest tez skierowane? Przy pozytywnym rozwiazaniu wczesniejszego dylematu, drugi problem wydaje sie nie prawdziwy.

[Jan Kraszewski]

Relacja \(\displaystyle{ \{(1,2),(2,3)\}}\) jest skierowana.

JK

edit: Nie jest, przepraszam - patrz niżej.

[grazyna19]

Mógłby mi ktoś wytłumaczyć dlaczego relacja \(\displaystyle{ \left\{ \left\langle 1,2 \right\rangle,\left\langle 2,3 \right\rangle \right\}}\) jest skierowana? Przecież nie ma w tej relacji pary uporządkowanej \(\displaystyle{ \left\langle 3,t \right\rangle}\), a wg mnie powinna być. Czy źle interpretuję przedstawioną definicję relacji skierowanej?