Binärrelationen < Relationen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:16 So 23.10.2011 | | Autor: | gpvw100 |
| Aufgabe 1 | Über die Agenten, die in der Wumpus-Welt operieren, ist folgendes bekannt:
Kennt ein Agent A einen Agenten B und auch einen Agenten C, so kennt der Agent B ebenfalls den Agenten C. Natürlich kennt jeder Agent auch sich selbst.
Zeigen Sie, dass in der Wumpus-Welt die zwischen Agenten bestehende binäre Relation "kennt" eine Äquivalenzrelation ist. |
| Aufgabe 2 | R [mm] \subseteq [/mm] A [mm] \times [/mm] A und S [mm] \subseteq [/mm] A [mm] \times [/mm] A seien zwei beliebige Äquivalenzrelationen auf einer Menge A.
Welche der folgenden Relationen sind dann ebenfalls Äquivalenzrelationen?
Begründen Sie Ihre Antwort durch einen Beweis oder durch die Angabe eines Gegenbeispiels.
a) R [mm] \cap [/mm] S
b) R [mm] \cup [/mm] S |
Hallo,
Ich wollte fragen, ob mir vielleicht jemand für diese beiden Aufgaben eine Hilfestellung geben könnte, da ich selber nicht weiterkomme bzw. nicht wirklich weiß wie ich Aufgaben angehen soll.
MfG
gpvw100
|
|
| |
|
Hallo gpvw100,
> Über die Agenten, die in der Wumpus-Welt operieren, ist
> folgendes bekannt:
> Kennt ein Agent A einen Agenten B und auch einen Agenten
> C, so kennt der Agent B ebenfalls den Agenten C. Natürlich
> kennt jeder Agent auch sich selbst.
> Zeigen Sie, dass in der Wumpus-Welt die zwischen Agenten
> bestehende binäre Relation "kennt" eine
> Äquivalenzrelation ist.
> R [mm]\subseteq[/mm] A [mm]\times[/mm] A und S [mm]\subseteq[/mm] A [mm]\times[/mm] A seien
> zwei beliebige Äquivalenzrelationen auf einer Menge A.
> Welche der folgenden Relationen sind dann ebenfalls
> Äquivalenzrelationen?
> Begründen Sie Ihre Antwort durch einen Beweis oder durch
> die Angabe eines Gegenbeispiels.
>
> a) R [mm]\cap[/mm] S
> b) R [mm]\cup[/mm] S
> Hallo,
> Ich wollte fragen, ob mir vielleicht jemand für diese
> beiden Aufgaben eine Hilfestellung geben könnte, da ich
> selber nicht weiterkomme bzw. nicht wirklich weiß wie ich
> Aufgaben angehen soll.
Nun, zunächst mal solltest du dir mal herausschreiben und verinnerlichen, was denn eine Äquivalenzrelation ist bzw. welche Eigenschaften ein Relation erfüllen muss, damit es eine Ä.-relation ist.
1) Sie muss reflexiv sein, dh. formal was?
2) Sie muss symmetrisch sein, dh. formal was?
3) Sie muss transitiv sein, dh. formal was?
Zur ersten Aufgabe:
Du betrachtest die Relation "Kennt" auf der Menge aller Agenten [mm]M[/mm], dh. "Kennt" [mm]\subset M\times M[/mm]
Nach Aufgabentext kennt jeder Agent sich selbst, steht also mit sich selbst in der Relation "Kennt".
Also: für alle Agenten [mm]A\in M[/mm] gilt: [mm]A[/mm] "Kennt" [mm]A[/mm], dh. [mm](A,A)\in[/mm] "Kennt"
Versuche, die beiden fehlenden Eigenschaften Symmetrie (dh. kennt ein Agent A einen Agenten B, so kennt der Agent B auch den Agenten A) und Transitivität (dh. kennt Agent A Agent B und kennt B Agent C, so kennt auch Agent A Agent C) aus den Angeben in der Aufgabenstellung herzuleiten.
Für die andere Aufgabe, Teil 1, benötigst du die formale Def. Ä-Relation und Schnittmenge.
Ich zeige mal Reflexivität: zu zeigen ist, dass für alle [mm]a\in A[/mm] gilt: [mm](a,a)\in R\cap S[/mm]
Seien [mm]R,S\subset A\times A[/mm] Ä-Relationen auf A
Dann sind [mm]R,S[/mm] insbesondere reflexiv, dh. für alle [mm]r\in A[/mm] ist [mm](r,r)\in R[/mm] und für alle [mm]s\in A[/mm] ist [mm](s,s)\in S[/mm]
Sei nun [mm]a\in A[/mm], dann ist [mm](a,a)\in R[/mm], [mm](a,a)\in S[/mm], da [mm]R,S[/mm] reflexiv
Also ist [mm](a,a)\in R\cap S[/mm]
Das war's schon (und viel ausführlicher als es sein müsste  )
Mache du dich mal an den Nachweis der anderen beiden Eigenschaften!
Und überlege mal selbst, ob das bei der Vereinigung auch so reibungslos klappt ...
>
> MfG
> gpvw100
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 16:52 So 23.10.2011 | | Autor: | gpvw100 |
Schonmal vielen Dank für die schnelle Hilfe.
Zu den Eigenschaften einer Äquivalenzrelation:
1) [mm] \forall [/mm] a [mm] \in [/mm] A. a [mm] \sim [/mm] a.
Also a steht in Beziehung zu sich selbst
2) [mm] \forall a_{1} [/mm] , [mm] a_{2} \in [/mm] A. [mm] a_{1} \sim a_{2} \Rightarrow a_{2} \sim a_{1} [/mm] .
Also steht [mm] a_{1} [/mm] mit [mm] a_{2} [/mm] in Relation steht auch a2 mit a1 in Relation.
3) [mm] \forall a_{1}, a_{2}, a_{3} \in [/mm] A. [mm] a_{1} \sim a_{2} \wedge a_{2} \sim a_{3} \Rightarrow a_{1} \sim a_{3}
[/mm]
Also wenn [mm] a_{1} [/mm] mit [mm] a_{2} [/mm] und [mm] a_{2} [/mm] mit [mm] a_{3} [/mm] in Relation steht, so steht auch [mm] a_{1} [/mm] mit [mm] a_{3} [/mm] in Relation.
Also die reflexivität ist ja, wie du bereits gesagt hast, durch den Satz "Jeder Agent kennt sich selber" gegeben.
Durch den Satz "Kennt ein Agent A einen Agenten B und auch einen Agenten C, so kennt der Agent B ebenfalls den Agenten C." ist dann ja quasi die transitivität gegeben, da der Satz ja folgendes Aussagt:
A [mm] \sim [/mm] B [mm] \wedge [/mm] A [mm] \sim [/mm] C [mm] \Rightarrow [/mm] B [mm] \sim [/mm] C
Da aber B [mm] \sim [/mm] C gilt, gilt dann ja auch folgende Aussagen:
A [mm] \sim [/mm] B [mm] \wedge [/mm] B [mm] \sim [/mm] C [mm] \Rightarrow [/mm] A [mm] \sim [/mm] C
Welches dann genau die reflexivität angibt.
Bei der symmetrie bin ich mir nicht ganz sicher, aber ich würde sagen durch den Satz "so kennt der Agent B ebenfalls den Agenten C" müsste ja nicht nur gelten das A B kennt sonder auch B A kennt. Daraus würde folgern:
A [mm] \sim [/mm] B [mm] \Rightarrow [/mm] B [mm] \sim [/mm] A
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:20 Di 25.10.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
