binäre Relationen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:02 Mi 03.05.2006 | | Autor: | Steffi21 |
| Aufgabe | Es sei M eine Menge mit 5 Elementen.
a) Wieviel binäre Relationen über M gibt es?
b) Wieviel sind reflexsiv?
c) Wieviel sind reflexsiv und symmetrisch? |
Hallo, Guten Abend,
ich bin gerade beim Nacharbeiten meiner Übung. Oben genannte Aufgabe a) habe habe ich mit 25 angegeben, ich nehme die Menge M mit den Elementen a, b, c, d, e, dann ergeben sich für mich folgende binäre Relationen:
aRa, aRb, aRc, aRd, aRe,
bRa, bRb, bRc, bRd, bRe,
je 5, bis eRe, sind für mich 25 binäre Relationen.
Bei gegebenen Relationen kann ich dann begründen, ob sie reflexsiv, irreflexsiv, symmetrisch, antisymmetrisch oder transitiv sind. Leider bekam ich auf meinen Ansatz der Aufgabe a) 0 Punkte, so dass b) und c) auch falsch wurden. Bitte helft mir, wo lag mein Fehler im Ansatz.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Danke Steffi
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 09:23 Do 04.05.2006 | | Autor: | DaMenge |
Hallo Steffi,
du verwechselst "binäre Relation" mit "Paar".
Es stimmt zwar, dass es 25 Paare gibt, aber eine binäre Relation ist eine beliebige Teilmenge aus MxM - nicht nur die einzelnen Paare.
Also ist zum Beispiel auch : [mm] $\{ (a,b) , (a,c) , (d,e) \}$ [/mm] und [mm] $\{ (a,b) , (e,c) \}$ [/mm] JEWEILS schon eine Relation.
(die anzahl der Paare in der Relation ist also nicht vorher irgendwie bestimmt.)
Die Anzahl der binären Relationen ist also gleich [mm] $|Pot(M\times [/mm] M)|$
(wobei Pot die Potenzmenge sein soll.)
Stell dir die Relation mal als Matrix vor : wir nehmen eine 5x5 Matrix und wir schreiben an der Stelle (i,j) genau dann eine 1, wenn das Paar (i,j) in der Relation R ist (also die Elemente aus M seien durchnummeriert, klar, oder?).
Und sonst stehen nur 0 in der Matrix
Du musst dich dann halt fragen : Wieviele verschiedene solcher Matrizen gibt es...
(in jedem Eintrag hast du die Wahl : eine 1 setzen oder nicht, also : [mm] 2^{25} [/mm] verschiedene Möglichkeiten...)
bei der b) sollte man sich dann überlegen, dass alle Paare (i,i) schon als Teilmenge in der Relation vorhanden sein müssen, also ist Die Antwort für b) : $| Pot( [mm] (M\times [/mm] M) [mm] \setminus\{(i,i) | i\in M \})|$
[/mm]
Hier wäre die Diagonale also schon mit 1 gefüllt, wieviele Möglichkeiten gibt es den Rest der Matrix zu füllen?
(bei wievielen Einträgen kann man also noch zwischen 0 und 1 wählen?)
bei der c) analog : Die Diagonale ist schon mit 1 besetzt und wieviele Möglichkeiten gibt es die obere Dreiecksmatrix zu füllen
(denn wenn Symmetrie herrscht, ist jeder Eintrag der unteren Dreiecksmatrix durch die in der oberen eindeutig bestimmt.)
versuchst du es nochmal?
viele Grüße
DaMenge
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:16 Do 04.05.2006 | | Autor: | Steffi21 |
Danke DaMenge,
bei der Aufgabe b) kommt demzufolge [mm] 2^{20}
[/mm]
bei der Aufgabe c) kommt demzufolge [mm] 2^{10} [/mm] raus,
Steffi
|
|
|
|
