Matematické Fórum

bobik · 22. 01. 2009 16:01

Ahojte, potreboval by som pomôcť s príkladom.

A) Koľko je všetkých binárnych relácií na konečnej n-prvkovej množine n > 1.
B) Koľko z nich je symetrických
C) Koľko z nich je tranzitívnych
D) Koľko z nich je reflexívnych a antisymetrických

Netuším ako by sa to malo počítať, ďakujem za pomoc

musixx · 22. 01. 2009 16:20 — Editoval musixx (23. 01. 2009 10:25)

↑ bobik: Umis si relaci predstavit jako matici z nul a jednicek? Pokud ano, pak to celkem snadno udelas (s trikem na tranzitivitu). Matice bude ctvercova, radu n.

A) Vyplnit takovou matici jakkoli pomoci 0 a 1 (= dve volby) jde $2^{n^2}$ zpusoby, vzdyt $n^2$ po sobe a nezavisle na sobe vybirame jednu z moznosti 0 a 1.

B) Symetricka relace se pozna tak, ze jeji matice je symetricka. Tedy si muzu pod hlavni diagonalu dat cokoli, na hlavni diagonalu cokoli a nad hlavni diagonalou je to uz jasne (jednoznacne urceno tim, co je pod ni). Ted jen secti, kolikrat po sobe tedy budes volit jednu ze dvou moznosti: Na hlavni diagonale je n prvku a pod ni je polovina z poctu vsech prvku pomenseneho o pocet prvku na hlavni diagonale.

D) Velice podobne B)

C) Takova hricka. Zatim necham k badani...

bobik · 22. 01. 2009 16:45

↑ musixx:
viem si prestaviť maticu z núl a jednotiek, ale trochu mi robí problém si prestaviť čo to pre relácie znamená.

potreboval by som to nejak konkrétnejšie zdôvodniť.

musixx · 22. 01. 2009 16:54

↑ bobik: Predstav si radky i sloupce teto matice oznacovane prvky one n-prvkove mnoziny, treba x1, x2, ..., xn. Kdyz bude v radku oznacenem xi a sloupci oznacenem xj jednicka, tak to znamena, ze xi je v relaci s xj (v tomto poradi). Kdyz tam bude nula, tak xi neni v relaci s xj.

bobik · 22. 01. 2009 17:30 — Editoval bobik (22. 01. 2009 17:37)

↑ musixx:
takze by som si to mohol predstavit aj takto:

| x_1 | x_2 | x_3 | x_4 | .... | x_n
x_1 | 0 0 1 0 1
x_2 | 1 1 0 1 0
x_3 | 1 0 1 0 0
x_4 | 0 0 1 0 1
. | ...
. | ...
. | ...
x_n | 0

vsetkych moznosti ako vyplnit tuto tabulku je $2^{n^{2}}$ symetrických relácií je potom $2^{\frac{n(n-1)}2}$ pretože tabuľka je symetrická vtedy ak je symetrická podľa diagonály, t.j. je jednoznačne určená prvkami pod alebo nad diagonálou pričom diagonála môže byť ľubovolná t.j. vyplňujem tabuľku pod diagonálou a nad ňou musí byť už jednoznačne určená.
Z toho potom vyplíva, že antisymetrických binárnych relácií je $2^{n^{2}} - 2^{\frac{n(n-1)}2} = 2^n\left$2^n-2^{\frac{(n-1)}2}\right$$ ?

reflexívnosť by mohla byť $2^n$ ? sledujem totiž iba diagonálu a teda n prvkov

tú tranzitívnosť teda neviem

mikee · 22. 01. 2009 23:12 — Editoval mikee (22. 01. 2009 23:13)

Myslím, že počet symetrických relácií (aj s odôvodnením) máš určený správne. Ale pri určovaní počtu antisymetrických relácií si sa dopustil (pomerne bežnej) chyby, a to takej, že si využil tvrdenie, že relácia, ktorá nie je symetrická, je automaticky antisymetrická, teda že súčet počtu symetrických a antisymetrických relácií sa rovná počtu všetkých relácií. Toto tvrdenie je však NEPRAVDIVÉ. Totiž, existujú relácie, ktoré nie sú ani symetrické ani antisymetrické, napríklad na množine {1, 2, 3, 4, 5} je to relácia ([1,2],[1,3],[3,1]). Ak má byť relácia R symetrická, tak pre všetky a,b ak [a,b] je v R, tak aj [b,a] je v R, čo v našom prípade neplatí, lebo [1,2] je v R, ale [2,1] nie je. Čiže symetrická nie je. Ale ak má byť antisymetrická, tak musí platiť, že ak [a,b] je v R a zároveň [b,a] je v R, tak a=b, čo v našom prípade [1,3] je v R aj [3,1] je v R, ale 1 sa nerovná 3. Takže táto relácia napríklad nie je symetrická ani antisymetrická. Toto je ale pomerne bežná chyba, takže nič si z toho nerob :)
Druhá vec je, že existujú relácie, ktoré sú zároveň symetrické aj antisymetrické, napríklad relácia {[1,1],[2,2]}. Veľmi ľahko sa dá overiť, že spĺňa rovnako podmienku pre symetrickosť aj antisymetrickosť (takéto relácie budú zrejme všetky také, ktoré budú zložené len z usporiadaných dvojíc tvaru [a,a] pre nejaké a).

musixx · 23. 01. 2009 08:48

↑ mikee: Odvozeni pro symetricke relace ovsem dobre nemas a ↑ mikee: nema pravdu. Nedocetls muj navod: pod hlavni diagonalou cokoli, coz determinuje tez nad hlavni diagonalou, ale jeste navic na hlavni diagonale cokoli. Pod diagonalou mame $\frac{n^2-n}2$ prvku, na ni $n$ , tedy celkem bude dvojka umocnena na $\frac{n^2-n}2+n=\frac{n(n+1)}2$ .

Reflexivni relace se vyznacuje tim, ze na hlavni diagonale jsou same jednicky, tedy neni co volit a zbyva $n^2-n$ prvku mimo hlavni diagonalu, kde se da dat cokoli, tedy reflexivnich je $2^{n(n-1)}$ .

A tak dale.

musixx · 23. 01. 2009 10:31

↑ bobik: K tem tranzitivnim - aby ses netrapil az prilis dlouho. Mrkni treba na tento odkaz.

bobik · 23. 01. 2009 14:11 — Editoval bobik (23. 01. 2009 14:14)

↑ musixx:

no tak tam je toho dosť popísané ale moc sa v tom nevyznám,

zhrniem si to
počet všetkých binárnych relácií z A do B je rovný počtu všetkých podmnožín AxB. Ak je A, B n-prvková množina tak môžeme povedať, že ich je $2^{n^2}$
alebo si môžeme binárne relácie predstaviť ako boolovskú maticu typu nxn, kde budú hodnoty buď 0 (prvok xi nie je v relácii s prvkom xj) alebo 1 (prvok xi je v relácii s prvkom xj)
potom všetkých binárnych relácií je počet všetkých možných možností ako vyplniť túto tabuľku, t.j. vyberáme z dvoch prvkov do n*n polí. Teda je ich $2^{n^2}$

počet všetkých reflexívnych binárnych relácií je potom $2^{n(n-1)}$ dôvod :

musixx napsal(a):
Reflexivni relace se vyznacuje tim, ze na hlavni diagonale jsou same jednicky, tedy neni co volit a zbyva $n^2-n$ prvku mimo hlavni diagonalu, kde se da dat cokoli

počet symetrických relácií je určený jednoznačne počtom prvokov pod diagonálou $\frac{n^2-n}{2}$ resp. nad ňou bez ohľadu na to čo je na diagonále (počet prvkov na diagonále je $n$ ) teda možností ako vyplniť túto tabuľku je $2^{\frac{n^2-n}{2}+n}$

v tom odkaze som sa dočítal, že počet všetkých antisymetrických relácií je $2^n3^{\frac{n(n-1)}{2}}$ ale netuším ako k tomu došli podobne ako aj k výsledku
koľko je reflexívnych a antisymetrických spolu $3^{\frac{n(n-1)}{2}}$

a tie tranzitívne tiež nemám šajn. neviem sa z toho vyznať.

musixx · 23. 01. 2009 15:21 — Editoval musixx (23. 01. 2009 15:22)

↑ bobik: Antisymetricke mas spravne: $2^n$ znamena cokoli na hlavni diagonalu a $3^{\dots}$ znamena, ze z prvku nad a pod diagonalou udelas dvojice (ty, co k sobe symetricky patri) a bud nedas jednicku nikam, nebo jen dolu, nebo jen nahoru (tedy 3 moznosti, ktere volis $\frac{n^2-n}2$ krat po sobe).

Reflexivni a antisymetricke dohromady mas take dobre - proste zadne $2^n$ tam neni, protoze na hlavni diagonale nebyla zadna moznost volby - kvuli reflexivite tam musely byt jednicky.

Pokud je mi znamo, tak neexistuje vzorec pro pocet vsech tranzitivnich relaci na n-prvkove mnozine. Vi se jen to, ze limitne je to $k\cdot2^{n^2}$ . Nevim, co presne se vi o tom 'k' (krom jeho existence).

bojkot · 29. 03. 2009 20:30

šlo by sestavit obecný vzorec na zjištění
všech reflexivních a symetrických relací?
případně všech reflexivních ,symetrických a antisymetrických?

Rumburak

Mně leccos vychází poněkud jinak.

Nechť m = (n-1)*n/2

Počet všech antisymetrických relací na n-prvkové množině je

(1) 3^m .

D ů k a z. Předně AS relace R má prázdný průnik s diagonálou, dále též R průnik R^(-1) je prázdný.
Označme F "to, co je pod diagonálou", tedy |F| = m a definujme

A = F průnik R , B = F průnik R^(-1) ,

potom i A průnik B je prázdný, neboť je částí (prázdné množiny) R průnik R^(-1) . Každou AS relaci R tak můžeme vyjádřit ve tvaru

R = A U B^(-1) , kde A, B jsou disjunktní podmnožiny v F.

Tedy kolika zbůsoby mohu z m- prvkové množiny F vybrat její disjunktní podmnožiny A, B ?
Nechť |A| = a, |B| = b, kde a + b <= m .
Množinu A mohu vybrat (m nad a) způsoby, množinu B disjunktrní s A pak ((m-a) nad b) způsoby. Tedy

Jsou-li dána nezáporná celá čísla a , b taková, že a + b <= m , pak AS relaci R splňující |F průnik R| = a , |F průnik R^(-1)| = b
mohu sestrojit

(2) (m nad a) * ((m-a) nad b)

způsoby. Počet všech AS relací R, které splňují pouze |F průnik R| = a dostanu tak, že (2) posčítám přes b = 0, ... , m-a , čímž dle bin. věty vyjde

(3) (m nad a) * 2^(m-a) .

Počet úplně všech AS relací na n-prvkové množině dostanu tak, že posčítám (3) přes a = 0, ... , m , čímž dle bin. věty vyjde 3^m .

Počet všech SLABĚ antisymetrických relací je (2^n) * (3^m)

(Každou SAS relaci sestrojím z nějaké AS relace R tak, že k ní přidám něco z diagonály.)

Matematické Fórum

#1 22. 01. 2009 16:01

binárne relácie

#2 22. 01. 2009 16:20 — Editoval musixx (23. 01. 2009 10:25)

Re: binárne relácie

#3 22. 01. 2009 16:45

Re: binárne relácie

#4 22. 01. 2009 16:54

Re: binárne relácie

#5 22. 01. 2009 17:30 — Editoval bobik (22. 01. 2009 17:37)

Re: binárne relácie

#6 22. 01. 2009 23:12 — Editoval mikee (22. 01. 2009 23:13)

Re: binárne relácie

#7 23. 01. 2009 08:48

Re: binárne relácie

#8 23. 01. 2009 10:31

Re: binárne relácie

#9 23. 01. 2009 14:11 — Editoval bobik (23. 01. 2009 14:14)

Re: binárne relácie

musixx napsal(a):

#10 23. 01. 2009 15:21 — Editoval musixx (23. 01. 2009 15:22)

Re: binárne relácie

#11 29. 03. 2009 20:30

Re: binárne relácie

#12 30. 03. 2009 10:49 — Editoval Rumburak (30. 03. 2009 11:41)

Re: binárne relácie

Zápatí