Skupovi

Relacije i njihove osobine

Ključne reči: relacija, osobine relacija, refleksivnost, simetričnost, tranzitivnost, antisimetričnost,

Definicija

A2=A×A=a,b:aA, bA
ρA2

Relacija ρ je podskup skupa AxA Dekartovog (kvadrata) proizvoda.

Primer:

A=1,3,6
AxA=1,1,1,3,1,6,3,1,3,3,3,6,6,1,6,3,6,6
ρ={1,1,1,3,1,6,3,3,3,6,6,6} | ρA2,


U ovom slučaju relacija ρ manje ili jednako izgleda ovako: (1≤1), (1≤3), (1≤6), (3≤3), (3≤6), (6≤6).

Osobine relacija

Refleksivnost

(aA): aρa

PREKO USMERENIH GRAFOVA: u svakom čvoru grafa postoji petlja.

Primer:ρ refleksivan, jer za bilo koji član relacije iz skupa A važi 11,33,66

Simetričnost

(a, bA): aρbbρa

PREKO USMERENIH GRAFOVA: ako je svaka grana grafa dvosmerna.

Primer:ρ nije simetričan, zato što da je 3 ≤ 6 [odnosno (3, 6) ∈ ρ], nem proizlazi da je i 6 ≤ 3 [odnosno (6, 3) ∈ ρ].

Tranzitívnost

(a, b,cA): aρbbρcaρc

PREKO USMERENIH GRAFOVA: ako postoji put između dva čvora, onda postoji i duži put.

Példa:ρ je tranzitívan, jer akoj je 1 ≤ 3 i 3 ≤ 6 onda iz ovog sledi da je i 1 ≤ 6.

Antisimetričnost

(a, bA): aρbbρa

PREKO USMERENIH GRAFOVA: ha bármely két különböz® pont között 0 vagy 1 irányban megy él.

Primer:ρ je antisimetričan, jer je svaki broj je manji ili jedak od samog sebe.

Tipovi relacija

  • Relacija ekvivalencije: reflleksivna, simetrična i tranzitivna
  • Relacija poretka: reflleksivna, antisimetrična i tranzitivna
  • Relacija strogog poretka: za bilo koji od a, b ∈ A važi da (a, b) ∈ ρ ili (b, a) ∈ ρ
    PREKO USMERENIH GRAFOVA: postoji linija između svih čvorova.
  • Linearna ili totalna relacija:, relacija poretka i relacija strogog poretka