3188.

68

TEKST ZADATKA

Da li je relacija ρ \rho određena tablicom relacija ekvivalencije ili poretka?

ρ1231⊥⊤⊤2⊤⊥⊥3⊤⊤⊤\begin{array}{c|ccc} \rho & 1 & 2 & 3 \\ \hline 1 & \bot & \top & \top \\ 2 & \top & \bot & \bot \\ 3 & \top & \top & \top \end{array}
REŠENJE ZADATKA

Da bi relacija bila relacija ekvivalencije, mora biti refleksivna, simetrična i tranzitivna. Da bi bila relacija poretka, mora biti refleksivna, antisimetrična i tranzitivna.

Prvo proveravamo refleksivnost. Relacija je refleksivna ako za svaki element skupa važi da je u relaciji sa samim sobom.

(∀x∈A)  xρx(\forall x \in A) \; x \rho x

Elementi na glavnoj dijagonali tablice nam pokazuju da li je relacija refleksivna. Vidimo da za elemente 1 1 i 2 2 važi:

1ρ1=⊥,2ρ2=⊥1 \rho 1 = \bot, \quad 2 \rho 2 = \bot

Pošto relacija nije refleksivna, ona automatski ne može biti ni relacija ekvivalencije ni relacija poretka. Ipak, radi potpunosti, proverićemo i ostale osobine.

Proveravamo simetričnost. Relacija je simetrična ako za svaka dva elementa važi da ako je prvi u relaciji sa drugim, onda je i drugi u relaciji sa prvim.

(∀x,y∈A)  xρy  ⟹  yρx(\forall x, y \in A) \; x \rho y \implies y \rho x

Iz tablice vidimo da je element 3 3 u relaciji sa 2, 2 , ali 2 2 nije u relaciji sa 3. 3 . Dakle, relacija nije simetrična.

3ρ2=⊤∧2ρ3=⊥3 \rho 2 = \top \land 2 \rho 3 = \bot

Proveravamo antisimetričnost. Relacija je antisimetrična ako iz činjenice da su dva različita elementa međusobno u relaciji sledi da su oni zapravo isti element.

(∀x,y∈A)  xρy∧yρx  ⟹  x=y(\forall x, y \in A) \; x \rho y \land y \rho x \implies x = y

Iz tablice vidimo da su elementi 1 1 i 2 2 međusobno u relaciji, iako su različiti. Dakle, relacija nije antisimetrična.

1ρ2=⊤∧2ρ1=⊤ali1≠21 \rho 2 = \top \land 2 \rho 1 = \top \quad \text{ali} \quad 1 \neq 2

Proveravamo tranzitivnost. Relacija je tranzitivna ako iz činjenice da je prvi element u relaciji sa drugim, a drugi sa trećim, sledi da je prvi u relaciji sa trećim.

(∀x,y,z∈A)  xρy∧yρz  ⟹  xρz(\forall x, y, z \in A) \; x \rho y \land y \rho z \implies x \rho z

Iz tablice vidimo da je 2 2 u relaciji sa 1, 1 , i 1 1 je u relaciji sa 3, 3 , ali 2 2 nije u relaciji sa 3. 3 . Dakle, relacija nije tranzitivna.

2ρ1=⊤∧1ρ3=⊤ali2ρ3=⊥2 \rho 1 = \top \land 1 \rho 3 = \top \quad \text{ali} \quad 2 \rho 3 = \bot

Konačan zaključak: pošto data relacija ne ispunjava potrebne uslove (nije refleksivna, nije simetrična, nije antisimetrična i nije tranzitivna), ona nije ni relacija ekvivalencije ni relacija poretka.