3200. Relacije | Balkan Tutor

TEKST ZADATKA

Koje od osobina: refleksivnost, simetričnost, antisimetričnost, tranzitivnost ima relacija $\rho ?$ Nacrtati graf i napraviti tablicu relacije $\rho$ ako je: $x \rho y \Leftrightarrow x^2 + y^2 \geqslant 25$ na skupu $A = \{-5, -3, -1, 2, 4\}$ ;

REŠENJE ZADATKA

Da bismo odredili elemente relacije, prvo računamo kvadrate svih elemenata skupa $A .$

x^2 \in \{(-5)^2, (-3)^2, (-1)^2, 2^2, 4^2\} = \{25, 9, 1, 4, 16\}

Sada proveravamo za svaki element $x \in A$ koje vrednosti $y \in A$ zadovoljavaju uslov $x^2 + y^2 \ge 25 .$

\begin{aligned} x=-5 &\Rightarrow 25 + y^2 \ge 25 \Rightarrow y \in \{-5, -3, -1, 2, 4\} \\ x=-3 &\Rightarrow 9 + y^2 \ge 25 \Rightarrow y^2 \ge 16 \Rightarrow y \in \{-5, 4\} \\ x=-1 &\Rightarrow 1 + y^2 \ge 25 \Rightarrow y^2 \ge 24 \Rightarrow y \in \{-5\} \\ x=2 &\Rightarrow 4 + y^2 \ge 25 \Rightarrow y^2 \ge 21 \Rightarrow y \in \{-5\} \\ x=4 &\Rightarrow 16 + y^2 \ge 25 \Rightarrow y^2 \ge 9 \Rightarrow y \in \{-5, -3, 4\} \end{aligned}

Zapisujemo relaciju $\rho$ kao skup uređenih parova.

\rho = \{(-5,-5), (-5,-3), (-5,-1), (-5,2), (-5,4), (-3,-5), (-3,4), (-1,-5), (2,-5), (4,-5), (4,-3), (4,4)\}

Pravimo tablicu relacije $\rho .$ U redove i kolone upisujemo elemente skupa $A .$ Ako su elementi u relaciji upisujemo 1, a ako nisu upisujemo 0.

\begin{array}{c|ccccc} \rho & -5 & -3 & -1 & 2 & 4 \\ \hline -5 & 1 & 1 & 1 & 1 & 1 \\ -3 & 1 & 0 & 0 & 0 & 1 \\ -1 & 1 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 & 0 & 0 \\ 4 & 1 & 1 & 0 & 0 & 1 \end{array}

Graf relacije se formira tako što se nacrtaju čvorovi za svaki element skupa $A ,$ a zatim se povlače usmerene grane od čvora $x$ do čvora $y$ ako važi $x \rho y .$ Zbog ograničenja formata, graf opisujemo: postoje petlje u čvorovima -5 i 4, a između ostalih povezanih čvorova postoje dvosmerne grane.

Ispitujemo refleksivnost. Relacija je refleksivna ako za svako $x \in A$ važi $x \rho x .$ Proveravamo element -3:

(-3)^2 + (-3)^2 = 9 + 9 = 18 < 25 \Rightarrow (-3, -3) \notin \rho

Pošto postoji element koji nije u relaciji sam sa sobom, relacija nije refleksivna.

Ispitujemo simetričnost. Relacija je simetrična ako $x \rho y \Rightarrow y \rho x .$ Zbog komutativnosti sabiranja, uslov uvek važi u oba smera.

x^2 + y^2 \ge 25 \Leftrightarrow y^2 + x^2 \ge 25

Dakle, relacija jeste simetrična.

Ispitujemo antisimetričnost. Relacija je antisimetrična ako $x \rho y \land y \rho x \Rightarrow x = y .$ Tražimo kontraprimer:

(-5) \rho (-3) \land (-3) \rho (-5), \text{ ali } -5 \neq -3

Pronašli smo kontraprimer, pa relacija nije antisimetrična.

Ispitujemo tranzitivnost. Relacija je tranzitivna ako $x \rho y \land y \rho z \Rightarrow x \rho z .$ Proveravamo sledeći slučaj:

(-3) \rho (-5) \land (-5) \rho (-1) \Rightarrow (-3) \rho (-1)

Proveravamo da li važi $(-3) \rho (-1) :$

(-3)^2 + (-1)^2 = 9 + 1 = 10 < 25 \Rightarrow (-3, -1) \notin \rho

Pošto uslov ne važi, relacija nije tranzitivna. Konačan zaključak je da relacija ima samo osobinu simetričnosti.

75.a