3201. 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 \in y$ na skupu $A = \{1, 2, \{1, 2\}, \{1, 2, \{1, 2\}\} \}$ ;

REŠENJE ZADATKA

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

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 \rho y \Leftrightarrow x \in y .$ Proveravamo za svaki par elemenata da li prvi element pripada drugom kao njegov član. Na primer, $1 \in \{1, 2\} ,$ pa je $(a_1, a_3) \in \rho .$

\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 ,$ relacija $\rho$ sadrži sledeće uređene parove:

\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 \in A$ važi $x \rho x .$ Pošto nijedan element ne sadrži samog sebe (na primer, broj 1 nije element broja 1, tj. $1 \notin 1$ ), relacija 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 \rho y$ sledi $y \rho x .$ Vidimo da važi $1 \rho \{1, 2\} ,$ ali ne važi obrnuto jer $\{1, 2\} \notin 1 .$ Dakle, relacija nije simetrič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 \rho y$ i $y \rho x$ sledi $x = y .$ U našoj relaciji ne postoji nijedan par različitih elemenata za koje istovremeno važi $x \rho y$ i $y \rho x .$ Zbog toga je uslov ispunjen (premisa implikacije je uvek netačna, pa je implikacija tačna), te relacija jeste antisimetrič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 \rho y$ i $y \rho z$ sledi $x \rho z .$ Proveravamo sve lance dužine 2 u relaciji:

\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\}\})$ i $(2, \{1, 2, \{1, 2\}\})$ ) već prisutni u relaciji $\rho ,$ zaključujemo da relacija jeste tranzitivna.

\rho \text{ jeste tranzitivna}

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

\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$ predstave kao čvorovi, a usmerene grane (strelice) se povlače od čvora $x$ ka čvoru $y$ ako važi $x \rho y .$ Skup čvorova $V$ i skup usmerenih grana $E$ su:

\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}

75.c