3200.

75.a

TEKST ZADATKA

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

REŠENJE ZADATKA

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

x2∈{(−5)2,(−3)2,(−1)2,22,42}={25,9,1,4,16}x^2 \in \{(-5)^2, (-3)^2, (-1)^2, 2^2, 4^2\} = \{25, 9, 1, 4, 16\}

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

x=−5⇒25+y2≥25⇒y∈{−5,−3,−1,2,4}x=−3⇒9+y2≥25⇒y2≥16⇒y∈{−5,4}x=−1⇒1+y2≥25⇒y2≥24⇒y∈{−5}x=2⇒4+y2≥25⇒y2≥21⇒y∈{−5}x=4⇒16+y2≥25⇒y2≥9⇒y∈{−5,−3,4}\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.

ρ={(−5,−5),(−5,−3),(−5,−1),(−5,2),(−5,4),(−3,−5),(−3,4),(−1,−5),(2,−5),(4,−5),(4,−3),(4,4)}\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. A . Ako su elementi u relaciji upisujemo 1, a ako nisu upisujemo 0.

ρ−5−3−124−511111−310001−110000210000411001\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 , a zatim se povlače usmerene grane od čvora x x do čvora y y ako važi xρy. 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∈A x \in A važi xρx. x \rho x . Proveravamo element -3:

(−3)2+(−3)2=9+9=18<25⇒(−3,−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ρy⇒yρx. x \rho y \Rightarrow y \rho x . Zbog komutativnosti sabiranja, uslov uvek važi u oba smera.

x2+y2≥25⇔y2+x2≥25x^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ρy∧yρx⇒x=y. x \rho y \land y \rho x \Rightarrow x = y . Tražimo kontraprimer:

(−5)ρ(−3)∧(−3)ρ(−5), ali −5≠−3(-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ρy∧yρz⇒xρz. x \rho y \land y \rho z \Rightarrow x \rho z . Proveravamo sledeći slučaj:

(−3)ρ(−5)∧(−5)ρ(−1)⇒(−3)ρ(−1)(-3) \rho (-5) \land (-5) \rho (-1) \Rightarrow (-3) \rho (-1)

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

(−3)2+(−1)2=9+1=10<25⇒(−3,−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.