Relationen & Eigenschaften
Eine Relation ist einfach eine Menge von Paaren. Die fünf Eigenschaften (reflexiv, irreflexiv, symmetrisch, antisymmetrisch, transitiv) sieht man am schnellsten im Graphen. Genau das trainierst du hier.
Definition · RelationDef. 1.27, Folien 2 S. 15
Eine Relation auf A ist eine Teilmenge R ⊆ A × A. Statt (a, b) ∈ R schreibt man aRb. Als gerichteter Graph: ein Punkt pro Element, ein Pfeil a → b für jedes Paar, eine Schlinge für (a, a) (Folien 2 S. 18).Definition · EigenschaftenDef. 1.29, Bsp. 1.30, Folien 2 S. 19–21
| reflexiv | (a, a) ∈ R für alle a ∈ A | an jedem Punkt eine Schlinge |
| irreflexiv | kein (a, a) ∈ R | keine einzige Schlinge |
| symmetrisch | (a, b) ∈ R ⇒ (b, a) ∈ R | jeder Pfeil hat einen Rückpfeil |
| antisymmetrisch | (a, b), (b, a) ∈ R ⇒ a = b | zwischen zwei Punkten nie hin und zurück |
| transitiv | (a, b), (b, c) ∈ R ⇒ (a, c) ∈ R | jeder Zweierweg hat eine Abkürzung |
Typischer Fehler
„irreflexiv“ ist nicht „nicht reflexiv“, und „antisymmetrisch“ ist nicht „nicht symmetrisch“ (Folien 2 S. 22). Eine Relation mit nur einigen Schlingen ist weder reflexiv noch irreflexiv. Die leere Relation ist symmetrisch und antisymmetrisch.Transitivität systematisch prüfen
Gehe jeden Pfeil a → b durch und schaue, welche Pfeile von b weggehen (b → c). Für jeden solchen muss a → c da sein. Vorsicht bei Hin und Zurück: a → b → a verlangt die Schlinge (a, a)!Beispiel · Eigenschaften ablesen
A = {1, 2, 3}, R = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3)}. Welche Eigenschaften hat R?
0 / 4
✏️ Übung · Eigenschaften erkennen (Zufall)
Zufallsrelationen. Drei komplett richtig = gelöst (0/3).
A = {a, b, c, d}, R = {(a, a), (a, b), (b, b), (c, c), (c, d), (d, d)}
| R ist reflexiv | |
| R ist irreflexiv | |
| R ist symmetrisch | |
| R ist antisymmetrisch | |
| R ist transitiv |
✏️ Übung · Relation konstruieren
Baue eine Relation auf {a, b, c}, die symmetrisch und transitiv, aber nicht reflexiv ist. (Tipp: Es geht, aber nicht jedes Element darf in einem Paar vorkommen.)
✗ reflexiv
(a, a) fehlt.
✓ irreflexiv
Keine einzige Schlinge.
✓ symmetrisch
Zu jedem Pfeil gibt es den Rückpfeil.
✓ antisymmetrisch
Zwischen zwei verschiedenen Elementen nie Hin- und Rückpfeil.
✓ transitiv
Jeder Weg aus zwei Pfeilen hat schon eine direkte Abkürzung.
Knoten anklicken, dann Zielknoten: Pfeil an/aus. Neue Pfeile sind farbig.
R = ∅
✏️ Übung · Reflexiv und antisymmetrisch, nicht transitiv
Baue eine Relation auf {1, 2, 3}, die reflexiv und antisymmetrisch, aber nicht transitiv ist.
✗ reflexiv
(1, 1) fehlt.
✓ irreflexiv
Keine einzige Schlinge.
✓ symmetrisch
Zu jedem Pfeil gibt es den Rückpfeil.
✓ antisymmetrisch
Zwischen zwei verschiedenen Elementen nie Hin- und Rückpfeil.
✓ transitiv
Jeder Weg aus zwei Pfeilen hat schon eine direkte Abkürzung.
Knoten anklicken, dann Zielknoten: Pfeil an/aus. Neue Pfeile sind farbig.
R = ∅