Relacije Flashcards
Kaj je relacija?
Relacija je posebna vrsta množice.
Množica R je (dvomestna) relacija, če je vsak njen element urejen par.
R je relacija <=> ∀x ∈ �R ∃u, v ∶ x = (u, v)
Kako je definirano definicijsko območje?
Naj bo R relacija v A. Potem definicijsko območje Dr definiramo kot: Dr = {x; ∃y: xRy}
Kako je definirana zaloga vrednosti?
Naj bo R relacija v A. Potem zalogo vrednosti Zr definiramo kot: Zr = {y; ∃x ∶ xRy}
Pojasnite naslednje lastnosti relacij: refleksivnost, simetričnost,
antisimetričnost, tranzitivnost, enoličnost. Za vsako lastnost navedite vsaj po
en primer
Refleksivnost: i. ∀x xRx, ii. Relacija je refleksivna, če je vsak element v relaciji sam s sabo. b. Simetričnost i. ∀x∀y (xRy ⇒ yRx) ii. Relacija R je simetrična, če iz aRb sledi bRa (dvosmerna puščica) c. Antisimetrična i. ∀x∀y (xRy ⋀ yRx ⇒ x = y) ii. ne sme biti dvo smernih puščic d. tranzitivna: i. ∀x∀y∀z (xRy ⋀ yRz ⇒ xRz) e. Sovisna: i. ∀x∀y (x ≠ y ⇒ xRy ⋁ yRx) f. Enolična: i. ∀x∀y∀z (xRy ⋀ xRz ⇒ y = z) ii. Relacija R je enolična v množici A, če za vsak element a ∈ A velja, da je v relaciji R s kvečjemu enim elementom
Kako grafično predstavimo relacijo?
Za vsak par a, b, za katerega je aRb, narišemo usmerjeno povezavo od točke,
ki predstavlja a, do točke, ki predstavlja b.
Kako je definirana inverzna relacija R−1 ?
Inverzna relacija:
i. R {(y, x) | (x, y) R}**−1 = ∈
ii. dobimo jo tako, da zamenjamo koordinati v vseh parih relacije R.
(zamenjaš številke v oklepajih)
Kako je definiran produkt relacij R ∗ S?
produkt relacije:
i. xR * Sy natanko tedaj, ko ∃z(xRz in zSy) ali
ii. R ∗ S := {(x, z) ; ∃y (xRy ∧ ySz)}
Naj bo n ∈ N naravno število. Kaj je potenca R**n relacije R?
Potenca relacije R**n vsebuje relacije iz množice R , ki imajo dolžino n .
Kaj je tranzitivna ovojnica relacije?
a. Tranzitivna ovojnica je unija vseh pozitivnih potenc relacije R
b. R ⋃ R+ =∞K=1 * R**K
Kako je definirana funkcija (kateri dogovori veljajo)?
Dogovor: pišemo tudi f: A –> B
Namesto xfx pišemo y = f(x) …. Pravimo da f (pre)slika x v y
X je argument, y pa vrednost funkcije/preslikave f pri x
Kaj je ekvivalenčna relacija in kaj so ekvivalenčni razredi?
a. Ekvivalenčna relacija je relacija, ki je:
i. Refleksivna,
ii. Simetrična in
iii. Tranzitivna.
b. Ekvivalenčni razred:
i. Ekvivalenčni razred elementa a ∈ A je množica vseh tistih elementov
množice A , ki so v relaciji z a .
ii. R[a] = {x | xRa}.
Kdaj je funkcija injektivna, surjektivna, bijektivna?
Kdaj je preslikava f : A → B injektivna, kdaj je surjektivna in kdaj je bijektivna?
a. Injektivna
i. ∀x∀y (f(x) = f(y) ⇒ x = y)
ii. dva različna originala, dve različne slike. Vsak original svojo sliko
b. Surjektivna
i. Zf = B
ii. Vsaka preslikava ima svoj original
iii. Mora vsebovati vsa naravna števila. Npr. Če imamo {1,2,..,10} se
morajo originali slikati v vseh 10 števk, brez da katero izpustimo
c. Bijektivna - Ko je injektivna in surjektivna hkrati.
Kdaj je relacija f ⊆ A × B preslikava iz A v B?
a. Relacija f ⊆ A × B je preslikava iz A v B, če je
i. f enolična (injektivna) in
ii. D A , definicijsko območje je cela množica .
f = f A
b. Če je f preslikava iz A v B , potem pišemo
i. f : A → B.
Kako je definiran kompozitum g ◦ f preslikav f : A → B in g : B → C? Kaj je
njegovo definicijsko območje in kaj zaloga vrednosti?
a. Kompozitum: naj bosta f in g preslikavi.
i. g◦f = f * g
ii. Kompozitum preslikav sovpada z relacijskim produktom, v katerem
zamenjamo vrstni red faktorjev
b. Df = A
Kaj lahko o kompozitumu sklepamo iz injektivnosti/surjektivnosti preslikav f,
g
a. Izberimo poljubni preslikavi f : A → B in g : B → C
i. Če sta f in g injektivni, potem je tudi preslikava g ◦ f : A → C injektivna
ii. Če sta f in g surjektivni, potem je tudi preslikava g ◦ f : A → C surjektivna.
iii. Če sta f in g bijektivni, potem je tudi preslikava g ◦ f : A → C bijektivna.
