Konfluenz < Mengenlehre < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Eine Relation R auf einer Menge M heißt genau dann konfluent, wenn
[mm] \forall [/mm] x [mm] \in [/mm] M [mm] \forall [/mm] y1,y2 [mm] \in [/mm] M:(xRy1 [mm] \wedge [/mm] xRy2 [mm] \Rightarrow \exists [/mm] z [mm] \in [/mm] M: y1Rz [mm] \wedge [/mm] y2Rz).
Gegeben seien die folgenden Relationen auf [mm] \IN0: [/mm] R1 = [mm] \{\}, R2=\{(0,0)\}, R3=\{(0,1),(0,2),(0,3),(1,3),(2,3),(3,3)}, [/mm] R4 = [mm] \{(x,y) \in \IN0 \times \IN0 | x = y\}, R5=\{(x,y) \in \IN0 \times \IN0 | x < y\} [/mm] und [mm] R6=\{(x,y) \in \IN0 \times \IN0 | x teilt y\}
[/mm]
Begründen Sie für jede dieser Relationen, ob sie konfluent ist oder nicht. |
Meine Lösung sieht wie folgt aus:
R1 ist konfluent, da für alle x,y1,y2 die Aussage gilt, da keine Elemente vorhanden sind.
R2 ist konfluent, da der erste Teil der Aussage nicht erfüllt wird. (Es gibt kein xRy1 [mm] \wedge [/mm] xRy2)
R3 ist konfluent, da für die Tupel, die ein gleiches x besitzen das y jeweils als x auftaucht, dem der gleiche Wert zugeordnet ist (3).
R4 ist konfluent, da der erste Teil der Aussage nie erfüllt wird, da die Relation bijektiv ist.
R5 ist konfluent, da, wenn ein x immer mindestens zwei verschiedene y hat, ein z existiert was gößter als diese y ist. [mm] (\IN0 [/mm] ist nicht nach oben begrenzt)
R6 ist konfluent, da, wenn x immer mindestens zwei verschiedene y hat, ein z mit z = y1*y2 existiert.
Stimmt das so alles oder hab ich bei der Definition von Konfluenz etwas falsch verstanden?
|
|
| |
|
> Eine Relation R auf einer Menge M heißt genau dann
> konfluent, wenn
> [mm]\forall[/mm] x [mm]\in[/mm] M [mm]\forall[/mm] y1,y2 [mm]\in[/mm] M:(xRy1 [mm]\wedge[/mm] xRy2
> [mm]\Rightarrow \exists[/mm] z [mm]\in[/mm] M: y1Rz [mm]\wedge[/mm] y2Rz).
>
> Gegeben seien die folgenden Relationen auf [mm]\IN0:[/mm] R1 = [mm]\{\}, R2=\{(0,0)\}, R3=\{(0,1),(0,2),(0,3),(1,3),(2,3),(3,3)},[/mm]
> R4 = [mm]\{(x,y) \in \IN0 \times \IN0 | x = y\}, R5=\{(x,y) \in \IN0 \times \IN0 | x < y\}[/mm]
> und [mm]R6=\{(x,y) \in \IN0 \times \IN0 | x\ teilt\ y\}[/mm]
>
> Begründen Sie für jede dieser Relationen, ob sie
> konfluent ist oder nicht.
>
> Meine Lösung sieht wie folgt aus:
>
> R1 ist konfluent, da für alle x,y1,y2 die Aussage gilt, da
> keine Elemente vorhanden sind. ![[ok]](/images/smileys/ok.gif "[ok]")
>
> R2 ist konfluent, da der erste Teil der Aussage nicht
> erfüllt wird. (Es gibt kein xRy1 [mm]\wedge[/mm] xRy2) ![[haee]](/images/smileys/haee.gif "[haee]")
Doch: x=0 , y1=0 , y2=0
(es war ja nicht verlangt, dass y1 [mm] \ne [/mm] y2 !)
> R3 ist konfluent, da für die Tupel, die ein gleiches x
> besitzen das y jeweils als x auftaucht, dem der gleiche
> Wert zugeordnet ist (3).
Ich denke, R3 ist nicht konfluent. Nähme man noch die
Paare (1,1) und (2,2) hinzu, wäre die Eigenschaft erfüllt.
> R4 ist konfluent,
> da der erste Teil der Aussage nie
> erfüllt wird, da die Relation bijektiv ist.
(gleicher Einwand wie schon bei R2)
> R5 ist konfluent,
> da, wenn ein x immer mindestens zwei
> verschiedene y hat, ein z existiert was gößter als diese
> y ist. [mm](\IN0[/mm] ist nicht nach oben begrenzt)
zur Begründung würde man vielleicht am besten auf
die Ordnungsstruktur von [mm] \IN [/mm] (Totalordnung ohne obere
Schranke) hinweisen.
> R6 ist konfluent,
> da, wenn x immer mindestens zwei
> verschiedene y hat, ein z mit z = y1*y2 existiert.
(... und dieses z ist dann natürlich sowohl durch y1 als
auch durch y2 teilbar ...)
> Stimmt das so alles oder hab ich bei der Definition von
> Konfluenz etwas falsch verstanden?
Im großen Ganzen stimmts. Ausnahmen habe ich
erwähnt (hoffentlich richtig).
LG , Al-Chw.
|
|
|
| |
|
OK bei R2 habe ich falsch argumentiert. Dennoch sollte R2 ja konfluent sein. Denn für x=0 y1=0 y2= 0 kann ich ja ein z mit z = 0 bestimmen, für das die Bedinung erfüllt ist.
Zu R3: Warum ist R3 denn nicht Konfluent? Ich sehe keinen Grund, warum es nicht Konfluent sein sollte.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 02:05 Do 30.10.2014 | | Autor: | Fulla |
Hallo infinity95!
> Zu R3: Warum ist R3 denn nicht Konfluent? Ich sehe keinen
> Grund, warum es nicht Konfluent sein sollte.
Sei zunächst [mm]y_1\not = y_2[/mm], dann kommt nur [mm]x=0[/mm] in Frage, da nur 0 mit zwei verschiedenen Elementen aus R3 in Relation steht. Dann erfüllt [mm]z=3[/mm] die Bedingung.
Für [mm]y_1=y_2[/mm] ist ebenfalls [mm]z=3[/mm] die entsprechende Wahl.
Ich denke also ebenfalls, dass R3 konfluent ist.
Lieben Gruß,
Fulla
|
|
|
| |
|
> Hallo infinity95!
>
> > Zu R3: Warum ist R3 denn nicht Konfluent? Ich sehe keinen
> > Grund, warum es nicht Konfluent sein sollte.
>
> Sei zunächst [mm]y_1\not = y_2[/mm], dann kommt nur [mm]x=0[/mm] in Frage,
> da nur 0 mit zwei verschiedenen Elementen aus R3 in
> Relation steht. Dann erfüllt [mm]z=3[/mm] die Bedingung.
> Für [mm]y_1=y_2[/mm] ist ebenfalls [mm]z=3[/mm] die entsprechende Wahl.
>
> Ich denke also ebenfalls, dass R3 konfluent ist.
>
> Lieben Gruß,
> Fulla
Guten Tag Fulla und [mm] $\infty_{95}$
[/mm]
Die Definition lautete aber:
Eine Relation R auf einer Menge M heißt genau dann konfluent, wenn
$ [mm] \forall [/mm] \ x\ [mm] \in [/mm] \ M\ \ [mm] \red{\forall \ y1\,,\,y2 \ \in M}:\ [/mm] (xRy1 \ [mm] \wedge\ [/mm] xRy2 \ [mm] \Rightarrow \exists [/mm] \ z \ [mm] \in [/mm] \ M: y1Rz \ [mm] \wedge [/mm] \ y2Rz)$
Da hier nicht verlangt wird, dass y1 [mm] \ne [/mm] y2 , sollte der Fall
y1 = y2 auch zugelassen sein, was dann halt bedeutet,
dass jedes Element y, zu dem im Relationsgraph ein Pfeil
hinführt, auch einen Pfeil haben müsste, der von y wegführt
oder ev. einen "Loop-Pfeil" (y,y) .
Falls trotzdem die Voraussetzung y1 [mm] \ne [/mm] y2 "gemeint"
sein sollte, dann müsste sie unbedingt in der Definition
stehen. Die Aussage $\ [mm] (\,y1\in [/mm] M\ [mm] \wedge\ y2\in M\,)\ \Rightarrow\ y1\ne [/mm] y2$ ist eben falsch.
LG , Al-Chw.
|
|
|
| |
|
> > Hallo infinity95!
> >
> > > Zu R3: Warum ist R3 denn nicht Konfluent? Ich sehe keinen
> > > Grund, warum es nicht Konfluent sein sollte.
> >
> > Sei zunächst [mm]y_1\not = y_2[/mm], dann kommt nur [mm]x=0[/mm] in Frage,
> > da nur 0 mit zwei verschiedenen Elementen aus R3 in
> > Relation steht. Dann erfüllt [mm]z=3[/mm] die Bedingung.
> > Für [mm]y_1=y_2[/mm] ist ebenfalls [mm]z=3[/mm] die entsprechende Wahl.
> >
> > Ich denke also ebenfalls, dass R3 konfluent ist.
> >
> > Lieben Gruß,
> > Fulla
>
>
> Guten Tag Fulla und [mm]\infty_{95}[/mm]
>
> Die Definition lautete aber:
>
> Eine Relation R auf einer Menge M heißt genau dann
> konfluent, wenn
> [mm]\forall \ x\ \in \ M\ \ \red{\forall \ y1\,,\,y2 \ \in M}:\ (xRy1 \ \wedge\ xRy2 \ \Rightarrow \exists \ z \ \in \ M: y1Rz \ \wedge \ y2Rz)[/mm]
>
> Da hier nicht verlangt wird, dass y1 [mm]\ne[/mm] y2 , sollte der
> Fall
> y1 = y2 auch zugelassen sein, was dann halt bedeutet,
> dass jedes Element y, zu dem im Relationsgraph ein Pfeil
> hinführt, auch einen Pfeil haben müsste, der von y
> wegführt
> oder ev. einen "Loop-Pfeil" (y,y) .
Aber genau diese Bedingung ist doch bei R3 immer erfüllt, oder nicht?
> Falls trotzdem die Voraussetzung y1 [mm]\ne[/mm] y2 "gemeint"
> sein sollte, dann müsste sie unbedingt in der Definition
> stehen. Die Aussage [mm]\ (\,y1\in M\ \wedge\ y2\in M\,)\ \Rightarrow\ y1\ne y2[/mm]
> ist eben falsch.
Fulla hat aber auch nicht behauptet, dass [mm] y1\ne [/mm] y2 ist. Er hat, wenn ich das richtig verstanden habe, zwei fälle betrachtet: Erstens y1 [mm] \ne [/mm] y2 und dann y1=y2. Und für beide Fälle erfüllt R3 Die Bedingung zur Konfluenz.
> LG , Al-Chw.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:43 Do 30.10.2014 | | Autor: | tobit09 |
Hallo Infinity95!
> > Da hier nicht verlangt wird, dass y1 [mm]\ne[/mm] y2 , sollte der
> > Fall
> > y1 = y2 auch zugelassen sein, was dann halt bedeutet,
> > dass jedes Element y, zu dem im Relationsgraph ein
> Pfeil
> > hinführt, auch einen Pfeil haben müsste, der von y
> > wegführt
> > oder ev. einen "Loop-Pfeil" (y,y) .
> Aber genau diese Bedingung ist doch bei R3 immer erfüllt,
> oder nicht?
Du hast völlig Recht.
> > Falls trotzdem die Voraussetzung y1 [mm]\ne[/mm] y2 "gemeint"
> > sein sollte, dann müsste sie unbedingt in der
> Definition
> > stehen. Die Aussage [mm]\ (\,y1\in M\ \wedge\ y2\in M\,)\ \Rightarrow\ y1\ne y2[/mm]
> > ist eben falsch.
> Fulla hat aber auch nicht behauptet, dass [mm]y1\ne[/mm] y2 ist. Er
> hat, wenn ich das richtig verstanden habe, zwei fälle
> betrachtet: Erstens y1 [mm]\ne[/mm] y2 und dann y1=y2. Und für
> beide Fälle erfüllt R3 Die Bedingung zur Konfluenz.
Richtig.
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:13 Do 30.10.2014 | | Autor: | Fulla |
> > Hallo infinity95!
> >
> > > Zu R3: Warum ist R3 denn nicht Konfluent? Ich sehe keinen
> > > Grund, warum es nicht Konfluent sein sollte.
> >
> > Sei zunächst [mm]y_1\not = y_2[/mm], dann kommt nur [mm]x=0[/mm] in Frage,
> > da nur 0 mit zwei verschiedenen Elementen aus R3 in
> > Relation steht. Dann erfüllt [mm]z=3[/mm] die Bedingung.
> > Für [mm]y_1=y_2[/mm] ist ebenfalls [mm]z=3[/mm] die entsprechende Wahl.
> >
> > Ich denke also ebenfalls, dass R3 konfluent ist.
> >
> > Lieben Gruß,
> > Fulla
>
>
> Guten Tag Fulla und [mm]\infty_{95}[/mm]
>
> Die Definition lautete aber:
>
> Eine Relation R auf einer Menge M heißt genau dann
> konfluent, wenn
> [mm]\forall \ x\ \in \ M\ \ \red{\forall \ y1\,,\,y2 \ \in M}:\ (xRy1 \ \wedge\ xRy2 \ \Rightarrow \exists \ z \ \in \ M: y1Rz \ \wedge \ y2Rz)[/mm]
Hallo Al!
Also, ich lese da: Für alle [mm]x, y_1, y_2\in M[/mm], für die [mm]xRy_1 \wedge xRy_2[/mm] gilt, folgt ...
Lieben Gruß,
Fulla
> Da hier nicht verlangt wird, dass y1 [mm]\ne[/mm] y2 , sollte der
> Fall
> y1 = y2 auch zugelassen sein, was dann halt bedeutet,
> dass jedes Element y, zu dem im Relationsgraph ein Pfeil
> hinführt, auch einen Pfeil haben müsste, der von y
> wegführt
> oder ev. einen "Loop-Pfeil" (y,y) .
>
> Falls trotzdem die Voraussetzung y1 [mm]\ne[/mm] y2 "gemeint"
> sein sollte, dann müsste sie unbedingt in der Definition
> stehen. Die Aussage [mm]\ (\,y1\in M\ \wedge\ y2\in M\,)\ \Rightarrow\ y1\ne y2[/mm]
> ist eben falsch.
>
> LG , Al-Chw.
|
|
|
| |
|
etschuldiget bitte,
i ha da gloubi es bitzeli es gnuusch im fadechörbli gha !
 Al
|
|
|
|
