Diskrete Mathematik - Beziehungen
Wann immer Mengen diskutiert werden, ist die Beziehung zwischen den Elementen der Mengen das nächste, was auftaucht. Relations kann zwischen Objekten derselben Menge oder zwischen Objekten von zwei oder mehr Mengen existieren.
Definition und Eigenschaften
Eine binäre Beziehung R von der Menge x zu y (geschrieben als $ xRy $ oder $ R (x, y) $) ist eine Teilmenge des kartesischen Produkts $ x \ times y $. Wenn das geordnete Paar von G umgekehrt wird, ändert sich auch die Beziehung.
Im Allgemeinen ist eine n-fache Beziehung R zwischen den Mengen $ A_1, \ dots, \ und \ A_n $ eine Teilmenge des n-fachen Produkts $ A_1 \ times \ dots \ times A_n $. Die minimale Kardinalität einer Beziehung R ist Null und das Maximum ist in diesem Fall $ n ^ 2 $.
Eine binäre Beziehung R auf einer einzelnen Menge A ist eine Teilmenge von $ A \ mal A $.
Für zwei unterschiedliche Mengen A und B mit den Kardinalitäten m bzw. n beträgt die maximale Kardinalität einer Beziehung R von A nach B mn .
Domäne und Reichweite
Wenn es zwei Mengen A und B gibt und die Beziehung R ein Ordnungspaar (x, y) hat, dann -
Das domainvon R ist Dom (R) die Menge $ \ lbrace x \: | \: (x, y) \ in R \: für \: einige \: y \: in \: B \ rbrace $
Das range von R ist Ran (R) die Menge $ \ lbrace y \: | \: (x, y) \ in R \: für \: some \: x \: in \: A \ rbrace $
Beispiele
Sei $ A = \ lbrace 1, 2, 9 \ rbrace $ und $ B = \ lbrace 1, 3, 7 \ rbrace $
Fall 1 - Wenn die Beziehung R 'gleich' ist, dann ist $ R = \ lbrace (1, 1), (3, 3) \ rbrace $
Dom (R) = $ \ lbrace 1, 3 \ rbrace, Ran (R) = \ lbrace 1, 3 \ rbrace $
Fall 2 - Wenn die Beziehung R 'kleiner als' ist, dann ist $ R = \ lbrace (1, 3), (1, 7), (2, 3), (2, 7) \ rbrace $
Dom (R) = $ \ lbrace 1, 2 \ rbrace, Ran (R) = \ lbrace 3, 7 \ rbrace $
Fall 3 - Wenn die Beziehung R 'größer als' ist, dann ist $ R = \ lbrace (2, 1), (9, 1), (9, 3), (9, 7) \ rbrace $
Dom (R) = $ \ lbrace 2, 9 \ rbrace, Ran (R) = \ lbrace 1, 3, 7 \ rbrace $
Darstellung von Beziehungen mit Graph
Eine Beziehung kann mithilfe eines gerichteten Graphen dargestellt werden.
Die Anzahl der Eckpunkte im Diagramm entspricht der Anzahl der Elemente in der Menge, aus denen die Beziehung definiert wurde. Für jedes geordnete Paar (x, y) in der Beziehung R gibt es eine gerichtete Kante vom Scheitelpunkt 'x' zum Scheitelpunkt 'y'. Wenn es ein geordnetes Paar (x, x) gibt, gibt es eine Selbstschleife am Scheitelpunkt 'x'.
Angenommen, es gibt eine Beziehung $ R = \ lbrace (1, 1), (1,2), (3, 2) \ rbrace $ auf der Menge $ S = \ lbrace 1, 2, 3 \ rbrace $, die es sein kann dargestellt durch die folgende Grafik -
Arten von Beziehungen
Das Empty Relation zwischen den Mengen X und Y oder auf E befindet sich die leere Menge $ \ Emptyset $
Das Full Relation zwischen den Mengen X und Y ist die Menge $ X \ mal Y $
Das Identity Relationauf Menge X ist die Menge $ \ lbrace (x, x) | x \ in X \ rbrace $
Die inverse Beziehung R 'einer Beziehung R ist definiert als - $ R' = \ lbrace (b, a) | (a, b) \ in R \ rbrace $
Example - Wenn $ R = \ lbrace (1, 2), (2, 3) \ rbrace $, dann ist $ R '$ $ \ lbrace (2, 1), (3, 2) \ rbrace $
Eine Beziehung R auf Satz A wird aufgerufen Reflexive wenn $ \ forall a \ in A $ mit a zusammenhängt (aRa gilt)
Example - Die Beziehung $ R = \ lbrace (a, a), (b, b) \ rbrace $ am Satz $ X = \ lbrace a, b \ rbrace $ ist reflexiv.
Eine Beziehung R auf Satz A wird aufgerufen Irreflexive wenn kein $ a \ in A $ mit a zusammenhängt (aRa gilt nicht).
Example - Die Beziehung $ R = \ lbrace (a, b), (b, a) \ rbrace $ am Satz $ X = \ lbrace a, b \ rbrace $ ist irreflexiv.
Eine Beziehung R auf Satz A wird aufgerufen Symmetric Wenn $ xRy $ $ yRx $ impliziert, $ \ forall x \ in A $ und $ \ forall y \ in A $.
Example - Die Beziehung $ R = \ lbrace (1, 2), (2, 1), (3, 2), (2, 3) \ rbrace $ am Satz $ A = \ lbrace 1, 2, 3 \ rbrace $ ist symmetrisch.
Eine Beziehung R auf Satz A wird aufgerufen Anti-Symmetric wenn $ xRy $ und $ yRx $ $ x = y \: \ forall x \ in A $ und $ \ forall y \ in A $ implizieren.
Example - Die Beziehung $ R = \ lbrace (x, y) \ zu N | \: x \ leq y \ rbrace $ ist antisymmetrisch, da $ x \ leq y $ und $ y \ leq x $ $ x = y $ implizieren .
Eine Beziehung R auf Satz A wird aufgerufen Transitive Wenn $ xRy $ und $ yRz $ $ xRz implizieren, \ forall x, y, z \ in A $.
Example - Die Beziehung $ R = \ lbrace (1, 2), (2, 3), (1, 3) \ rbrace $ am Satz $ A = \ lbrace 1, 2, 3 \ rbrace $ ist transitiv.
Eine Beziehung ist eine Equivalence Relation wenn es reflexiv, symmetrisch und transitiv ist.
Example - Die Beziehung $ R = \ lbrace (1, 1), (2, 2), (3, 3), (1, 2), (2,1), (2,3), (3,2), (1,3), (3,1) \ rbrace $ on set $ A = \ lbrace 1, 2, 3 \ rbrace $ ist eine Äquivalenzbeziehung, da sie reflexiv, symmetrisch und transitiv ist.