06 Relasjoner Flashcards
6.1 Relasjon
En binær relasjon fra mengden S til mengden T er en delmengde av S ⨯ T. En binær relasjon på mengden S er en delmengde av S2 = S ⨯ S. Mer generelt, en n-ær relasjon er en delmengde av A1 ⨯ … ⨯ An, og en n-ær relasjon på en mengde A er en delmengde av An.
6.2 Refleksiv relasjon
En binær relasjon R på mengden S er refleksiv hvis det for alle x i S er slik at 〈x, x〉 ∈ R.
6.3 Symmetrisk relasjon
En binær relasjon R på mengden S er symmetrisk hvis det for alle x, y er slik at hvis 〈x, y〉 ∈ R, så 〈y, x〉 ∈ R.
6.4 Transitiv relasjon
En binær relasjon R på mengden S er transitiv hvis det for alle x, y, z er slik at hvis 〈x, y〉 ∈ R og 〈y, z〉 ∈ R, så 〈x, z〉 ∈ R.
6.5 Ekvivalensrelasjon
En binær relasjon på mengden S er en ekvivalensrelasjon hvis den er refleksiv, symmetrisk og transitiv.
6.6 Anti-symmetrisk relasjon
En binær relasjon R på mengden S er anti-symmetrisk hvis det for alle x, y er slik at hvis 〈x, y〉 ∈ R og 〈y, x〉 ∈ R, så x = y.
6.7 Irrefleksiv relasjon
En binær relasjon R på mengden S er irrefleksiv hvis det ikke er noen x ∈ S slik at 〈x, x〉 ∈ R.
6.8 Partiell ordning
En binær relasjon på mengden S er en partiell ordning hvis den er refleksiv, transitiv og anti-symmetrisk.
6.9 Total ordning
En partiell ordning R på en mengde S kalles en total ordning eller en lineær ordning hvis det for alle x og y i S er slik at xRy eller yRx.
