Diskrete Mathematik 2. Semester

R1 = { (Tom, Lisa), (Tom, Paula) } = x ist befreundet mit y

R2 = { (Paul, Paula) } = x ist verwandt mit y

Sei R als Teilmenge von M x N eine beliebige Relation zwischen M und N. R^(-1) = { (x,y) | (y,x) e R } ist eine Relation zwischen N und M (inverse Relation).

R1^(-1) = y hat zum Vater x

R2^(-1) = y ist verheiratet mit x

Seien R1 als Teilmenge von M1 x M2 und R2 als Teilmenge von M2 x M3 beliebige Relationen. Die Verkettung von R1 mit R2 ist die Relation R1 • R2 = { (x,z) | x e M1 und z e M3 und es gibt ein y e M2, für das gilt: (x,y) e R1 und (y,z) e R2 }

R1 • R2 = x ist Mutter von z

R3 • R4 = x ist Schwiegervater von z

R heißt reflexiv genau dann, wenn die Identitätsmenge eine Teilmenge der Relation ist, also für alle x e M gilt: (x,x) e R

R heißt irreflexiv genau dann, wenn für alle x e M gilt: (x,x) nicht e R, die Schnittmenge der Identitätsmenge und R also die leere Menge ist.

Bemerkung: Keine Relation ist gleichzeitig reflexiv und irreflexiv. Es gibt allerdings Relationen, die weder reflexiv noch irreflexiv sind.

R heißt symmetrisch genau dann, wenn für alle x und y e M gilt: (x,y) e R --> (y,x) e R, also R eine Teilmenge der inversen Relation von R ist.

Ja. Sie hat keine Elemente, damit ist die Voraussetzung falsch und die Folgerung wahr.

R heißt asymmetrisch genau dann, wenn für alle x, y e M gilt: (x,y) e R --> (y,x) nicht e R

R1 = x kennt y --> nicht symmetrisch, nicht asymmetrisch

R2 = x ist größer als y --> asymmetrisch

R3 = x hat dasselbe Geschlecht wie y --> symmetrisch

R4 = {} --> symmetrisch und asymmetrisch

R heißt transitiv genau dann, wenn für alle x,y und z e M gilt: (x,y) e R und (y,z) e R --> (x,z) e R

R = x größer als y

Eine Relation heißt antisymmetrisch genau dann, wenn für alle x,y e M gilt: (x,y) e R und (y,x) e R --> x=y

(Die Schnittmenge von R und R^-1 ist Teilmenge der Identitätsmenge)

Sei M die Menge der Geraden der Ebene. Die Parallelitätsrelation ist reflexiv, da eine Gerade zu sich selbst parallel ist.

Sei M die Menge der Gerade einer Ebene. Die Relation "senkrecht stehen auf" ist irreflexiv, da eine Gerade nicht auf sich selbst senkrecht steht.

Sei M die Menge der Geraden einer Ebene. Die Relation "beide Geraden horizontal", d.h. (x, y) e R falls x und y zwei horizontale Geraden sind, ist weder reflexiv noch irreflexiv: falls x eine horizontale Gerade ist, dann ist (x, x) e R aber falls x keine horizontale Gerade ist, dann ist (x, x) nicht e R

Jede asymmetrische Relation ist irreflexiv.

Jede asymmetrische Relation ist antisymmetrisch.

Jede irreflexive Relation ist nicht reflexiv.

Jede reflexive Relation ist nicht irreflexiv.

Wenn R und S symmetrisch sind, dann ist auch die Vereinigungsmenge von R und S symmetrisch.

Die Relation ist:

• nicht symmetrisch, weil (Hänsel,Gretel) ∈ R und (Gretel,Hänsel) nicht ∈ R

• nicht asymmetrisch, weil (Castor,Pollux) ∈ R und (Pollux,Castor) ∈ R

• irreflexiv, weil keiner sein eigener Bruder ist.

• nicht transitiv, da Castor Bruder von Pollux ist und Pollux Bruder von Castor. Aber Castor ist nicht Bruder von Castor.

Die transitive Hülle einer Relation R auf M ist die kleinste Relation auf M, die R enthält und die transitiv ist. Natürlich ist R ihre transitive Hülle, falls R transitiv ist. Die Transitive Hülle versteht man am besten, wenn man eine Relation als gerichteter Graph darstellt: wenn man zwei aufeinanderfolgende Pfeile hat, sollte man auch einen direkten Pfeil haben (falls nicht vorhanden, eine direkte Straße anlegen).

Sei R als Teilmenge von MxM eine beliebige Relation. Die transitive Hülle von R ist die Relation R+ = Vereinigungsmenge von R^n mit n zwischen 1 und unendlich. R+ = { (x,y) | es gibt ein n e N, für das gilt: (x,y) e R^n }

R+ steht für die transitive Hülle, R* für die reflexive transitive Hülle. R* enthält also R+ und zusätzlich alle mit sich selbst in Beziehung stehenden Elemente.

Um die transitive Hülle einer Relation zu erhalten, müssen alle indirekten Verbindungen auch direkt verfügbar sein.

Schritt 1: Das 2. Element jedes Tupels ansehen und schauen, ob es in einem anderen Tupel als erstes Element auftritt.

Schritt 2: Prüfen, ob es für diese indirekte Verbindung zwischen dem ersten Element des 1. Tupels und dem zweiten Element des 2. Tupels auch schon eine direkte Verbindung gibt. Wenn nein, Hinzufügen des Tupels.

(a,b): Tupel mit b als erstem Element: (b,c), (b,e) --> (a,c), (a,e)

(b,c): Tupel mit c als erstem Element: /

(b,e): Tupel mit e als erstem Element: (e,d) --> (b,d)

(e,d): Tupel mit d als erstem Element: /

Relation: { (a,b), (a,c), (a,e), (b,c), (b,e), (b,d), (e,d) }

Schritt 3: Schritt 1 und 2 wiederholen, bis keine weiteren Tupel mehr hinzukommen.

transitive Hülle R+ = { (a,b), (a,c), (a,d), (a,e), (b,c), (b,e), (b,d), (e,d) }

Sei R als Teilmenge von MxM eine beliebige Relation. Die transitive Hülle von R ist die kleinste transitive Relation, die R umfasst, d.h.:

1.) R+ ist transitiv.

2.) R+ ist Obermenge von R

3.) Wenn S eine transitive Relation ist, die R umfasst, dann umfasst S auch R+.

Sei M ungleich leere Menge beliebig. R als Teilmenge von M x M heißt Ordnungsrelation genau dann, wenn

1.) R reflexiv ist.

2.) R transitiv ist.

3.) R antisymmetrisch ist.

R heißt strikte Ordnungsrelation genau dann, wenn

1.) R transitiv ist.

2.) R asymmetrisch ist.

Bemerkung: Falls R eine Ordnungsrelation ist, ist R ohne die Identitätsmenge eine strikte Ordnungsrelation.

R* ist die kleinste transitive und reflexive Relation, die R umfasst.

1.)  R* ⊇ R ist transitiv und reflexiv.

2.) Ist S eine beliebige transitive und reflexive Relation mit S ⊇ R, dann ist S ⊇ R*

Hasse Diagramm:

Das ”Hasse Diagramm“ einer Ordnungsrelation ist das Pfeildiagramm der Nachbarschaftsrelation.

Vorstellung als Hasse Diagramm:

1. Ebene: ∅

2. Ebene: {1}, {2}, {3}

3. Ebene: {1,2}, {1,3}, {2,3}

4. Ebene: {1,2,3}

Nachbarschaftsrelation = { (∅,{1}), (∅,{2}), (∅,{3}), ({1},{1,2}), ({1},{1,3}), ({2},{1,2}), ({2},{2,3}), ({3},{1,3}), ({3},{2,3}), ({1,2},{1,2,3}), ({1,3},{1,2,3}), ({2,3},{1,2,3})}

Sei R eine strikte Ordnungsrelation in M. Die Nachbarschaftsrelation von R ist definiert durch:

Für alle x,y e M gilt: x ist Nachbar von y genau dann, wenn x in strikter Ordnung zu y steht und es kein z e M gibt, für das gilt: x in strikter Ordnung zu z und z in strikter Ordnung zu y.

Sei R eine Ordnungsrelation in M und A Teilmenge von M. s e M heißt obere Schranke von A genau dann, wenn für alle a e A gilt: a <= s (alle Elemente aus A sind kleiner oder gleich s).

Sei R eine Ordnungsrelation in M und A Teilmenge von M. g e M heißt obere Grenze von A genau dann, wenn g minimales Element der Menge der oberen Schranken ist.

Sei R eine Ordnungsrelation in M und A Teilmenge von M. s e M heißt Supremum von A genau dann, wenn s kleinstes Element der Menge der oberen Schranken von A ist.

minimales Element einer Menge M: x e M und es gibt kein y e M für das gilt: y < x.

Es kann also mehrere minimale Elemente geben, da nicht ausgeschlossen wurde, dass y = x sein darf.

kleinstes Element einer Menge M: x e M und es gibt kein y e M für das gilt: y <= x.

Beim kleinsten Element wird dieser Fall ausgeschlossen, womit es maximal ein kleinstes Element geben kann.

Sei R eine Relation in M. R heißt Äquivalenzrelation genau dann, wenn

1.) R reflexiv ist,

2.) R transitiv ist und

3.) R symmetrisch ist.