matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenDiskrete Mathematikbinäre Relationen
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Geschichte • Erdkunde • Sozialwissenschaften • Politik/Wirtschaft
Forum "Diskrete Mathematik" - binäre Relationen
binäre Relationen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Diskrete Mathematik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

binäre Relationen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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

        
Bezug
binäre Relationen: bitte überprüfen !
Status: (Antwort) fertig Status 
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

Bezug
                
Bezug
binäre Relationen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Diskrete Mathematik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]