Relationer Flashcards
Vad är ett par?
Ett par (x,x) är en ordnad samling av två (möjliga lika) elment x och y
Vila av dess är par?
- (0,1)
- (tomma mängden, {0,3}
- (0,1)
Alla!
Vad är den kartesiska produkten? (A X A)
Låt A och B vara mängder. Den kartesiska produkten av A och B defineras som A X B = {(x,y) | x ∈A och y∈B}
Vad är den kartesiska produkten av följande mängder?
- A={0,1,2} B = {a, b} A X B?
- A = {0,1} A x A
- AxB = {(0,a), (0,b), (1,a), (1,b), (2,a), (2,b)}
2. {(0,0), (0,1), (1,0), (1,1)}
Vad är en relation?
Låt A och B vara mängder. En binär relation R på A och B är en delmängd till AxB. Dvs. R ⊆ A x B
Skriv sätt (X, Y) ∈ R skrivs R(x, y)
Vad är några relationer av följande mängder?
A = {0,1,2} B = {a,b,c}
R1 = {(0,a), (1,b), (b, C)}
R2 = {(0, a), (0,b), (0,c)}
R3 = A X B
R4 = tomma mängdenVad är identitetsrelation? (idA)
Låt A vara en mängd. Identitetsrelationen är alla relationer med A och sig själv
Vad är identitetsrelationen till följande mängd?
A = {0, 1, 2}
IdA={(0,0), (1,1), (2,2)}
Vad är relation invers? R^-1
Låt R ⊆ A X B vara en relation. Inversen R^-1 är då R^-1={(a,b)|(b,a)∉ R}
Vad är R^-1?
R = {(0,0), (0,1), (1,2),(3,1)}
R^-1= {(0,0),(1,0),(2,1),(1,3)}
Vad är reflexivitet?
En relation R ⊆ A X A är reflexiv omm (x, x) ∈ R för alla X ∈ A
Vilka relationer är reflexiva och vaför/inte?
R1 = {(0,1), (1,2), (2,3)}
R2 = {(0,1), (1,0), (2,3), (3,2)}
R3 = {(0,0), (0,1), (0,2), (0,3), (1,0), (1,1), (1,2), (1,3), (2,0), (2,1), (2,2), (2,3), (3,0), (3,1), (3,2), (3,3)}
R4 = {(0,1)}
R5 = tomma mängden
R3 är reflexiv
Vad är symmetri?
En relation R ⊆ A X A är symmetrisk omm (x, y) ∈ R för alla X ∈ A medför att (y, x) ∈ R för alla x,y ∈A
∀ X∈ A: (x,y) ∈ R –> (y,x) ∈R
Vilka relationer är symmetriska och vaför/inte?
R1 = {(0,1), (1,2), (2,3)}
R2 = {(0,1), (1,0), (2,3), (3,2)}
R3 = {(0,0), (0,1), (0,2), (0,3), (1,0), (1,1), (1,2), (1,3), (2,0), (2,1), (2,2), (2,3), (3,0), (3,1), (3,2), (3,3)}
R4 = {(0,1)}
R5 = tomma mängden
R2, R3, R5 är symmetrisk.
R5 är symmetrisk för att det inte finns några par
vad är transitiv?
En relation R ⊆ A X A är transitiv omm (x, y) ∈ R och (y, z) ∈ R medför att (y, x) ∈ R för alla x,y ∈A
För alla X∈ A: (x,y) ∈ R –> (y,z) ∈R
∀x,y: (x,y)∈R ∧ (y,z) ∈ –> (y,z) ∈ R
Vilka relationer är transitiva och vaför/inte?
R1 = {(0,1), (1,2), (2,3)}
R2 = {(0,1), (1,0), (2,3), (3,2)}
R3 = {(0,0), (0,1), (0,2), (0,3), (1,0), (1,1), (1,2), (1,3), (2,0), (2,1), (2,2), (2,3), (3,0), (3,1), (3,2), (3,3)}
R4 = {(0,1)}
R5 = tomma mängden
R3
R4 och R5 är transitiva eftersom det inte finns några x,y,z. Då gäller den första delen av implikationen.
Vad är anti-symmetri?
En relation R ⊆ A X A är anti-symmetrisk omm (x, y) ∈ R och (y, x) ∈ R medför att (y,=x)
∀x,y: (x,y)∈R ∧ (y,x) ∈ –> y = x
Vilka relationer är anti-symmetriska och vaför/inte?
R1 = {(0,1), (1,2), (2,3)}
R2 = {(0,1), (1,0), (2,3), (3,2)}
R3 = {(0,0), (0,1), (0,2), (0,3), (1,0), (1,1), (1,2), (1,3), (2,0), (2,1), (2,2), (2,3), (3,0), (3,1), (3,2), (3,3)}
R4 = {(0,1)}
R5 = tomma mängden
Inga är anti symmetriska
Vad är partialordning?
En relation R ⊆ A X A som är transitiv, reflexiv och anti-symmetrisk
Vad är en sammansättning? °
°
Låt R ⊆ A x B och s ⊆ B X C. Sammansättningen av R och S betecknas S ° R och defineras som
S ◦ R = {(x, z) ∈ A × C | ∃y ∈ B[(x, y) ∈ R ∧ (y, z) ∈ S]}
R°R d’r R = {(0,1), (1,1), (2,2)}
{(0,0), (1,0), (2,1)}
Vad är R^i?
Låt R ⊆ A x A vara en relation. Vi definerar då
R^0 = idA
R^n = R ° R^n-1 n > 0
t.ex R^4 = R ° R^3 R ° (R°R^2) osv.
Vad är det symmetriska höljet?
Det symmetriska höljet av en relation R ⊆ A x A är
R U R^-1
Vad är det symmetriska höljet till R?
R = {(0,1), (1,2), (2,2)}
R U R^-1 = {(0,0),(0,1), (1,1),(2,2),(2,3),(3,2),(3,3)}
Vad är det reflexiva höljet? R^=
Det reflexiva höljet av en relation R ⊆ A x A är R^= R U idA
Vad är det reflexiva höljet till relationen?
A = {0,1,2}
R^= {(0,0), (0,1), (1,1), (2,2)}
Vad är det transitiva höljet? R^+
Det transitiva höljet av en relation R ⊆ A x A är R^= R^1 U R^2U R^3 …. U R^i
Hur är algoritmen för att hitta det transitiva höljet av R?
- S0 = R
- Låt Sn+1 = (R ° Sn) U Sn
- Om Sn+1 = Sn, klar R^+ = Sn, annars gå till 2
Vad är en ekvivalensrelation?
En relation R ⊆ A x A som är reflexiv, symmetrisk och transitiv
Vad är en ekvivalensklass?
Låt R ⊆ A x A vara en ekvivalensrelation- För varje X ⊆ A definerar vi en ekvivalensklass [x] med avseende på R som [x] = {y ∈ A | (x,y)∈ R}
Vad är en partition?
Låt S vara en mängd och S1.. Sk icke tomma delmängder av S- Mängden P={Si … Sj} är en partition omm
Si och Sj är disjunkta om i inte är lika med j
Si U Sj U … U Sk = S
