Nettkurs

Boka

Definisjon

• En binær relasjon (binary relation) fra mengden $S$ til mengden $T$ er en delmengde av $S \times T$.
• En binær relasjon på mengden $S$ er en delmengde av $S^2 = S \times S$.
• Mer generelt, en $n$-ær relasjon ($n$-ary relation) er en delmengde av $A_1 \times ... \times A_n$.

Noen spesielle relasjoner

• Identitetsrelasjonen (identity relation) på $S$, eller likhetsrelasjon, som relaterer alle elementer til seg selv: $\{ \langle x,x\rangle \mid x \in S\}$.
  • Her er identitetsrelasjonen på mengden $\{1,2,3\}$: $\{\lang 1,1\rang, \lang 2,2\rang, \lang 3,3\rang\}$
  • Må alltid være på en mengde
• Den tomme relasjonen (empty relation) fra $S$ til $T$, som ikke relaterer noe elementer til hverandre: $Ø$.
  • Den tomme relasjonen på mengden $\{1,2,3\}$: $Ø$
• Den universelle relasjonen (universal relation) fra $S$ til $T$, som relaterer alle elementer i $S$ til alle elementer i $T$: $S \times T$.
  • Den universelle relasjonen på mengden $\{1,2,3\}$: $\{\lang 1,1\rang, \lang 1,2\rang, \lang 1,3\rang, \lang 2,1\rang, \lang 2,2\rang, \lang 2,3\rang, \lang 3,1\rang, \lang 3,2\rang, \lang 3,3\rang\}$

Universet av relasjoner

Refleksivitet

• En binær relasjon $R$ på mengden $S$ er refleksiv (reflexive) hvis det for alle $x$ i $S$ er slik at $\lang x,x\rang \in R$.

  • La $S$ være mengden $\{1,2,3\}$. Da skal en refleksiv relasjon på den mengden inneholde $\{\lang 1,1\rang, \lang 2,2\rang, \lang 3,3\rang\}$.
  • $\{\lang 1,1\rang, \lang 1,3\rang,\lang 2,2\rang, \lang 3,2\rang,\lang 3,3\rang\}$ er en refleksiv relasjon på $S$.
  • $\{\lang 1,1\rang, \lang 1,2\rang,\lang 1,3\rang\}$ er ikke en refleksiv relasjon på $S$.
  • Eksempler på refleksive relasjoner:

  

Symmetri

• En binær relasjon $R$ på mengden $S$ er symmetrisk (symmetric) hvis det for alle $x,y$ er slik at hvis $\lang x,y\rang \in R$, så $\lang y,x\rang \in R$.

  • La $S$ være mengden $\{a,b,c\}$.
  • Da er $\{\lang a,b\rang, \lang b,a\rang,\lang b,c\rang, \lang c,b\rang\}$ en symmetrisk relasjon på $S$.
  • $\{\lang a,b\rang, \lang b,a\rang,\lang b,c\rang\}$ er ikke en symmetrisk relasjon på $S$.

  

Transitivitet

• En binær relasjon $R$ på mengden $S$ er transitiv (transitive) hvis det for alle $x,y,z$ er slik at hvis $\lang x,y\rang \in R$ og $\lang y,z\rang \in R$ , så $\lang x,z\rang \in R$.

  • La $S$ være mengden $\{1,2,3\}$.
  • $\{\lang 1,2\rang, \lang 2,3\rang,\lang 1,3\rang\}$ er transitiv relasjon på S.
  • $\{\lang 1,2\rang, \lang 2,3\rang\}$ er ikke transitiv.
  • $\{\lang 1,2\rang, \lang 2,1\rang\}$ er ikke transitiv heller, fordi den mangler $\lang 1,1\rang$ og $\lang 2,2\rang$. Så hvis vi går fra $1$ til $2$ og tilbake, da burde vi ha den tredje steg fra $1$ til $1$.
  • Steg kan gå fremover og bak bare mellom to elementer i mengden, ikke mer. Hvis det er mer enn to, da er det alltid en direksjon.
  • Også, når du ser på en mengde, må du telle alle instanser av to-steg hopp, og hvis alle er transitive, da og bare da er hele mengden transitiv.

  

Ekvivalens