Ayrık Matematik - İlişkiler
Ne zaman setler tartışılırsa, setlerin unsurları arasındaki ilişki ortaya çıkan bir sonraki şeydir. Relations aynı kümedeki nesneler arasında veya iki veya daha fazla kümenin nesneleri arasında var olabilir.
Tanım ve Özellikler
Set x'ten y'ye ikili ilişki R ($ xRy $ veya $ R (x, y) $ olarak yazılır), Kartezyen çarpımı $ x \ times y $'ın bir alt kümesidir. Sıralı G çifti tersine çevrilirse, ilişki de değişir.
Genellikle $ A_1, \ dots, \ ve \ A_n $ kümeleri arasındaki n-ary ilişkisi R, $ A_1 \ times \ dots \ times A_n $ n-ary ürününün bir alt kümesidir. Bu durumda bir R ilişkisinin minimum kardinalitesi Sıfır ve maksimum $ n ^ 2 $ 'dır.
Tek bir A kümesindeki ikili ilişki R, $ A \ times A $ 'nın bir alt kümesidir.
Sırasıyla m ve n kardinalitelerine sahip iki ayrı küme için, A ve B, A'dan B'ye bir R ilişkisinin maksimum kardinalitesi mn'dir .
Etki Alanı ve Aralık
İki A ve B kümesi varsa ve R ilişkisi sıra çiftine (x, y) sahipse, o zaman -
domainof R, Dom (R), $ \ lbrace x \: | kümesidir. \: (x, y) \ in R \: for \: bazı \: y \: in \: B \ rbrace $
range of R, Ran (R), R \: için \: bazı \: x \: \: A \ rbrace $ için $ \ lbrace y \: | \: (x, y) \ kümesidir
Örnekler
$ A = \ lbrace 1, 2, 9 \ rbrace $ ve $ B = \ lbrace 1, 3, 7 \ rbrace $ olsun
Durum 1 - R ilişkisi 'eşitse' $ R = \ lbrace (1, 1), (3, 3) \ rbrace $
Dom (R) = $ \ lbrace 1, 3 \ rbrace, Ran (R) = \ lbrace 1, 3 \ rbrace $
Durum 2 - R ilişkisi 'küçüktür' ise $ R = \ lbrace (1, 3), (1, 7), (2, 3), (2, 7) \ rbrace $
Dom (R) = $ \ lbrace 1, 2 \ rbrace, Ran (R) = \ lbrace 3, 7 \ rbrace $
Durum 3 - R ilişkisi 'büyükse' $ R = \ lbrace (2, 1), (9, 1), (9, 3), (9, 7) \ rbrace $
Dom (R) = $ \ lbrace 2, 9 \ rbrace, Ran (R) = \ lbrace 1, 3, 7 \ rbrace $
İlişkilerin Grafik Kullanılarak Gösterimi
Bir ilişki, yönlendirilmiş bir grafik kullanılarak temsil edilebilir.
Grafikteki köşe sayısı, ilişkinin tanımlandığı kümedeki öğe sayısına eşittir. R ilişkisindeki her bir sıralı çift (x, y) için, 'x' tepe noktasından 'y' tepe noktasına yönlendirilmiş bir kenar olacaktır. Sıralı bir çift (x, x) varsa, 'x' tepe noktasında kendi kendine döngü olacaktır.
Diyelim ki, $ S = \ lbrace 1, 2, 3 \ rbrace $ setinde $ R = \ lbrace (1, 1), (1,2), (3, 2) \ rbrace $ ilişkisi var, bu aşağıdaki grafikte gösterilmektedir -
İlişki Türleri
Empty Relation X ve Y kümeleri arasında veya E üzerinde, boş küme $ \ emptyset $
Full Relation X ve Y kümeleri arasında $ X \ times Y $
Identity Relationsette X, $ \ lbrace (x, x) | x \ içinde X \ rbrace $
Bir R ilişkisinin Ters İlişki R '- $ R' = \ lbrace (b, a) | (a, b) \ R \ rbrace $ içinde
Example - $ R = \ lbrace (1, 2), (2, 3) \ rbrace $ ise $ R '$ $ \ lbrace (2, 1), (3, 2) \ rbrace $ olacaktır
A kümesinde bir R ilişkisi denir Reflexive A $ 'daki $ \ forall a \ a ile ilişkiliyse (aRa tutmalar)
Example - $ X = \ lbrace a, b \ rbrace $ kümesindeki $ R = \ lbrace (a, a), (b, b) \ rbrace $ ilişkisi dönüşlüdür.
A kümesinde bir R ilişkisi denir Irreflexive A $ içindeki hiçbir $ a \ a ile ilişkili değilse (aRa tutmaz).
Example - $ X = \ lbrace a, b \ rbrace $ kümesindeki $ R = \ lbrace (a, b), (b, a) \ rbrace $ ilişkisi yansıtmasızdır.
A kümesinde bir R ilişkisi denir Symmetric $ xRy $, $ yRx $ anlamına geliyorsa, A $ için $ \ forall x \ ve A $ için $ \ forall y \.
Example - $ A = \ lbrace 1, 2, 3 \ rbrace $ kümesindeki $ R = \ lbrace (1, 2), (2, 1), (3, 2), (2, 3) \ rbrace $ ilişkisi simetrik.
A kümesinde bir R ilişkisi denir Anti-Symmetric $ xRy $ ve $ yRx $, A $ için $ x = y \: \ forall x \ ve A $ için $ \ forall y \ anlamına gelir.
Example - $ R = \ lbrace (x, y) \ ile N | \: x \ leq y \ rbrace $ ilişkisi anti-simetriktir çünkü $ x \ leq y $ ve $ y \ leq x $ $ x = y $ anlamına gelir .
A kümesinde bir R ilişkisi denir Transitive $ xRy $ ve $ yRz $, $ xRz, \ forall x, y, z \ anlamına gelirse, A $.
Example - $ A = \ lbrace 1, 2, 3 \ rbrace $ kümesindeki $ R = \ lbrace (1, 2), (2, 3), (1, 3) \ rbrace $ ilişkisi geçişlidir.
Bir ilişki bir Equivalence Relation dönüşlü, simetrik ve geçişli ise.
Example - $ R = \ lbrace (1, 1), (2, 2), (3, 3), (1, 2), (2,1), (2,3), (3,2) ilişkisi, $ A = \ lbrace 1, 2, 3 \ rbrace $ kümesindeki (1,3), (3,1) \ rbrace $, dönüşlü, simetrik ve geçişli olduğu için bir eşdeğerlik ilişkisidir.