Korisnički Kontrolni Panel
Pogledajte svoj profil
Pogledajte svoje postove
ČPP
Prijavite se

Matematički forum na kojem možete da diskutujete o raznim matematičkim oblastima, pomognete drugima oko rešavanja zadataka, a i da dobijete pomoć kada vam zatreba


















Index stranica OSTALE MATEMATIČKE OBLASTI TEORIJA SKUPOVA

Koliko ima binarnih relacija koje su simetricne refleksivne?

[inlmath]C\backslash\left(A\cap B\right)=\left(C\backslash A\right)\cup\left(C\backslash B\right)[/inlmath]

Koliko ima binarnih relacija koje su simetricne refleksivne?

Postod Loophoop » Četvrtak, 25. Maj 2017, 11:29

Zdravo iz zbirke

Diskretna matematika
Osnove kombinatorike i teorije grafova
-Zbirka resenih zadataka-

Glasi:
Koliko se binarnih relacija moze definisati na skupu sa [inlmath]n[/inlmath] elemenata? Koliko postoji:
a) refleksivnih
b) simetricnih
c) refleksivnih i simetricnih


Resenje za opste pitanje:
Neka je [inlmath]X_{n,n}=\{1,2,\ldots,n\}\times\{1,2,\ldots,n\}[/inlmath].
Binarna relacija [inlmath]p[/inlmath] na skupu [inlmath]\{1,2,\ldots,n\}[/inlmath] je svaki podskup skupa [inlmath]X[/inlmath], pa je ukupan broj binarnih relacija jednak [inlmath]2^{\left(n^2\right)}[/inlmath]

Razumem odgovor za, koliko se binarnih relacija moze definisati na skupu sa [inlmath]n[/inlmath] elementa
Pa jel moze da se preformulise moje pitanje
Koliko postoji relacija na skupu od [inlmath]n[/inlmath] elemenata koje su:
a) refleksivne
b) simetricne
c) refleksivne i simetricne

Ima i resenje
1) Relacija [inlmath]p[/inlmath] je refleksivna ako sadrzi skup [inlmath]\{(1,1),(2,2),\ldots,(n,n)\}[/inlmath]. Od preostalih [inlmath]n^2-n[/inlmath] uredjenih parova iz skupa [inlmath]X_{n,n}[/inlmath] moze se izabrati proizvoljan podskup, pa je ukupan broj refleksivnih relacija jednak [inlmath]2^{\left(n^2-n\right)}[/inlmath].

Pitanje:
ne razumem sta smo ovde radili, jasno mi je da je skup
[inlmath]\{(1,1),(2,2)\ldots(n,n)\}[/inlmath]
refleksivna relacija, i da takvih elementa ima [inlmath]n[/inlmath], i po mojoj logici
tu bih stao, rekao bih da ih ima [inlmath]2^n[/inlmath]?
Ne razumem sta se krije iza resenja [inlmath]2^{\left(n^2-n\right)}[/inlmath]

b) Relacija [inlmath]p[/inlmath] je simetricna ako za svaki uredjeni par [inlmath](x,y)[/inlmath] sadrzi i uredjeni par [inlmath](y,x)[/inlmath]. Zato je simetricna relacija [inlmath]p[/inlmath] u potpunosti odredjena ako znamo koji uredjeni parovi [inlmath](x,y)[/inlmath], kod kojih je [inlmath]x\le y[/inlmath] pripadaju [inlmath]p[/inlmath]. Takvih parova ima [inlmath]\frac{n(n+1)}{2}[/inlmath]
pa je ukupan broj simetricnih relacija jednak [inlmath]2^{\left(\frac{n(n+1)}{2}\right)}[/inlmath]

Pitanje:
Ne razumem sta se krije iza [inlmath]\frac{n(n+1)}{2}[/inlmath]
Jel ima ovo neke logike
imamo [inlmath]n[/inlmath] elementa i treba da ih spojimo sa ostalima (tu racunamo i prazan skup otuda [inlmath]n+1[/inlmath])
pa posto smo ih racunali kao [inlmath](x,y)[/inlmath] i kao [inlmath](y,x)[/inlmath], nama to nista ne znaci pa delimo sve sa [inlmath]2[/inlmath]

c) Refleksivna i simetricna relacija [inlmath]p[/inlmath] sadrzi skup [inlmath]\{(1,1),\ldots,(n,n)\}[/inlmath]
a u potpunosti je odredjena ako znamo koji uredjeni parovi [inlmath](x,y)[/inlmath], kod kojih je [inlmath]x<y[/inlmath], pripadaju [inlmath]p[/inlmath]. Ovakvih parova ima [inlmath]\frac{n(n-1)}{2}[/inlmath], pa zato je ukupan broj refleksivnih i simetricnih relacija jednak [inlmath]2^{\left(\frac{n(n-1)}{2}\right)}[/inlmath]

Pitanje:
Za ovaj imam samo neku malu predstavu da stoji [inlmath]n-1[/inlmath], posto se radi o operatoru [inlmath]<[/inlmath].
Poslednji put menjao Corba248 dana Četvrtak, 25. Maj 2017, 12:37, izmenjena 3 puta
Razlog: Korekcija LaTex-a
 
Postovi: 10
Zahvalio se: 4 puta
Pohvaljen: 0 puta

Sharuj ovu temu na:

Share on Facebook Facebook Share on Twitter Twitter Share on MySpace MySpace Share on Google+ Google+
  • +1

Re: Koliko ima binarnih relacija koje su simetricne refleksivne?

Postod Corba248 » Četvrtak, 25. Maj 2017, 12:35

Prepravio sam ti LaTex. Pre nego što klikneš na "Pošalji" imaš opciju "Pregled" da vidiš kako će tvoj post izgledati. Za razlomak se koristi komanda \frac umesto /. Molim te da proveriš da li sam sve prepravio onako kako bi trebalo da piše.
Možda si hteo umesto [inlmath]p[/inlmath] za relaciju da koristiš oznaku [inlmath]\rho[/inlmath]?
Zaslužni forumaš
 
Postovi: 314
Zahvalio se: 37 puta
Pohvaljen: 352 puta

Re: Koliko ima binarnih relacija koje su simetricne refleksivne?

Postod Loophoop » Četvrtak, 25. Maj 2017, 16:09

To je to hvala, hteo sam [inlmath]\rho[/inlmath]
A za ostalo, pretisao sam "Pregled" pre "Posalji", mislio sam da onako treba...
 
Postovi: 10
Zahvalio se: 4 puta
Pohvaljen: 0 puta

  • +1

Re: Koliko ima binarnih relacija koje su simetricne refleksivne?

Postod Daniel » Nedelja, 28. Maj 2017, 09:49

Loophoop je napisao:1) Relacija [inlmath]p[/inlmath] je refleksivna ako sadrzi skup [inlmath]\{(1,1),(2,2),\ldots,(n,n)\}[/inlmath]. Od preostalih [inlmath]n^2-n[/inlmath] uredjenih parova iz skupa [inlmath]X_{n,n}[/inlmath] moze se izabrati proizvoljan podskup, pa je ukupan broj refleksivnih relacija jednak [inlmath]2^{\left(n^2-n\right)}[/inlmath].

Pitanje:
ne razumem sta smo ovde radili, jasno mi je da je skup
[inlmath]\{(1,1),(2,2)\ldots(n,n)\}[/inlmath]
refleksivna relacija, i da takvih elementa ima [inlmath]n[/inlmath], i po mojoj logici
tu bih stao, rekao bih da ih ima [inlmath]2^n[/inlmath]?
Ne razumem sta se krije iza resenja [inlmath]2^{\left(n^2-n\right)}[/inlmath]

Najlakše je to posmatrati tabelarno. Verovatno znaš za tabelarno prikazivanje relacija – ako je npr. [inlmath]1.[/inlmath] element u relaciji s [inlmath]3.[/inlmath] elementom, tada popunjavamo polje koje se nalazi u [inlmath]1.[/inlmath] vrsti i u [inlmath]3.[/inlmath] koloni. Kod relacija koje su refleksivne, tj. kod kojih je [inlmath]1.[/inlmath] element u relaciji s [inlmath]1.[/inlmath] elementom, [inlmath]2.[/inlmath] element u relaciji s [inlmath]2.[/inlmath] elementom itd., biće popunjena sva polja na glavnoj dijagonali, dok ćemo ostala polja popuniti znacima pitanja, jer ostali elementi mogu, ali i ne moraju, biti u relaciji s ostalim elementima:
[dispmath]\begin{array}{c|c|c|c|c|c|c|}
& 1 & 2 & 3 & \cdots & n-1 & n\\ \hline
1 & \color{blue}\Large\bullet & ? & ? & \cdots & ? & ?\\ \hline
2 & ? & \color{blue}\Large\bullet & ? & \cdots & ? & ?\\ \hline
3 & ? & ? & \color{blue}\Large\bullet & \cdots & ? & ?\\ \hline
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ \hline
n-1 & ? & ? & ? & \cdots & \color{blue}\Large\bullet & ?\\ \hline
n & ? & ? & ? & \cdots & ? & \color{blue}\Large\bullet\\ \hline
\end{array}[/dispmath] Ukupan broj polja je [inlmath]n^2[/inlmath]. Na glavnoj dijagonali imamo [inlmath]n[/inlmath] polja. Znači, kad od ukupnog broja polja oduzmemo broj polja na glavnoj dijagonali, dobijamo broj onih polja koja možemo proizvoljno (ne) popunjavati (koja su označena znacima pitanja). Takvih polja ima [inlmath]n^2-n[/inlmath], a pošto svako od njih možemo ili popuniti ili ne popuniti, broj takvih mogućnosti je [inlmath]2^{n^2-n}[/inlmath].

Loophoop je napisao:b) Relacija [inlmath]p[/inlmath] je simetricna ako za svaki uredjeni par [inlmath](x,y)[/inlmath] sadrzi i uredjeni par [inlmath](y,x)[/inlmath]. Zato je simetricna relacija [inlmath]p[/inlmath] u potpunosti odredjena ako znamo koji uredjeni parovi [inlmath](x,y)[/inlmath], kod kojih je [inlmath]x\le y[/inlmath] pripadaju [inlmath]p[/inlmath]. Takvih parova ima [inlmath]\frac{n(n+1)}{2}[/inlmath]
pa je ukupan broj simetricnih relacija jednak [inlmath]2^{\left(\frac{n(n+1)}{2}\right)}[/inlmath]

Pitanje:
Ne razumem sta se krije iza [inlmath]\frac{n(n+1)}{2}[/inlmath]

Pošto je relacija simetrična, znači da u odnosu na glavnu dijagonalu polja moraju biti simetrično popunjena. To znači, ako je polje [inlmath](1,3)[/inlmath] popunjeno, tada mora biti popunjeno i polje [inlmath](3,1)[/inlmath]. Ako polje [inlmath](2,3)[/inlmath] nije popunjeno, tada ne sme biti popunjeno ni polje [inlmath](3,2)[/inlmath] itd.
Zbog toga polja iznad glavne dijagonale ne smemo popunjavati proizvoljno, već je njihova (ne)popunjenost uslovljena (ne)popunjenošću polja ispod glavne dijagonale.
Polja na glavnoj dijagonali možemo popunjavati proizvoljno, jer nije dat uslov da je ova relacija refleksivna.
[dispmath]\begin{array}{c|c|c|c|c|c|c|}
& 1 & 2 & 3 & \cdots & n-1 & n\\ \hline
1 & ? & \color{green}\Large\bullet & \color{green}\Large\bullet & \cdots & \color{green}\Large\bullet & \color{green}\Large\bullet\\ \hline
2 & ? & ? & \color{green}\Large\bullet & \cdots & \color{green}\Large\bullet & \color{green}\Large\bullet\\ \hline
3 & ? & ? & ? & \cdots & \color{green}\Large\bullet & \color{green}\Large\bullet\\ \hline
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ \hline
n-1 & ? & ? & ? & \cdots & ? & \color{green}\Large\bullet\\ \hline
n & ? & ? & ? & \cdots & ? & ?\\ \hline
\end{array}[/dispmath] I sad prebrojavamo koliko imamo polja s upitnicima (tj. polja koja možemo proizvoljno popunjavati). U prvoj vrsti imamo [inlmath]1[/inlmath] takvo polje. U drugoj vrsti ih imamo [inlmath]2[/inlmath]. U trećoj ih imamo [inlmath]3[/inlmath]. U [inlmath](n-1).[/inlmath] vrsti ih imamo [inlmath]n-1[/inlmath] i u [inlmath]n[/inlmath]-toj vrsti ih imamo [inlmath]n[/inlmath]. Njihov broj, dakle, dobijamo kao sumu aritmetičkog niza [inlmath]1+2+\cdots+n[/inlmath], a to je [inlmath]\frac{n(n+1)}{2}[/inlmath].
Ukupan broj načina da se takva tabela popuni (tj. ukupan broj simetričnih relacija na skupu od [inlmath]n[/inlmath] elemenata) iznosi, prema tome, [inlmath]2^\frac{n(n+1)}{2}[/inlmath].

(Naravno, isti rezultat bismo dobili i da smo u polja iznad glavne dijagonale upisali znake pitanja, a da smo sadržaje polja ispod glavne dijagonale uslovili sadržajima polja iznad glavne dijagonale.)

Loophoop je napisao:Jel ima ovo neke logike
imamo [inlmath]n[/inlmath] elementa i treba da ih spojimo sa ostalima (tu racunamo i prazan skup otuda [inlmath]n+1[/inlmath])
pa posto smo ih racunali kao [inlmath](x,y)[/inlmath] i kao [inlmath](y,x)[/inlmath], nama to nista ne znaci pa delimo sve sa [inlmath]2[/inlmath]

Ovo nisam razumeo, pa ne mogu ni da komentarišem.

Loophoop je napisao:c) Refleksivna i simetricna relacija [inlmath]p[/inlmath] sadrzi skup [inlmath]\{(1,1),\ldots,(n,n)\}[/inlmath]
a u potpunosti je odredjena ako znamo koji uredjeni parovi [inlmath](x,y)[/inlmath], kod kojih je [inlmath]x<y[/inlmath], pripadaju [inlmath]p[/inlmath]. Ovakvih parova ima [inlmath]\frac{n(n-1)}{2}[/inlmath], pa zato je ukupan broj refleksivnih i simetricnih relacija jednak [inlmath]2^{\left(\frac{n(n-1)}{2}\right)}[/inlmath]

Vrlo je slično kao i pod b), samo što ovde, naravno, ne smeš elemente na glavnoj dijagonali uzimati proizvoljno – glavna dijagonala mora biti popunjena, zbog refleksivnosti. Ovo ostavljam tebi da uradiš, a kao pomć, tu ti je tabela za ovaj slučaj:
[dispmath]\begin{array}{c|c|c|c|c|c|c|}
& 1 & 2 & 3 & \cdots & n-1 & n\\ \hline
1 & \color{blue}\Large\bullet & \color{green}\Large\bullet & \color{green}\Large\bullet & \cdots & \color{green}\Large\bullet & \color{green}\Large\bullet\\ \hline
2 & ? & \color{blue}\Large\bullet & \color{green}\Large\bullet & \cdots & \color{green}\Large\bullet & \color{green}\Large\bullet\\ \hline
3 & ? & ? & \color{blue}\Large\bullet & \cdots & \color{green}\Large\bullet & \color{green}\Large\bullet\\ \hline
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ \hline
n-1 & ? & ? & ? & \cdots & \color{blue}\Large\bullet & \color{green}\Large\bullet\\ \hline
n & ? & ? & ? & \cdots & ? & \color{blue}\Large\bullet\\ \hline
\end{array}[/dispmath]
Bilo bi korisno da pogledaš i ovu temu.


EDIT 24.9.2018: Postavljena tema o broju svih binarnih relacija nad skupom od [inlmath]n[/inlmath] elemenata – LINK.
Poslednji put menjao Daniel dana Ponedeljak, 24. Septembar 2018, 17:56, izmenjena samo jedanput
Razlog: Dodavanje linka ka srodnoj temi
I do not fear death. I had been dead for billions and billions of years before I was born, and had not suffered the slightest inconvenience from it. – Mark Twain
Korisnikov avatar
Daniel  OFFLINE
Administrator
 
Postovi: 9300
Lokacija: Beograd
Zahvalio se: 5151 puta
Pohvaljen: 4951 puta


Povratak na TEORIJA SKUPOVA

Ko je OnLine

Korisnici koji su trenutno na forumu: Nema registrovanih korisnika i 31 gostiju


Index stranicaTimObriši sve kolačiće boarda
Danas je Četvrtak, 28. Mart 2024, 13:19 • Sva vremena su u UTC + 1 sat
Pokreće ga phpBB® Forum Software © phpBB Group
Prevod – www.CyberCom.rs