Relationer (færdig) Flashcards
Hvad er en relation?
Vis et eksempel.
En binærrelation fra A til B er en delmængde af A x B. hvor relationen R består af ordnede par hvori det første element kommer fra A og det andet element kommer fra B.
Eksempel.
A = {1,2,3}, B= {a,b,c}
R = {(1,a),(1,b),(2,b),(2,c),(3,a)}
Den inkluderer ikke alle ordnede par fordi det er et delmængde af A x B, så det /kan/ indebære alle sættene, men det gør det ikke.
Tegn med graf (pilene)
Hvad er en aflukning?
Kaldes også en udvidelse af en relation. Hvis R er en relation på A og ikke opfylder at være refleksiv/symmetrisk/transitiv.
Så skal man finde S hvor R ⊆ S og S opfylder at være enten refleksiv/symmetrisk/transitiv.
En aflukning er altså en metode, der handler om hvilke elementer, der skal tilføjes for at S opfylder at blive enten refleksiv, symmetrisk eller transitiv.
Hvad kendetegner en transitiv aflukning?
R er en relation på mængden A.
R^n ⊆ R for n = 1,2,3…
Hvis |A| = n, så er R* = foreningsmængden af R1 U R2 U… U Rn
Eksempel:
A = {1, 2, 3, 4}
R = { (1,1), (1,2), (4,3), (3,2), (2,4) }
R^2 = {… (1,4), (2,3), (3,4), (4,2) }
R^3 = {… (1,3), (2,2), (3,3), (4,4) }
R^4 = {… ingen nye}
R* = { (1,1), (1,2), (4,3), (3,2), (2,4), (1,4), (2,3), (3,4), (4,2), (1,3), (2,2), (3,3), (4,4) }
tegn graf.
for hver potens hoppes der en gang
Hvad kendetegner en refleksiv aflukning?
R er en relation på mængden A.
T = { (a, a) | a ∈ A}
så S = R U T (foreningsmængden af R og T)
den refleksive aflukning på R.
Eksempel:
A = {1, 2, 3}
R = { (1,1), (1,2), (2,2), (2,3) }
T = { (1,1), (2,2), (3,3) }
Vi smider det vi mangler ind i relationen.
Dvs.
S = { (1,1), (1,2), (2,2), (2,3), (3,3) }
(3,3) er tilføjet
Hvad kendetegner en symmetrisk aflukning?
R er en relation på mængden A.
R^-1 = { (b, a) | (a,b) ∈ R}
så S = R U R^-1 (foreningsmængden af R og R^-1)
den symmetriske aflukning på R.
Eksempel:
A = {1, 2, 3}
R = { (1,1), (1,2), (2,2), (2,3) }
R^-1 = { (1,1), (2,1), (2,2), (3,2) }
Vi smider det vi mangler ind i relationen.
Dvs.
S = { (1,1), (1,2), (2,1), (2,2), (2,3), (3,2) }
(2,1) og (3,2) er tilføjet
Hvad er ækvivalensklasser?
Et sæt af elementer ækvivalente til et element a i A gennem ækvivalenrelationen R er kaldet ækvivalensklassen a, hvilket skrives [a]R.
Ækvivalensklasser bruges til at samle ensartede elementer.
Eksempel:
R er en ækvivalensrelation på mængden A. Mængden af alle elementer som er relateret under R med et element a ∈ A, er kaldt ækvivalensklasse af a.
Det skrives:
[a]_R = { S|( a, S) ∈ R}
(hvor R’et i [a] er nedløftet)
Eksempel:
KOM MED EKSEMPEL
Hvad er en ækvivalensrelation?
En ækvivalensrelation er en relation, der både er refleksiv, transitiv og symmetrisk.
Hvad kendetegner en refleksiv relation?
Vis et eksempel.
At a er relateret til a
Dvs. a R a
a - a = 0
a = a
Hvad kendetegner en transitiv relation?
Vis et eksempel.
Hvis a er relateret til b og b er relateret til c, så er a relateret til c.
Dvs. a R b og b R c så a R c
a R c = (a - b ) - (b - c) ∈ Z
Hvad kendetegner en symmetrisk relation?
Vis et eksempel.
At a er relateret til b.
Dvs. a R b, så b R a
Hvis a er relateret til b, så er b relateret til a.
a R b og b R a
a - b ∈ Z så b - a ∈ Z
Hvad kendetegner en antisymmetrisk relation?
Vis et eksempel.
∀ a, b ∈ A
hvis (a, b) ∈ R ∧ (b, a) ∈ R → a = b
dvs. hvis (a,b) er en relation i R, så (b,a) ikke er en relation i R medmindre de er lig hinanden
Der må ikke være forskellige elementer, hvor (a, b) og (b, a) ligger i relationen. Antisymmetrisk er IKKE det modsatte af symmetrisk.
Definer potens af relationer.
En sammensætning af relationer.
Er R en relation på A kan vi definere R ∘ R.
Mere generelt:
R^1=R
R^(n+1) = R^n ∘ R
Eksempel:
A= {1,2,3}
R= {(1,1), (1,2), (2,3)}
R^2 = {(1,1), (1,2), (1,3)}
hvor R^2 betyder at man må hoppe 2 gange
R^3 = {(1,1), (1,2), (1,3)}
hvor R^3 betyder at man må hoppe 3 gange
På et tidspunkt har man udforsket alle muligheder. F.eks. kommer der ikke et nyt par til i R^3. Derfor er R^2=R^3.
(er det det samme som en transitiv aflukning??)
Evt. tegn graf for relationen.
Hvad betyder det at når to relationer “prikker”/”boller” hinanden?
F.eks. S ∘ R
En sammensætning af relationer.
R: en relation fra A til B
S: en relation fra B til C
S ∘ R: relationen hvor (a, c) ∈ S ∘ R
hvis og kun hvis der er et b ∈ B, så (a, b) ∈ R og (b, c) ∈ S.
evt. tegn graf for relationen
Hvad er modulo?
Vis et eksempel.
a ∈ Z og d ∈ Z+
der findes entydige (der findes altså ikke andre) heltal q og r, hvor 0 ≤ r < d, sådan at a = d*q + r
Eksempel:
a = 10, d = 3
dvs. 10 = 3 * 3 + 1, hvor første 3-tal er d og 1 er r
10 mod 3 = 1 (dvs. r)
a = 12, d = 3
dvs. 12 = 3 * 4 + 0, hvor 3 er d og 0 er r
12 mod 3 = 0 (dvs. r)
