3202.

75.b

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=(y−1)2 x \rho y \Leftrightarrow x = y \lor x = (y - 1)^2 na skupu A={0,1,2,3} A = \{0, 1, 2, 3\} ;

REŠENJE ZADATKA

Prvo ćemo odrediti sve uređene parove (x,y) (x, y) koji pripadaju relaciji ρ. \rho . Uslov je x=y x = y ili x=(y−1)2 x = (y - 1)^2 za elemente iz skupa A. A .

A={0,1,2,3}A = \{0, 1, 2, 3\}

Iz uslova x=y x = y dobijamo parove gde su prva i druga koordinata jednake:

ρ1={(0,0),(1,1),(2,2),(3,3)}\rho_1 = \{(0,0), (1,1), (2,2), (3,3)\}

Iz uslova x=(y−1)2 x = (y - 1)^2 računamo vrednosti x x za svako y∈A: y \in A :

y=0⇒x=(0−1)2=1⇒(1,0)y=1⇒x=(1−1)2=0⇒(0,1)y=2⇒x=(2−1)2=1⇒(1,2)y=3⇒x=(3−1)2=4∉A\begin{aligned} y = 0 &\Rightarrow x = (0 - 1)^2 = 1 \Rightarrow (1,0) \\ y = 1 &\Rightarrow x = (1 - 1)^2 = 0 \Rightarrow (0,1) \\ y = 2 &\Rightarrow x = (2 - 1)^2 = 1 \Rightarrow (1,2) \\ y = 3 &\Rightarrow x = (3 - 1)^2 = 4 \notin A \end{aligned}

Unijom ova dva skupa parova dobijamo konačan skup elemenata relacije ρ: \rho :

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

Pravimo tablicu relacije ρ. \rho . U redovima su vrednosti x, x , a u kolonama vrednosti y. y . Upisujemo 1 ako su u relaciji, a 0 ako nisu.

00
11
22
33
00
11
11
00
00
11
11
11
11
00
22
00
00
11
00
33
00
00
00
11

Ispitujemo refleksivnost. Relacija je refleksivna ako za svako x∈A x \in A važi (x,x)∈ρ. (x,x) \in \rho .

(0,0),(1,1),(2,2),(3,3)∈ρ⇒Relacija jeste refleksivna.(0,0), (1,1), (2,2), (3,3) \in \rho \Rightarrow \text{Relacija jeste refleksivna.}

Ispitujemo simetričnost. Relacija je simetrična ako iz (x,y)∈ρ (x,y) \in \rho sledi (y,x)∈ρ. (y,x) \in \rho .

(1,2)∈ρ, ali (2,1)∉ρ⇒Relacija nije simetricˇna.(1,2) \in \rho, \text{ ali } (2,1) \notin \rho \Rightarrow \text{Relacija nije simetrična.}

Ispitujemo antisimetričnost. Relacija je antisimetrična ako iz (x,y)∈ρ (x,y) \in \rho i (y,x)∈ρ (y,x) \in \rho sledi x=y. x = y .

(1,0)∈ρ i (0,1)∈ρ, ali 1≠0⇒Relacija nije antisimetricˇna.(1,0) \in \rho \text{ i } (0,1) \in \rho, \text{ ali } 1 \neq 0 \Rightarrow \text{Relacija nije antisimetrična.}

Ispitujemo tranzitivnost. Relacija je tranzitivna ako iz (x,y)∈ρ (x,y) \in \rho i (y,z)∈ρ (y,z) \in \rho sledi (x,z)∈ρ. (x,z) \in \rho .

(0,1)∈ρ i (1,2)∈ρ, ali (0,2)∉ρ⇒Relacija nije tranzitivna.(0,1) \in \rho \text{ i } (1,2) \in \rho, \text{ ali } (0,2) \notin \rho \Rightarrow \text{Relacija nije tranzitivna.}

Graf relacije se crta tako što se postave čvorovi za svaki element skupa A A (0, 1, 2, 3) i povuku usmerene grane (strelice) od čvora x x ka čvoru y y za svaki par (x,y)∈ρ. (x,y) \in \rho . Na osnovu skupa parova, postoje petlje u svakom čvoru (zbog refleksivnosti), dvosmerna grana između 0 i 1, i jednosmerna grana od 1 ka 2.