3201.

75.c

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⇔x∈y x \rho y \Leftrightarrow x \in y na skupu A={1,2,{1,2},{1,2,{1,2}}} A = \{1, 2, \{1, 2\}, \{1, 2, \{1, 2\}\} \} ;

REŠENJE ZADATKA

Da bismo lakše zapisivali elemente, obeležimo elemente skupa A A na sledeći način:

A={a1,a2,a3,a4} gde je a1=1,a2=2,a3={1,2},a4={1,2,{1,2}}A = \{a_1, a_2, a_3, a_4\} \text{ gde je } a_1 = 1, a_2 = 2, a_3 = \{1, 2\}, a_4 = \{1, 2, \{1, 2\}\}

Relacija ρ \rho je definisana uslovom xρy⇔x∈y. x \rho y \Leftrightarrow x \in y . Proveravamo za svaki par elemenata da li prvi element pripada drugom kao njegov član. Na primer, 1∈{1,2}, 1 \in \{1, 2\} , pa je (a1,a3)∈ρ. (a_1, a_3) \in \rho .

ρ={(a1,a3),(a1,a4),(a2,a3),(a2,a4),(a3,a4)}\rho = \{(a_1, a_3), (a_1, a_4), (a_2, a_3), (a_2, a_4), (a_3, a_4)\}

Zapisano sa originalnim elementima skupa A, A , relacija ρ \rho sadrži sledeće uređene parove:

ρ={(1,{1,2}),(1,{1,2,{1,2}}),(2,{1,2}),(2,{1,2,{1,2}}),({1,2},{1,2,{1,2}})}\rho = \{(1, \{1, 2\}), (1, \{1, 2, \{1, 2\}\}), (2, \{1, 2\}), (2, \{1, 2, \{1, 2\}\}), (\{1, 2\}, \{1, 2, \{1, 2\}\})\}

Ispitujemo **refleksivnost**. Relacija je refleksivna ako za svako x∈A x \in A važi xρx. x \rho x . Pošto nijedan element ne sadrži samog sebe (na primer, broj 1 nije element broja 1, tj. 1∉1 1 \notin 1 ), relacija nije refleksivna.

(∃x∈A)¬(xρx)  ⟹  ρ nije refleksivna(\exists x \in A) \neg(x \rho x) \implies \rho \text{ nije refleksivna}

Ispitujemo **simetričnost**. Relacija je simetrična ako iz xρy x \rho y sledi yρx. y \rho x . Vidimo da važi 1ρ{1,2}, 1 \rho \{1, 2\} , ali ne važi obrnuto jer {1,2}∉1. \{1, 2\} \notin 1 . Dakle, relacija nije simetrična.

(1,{1,2})∈ρ∧({1,2},1)∉ρ  ⟹  ρ nije simetricˇna(1, \{1, 2\}) \in \rho \land (\{1, 2\}, 1) \notin \rho \implies \rho \text{ nije simetrična}

Ispitujemo **antisimetričnost**. Relacija je antisimetrična ako iz xρy x \rho y i yρx y \rho x sledi x=y. x = y . U našoj relaciji ne postoji nijedan par različitih elemenata za koje istovremeno važi xρy x \rho y i yρx. y \rho x . Zbog toga je uslov ispunjen (premisa implikacije je uvek netačna, pa je implikacija tačna), te relacija jeste antisimetrična.

(∀x,y∈A)(xρy∧yρx  ⟹  x=y)  ⟹  ρ jeste antisimetricˇna(\forall x, y \in A) (x \rho y \land y \rho x \implies x = y) \implies \rho \text{ jeste antisimetrična}

Ispitujemo **tranzitivnost**. Relacija je tranzitivna ako iz xρy x \rho y i yρz y \rho z sledi xρz. x \rho z . Proveravamo sve lance dužine 2 u relaciji:

1ρ{1,2}∧{1,2}ρ{1,2,{1,2}}  ⟹  1ρ{1,2,{1,2}}2ρ{1,2}∧{1,2}ρ{1,2,{1,2}}  ⟹  2ρ{1,2,{1,2}}\begin{aligned} 1 \rho \{1, 2\} \land \{1, 2\} \rho \{1, 2, \{1, 2\}\} &\implies 1 \rho \{1, 2, \{1, 2\}\} \\ 2 \rho \{1, 2\} \land \{1, 2\} \rho \{1, 2, \{1, 2\}\} &\implies 2 \rho \{1, 2, \{1, 2\}\} \end{aligned}

Pošto su svi dobijeni parovi ( (1,{1,2,{1,2}}) (1, \{1, 2, \{1, 2\}\}) i (2,{1,2,{1,2}}) (2, \{1, 2, \{1, 2\}\}) ) već prisutni u relaciji ρ, \rho , zaključujemo da relacija jeste tranzitivna.

ρ jeste tranzitivna\rho \text{ jeste tranzitivna}

Pravimo tablicu relacije ρ. \rho . U preseku reda x x i kolone y y pišemo 1 ako važi xρy x \rho y (odnosno x∈y x \in y ), a 0 ako ne važi.

ρ12{1,2}{1,2,{1,2}}1001120011{1,2}0001{1,2,{1,2}}0000\begin{array}{c|cccc} \rho & 1 & 2 & \{1, 2\} & \{1, 2, \{1, 2\}\} \\ \hline 1 & 0 & 0 & 1 & 1 \\ 2 & 0 & 0 & 1 & 1 \\ \{1, 2\} & 0 & 0 & 0 & 1 \\ \{1, 2, \{1, 2\}\} & 0 & 0 & 0 & 0 \end{array}

Graf relacije se crta tako što se elementi skupa A A predstave kao čvorovi, a usmerene grane (strelice) se povlače od čvora x x ka čvoru y y ako važi xρy. x \rho y . Skup čvorova V V i skup usmerenih grana E E su:

V={1,2,{1,2},{1,2,{1,2}}}E={(1,{1,2}),(1,{1,2,{1,2}}),(2,{1,2}),(2,{1,2,{1,2}}),({1,2},{1,2,{1,2}})}\begin{aligned} V &= \{1, 2, \{1, 2\}, \{1, 2, \{1, 2\}\} \} \\ E &= \{(1, \{1, 2\}), (1, \{1, 2, \{1, 2\}\}), (2, \{1, 2\}), (2, \{1, 2, \{1, 2\}\}), (\{1, 2\}, \{1, 2, \{1, 2\}\})\} \end{aligned}