Relacija

Iz MaFiRaWiki

(Preusmerjeno iz Binarna relacija)

Relacija R med množicama A in B je podmnožica kartezičnega produkta A × B. Trojica (A,B,R) se imenuje incidenčna struktura. Relacijo lahko opišemo z njeno incidenčno matriko. Zanimive so tudi operacije nad relacijami.

Oznaka R[x] označuje množico naslednikov elementa x ∈ A.

  • R[x] := {y ∈ A| x R y}

Če je A = B, rečemo, da je R dvojiška relacija, oziroma rečemo, da je (A,R) množica urejena z relacijo.

V relacijskih zbirkah igrajo pomembno vlogo tudi večmestne relacije, ki so podmnožice kartezičnega produkta A1 × A2 × ... × An. Pri tem se n-terica (A1, A2 , ... , An) imenuje signatura n-mestne relacije.

1-mestna relacija je v bistvu podmnožica ali predikat.

Če sta R is S relaciji z isto signaturo in je RS, pravimo, da je relacija R bolj groba od relacije S, oz. da je S finejša od R.

Lastnosti relacij

Relacija R⊆ A×A je:

  • Refleksivna: \forallx\inA. xRx
  • Simetrična: \forallx, y\inA. xRy\implies yRx
  • Antisimetrična: \forallx, y\inA. xRy\land yRx \implies x=y
  • Tranzitivna: \forallx, y, z\inA. xRy \land yRz\implies xRz
  • Irefleksivna: \forallx\inA. \lnot(xRx)
  • Asimetrična: \forallx, y\inA. xRy\implies \lnot(yRx)
  • Sovisna: \forallx, y\inA.\lnot(x=y)\implies (xRy)\lor(yRx)
  • Strogo sovisna: \forallx, y \in . (xRy)\lor(yRx)

Glej tudi

Osebna orodja