Relasjoner

[executer]

La R være en relasjon på mengden {1,2,3,4,5,6} definert ved

R = {(a,b) | a går opp i b}.

(a) Skriv relasjonen R på listeform.
(b) Representer R med en matrise og en orientert graf.
(c) Avgjør om R er refleksiv, symmetrisk, antisymmetrisk og/eller transitiv.

[Solar Plexsus]

a)

R = {(1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (2,2), (2,4), (2,6), (3,3), (3,6), (4,4), (5,5), (6,6)}.


b)

R representert som en matrise (Her står U for usann og S for sann):

Kode: Velg alt

[S S S S S S]
[U S U S U S]
[U U S U U S]
[U U U S U U]
[U U U U S U]
[U U U U U S]

R representert som en orientert graf er for vanskelig å tegne.


c)

* aRa fordi a alltid går opp i a, så R er refleksiv.
* Dersom aRb og bRa, vil a≤b og b≤a, dvs. at a=b. M.a.o. er R antisymmetrisk.
* Hvis aRb og bRc, vil a gå opp i b som går opp i c, som igjen medfører at a går opp i c, dvs. at aRc. Altså er R transitiv.

[Gjest]

E er vel ikke transitiv?

Fordi det er ikke slik at alle relasjonene av (a,b) og (b,c) er med i (a,c). For eksempel har vi (1,2) og (2,2), men vi har ikke (2,1).

Har du et eksempel på at R er transitiv?

[Solar Plexsus]

I ditt eksempel med (a,b)=(1,2) og (b,c)=(2,2) får vi at (a,c) = (1,2) (ikke (2,1) som du hevder). Og 1 går da vitterlig opp i 2. Altså er R transitiv i dette tilfellet.