To tylko jedna z 5 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
1.2. Relacje
Określenie relacji:
Relacja R jest zbiorem par uporządkowanych, czyli podzbiorem iloczynu kartezjańskiego dwóch
zbiorów: A (dziedzina relacji) i B (przeciwdziedzina relacji)
R ⊆ A×B
Zamiast pisać (a, b)∈ R piszemy często aRb. Jeśli dziedzina i przeciwdziedzina relacji są tym
samym zbiorem (A=B), to mówimy o relacji określonej na zbiorze A.
R ⊆ A×A
Własności relacji:
Mówimy, że relacja R na zbiorze A jest:
─ zwrotna, jeśli (∀a∈A) (aRa)
─ przeciwzwrotna, jeśli (∀a∈A) (¬(aRa))
─ przechodnia, jeśli (aRb ∧ bRc) ⇒ aRc
─ symetryczna, jeśli aRb ⇒ bRa
─ przeciwsymetryczna, jeśli aRb ⇒ ¬(bRa)
─ antysymetryczna, jeśli (aRb ∧ bRa) ⇒ a=b
Relacje równoważności:
Relację R na zbiorze A nazywamy relacją równoważności, gdy R jest:
─ zwrotna,
─ symetryczna,
─ przechodnia.
Relacja równoważności dzieli zbiór A na klasy równoważności (klasy abstrakcji). Przez [a] R
oznaczamy klasę równoważności relacji R o reprezentancie a.
[a]R = { b | b∈A ∧ aRb }
(∀a,b∈A) ( [a]R = [b]R ∨ [a]R ∩ [b]R = Ø )
[a]R = A
a∈A
Relacje porządkujące:
Relacją częściowego porządku na zbiorze A nazywamy relację R, która jest:
─ zwrotna,
─ przechodnia,
─ antysymetryczna.
Przykładem relacji częściowego porządku może być relacja zawierania się zbiorów (⊆) określona
na zbiorze potęgowym.
Relacją liniowego porządku na zbiorze A nazywamy relację R, która posiada następujące
własności:
─ jest relację częściowego porządku, tzn. jest zwrotna, przechodnia i antysymetryczna,
─ spełnia warunek spójności:
(∀a,b∈A) ( aRb ∨ bRa )
Przykładem relacji liniowego porządku jest relacja „mniejszy lub równy” (≤) określona na zbiorze
nieujemnych liczb całkowitych.
Domknięcia relacji:
k-ty stopień Rk relacji R na zbiorze A określamy nastepująco:
aRob ⇔ a=b
aR1b ⇔ aRb
........................
aRkb ⇔ (∃c∈A) (aRc ∧ cRk-1b)
czyli np.
aR2b ⇔ (∃c∈A) (aRc ∧ cRb)
aR3b ⇔ (∃c1∈A) (aRc1 ∧ cR2b) ⇔ (∃c1,c2∈A) (aRc1 ∧ c1Rc2 ∧ c2Rb)
Przykład:
R ⊆ N×N
N = {0, 1, 2, ...} – zbiór liczb naturalnych (z zerem)
nRm ⇔ n = m+2
nR2m ⇔ n = p+2 ∧ p = m+2 ⇔ n = m+4
nR3m ⇔ n = p1+2 ∧ p1 = p2+2 ∧ p2 = m+2 ⇔ n = m+6
(8, 6) ∈ R
(8, 4) ∈ R2
(8, 2) ∈ R3
Przechodnie domknięcie R+ relacji R na zbiorze A definiujemy następująco:
aR+b ⇔ (∃i≥1) ( aRib )
Przechodnie i zwrotne domknięcie R* relacji R na zbiorze A definiujemy następująco:
aR*b ⇔ (∃i≥0) ( aRib )
Inna (rekurencyjna) definicja domknięcia przechodniego R+
(1) aRb ⇒ aR+b
(2) (aR+b ∧ bR+c) ⇒ aR+c
(3) nic innego nie należy do R+ poza tym, co wynika z punktów (1) i (2).
Niektóre użyteczne zależności:
aR*b ⇔ aR+b ∨ a=b
R * = R+ ∪ R o
R+ = Ri
i≥1
R* = Ri
i≥0
Przechodnie domknięcie R+k relacji R stopnia k na zbiorze A definiujemy następująco:
aR+kb ⇔ ( ∃ 1≤ i≤ k ) ( aRib )
Przechodnie i zwrotne domknięcie R*k relacji R stopnia k na zbiorze A definiujemy następująco:
aR*kb ⇔ ( ∃ 0≤i≤k ) ( aRib )
Niektóre użyteczne zależności:
R+k = R1 ∪ R2 ∪ ... ∪ Rk = Ri
1≤i≤k
R*k = Ro ∪ R1 ∪ ... ∪ Rk = Ri
0≤i≤k
Twierdzenie:
Niech n = #A, n
... zobacz całą notatkę
Komentarze użytkowników (0)