Diskrete Strukturen - 3. Kapitel - Relationen
32 flashcards · Mathematics · by Pepper and Love
Die Teile einer Paares stehen in einer Beziehung zueinander ( z.B. [Berlin, Deutschland] - die Beziehung ist "ist Hauptstadt von"). Wir können die Beziehungen einzeln betrachten oder die Menge dieser Beziehungen als Struktur. Die Struktur wird dan Relation genannt.
Relationen sind ein mathematisches Hilfsmittel, um Beziehungen zwischen einzelnen Objekten zu beschreiben. die Mengen können verschieden sein, oder identisch oder die gleiche Menge, wo die eigenen Elemente miteinander verglichen werden um die nach spezifischen Eigenschaften zu gruppieren (Grade zahlen, Primzahlen...)
Eine Relation ist ...
Eine Relation R zwischen den Mengen A und B ist eine Teilmenge des kartesischen Produktes A × B, also R ⊆ A × B. Fur (a , b) ∈ R sagt man: ” a steht in Relation R zu b“. Oft schreibt man auch aRb statt (a , b) ∈ R Im Spezialfall A = B, also von Relationen R ⊆ A × A, spricht man von einer Relation in A oder einer Relation auf A. A = {Wien , Bonn , Dresden}B = {A,D,CH}A x B = R1 = {(Wien , A), (Bonn , D), ( Dresden , D)}
Eine 2-stellige Relation nennt man → binäre Relation.
Was ist eine reflexive Relation ?
für alle x ∈ M gilt: (x , x) ∈ R Eine reflexive Relation enthält also alle Paare (a, a) ∈ A × A, oder kurz: IAI_AIA ⊆ R , wobei IAI_AIA = (a, a)| a ∈ A die Identitätsrelation bezeichnet. IM ⊆ R Grafisch: hat an jeden Knoten eine Schlinge ( jedes Element steht mit sich in Relation )
Was ist eine irreflexive Relation ?
für alle x ∈ M gilt; (x , x) ∉\not∈∈ R Grafisch: Wenn es keine Schlingen gibt
Was ist eine symmetrische Relation ?
für alle x , y ∈ M gilt: (x , y) ∈ R ⇒ (y , x) ∈ R R-1 = R charakterisiert werden Grafisch: wenn für je zwei Knoten x und y gilt: → es gibt eine Kante von x nach y, so auch eine von y nach x
Was ist eine antisymmetrische Relation ?
für alle x , y ∈ M gilt: (x , y) ∈ R ∧\land∧ ( y , x) ∈ R ∈ x = y R−1 ∩ R ⊆ IM ( IM sind die reflexiven Elemente) Grafisch: kann es zwischen zwei verschiedenen Knoten höchstens einen Pfeil geben( darf nicht symmetrisch sein) (Schlingen können vorkommen).
Was ist eine asymmetrische Relation ?
für alle x , y ∈ M gilt: (x , y) ∈ R ⇒ (y , x) ∉\not∈∈ R R−1 ∩ R = { } Grafisch: kann es zwischen zwei verschiedenen Knoten höchstens einen Pfeil geben und Schlingen sind nicht zugelassen
Was ist eine transitive Relation ?
für alle x , y , z, ∈ M gilt; (x, y) ∈ R ∧\land∧ (y, z) ∈ R ⇒ (x, z) ∈ R R ◦ R ⊆ R Grafisch: Wenn ein Pfeil von a nach b geht und einer von b nach c, so gibt es auch einen von a nach c R ◦ R ist eine VerkettungEs muss nicht jeder Knoten transitiv sein, aber wenn 3 knoten miteinander verbunden sind aber keine Transitivität da ist da eine Kante fehlt - kann die Relation nicht transitiv seinDie Implikation (x, y) ∈R ∧ (y, z) ∈ R → (x, z) ∈ R ist für x = y und auch für y = z immer wahr. Deshalb bra…
Ist diese Relation transitiv, reflexiv oder irreflexiv, symmetrisch, antisymmetrisch, und asymmetrisch ?
Nicht transitiv, da wir (v, y),(y, z) haben aber nicht (v, z) nicht reflexiv und irreflexivnicht symmetrisch antisymmetrisch und asymmetrisch ( da keine schlingen und keine Symmetrie)
Wann müssen wir nach einer Eigenschaft der Relation nicht prüfen ?
Wenn zwei Knoten nicht verbunden sind, dann prüfen wir nicht auf Symmetrie, Asymmetrie und Antisymmetrie Wenn drei knoten x ,y, z ∈ M keine gemeinsame Verbindung haben (x, y) ∈ R und (y, z) ∈ R dan prüfen wir auf keine Transitivität eine leere Relation is sowohl symmetrisch als auch antisymmetrisch, asymmetrisch und transitiv Die Implikation (x, y) ∈ R ∧\land∧ (y, z) ∈ R → \to→ (x, z) ∈ R ist für x = y und auch für y = z immer wahr. Deshalb braucht man zum Nachprüfen der Transitivität einer Rel…
Was ist eine Inverse Relation ( Umkehrrelation ) ?
Es sei R ⊆ A × B eine Relation. Dann heißt die Relation R−1 = {(b, a) | (a, b) ∈ R} ⊆ B × A die zu R inverse Relation (oder Umkehrrelation). R2= {(1, (3, 4)), (1, (5, 6)), (2, (3, 4)), (2, (5, 6))} R 2−1 = {((3, 4), 1), ((5, 6), 1), ((3, 4), 2), ((5, 6), 2)}
Was ist eine Komposition ( Verkettung ) von Relationen ?
Es seien M1, M2 und M3 Mengen und R1 ⊆ M1 × M2 sowie R2 ⊆ M2 × M3 binäre Relationen. Dann heißt die Relation R2 ◦ R1 = {(x, y) | es gibt ein z ∈ M2 mit (x, z) ∈ R1 und (z, y) ∈ R2} die Komposition (oder Verkettung / Verknüpfung) von R1 und R2. (R2 ◦ R1 wird oft gesprochen als R2 “Kreis” R1) S ◦ R ist von rechts nach links zu lesen! S ◦ R meint also ”erst R, dann S“! R = {(1, a),(2, b),(3, c)}S = {(a, x),(a, y),(b, z)}S ◦ R = {[1,x], [1,y],[2,z]}Da es von rechts nach lings gelesen wird, schauen…
Die Verknüpfung von Relationen ist assoziativ, d.h., es gilt (R3 ◦ R2) ◦ R1 = R3 ◦ (R2 ◦ R1). Das bedeutet, dass die Klammern weggelassen werden können. Achtung: Die Verknüpfung ist nicht kommutativ, d.h., im Allgemeinen ist R1 ◦ R2 ≠\not== R2 ◦ R1!
Für SoR ist RoS eine Umkehrrelation - und stellt nur die Wichtigkeit da wie die Tupel geschrieben werden da es die Relation/Beziehung verändert (x , y) ist nicht immer gleicht (y ,x).
Was ist eine reflexive Hülle ?
Reflexive Hülle [R]refl von R versteht man die ( bezügliche der Mengeninklusion) kleinste Relation S ⊆ M × M, die reflexiv ist und R enthält (d.h., S ⊇ R). [R] refl = R ∪ IA Bildung der reflexiven Hülle bedeutet, dass jeder Knoten eine Schlinge bekommt (falls nicht bereits vorhanden)Gegeben ist die Relation R auf Menge AA = {a, b, c, d, e}R = {(a, b),(b, c),(c, d),(d, e)}Um zur reflexiven Hülle zu gelangen, sind alle noch nicht in R vorkommenden Paare mit gleichen Komponenten hinzuzufügen: [R]…
Was ist eine symmetrische Hülle ?
Symmetrische Hülle [R]sym von R versteht man die kleinste Relation S ⊆ M × M , die symmetrisch ist und R enthält. [R] sym = R ∪ R−1 Bildung einer symmetrische Hülle bedeutet dass jeder Pfeil durch einen zweiten Pfeil in die entgegengesetzte Richtung ergänzt wird (sofern er nicht ohnehin schon da ist)M = {a, b, c, d} R = {(a, a), (a, b), (a, c), (a, d), (b, a), (c, b)}Die symmetrische Hülle erhält man durch Hinzufügen aller nicht in R vorkommenden Paare (y, x), für die aber (x, y) bereits in R l…
Was ist eine transitive Hülle ?
Transitive Hülle [R]trans von R versteht man die kleinste Relation S ⊆ M×M, die transitiv ist und R enthält. Ist R eine binäre Relation auf einer n-elementaren Menge M, so gilt mit Rk = R ◦ R ◦ . . . ◦ R. [R] (t) = R ∪ R 1 ∪ . . . ∪ R n . Gegeben ist die Relation R = {(a, a), (a, b), (a, c), (a, d), (b, a), (c, b)}Die transitive Hülle kann auf folgende Weise bestimmt werden: Um alle “fehlenden” Paare zu ergänzen, sind zunächst die Paare (b, b), (b, c), (b, d) und (c, a) hinzuzufügen. Durch Hinz…
Was ist eine Äquivalenzrelation ?
Eine Relation R auf einer Menge A heißt Äquivalenzrelation, wenn sie reflexiv, symmetrisch und transitiv ist. Für (a ,b) ∈ R sagt man auch: "a ist äquivalent zu b". ist R eine Äquivalenzrelation, so schreibt man anstelle von (x ,y) ∈ R meistens x ∼ y und nennt x und y äquivalent (bezüglich R). Reflexivität: ∀x ∈ R : x =∼ xSymmetrie: ∀x ,y ∈ R : x =∼ y ⇒ y =∼ xTransitivität: ∀x ,y ,z ∈ R : x =∼ y ∧ y =∼ z ⇒ x =∼ z
Ist R = {(1, 1), (1,-1), (-1, 1), (-1,-1), (2, 2), (2,-2), (-2, 2), (-2,-2)} eine Äquivalenzrelation auf A = {-2,-1, 1, 2}, und warum ?
Ja, denn: • (a, a) ∈ R für alle a (Reflexivität); ( z.B. ( -1,-1) • (a, b) ∈ R ist auch (b, a) ∈ R (Symmetrie); (1,-1) und (-1,1) • (a, b) ∈ R und (b, c) ∈ ist auch (a, c) ∈ (Transitivität).( 1,1) (1,-1)(-1,1) In Worten: “a und b haben denselben Betrag”. Zwei Zahlen sind hier also äquivalent, wenn sie denselben Betrag haben.
Ist die Relation mit (a, b) ∈ R wenn a in der gleichen Gehaltsstufe wie b ist eine Äquivalenzrelation auf der Menge aller Miterbeiter einer Firma ?
Ja weil: Jeder ist in der gleichen Gehaltsstufe wie er selbst: (a, a) ∈ R ( Reflexivität); Wenn a gleich b ist. dan ist auch b gleich a: (a, b) ∈ R und (b, a) ∈ R ( Symmetrie); Wenn a und b gleich sind, und b auf der gleichen Gehaltsstufe ist wie c, dann ist auch a auf der gleichen Gehaltsstufe wie c: (a, b) ∈ R, (b, c) ∈ R, (a, c) ∈ R (Transitivität);
Ist die Relation (a, b) ∈ R, wenn a in einem gleichen Projekt arbeitet wie b, eine Äquivalenzrelation auf der Menge aller Miterbeiter einer Firma ?
Nein weil, obwohl a und b zusammen arbeiten, am gleichen Projekt, kann es sein das b in noch anderen Projekten arbeitet in denen a nicht mitarbeitet, so haben wie keine Transitivität. (a, b) ∈ R, (b, c) ∈ R aber nicht (a, c) ∈ R
Was ist eine Äquivalenzklasse ?
Unterteilt eine Menge A in Klassen von Äquivalenzrelationen: Wenn R eine Äquivalenzrelation auf A ist und a ∈ A. Dann heißt die Menge [a] = {x ∈ A |(a, x) ∈ R} die Äquivalenzklasse von a. Sie besteht also aus allen Elementen, die äquivalent zu a sind (und je zwei Elemente aus [a] sind auch äquivalent zueinander aRx / a ∼ x ) Man nennt a und jedes andere Element aus [a] einen Vertreter aus dieser Äquivalenzklasse. Je zwei verschiedene Äquivalenzklassen sind disjunkt Die Vereinigung aller Äquival…
Ist "a ist gleich alt wie b" in einer Menge von Personen eine Äquivalenzrelation ?
Ja, denn: jeder ist in dem gleichen Alter wie er selbst (Reflexiv) wenn a gleicht alt ist wie b, dan ist b gleich alt wie a ( Symmetrisch) wenn a gleich b ist und b gleich c ist dan ist auch a gleich c" (Transivität)
Was wären Äquivalenzklassen in der Äquivalenzrelation R = {(1, 1), (1,-1), (-1, 1), (-1,-1), (2, 2), (2,-2), (-2, 2), (-2,-2)} der Menge A = {-2,-1, 1, 2}, und warum ?
Das sind: [1] = {-1,1} [2] = {-2,2} Müssen disjunkt sein - keine gemeinsamen Elemente haben.Deren Vereinigung ist gleich A.
Mitarbeiter A, B, C, D, E, F einer Firma: A und C sind in Gehaltsstufe 1; bildet an sich eine Äquivalenzrelation in der Menge der Mitarbeiter B, D und E sind in Gehaltsstufe 2; F ist in Gehaltsstufe 3; Geben Sie die Äquivalenzklassen an:
Die Äquivalenzenklassen sind die drei Gehaltsstufen: K1 = { A,C} ... Gehaltsstufe 1 K2 = {B,D,E} ... Gehaltsstufe 2 K3 = {F} ... Gehaltsstufe 3 Die Beziehung a = b (mod m) ist eine Äquivalenzrelation auf Z. Die Restklassen sind nichts anderes als die zugehörigen Äquivalenzklassen.
Was ist eine Ordnungsrelation ?
Eine Relation R in einer Menge A heißt Ordnungsrelation, wenn sie reflexiv, antisymmetrisch und transitiv ist. Ist R eine Ordnungsrelation auf M, so nennt man (M,R) eine geordnete Menge und schreibt anstelle von (x, y) ∈ R auch x ⪯ y. Ist x ⪯ y und x ≠\not == y so nennt man x auch Vorgänger von y. Ist x Vorgänger von y und gibt es kein z ∈ M mit z ≠\not= = x, y, x ⪯ z und z ⪯ y, so heißt x unmittelbarer Vorgänger von y.
Ein typisches Beispiel einer Ordnungsrelation ?
Eine typische Ordnung ist die Relation ≤ in den natürlichen Zahlen. Denn diese Relation ist reflexiv (a ≤ a), antisymmetrisch (wenn a ≤ b und b ≤ a, dann muss a = b sein) und transitiv (wenn a ≤ b und b ≤ c, dann ist a ≤ c). Das ist das Paradebeispiel fur eine Ordnung, daher verwendet man oft auch für andere Ordnungsrelationen R die Schreibweise a ≤ b statt (a, b) ∈ R.
Was ist eine totale Ordnungsrelation ?
Eine Ordnungsrelation auf einer Menge M heißt totale Ordnungsrelation, wenn für je zwei Elemente x, y ∈ M gilt: x ⪯ y oder y ⪯ x. Total heißt also, dass – welche Elemente man auch immer aus M herausgreift – diese immer bezüglich R in Beziehung zueinander stehen. Entweder (a, b) ∈ R oder (b, a) ∈ R. Der Begriff ” total“ bzw. ” partiell“ kann auch analog fur eine strikte Ordnung verwendet werden. a ≤ b ist eine totale Ordnung in den natürlichen Zahlen, denn für zwei Zahlen a, b ∈ N ist immer a ≤…
Was ist eine geordnete Menge ?
Eine Menge M zusammen mit einer totalen Ordnungsrelation auf M heißt linear geordnete Menge oder auch Kette.
Wieso ist die Relation “ ≤ " eine Ordnungsrelation auf R ( und auch auf jeder Teilmenge von R) ?
Was sind Hasse Diagramme ?
Diagraphen durch denen eine binäre Ordnungsrelation auf einen endlichen Menge M dargestellt werden.
Gesucht ist eine Relation aus der Menge M = {1, 2 ,3 ,4}, die reflexiv, symmetrisch aber nicht transitiv ist.
R={(1,1),(2,2),(3,3),(4,4)} die wäre reflexiv, symmetrisch, aber auch transitiv. R={(1,1),(2,2),(3,3),(4,4),(1,2),(2,1), (2,3),(3,2),(2,4),(4,2) } Das ist nicht transitiv, da " (3,2),(2,4) ∈ R ==> (3,4) ∈ R nicht gilt."