Upload
cindy
View
23
Download
3
Embed Size (px)
DESCRIPTION
Eigenschaften von Relationen und deren Überprüfung; Definition von Ordnung. Garnier, R. & Taylor, J. (1997). Discrete Mathematics for New Technology. Bristol: Institute of Physics Publishing. Definition von Relation. - PowerPoint PPT Presentation
Citation preview
1
Eigenschaften von Relationen und Eigenschaften von Relationen und deren Überprüfung; Definition von deren Überprüfung; Definition von
OrdnungOrdnung
Garnier, R. & Taylor, J. (1997). Discrete Mathematics for New Technology. Bristol: Institute of Physics Publishing
2
Definition von RelationDefinition von Relation
Die binäre Relation R von A nach B (oder
zwischen A und B) ist eine Teilmenge des
kartesischen Produktes A B.
Man schreibt aRb, wenn (a, b) R.
3
BeispielBeispiel
R = {(a, b): a ist Hauptstadt von b}
A = {Rom, Paris, Berlin, Wien};
B = {I, F, D, A}
A B = {(Rom, I), (Rom, F), (Rom, D), (Rom, A) … }
R = {(Rom, I), (Paris, F), (Berlin, D), (Wien, A)}
(Rom)R(I), (Paris)R(F), (Berlin)R(D), (Wien)R(A)
4
Darstellung von Relationen IDarstellung von Relationen I
Koordinatengitter
R = {(a, b): a < b}A = B = {1, 2, 3, 4, 5}
5
Darstellung von Relationen IIDarstellung von Relationen II
1
5
4
2
3
1 2 3 4 5
1 2 3 4 5
Gerichtete Graphen
R = {(a, b): a < b}A = B = {1, 2, 3, 4, 5}
6
Darstellung von Relationen IIIDarstellung von Relationen III
Binäre Matrix
R = {(a, b): a < b}A = B = {1, 2, 3, 4, 5}
00000
10000
11000
11100
11110
7
Eigenschaften von RelationenEigenschaften von Relationen
Reflexivität aRa für alle a, b, c A
Irreflexivität aRa
Symmetrie aRb bRa
Asymmetrie aRb bRa
Antisymmetrie
aRb bRa a=b
Transitivität aRb bRc aRc
Neg. Trans. aRb bRc aRc
Konnektivität
aRb bRa
Schw. Konn. aRb bRa a=b
8
Überprüfung der ReflexivitätÜberprüfung der Reflexivität
aRa
gerichteter Graph Pfeil zu sich selbst
binäre Matrix Zellen der Haupt-
diagonale mit 1 besetzt
1
1
1
1
1
0000
0000
0000
0000
0000
9
Überprüfung der SymmetrieÜberprüfung der Symmetrie
aRb bRa
gerichteter Graph nur bidirektionale Pfeile
binäre Matrix symmetrisch entlang der
Hauptdiagonale
10000
0100
0010
0010
0001
1
1
1
1
10
Überprüfung der Überprüfung der AntisymmetrieAntisymmetrie
aRb bRa a=b
gerichteter Graph nur unidirektionale Pfeile
binäre Matrix Wenn eine beliebige
Zelle (i, j) 1 enthält, muss
die Zelle (j, i) 0 enthalten.
10000
0100
0010
0010
0001
0
1
1
0
11
Überprüfung der TransitivitätÜberprüfung der Transitivität
aRb bRc aRc
10000
01000
010
00010
0001
11
1
a b
c
12
Definition von OrdnungDefinition von Ordnung
Als Ordnung oder Ordnungsrelation wird jede
transitive Relation bezeichnet.
13
DankeDanke
Folien, Text und Handout des Referats stehen auf der Homepage zum Download bereit.