Relacije

Pozdravljeni, mi kdo po "kmečko" pove kaj je tranzitivna ovojnica relacije in tranzitivno-refleksivna ovojnica relacije (R+,R*)
Potem pa še ena naloga:


kako relacijo sploh opisat in ni mi jasno kako na tak način pokazat ali je refleksivna itd..
(Prebral sem skripto od raste škrekovskega, pa mi je po prebrani skripti vse še manj jasno, kot mi je bilo pred tem ko sem karkoli začel delat :D ..)
Mogoče kak nasvet, kako se naj interpretiram relacije ali pa kako naj začnem, karkoli ? Hvala že vnaprej

S ful besedami sem povedala in na dolgo, ampak upam da "po kmečko" in da je razumljivo :)


Relacijo lahko predstaviš s podmnožico kartezičnega produkta. Recimo da imaš relacijo < na množici {1, 2, 3}.
Kartezični produkt je {(1, 1), (1, 2), (2, 1), (2, 2)...(3, 3)}; vsi možni pari.
Relacija < je {(1, 2), (1, 3), (2, 3)}.

Relacijo vedno gledaš na elementih neke podane množice, ker je različno od množice do množice. Za relacijo lahko ugotavljamo ali ima kakšno lastnost (npr. refleksivnost, tranzitivnost, simetričnost...). Katero lastnost najdemo je odvisno od relacije in od množice. (Recimo relacija "je deljiv" ni simetrična v množici {1, 2, 3} je pa v množici {1}.)


Recimo, da imamo eno relacijo na eni množici, ki ni tranzitivna. Radi bi pa, da je (ne vem zakaj, i guess da zato, ker potem velja en kup fajn lastnosti). Zato skonstruiramo "tranzitivno ovojnico (stare) relacije". To pomeni da poskusimo najti novo relacijo. Ta relacija mora biti taka, da velja za vse pare, za katere je veljala stara relacija. In mora biti taka, da je najmanjša od vseh, ki jih lahko najdemo.

Primer: Recimo da imamo množico {Babica, Mama, Hči} in relacijo "je mama". V tej relaciji imamo {(Babica, Mama), (Mama, Hči)}. Ta relacija ni tranzitivna, ker nam manjka {(Babica, Hči)}. Na tej množici si lahko zmislimo novo relacijo "je prednik". V tej relaciji imamo {(Babica, Mama), (Mama, Hči), (Babica, Hči)}. Ta relacija je tranzitivna. Vsebuje vse pare iz prejšnje relacije. Je najmanjša. (Obstajajo postopki, kako konstruiramo ovojnice oziroma preverimo da so najmanjše.) Zato je "je prednik" tranzitivna ovojnica relacije "je mama" na dani množici.

Recimo na tej množici si lahko zmislimo še druge relacije, recimo "je sorodnik". V tej relaciji imamo {(Babica, Mama), (Mama, Hči), (Babica, Hči), (Mama, Babica), (Hči, Mama), (Hči, Babica)}. Ta sicer vsebuje vse pare iz relacije "je mama", ampak ni tranzitivna. Zato to ni tranzitivna ovojnica.

Pa še eno: recimo "ima soroden DNK". V tej relaciji imamo vse pare (vse imajo soroden DNK same s sabo in z drugimi). Ta je tranzitivna in ima vse pare iz prejšnje relacije. Ampak ni najmanjša taka - smo zgoraj našli manjšo. Zato tudi to ni tranzitivna ovojnica relacije "je mama".


Pri matematiki znaš še velikokrat slišati za ovojnico ali pa zaprtje (closure). To vedno pomeni, da dano stvar malo razširimo - najmanj možno, tako da dobimo nekaj novega, kar pa ima željeno lastnost.


Še angleški wiki: LINK