Monday, September 21, 2009

DiMS Uge 4

Relationer

Vi skal have relationer på palds før vi går videre. Funktioner, osv.
Vi studerer relationer vha. forskellige måder at udtrykke dem på, hhv. mængder, udsagne, grafer og matricer.

Mængder


  • Det kartesiske produkt A\times B=\{(A,B)|a\in A,\ \ \ b\in B\}
  • DEF: En relation fra A til B er en delmængde R\leq A\times B, hvis A=B så siger vi oftest "a relation i A"
R0 = {(j,m)}

DOM -> domain(dan: domæne)
RAN -> Range(dan: billedet)

DEF:
DOM(R) = \{a\in A|\ \exist b\in B:\ aRb}
RAN(R) = \{b\in B|\ \exist a\in A: aRb}

DOM(R0) = {j, f, m}
RAN(R0) = {m,i,c}

Udsagn

OBServation: En relation fra A til B definerer åbne udsagn (a.b)\in R eller (a.b)\notin R
NOTation: Vi vil ofte skrive dette som: aRb eller a\cancel{R}b
-------------
Vi forkorter nu, altså bruger en simplere notation:

OBS: En relation fra A til B definerer åbne udsagn aRb\Leftrightarrow(a,b)\in R.
DEF: En relation R i A er:
  • Refleksiv, hvis \forall a\in A: aRa
    • R0? f\cancel{R_0}f -> NEJ
  • Symetrisk, hvis \forall a,\ b\in A: aRb\Rightarrow bRa
    • R0? -> NEJ
  • Transitiv, hvis \forall a,\ b,\ c\in A\ [aRb\wedge bRc] \Rightarrow aRc
    • R0? -> NEJ da j er ikke forældre til c, selvom j->m->c
  • Antisymmetrisk, hvis 
    • R0? -> JA!

Grafer

Digraph -> directed graph -> den orienterede graf for R
Hvis R er en relation i A, hvor A er endelig, så definerer vi en graf med knuder hvor a\in A og med kanter fra til netop når aRb.

Refleksiv
Symmetrisk
Transitiv
Antisymmetrisk

Matricer

En relation fra A=\{a_1,a_2,a_3,\ \ldots\ ,a_n\} til B=\{b_1,b_2, b_3,\ \ldots\ ,b_n\} definerer en m\times n boolsk matrix M_R=\{m_{ij}\}

m_{ij}=\left {{0\ \ \ hvis\ \ \ a_i\cancel{R}b_j\over 1\ \ \ hvis\ \ \ a_iRb_i}
Refleksiv
Symmetrisk
Transitiv
Antisymmetrisk
1
?
?
?
1
?
?
?
1
\
0
1
0
\
0
1
0
\



R0 opstillet som matrix:

j
f
m
c
i
j
0
0
1
0
0
f
0
0
0
1
1
m
0
0
0
1
1
c
0
0
0
0
0
i
0
0
0
0
0

Eksempler

Hvis ikke relationen er symetrisk, er den ikke nødvendigvis antisymmetrisk!!
Givet et sæt: A=\{1,2,3,4,5,6,7\}
Analyserer vi nu følgende udsagn:

aR_1b\Leftrightarrow a|b         -> a|b\wedge b|c\Right a|c -> ergo er vi transitive
aR_2b\Leftrightarrow f_3(a)=f_3(b)
aR_3b\Leftrightarrow gcd(a,b) =1

Jeg orker ikke at tegne den orienterede graf, men vi bruger den altså til at bestemme om R1

For at løse R2, bruger vi nu en anden metode:
Vi tager udgangspunkt i en matrixrelation:


1
2
0
1
2
0
1


1
2
3
4
5
6
7
1
1
1
0
0
1
0
0
1
2
2
0
1
0
0
1
0
0
0
3
0
0
1
0
0
1
0
1
4
1
0
0
1
0
0
1
2
5
0
1
0
0
1
0
0
0
6
0
0
1
0
0
1
0
1
7
1
0
0
1
0
0
1

Resultaterne opstiller vi nu i et tabel:


REF
SYM
TRAN
ANTI
R1
T
F (1,2)
T
T
R2
T
T
T
F (1,4)
R3
F
F
F
F

Dom(R1) = A = Ran(R1)

Posted by at No comments:
Subscribe to: Comments (Atom)