MATEMANIJA

Pozz, spremam ispit iz diskretne matematike, polako prelazim relacije i preslikavanja, ali imam nekih nedoumica. U vezi relacija, najcesci tip zadataka koji dolazi na ispitu je da se ispitaju svojstva relacije, da li je relacija poretka ili ekvivalencije itd. Malo me svojstva zezaju, znam odrediti da li je relacija refleksivna, ali ostale tri osobine(simetricnost, antisimetricnost, tranzitivnost) vec malo teze. Da li smijem da postavim primjer nekog ispitnog zadatka, samo da vidim kako se radi?
eo jedan primjer:

Neka je dat skupa [inlmath]A=\{1,2,3,4\}[/inlmath] i neka je [inlmath]R[/inlmath] relacija zadana na [inlmath]A\times A[/inlmath] kako slijedi:
[dispmath](x,y)R(z,t)\iff yz\vert xt[/dispmath]
a) Ispitati svojstva relacije
b) naci minimum, maksimum, minimalni element, maksimalni element ako postoje
c) Koji elementi su u relaciji sa [inlmath](2,1)[/inlmath]?

Hajde da vidimo šta ti pravi problem. Koliko sam razumeo, refleksivnost si dokazao.

• Simetričnost ispituješ tako što proveravaš da li važi
  [dispmath](x,y)R(z,t)\;\Longrightarrow\;(z,t)R(x,y)[/dispmath]
  to jest, u ovom slučaju,
  [dispmath]yz\vert xt\;\Longrightarrow\;tx\vert zy[/dispmath]
• Antisimetričnost ispituješ tako što proveravaš da li važi
  [dispmath](x,y)R(z,t)\;\land\;(z,t)R(x,y)\;\Longrightarrow\;(x,y)=(z,t)[/dispmath]
  to jest, u ovom slučaju,
  [dispmath]yz\vert xt\;\land\;tx\vert zy\;\Longrightarrow\;(x,y)=(z,t)[/dispmath]
• Tranzitivnost ispituješ tako što proveravaš da li važi
  [dispmath](x,y)R(z,t)\;\land\;(z,t)R(u,v)\;\Longrightarrow\;(x,y)R(u,v)[/dispmath]
  to jest, u ovom slučaju,
  [dispmath]yz\vert xt\;\land\;tu\vert zv\;\Longrightarrow\;yu\vert xv[/dispmath]

Bi li umeo sad da nastaviš, tj. da proveriš svako od ovih svojstava?

Refleksivnost : DA, zato sto svaki broj je djeljiv sa samim sobom,
SImetricnost: NE, npr [inlmath](1,2)R(1,4)[/inlmath], ali [inlmath](1,4)[/inlmath] nije u relaciji sa [inlmath](1,2)[/inlmath], zato sto [inlmath]4|2[/inlmath],
Antisimetricnost: Nije narusena, zato sto se ne javljaju povratni lukovi,
Tranzitivnost: nzm tranzitivnost, da li je ovo gore u redu?

jelacpp je napisao:Refleksivnost : DA, zato sto svaki broj je djeljiv sa samim sobom,

To, zapravo, dokazujemo na sledeći način:
Proveravamo da li važi [inlmath](x,y)R(x,y)[/inlmath].
Prema definiciji relacije [inlmath]R[/inlmath], to možemo pisati kao [inlmath]xy\vert xy[/inlmath].
E sada, pošto je svaki prirodan broj deljiv samim sobom, to isto važi i za broj [inlmath]xy[/inlmath], pa će važiti [inlmath]xy\vert xy[/inlmath], iz čega zaključujemo da važi refleksivnost.

jelacpp je napisao:SImetricnost: NE, npr [inlmath](1,2)R(1,4)[/inlmath], ali [inlmath](1,4)[/inlmath] nije u relaciji sa [inlmath](1,2)[/inlmath], zato sto [inlmath]4|2[/inlmath],

U redu, naveo si validan kontraprimer, samo rečenicu nisi najbolje formulisao. [inlmath](1,2)[/inlmath] je u relaciji sa [inlmath](1,4)[/inlmath] zbog toga što važi [inlmath]2\vert4[/inlmath], ali [inlmath](1,4)[/inlmath] nije u relaciji sa [inlmath](1,2)[/inlmath] jer ne važi [inlmath]4\vert2[/inlmath].
Ovo podvučeno si izostavio.

jelacpp je napisao:Antisimetricnost: Nije narusena, zato sto se ne javljaju povratni lukovi,

Ne važi antisimetričnost, a kontraprimer bi bio [inlmath](x,y,z,t)=(4,2,2,1)[/inlmath]:
[dispmath](4,2)R(2,1)\;\land\;(2,1)R(4,2)\;\Longrightarrow\;(4,2)=(2,1)[/dispmath]
Desna strana implikacije je očigledno netačna, pa da bi cela implikacija bila netačna potrebno je da leva strana bude tačna:
[dispmath](4,2)R(2,1)\;\land\;(2,1)R(4,2)\\
(2\cdot2)\vert(4\cdot1)\;\land\;(1\cdot4)\vert(2\cdot2)\\
4\vert4\;\land\;4\vert4\\
\top\;\land\;\top\\
\top[/dispmath]
Pošto je leva strana implikacije tačna a desna netačna, tačno implicira netačno, pa je cela implikacija netačna – kontraprimer.

jelacpp je napisao:Tranzitivnost: nzm tranzitivnost, da li je ovo gore u redu?

Znači, kod tranzitivnosti je potrebno ispitati da li za svako [inlmath]x,y,z,t,u,v\in A[/inlmath] važi
[dispmath]yz\vert xt\;\land\;tu\vert zv\;\Longrightarrow\;yu\vert xv[/dispmath]
Ako je [inlmath]a\vert b[/inlmath] i [inlmath]c\vert d[/inlmath], tada važi i [inlmath]ac\vert bd[/inlmath] (osobina deljivosti). Na osnovu toga, iz [inlmath]yz\vert xt\;\land\;tu\vert zv[/inlmath] sledi [inlmath]yztu\vert xtzv[/inlmath].
Budući da kod deljivosti takođe važi i [inlmath]ka\vert kb\iff a\vert b\;(k\in\mathbb{N})[/inlmath], to će iz [inlmath]yztu\vert xtzv[/inlmath] slediti [inlmath]yu\vert xv[/inlmath], čime je dokazano da važi tranzitivnost (i to ne samo za elemente skupa [inlmath]A[/inlmath], već za bilo koje prirodne brojeve).