Relationen
Elemente in einer Menge stehen in bestimmten Beziehungen zueinander. Diese Beziehungen lassen sich durch Relationen beschreiben. Konkret ist eine Relation eine Teilmenge des kartesischen Produkts zweier Mengen.
Sei A und B zwei beliebige Mengen. Jede Menge R mitMan spricht in dieser Definition deshalb von einer binären Relation, weil lediglich eine Relation zwischen zwei Elementen besteht. Tatsächlich lassen sich auch Teilmengen von Produkten von drei oder mehreren Mengen bilden, die ebenfalls Relationen sein können.
R ⊆ A χ B
heißt (binäre) Relation.
Eine Relation lässt sich auf unterschiedliche Weisen darstellen. Jede hier vorgestellte Darstellung hat ihre eigene Vor- und Nachteile. Man kann Relationen folgendermaßen darstellen:
- Darstellung als Menge
- Darstellung als Graph
- Darstellung als Tabelle/Matrix
Da Relationen letztendlich nichts anderes als spezielle Mengen sind, können sämtliche Konzepte aus der Mengenlehre auch auf Relationen übertragen werden. So können Relationen gleich sein oder eine Relation kann eine Teilrelation von einer anderen Relation sein. Weiter kann man Relationen vereinigen oder auch das Komplement bilden. Darüber hinaus gibt es aber noch einige speziell für Relationen definierte Operationen von denen nachfolgend vor allem die inverse Relation und das Relationsprodukt interessant sind.
Inverse Relation
Die inverse Relation ist wie folgt definiert:
R-1 := {(y,x) | (x,y) ∈ R}
Beispiel einer inversen Relation
Die inverse Relation der folgenden OrdnungsrelationR := {(x,y) | x ≤ y}
lautet:
R-1 := {(x,y) | x ≥ y}
Relationenprodukt
Das Relationenprodukt sei wie folgt definiert:
R ⋅ S := {(x,z) | es existiert ein y mit x und y stehen bezüglich Relation R in Beziehung und y und z stehen bezüglich Relation S in Beziehung}
Mit diesen Operationen lassen sich Relationenattribute elegant charakterisieren. Welche Attribute das sind, erfährt man nachfolgend.
Relationenattribute
Eine Relation R in der Menge M heißt:
- reflexiv in M, falls für alle x ∈ M das Element x in Relation mit x steht, also xRx gilt
- irreflexiv in M, falls für alle x ∈ M das Element x nicht in Relation mit x steht
- symmetrisch in M, falls für alle x,y ∈ M aus x steht in Relation mit y stets folgt, dass y in Relation zu x steht.
- asymmetrisch in M, falls für alle x,y ∈ M aus x steht in Relation mit y stets folgt, dass y nicht in Relation zu x steht.
- antisymmetrisch in M, falls für alle x,y ∈ M aus x steht in Relation mit y und y steht in Relation zu x stets folgt, dass x=y ist
- transitiv in M, falls für alle x,y,z ∈ M aus x steht in Relation mit y und y steht in Relation zu z stets folgt, dass x in Relation zu z steht.
Reflexivität
Für eine reflexive Relation gilt, dass für alle x aus einer Menge M gilt, x steht in Relation zu x. Am einfachsten begreiflich machen kann man die Reflexivität mit einem einfachen Beispiel. Die Relation „hat die selben Eltern wie“ zwischen drei Brüdern ist beispielsweise reflexiv. Denn schließlich hat jeder die selben Eltern wie man selbst. Klar wird die Reflexivität auch in der Darstellung von Graphen oder in einer Adjazenzmatrix.Reflexiven Relation in Graphendarstellung
![Beispiel einer reflexiven Relation - Graph](bilder/relationen/reflexive-relationen.png)
Wie man erkennen kann, muss bei diesem Graph eine reflexive Relation vorliegen. Entscheidend sind nämlich die Schlingen an jedem Knoten. Sobald jeder Knoten eine Schlinge besitzt, ist der Graph reflexiv, da jeder Knoten auf „sich selbst zeigt“.
Reflexiven Relation in Matrixdarstellung
![Beispiel einer reflexiven Relation - Matrix](bilder/relationen/reflexive-relation-adjazenzmatrix.png)
Auch in der Matrixdarstellung, wie die obere Adjazenzmatrix des oberen Graphen, sieht man mit einem Blick, ob die Relation reflexiv ist oder nicht. Sobald in der Hauptdiagonalen alle Einträge eine 1 sind, liegt Reflexivität vor.
Irreflexivität
Eine Relation ist dann irreflexiv, wenn für alle x aus einer Menge M gilt, dass x in keiner Relation zu x steht.ACHTUNG! Ist eine Relation nicht reflexiv, folgt daraus nicht zwangsläufig, dass die Relation deshalb irreflexiv ist. Damit eine Relation irreflexiv ist, muss für alle x gelten, dass x in keiner Relation zu x steht.
Beispiel für irreflexive Relation
Sei folgende Menge gegeben: M := {1,2,3}Nun ist folgende Relation beispielsweise reflexiv:
R1 ={(1,1), (1,2), (2,2), (3,3)}
Würde man aus dieser Relation R1 nun (3,3) löschen, hätte man folgende Relation:
R2 ={(1,1), (1,2), (2,2)}
Diese Relation R2 wäre nun nicht Reflexiv aber eben auch nicht irreflexiv, da die Relation eben noch (1,1) und (2,2) enthält. Erst wenn man diese löscht, wäre die Relation irreflexiv.
R3 ={(1,2)}
R3 ist nun irreflexiv!
Symmetrie
Eine Relation ist dann symmetrisch, wenn für alle x,y ∈ M gilt, dass x zu y in Relation steht und daraus folgt, dass auch y zu x in Relation steht. Stellt man eine Relation als Graph dar, kann man eine symmetrische Relation sofort erkennen. Diese liegt nämlich vor, wenn jeder Knoten mit seinem Nachbarknoten durch eine gerichtete Kante an beiden Enden verbunden ist. Also wenn an jede Kante zu jedem Knoten mit einer Pfeilspitze abschließt. Dies ist beispielsweise beim nachfolgenden Graph der Fall.Symmetrische Relation in Graphendarstellung
![Beispiel einer symmetrischen Relation](bilder/relationen/symmetrische-relation.png)
Asymmetrie
Bei einer asymmetrischen Relation muss für alle x,y ∈ M gelten, wenn x zu y in Relation steht, dann steht nicht y in Relation zu x.Wie auch bei der Irreflexivität, muss man auch bei der Asymmetrie aufpassen. Wenn eine Relation nämlich nicht Symmetrisch ist, bedeutet dies nicht automatisch, dass die Relation dann asymmetrisch ist.
Antisymmetrie
Bei einer antisymmetrischen Relation gilt für alle x,y ∈ M, dass wenn x in Relation zu y steht und y in Relation zu x, dann ist x=y.Man sollte sich von dem Begriff "Antisymmetrie" nicht täuschen lassen! Eine Relation kann sehr wohl gleichzeitig symmetrisch als auch antisymmetrisch sein, da beides keine Gegensätze sind.
Beispiel: Die Relation R1 ={(1,1), (2,2), (3,3)} ist symmetrisch, aber auch antisymmetrisch.
Transitivität
Eine Relation ist dann transitiv, wenn für alle x,y,z ∈ M gilt, wenn x in Relation steht zu y und y in Relation steht zu z, dann steht auch x in Relation zu z.Ein Beispiel für eine transitive Relation wäre die "kleiner als"-Relation: R<= {(0,1), (0,2), (1,2)}
Es ergibt sich: 0 ist kleiner als 1 und 1 ist kleiner als 2, also muss auch 0 kleiner als 2 sein. Was wahr ist und somit ist R< eine transitive Relation.
Äquivalenzrelation
Eine Relation R ist eine Äquivalenzrelation, wenn sie gleichzeitig reflexiv, symmetrisch und transitiv ist.
Eine Äquivalenzrelation hat die Eigenschaft , die Elemente aus einer Menge M in Äquivalenzklassen einzuteilen. Durch die Eigenschaften der Reflexivität, der Symmetrie und der Transitivität führt dazu, dass diese gebildeten Äquivalenzklassen paarweise disjunkt sind.
Allgemeine Frage: Wie viele Äquivalenzklassen kann eine drei-elementige Menge haben?
Antwort: 5
Man nehme an, die Menge sei: M := {a,b,c}, dann wären die fünf möglichen Klassen:
- a in einer Klasse, b in einer Klasse und c in einer Klasse
- a und b in einer Klasse und c in einer Klasse
- a und c in einer Klasse und b in einer Klasse
- a in einer Klasse und b und c in einer Klasse
- a und b und c in einer Klasse
Ordnungsrelation
Eine Relation R ist eine Ordnungsrelation, wenn sie gleichzeitig reflexiv, antisymmetrisch und transitiv ist.
Quellen:
- Theoretische Informatik von Dirk W. Hoffmann
- Deutsche Wikipedia - de.wikipedia.org