MATEMANIJA

Izračunati broj svih binarnih relacija definisanih na skupu [inlmath]M=\left\{1,2\right\}[/inlmath] koje su:
a) proizvoljne
b) refleksivne
c) simetrične
d) antisimetrične
e) tranzitivne
f) ekvivalencije
d) poretka
h) ni simetrične ni antisimetrične
i) simetrične i antisimetrične
j) relacije ekvivalencije i poretka

Rešenja su [inlmath]16,4,8,12,13,2,3,0,4,1[/inlmath]. Ja ne mogu ni da provalim kako je dobio da ima [inlmath]16[/inlmath] proizvoljnih relacija a kamoli ostale, ja sam skontao samo [inlmath](11),(22),(12),(21)[/inlmath]. Treba mi primer logike ovog zadatka i primer kako se radi jedna!

Odd one out je napisao:ja sam skontao samo [inlmath](11),(22),(12),(21)[/inlmath]

Zapravo, to što si ovde napisao predstavlja samo jednu od mogućih binarnih relacija. I, njen pravilan zapis bio bi [inlmath]\{(1,1),(2,2),(1,2),(2,1)\}[/inlmath].
Svi primeri proizvoljnih binarnih relacija na ovom skupu bili bi:

[inlmath]1.\;\emptyset[/inlmath] (prazan skup – nijedan element nije u relaciji ni s jednim elementom);
[inlmath]2.\;\{(1,1)\}[/inlmath]
[inlmath]3.\;\{(1,2)\}[/inlmath]
[inlmath]4.\;\{(2,1)\}[/inlmath]
[inlmath]5.\;\{(2,2)\}[/inlmath]
[inlmath]6.\;\{(1,1),(1,2)\}[/inlmath]
[inlmath]7.\;\{(1,1),(2,1)\}[/inlmath]
[inlmath]8.\;\{(1,1),(2,2)\}[/inlmath]
[inlmath]9.\;\{(1,2),(2,1)\}[/inlmath]
[inlmath]10.\;\{(1,2),(2,2)\}[/inlmath]
[inlmath]11.\;\{(2,1),(2,2)\}[/inlmath]
[inlmath]12.\;\{(1,1),(1,2),(2,1)\}[/inlmath]
[inlmath]13.\;\{(1,1),(1,2),(2,2)\}[/inlmath]
[inlmath]14.\;\{(1,1),(2,1),(2,2)\}[/inlmath]
[inlmath]15.\;\{(1,2),(2,1),(2,2)\}[/inlmath]
[inlmath]16.\;\{(1,1),(1,2),(2,1),(2,2)\}[/inlmath] – svaki element je u relaciji sa svakim.

Naravno, nije potrebno ispisivati sve moguće binarne relacije da bi se odredio njihov broj. To se može učiniti primenom kombinatorike. Uređenih parova elemenata tog skupa imamo četiri (to su ona četiri uređena para koja si napisao). Svaki od tih uređenih parova može i da bude i da ne bude element binarne relacije tog skupa. Npr. uređeni par [inlmath](1,2)[/inlmath] je element relacije u 3, 6, 9, 10, 12, 13, 15. i 16. slučaju gorenapisanih binarnih relacija. U ostalim slučajevima nije. Prema tome, možemo to posmatrati kao dva moguća slučaja za svaki od četiri uređena para (da pripada ili da ne pripada binarnoj relaciji). Znači, ukupan broj slučajeva bio bi [inlmath]2\cdot2\cdot2\cdot2[/inlmath], tj. [inlmath]2^4[/inlmath]. Ili, broj varijacija s ponavljanjem od [inlmath]2[/inlmath] elementa [inlmath]4.[/inlmath] klase, [inlmath]\overline V_2^4[/inlmath].

U opštijem slučaju, na skupu od [inlmath]n[/inlmath] elemenata, broj uređenih parova bio bi [inlmath]\overline V_n^2=n^2[/inlmath] (varijacije s ponavljanjem od [inlmath]n[/inlmath] elemenata [inlmath]2.[/inlmath] klase), svaki od njih može ili pripadati ili ne pripadati binarnoj relaciji tog skupa, pa bi ukupan broj postojećih binarnih relacija bio [inlmath]2^{n^2}[/inlmath] (broj varijacija s ponavljanjem od [inlmath]2[/inlmath] elementa [inlmath]n^2[/inlmath]-te klase).

Sad ti, pretpostavljam, nije problem da uočiš koje od nabrojanih [inlmath]16[/inlmath] binarnih relacija (tj. koliko njih) ispunjava uslove pod b), pod c), pod d)...


EDIT 24.9.2018: Postavljena tema o broju svih binarnih relacija nad skupom od [inlmath]n[/inlmath] elemenata – LINK.