3199.

75.d

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⇔3∣x+y x \rho y \Leftrightarrow 3 \mid x + y na skupu A={1,2,3,4,5}. A = \{1, 2, 3, 4, 5\} .

REŠENJE ZADATKA

Da bismo ispitali osobine relacije, prvo ćemo odrediti sve uređene parove (x,y) (x, y) koji pripadaju relaciji ρ. \rho . Uslov je da zbir x+y x + y bude deljiv sa 3, pri čemu x,y∈A. x, y \in A .

Proveravamo sve moguće kombinacije elemenata iz skupa A A i izdvajamo one čiji je zbir deljiv sa 3:

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

**Refleksivnost:** Relacija je refleksivna ako za svako x∈A x \in A važi xρx. x \rho x . U našem slučaju, za x=1, x = 1 , zbir 1+1=2 1 + 1 = 2 nije deljiv sa 3, pa (1,1)∉ρ. (1, 1) \notin \rho .

Relacija nije refleksivna.\text{Relacija nije refleksivna.}

**Simetričnost:** Relacija je simetrična ako iz xρy x \rho y sledi yρx. y \rho x . Ako 3∣(x+y), 3 \mid (x + y) , onda zbog komutativnosti sabiranja važi i 3∣(y+x). 3 \mid (y + x) .

Relacija jeste simetricˇna.\text{Relacija jeste simetrična.}

**Antisimetričnost:** Relacija je antisimetrična ako iz xρy x \rho y i yρx y \rho x sledi x=y. x = y . Imamo da (1,2)∈ρ (1, 2) \in \rho i (2,1)∈ρ, (2, 1) \in \rho , ali 1≠2. 1 \neq 2 .

Relacija nije antisimetricˇna.\text{Relacija nije antisimetrična.}

**Tranzitivnost:** Relacija je tranzitivna ako iz xρy x \rho y i yρz y \rho z sledi xρz. x \rho z . Imamo da (1,2)∈ρ (1, 2) \in \rho i (2,4)∈ρ, (2, 4) \in \rho , ali (1,4)∉ρ (1, 4) \notin \rho jer 1+4=5 1 + 4 = 5 nije deljivo sa 3.

Relacija nije tranzitivna.\text{Relacija nije tranzitivna.}

Graf relacije se crta tako što se postave čvorovi za svaki element skupa A A i povuku usmerene grane od x x do y y za svaki par (x,y)∈ρ. (x, y) \in \rho . Zbog simetričnosti, sve grane između različitih čvorova su dvosmerne, a postoji samo jedna petlja (na čvoru 3).

Tablica relacije ρ \rho (gde ⊤ \top označava da su elementi u relaciji, a ⊥ \bot da nisu) izgleda ovako:

ρ123451⊥⊤⊥⊥⊤2⊤⊥⊥⊤⊥3⊥⊥⊤⊥⊥4⊥⊤⊥⊥⊤5⊤⊥⊥⊤⊥\begin{array}{|c|ccccc|}\hline\rho & 1 & 2 & 3 & 4 & 5 \\\hline1 & \bot & \top & \bot & \bot & \top \\2 & \top & \bot & \bot & \top & \bot \\3 & \bot & \bot & \top & \bot & \bot \\4 & \bot & \top & \bot & \bot & \top \\5 & \top & \bot & \bot & \top & \bot \\\hline\end{array}