Relationen auf M < Relationen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | M ist eine Menge mit n Elementen
1. Bestimme die Anzahl aller Relationen auf M.
2. Bestimme die Anzahl aller reflexiven Relationen auf M.
3. Bestimme die Anzahl aller symetrischen Relationen auf M.
Begründe die Antworten! |
Okay...ich habe da mal etwas versucht....
1.Relationen sind def. als Teilmengen des kartesischen Produktes von MxM. Gesucht sind alle Teilmenge von M², wobei die Mächtigkeit aller Teilmengen einer Menge M
[mm] [2^M] [/mm] beträgt. Daher gibt es [mm] [2^{|MxM|}=2^{|M|^2}] [/mm] Teilmengen bzw. Relationen in M.
Oder muss ich das irgendwie auführlicher darstellen?
2. bei reflexiv müssen genau alle Paare der "Diagonalen" in entsprechenden R enthalten sein
[mm] [{2^{|M|^2}}*{2^|M|}=2^{|M|^2-|M|}]
[/mm]
3.Wenn man sich eine |M|x|M| - Matrix nimmt und die Def. von Symmetrisch m,n aus M: (m,n) in R --> (n,m) in R betrachtet, würde ich sagen:
[mm] [2^{{|M|^2+|M|}{2}}] [/mm] ist die gesuchte Anzahl, denn ich kann eine Hälfte(links oder rechts der Diagonalen + Diagonale (+|M| in der Formel) in der Matrix beliebig wählen und die restlichen Paare sind dadurch eindeutig bestimmt.
ist das so okay? Das wäe meine Idee gewesen.
Mathegirl
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 07:30 So 14.11.2010 | | Autor: | felixf |
Moin!
> M ist eine Menge mit n Elementen
>
> 1. Bestimme die Anzahl aller Relationen auf M.
> 2. Bestimme die Anzahl aller reflexiven Relationen auf M.
> 3. Bestimme die Anzahl aller symetrischen Relationen auf
> M.
>
> Begründe die Antworten!
> Okay...ich habe da mal etwas versucht....
>
> 1.Relationen sind def. als Teilmengen des kartesischen
> Produktes von MxM. Gesucht sind alle Teilmenge von M²,
> wobei die Mächtigkeit aller Teilmengen einer Menge M
> [mm][2^M][/mm] beträgt. Daher gibt es [mm][2^{|MxM|}=2^{|M|^2}][/mm]
> Teilmengen bzw. Relationen in M.
Wenn du die schliessende eckige Klammer etwas verschiebst, passt es.
> Oder muss ich das irgendwie auführlicher darstellen?
Ich denke nicht.
> 2. bei reflexiv müssen genau alle Paare der "Diagonalen"
> in entsprechenden R enthalten sein
> [mm][{2^{|M|^2}}*{2^|M|}=2^{|M|^2-|M|}][/mm]
Das ergibt so keinen Sinn. Die linke Seite entspricht nicht der rechten Seite.
Das was auf der rechten Seite steht stimmt allerdings.
> 3.Wenn man sich eine |M|x|M| - Matrix nimmt und die Def.
> von Symmetrisch m,n aus M: (m,n) in R --> (n,m) in R
> betrachtet, würde ich sagen:
> [mm][2^{{|M|^2+|M|}{2}}][/mm] ist die gesuchte Anzahl, denn ich
> kann eine Hälfte(links oder rechts der Diagonalen +
> Diagonale (+|M| in der Formel) in der Matrix beliebig
> wählen und die restlichen Paare sind dadurch eindeutig
> bestimmt.
Da sollte wohl eine andere Formel stehen; hast du zufaellig \frac vergessen?
LG Felix
|
|
|
| |
|
Danke das du mal darüber geschaut hast! ich weiß nicht was dann links stehen muss, wenn rechts okay ist....ich sehe selbst das es nicht stimmt, aber wenn ich versuche das abzuändern komme ich immer rechts auf ein anderes Ergebnis.
Was meinst du mit [mm] \frac [/mm] und das die Formel nicht stimmt?
Mathegirl
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:06 Mo 15.11.2010 | | Autor: | felixf |
Moin!
> Danke das du mal darüber geschaut hast! ich weiß nicht
> was dann links stehen muss, wenn rechts okay ist....ich
> sehe selbst das es nicht stimmt, aber wenn ich versuche das
> abzuändern komme ich immer rechts auf ein anderes
> Ergebnis.
>
> Was meinst du mit [mm]\frac[/mm] und das die Formel nicht stimmt?
Soll $ [mm] [2^{{|M|^2+|M|}{2}}] [/mm] $ wirklich das sein, was du scheiben wolltest? Was macht die 2 da ganz rechts? Die sollte da sicher nicht so stehen.
LG Felix
|
|
|
| |
|
Wo hab ich denn die Klammern falsch gesetzt bzw. wie krieg ich es hin, das linke und rechte seite überein stimmen?
Stimmt der Grundansatz soweit?
Wäre für Hilfe dankbar!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:07 Mo 15.11.2010 | | Autor: | felixf |
Moin!
> Wo hab ich denn die Klammern falsch gesetzt bzw. wie krieg
> ich es hin, das linke und rechte seite überein stimmen?
Guck dir diese Formel hier an: $ [mm] [2^{|MxM|}=2^{|M|^2}] [/mm] $
Was soll es bedeuten, wenn du eine Gleichung in eckige Klammern setzt?
> Stimmt der Grundansatz soweit?
Ja.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:42 So 14.11.2010 | | Autor: | dfx |
Hallo nochmal,
> Okay...ich habe da mal etwas versucht....
>
> 1.Relationen sind def. als Teilmengen des kartesischen
> Produktes von MxM. Gesucht sind alle Teilmenge von M²,
> wobei die Mächtigkeit aller Teilmengen einer Menge M
> [mm][2^M][/mm] beträgt. Daher gibt es [mm][2^{|MxM|}=2^{|M|^2}][/mm]
> Teilmengen bzw. Relationen in M.
"Relationen sind definiert als Teilmengen des kartesischen Produktes von $M [mm] \times [/mm] M$. Sei n die Anzahl der Elemente von $M$. Dann beträgt die Mächtigkeit aller Teilmengen [mm] 2^n. [/mm] Daher gibt es [mm] $2^{n \cdot n} [/mm] = [mm] 2^{n^{2}}$ [/mm] Teilmengen von $M [mm] \times [/mm] M$."
> Oder muss ich das irgendwie auführlicher darstellen?
Man kann das ausführlicher begründen, denke ich. Aber es sollte so völlig ausreichend sein. Du solltest dir nochmal die Aufgabenstellung ansehen, wenn du über das n, was bei mir auftaucht, verwundert bist. Soweit ich mich erinnern kann, wissen wir nicht aus der Vorlesung, dass |M| als die Anzahl der Elemente von M definiert ist.
Was den Rest angeht, sollte wohl klar sein, dass es sich nur um Relationen der Möglichen, die wir grad beziffert haben, handeln kann.
> 2. bei reflexiv müssen genau alle Paare der "Diagonalen"
> in entsprechenden R enthalten sein
> [mm][{2^{|M|^2}}*{2^|M|}=2^{|M|^2-|M|}][/mm]
Welche davon sind nun reflexiv. Also du sagst:
"Zur Reflexivität müssen genau alle Paare der 'Diagonalen' in den entsprechenden Relationen enthalten sein."
Hast du dir das mal veranschaulicht? Das geht übrigens wunderbar bei der vorherigen Aufgabe. Wieviele Paare sind denn in der Diagonalen, wenn du n=2 hast?
Also willst du sagen [mm] 2^{n^2-n} [/mm] Teilmengen sind reflexiv. Dem stimme ich auch zu.
> 3.Wenn man sich eine |M|x|M| - Matrix nimmt und die Def.
> von Symmetrisch m,n aus M: (m,n) in R --> (n,m) in R
> betrachtet, würde ich sagen:
> [mm][2^{{|M|^2+|M|}{2}}][/mm] ist die gesuchte Anzahl, denn ich
> kann eine Hälfte(links oder rechts der Diagonalen +
> Diagonale (+|M| in der Formel) in der Matrix beliebig
> wählen und die restlichen Paare sind dadurch eindeutig
> bestimmt.
Hier bin ich selbst noch nicht so richtig auf den Punkt gekommen. Aber deine Ausführungen werde ich mir mal durch den Kopf gehen lassen.
Rechnen mit Potenzen wäre wohl mal eine Wiederholung wert.
gruss, dfx
Edit#x: Edits entfernt :<
Ich komm da nicht so wirklich auf einen grünen Zweig. Allerdings finde ich, die Hälfte der durch die Diagonale getrennten Relationen, ergibt die andere Hälfte eigentlich ganz schlüssig. Bleibt zwar evtl. fragwürdig was mit der Diagonalen passiert, aber hmm...
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 08:36 Mo 15.11.2010 | | Autor: | dfx |
Hallo,
die letzte Aufgabe bereitet mir mehr Probleme als ich gedacht hätte. Darum versuch ich es nochmal in einer Frage auszudrücken, nachdem ich meine Ansätze angesprochen habe.
Mein erster Ansatz wäre eben mit der Diagonalen zu argumentieren, wie es Mathegirl versucht hat. D.h. Ich sage, aus der einen Hälfte, der durch die Diagonalen getrennten Relationen, lässt sich die andere mithilfe der Symmetrie herleiten. Entspräche das dann nicht der Hälfte aller möglichen Relationen?
Ich habe es mir durch den Kopf gehen lassen und bin im Falle der Relationen der Menge {a,b} auf zwei 1-elementige, zwei 2-elementige, zwei 3-elementige und den trivialen Relationen, die beide symmetrisch sind, gekommen. Jetzt sehe ich darin eine Bestätigung für den Ansatz, aber ist das so korrekt?
gruss, dfx
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:23 Mo 15.11.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
