množice,relacije

[tati]

kako bi rešili to nalogo?
Na množici {1,2,3,4,5,6} imamo podano relacijo
R = {(3,5),(5,4),(4,5),(4,4),(3,4),(3,2),(3,1),(6,2),(1,6),(6,1),(5,5)}

Najmanj koliko elementov moramo dodati relaciji R, da bo le-ta postala tranzitivna?Je dobljena relacija refleksivna? Je dobljena relacija simetrična?

poznam pravila za določanje tega ali je sim.,ref. in podobno,samo ko pridem do prvega dela, ne znam ostali dve vpr.sta ok, tole prvo pa mi ne gre naj si narišem ali kako? samo kako potem iz dega ven? :'(

hvala

[Aniviller]

Ja, jaz bi narisal Nisem vešč množic, ampak jaz bi se tega tako lotil, da bi enostavno "zaprl" množico relacij: najlažje je najbrž tako, da si narediš razpredelnico 6x6 in označiš polja, ki so v relaciji (recimo prva relacija pobarva polje (3,5)). Potem samo za vsa prazna polja preveriš, če so kombinacija dveh drugih, in za vsakega, ki je, tudi označiš. Če so to razpredelnica enke in ničle, potem lahko stvar razglasiš za matriko. Kvadrat matrike ima potem neničelne elemente na mestih, kjer dobiš relacijo s kompozicijo dveh relacij. To potem prišteješ originalni matriki (in vse >1 daš na 1) in ponavljaš, dokler se ne neha spreminjat.

Recimo relacija
{1,2,3}, R={(1,2),(2,3),(1,1)}
bi se zapisala A=
[1,1,0]
[0,0,1]
[0,0,0]
potem A^2=
[1,1,1]
[0,0,0]
[0,0,0]
kar pri prištevanju A+A^2 očitno doda relacijo (1,3) na seznam:
[1,1,1]
[0,0,1]
[0,0,0]
To je mogoče na majhnih bolj nepregledno, ampak na 6x6 pa mislim, da je edino pametno (poleg risanja, pa še tam kaj pozabiš). Tole kompliciranje s števili, večjimi od 1, upravičiš tako, da delaš namesto seštevanja operacijo "ali" in namesto množenja operacijo "in".

[tati]

na kakšen način si to narišem? tole z enkami ne razumem

[Aniviller]

Na mestu ij matrike A postaviš "DA", če imaš relacijo (i,j), in "NE", če jo nimaš. Komponiranje relacij v stilu
(i,k) IN (k,j)
potem tvori (po tranzitivnosti) relacijo (i,j), ampak samo, če za VSAJ en k, obstajata tako relacija (i,k) kot (k,j). To lahko zapišeš kot
(i,j)=[ (i,1) IN (1,j) ] ALI [ (i,2) IN (2,j) ] ALI ...
kar lahko pišeš kot
\(B_{ij}=\sum_{k} A_{ik}A_{kj}\)
oziroma B=A^2, ker prepoznaš matrično množenje, pri čemer pri nas množenje pomeni operacijo "IN", seštevanje v zgornji vsoti pa operacijo "ALI" (kar je pravzaprav tudi ena izmed ustaljenih dogovorjenih notacij za algebro na Boolovih spremenljivkah). Matrika B ima potem "DA" na mestih, katere relacije si na novo skonstruiral s kompozicijo obstoječih relacij. A+B je potem združena razširjena množica relacij, ki vsebuje tako stare kot nove (+ je spet "ALI"). In to ponavljaš, dokler kompozicija ne ustvari nobene nove relacije. S tem je množica relacij tranzitivna, saj kompozicija katerega koli para tvori relacijo, ki je tudi v množici.

To si lahko misliš kot usmerjen graf. Narišeš si točke za elemente množice, relacije so pa puščice od prvega do drugega elementa. Zgornji postopek tvori nove povezave, če lahko v smeri puščic po daljši poti prideš med dvema elementoma, potem dodaš še direktno puščico. Ko je vse povezano, bi moralo bit tranzitivno. Seveda je potem vprašljivo, kaj te relacije pomenijo. Recimo relacija kot je neenakost, lahko v taki strukturi obstaja samo, če nimaš sklenjenih zank. a<b<c<a namreč nima smisla. V tem primeru moraš imeti ekvivalenčno relacijo ali kaj podobnega.

[tati]

hvala
sicer sem že zadnjoč potem pogruntala,pa sem potem pozabila napisat

imam še eno vprašanje. baje je to najlažje,meni pa dela največ problemov...
Kako relaciji določiti ekvivalenčni razred? Ja ok, razumem, relacija mora biti ekvivalenčna,potem pa kaj??
ni mi jasno,res oprostite

hvala

[tati]

pa še tole bi potrebovala...

Na potencni mnozici mnozice naravnih stevil P(N) deniramo relacijo R s predpisom: ARB <=> |A + B| <= 1
(Dve mnozici sta v relaciji R natanko tedaj, kadar je moc njune simetricne razlike manjsa ali enaka 1.)
a) Katere od znanih lastnosti (refleksivnost, simetricnost, antisimetricnost,tranzitivnost, sovisnost) ima relacija R? Odgovore utemelji.
b) Za katere mnozice A podm. N velja AR?
c) Za katere mnozice A podm. N velja AR{1}?

prva bi še nekako šla kaj pa druga in tretja podnaloga?