Relationen und Funktionen (Teil II) Florian Finkfinkf/mm/slides/07_relationsII.pdfCentrum f ur Informations- und Sprachverarbeitung (CIS) 2. Juni 2014 Florian Fink Mathematische Grundlagen

Operationen auf RelationenZusammenfassung

Mathematische Grundlagen der ComputerlinguistikRelationen und Funktionen (Teil II)

Florian Fink

Centrum fur Informations- und Sprachverarbeitung (CIS)

2. Juni 2014

Florian Fink Mathematische Grundlagen der Computerlinguistik


Operationen auf RelationenUmkehrrelationKomposition von RelationenKetten und Zyklen

Table of Contents

1 Operationen auf RelationenOperationen auf RelationenUmkehrrelationKomposition von RelationenKetten und Zyklen

2 Zusammenfassung




Operationen auf Relationen

Ebenso wie bei Mengen, gibt es einige besondere Operationen aufRelationen. Diese Operationen erlauben es aus bestehendenRelationen neue Relationen zu erzeugen.Zwei Operationen, Komposition und Umkehrung sind hierbei vonvorrangiger Bedeutung.




Umkehrrelation

Definition Umkehrrelation

Sei R ⊆ A× B eine zweistellige Relation. Die MengeR−1 := {〈y , x〉|R(x , y)} heißt die zu R inverse Relation oder dieUmkehrrelation von R.

Ist Y ⊆ B, so heißt R−1(Y ) das Urbild von Y unter R.




Beispiel Umkehrrelation

Ist eine Relation durch Pfeile dargestellt, so ergibt sich die inverseRelation R−1 einfach durch die Umkehrung der Pfeile.

Abbildung : Die Relation R

Abbildung : Umkehrrelation R−1




Urbild

Abbildung : Die Relation R

Die grauen Elemente in der Abbildung sind das Bild R({1, 2, 3}).Die weißen Elemente in der Abbildung sind das UrbildR−1({a, c , d , f }).




Beispiel Umkehrrelation

Ist eine Relation durch eine Matrix dargestellt, ergibt sich dieinverse Relation durch Spiegelung an ihrer Diagonalen (bzw. durchVertauschung der Zeilen und Spalten).

R 1 2 3 4 5

1 0 0 1 0 1

2 0 0 0 0 0

3 0 0 0 1 1

4 0 0 0 0 0

5 0 0 1 0 0

R 1 2 3 4 5

1 0 0 0 0 0

2 0 0 0 0 0

3 1 0 0 0 1

4 0 0 1 0 0

5 1 0 1 0 0




Weitere Beispiele

Werden Relationen zur Formalisierung von transitiven Verben,wie kennen oder lieben verwendet, ergibt sich die Inversedurch Passivbildung. So entspricht z.B lieben−1 dem Passivwird geliebt von.

Sei A eine Menge von Personen, und K ⊆ A× A dieKinderbeziehung, dann ist die Inverse K−1 dieElternbeziehung E und E = K−1.




Umkehrrelationen

Lemma Umkehrrelation

Es seien R ⊆ A× B und S ⊆ A× B zweistellige Relationen. Danngilt stets:

(R−1)−1 = R

(R ∪ S)−1 = R−1 ∪ S−1

(R ∩ S)−1 = R−1 ∩ S−1




Beweis

Zu zeigen:(R ∪ S)−1 = R−1 ∪ S−1

Sei 〈b, a〉 ∈ (R ∪ S)−1. Dann gilt 〈a, b〉 ∈ (R ∪ S) und somit〈a, b〉 ∈ R oder 〈a, b〉 ∈ S .

Falls 〈a, b〉 ∈ R gilt auch 〈b, a〉 ∈ R−1.

Falls 〈a, b〉 ∈ S gilt auch 〈b, a〉 ∈ S−1.

Es gilt daher immer 〈b, a〉 ∈ R−1 ∪ S−1. Die Umkehrung folgtdann analog dazu




Komposition von Relationen

Definition Komposition

Es seien R ⊆ A× B und S ⊆ B × C zwei Relationen. Die Menge

R ◦ S := {〈a, c〉 ∈ A× C |∃b ∈ B : R(a, b) ∧ S(b, c)}

heißt das Produkt von R und S oder die Komposition von R und S .

Fur das n-fache Produkt R ◦ R ◦ · · · ◦ R schreibt man ahnlich wiebeim kartesischen Proukt kurz Rn (fur n ≥ 1).




Beispiel Komposition von Relationen

Offensichtlich ist mit R ⊆ A× B und S ⊆ B × C auch R ◦ Swieder eine Relation. Es gilt: R ◦ S ⊆ A× C .Das folgende Bild zeigt die Komposition zweier Relationen:

Abbildung : Die Relation R ◦ S





Sind A,B,C endliche Mengen, mit m, n, l Elementen konnen dieRelationen R ⊆ A×B und S ⊆ B × C durch die Matrizen MR undMS reprasentiert werden.Die Matrix die die Relation darstellt, die das Ergebnis derKomposition von R ◦ S ist, kann durch eine spezielle Art derMatrixmultiplikation aus MR und MS berechnet werden.M hat dann m Zeilen und l Spalten. Der Eintrag M[i , j ] ergibt sichaus dem Maximum uber alle Produkte MR [i , k] ·MS [k , j ] (fur1 ≤ k ≤ n).





R a b c d

0 0 0 0 01 1 1 0 02 0 1 1 03 0 0 0 04 0 0 1 0

×

S 5 6 7 8 9

a 0 0 0 0 0b 1 0 0 0 0c 0 0 0 0 1d 0 0 1 1 0

=

R ◦ S 5 6 7 8 9

0 0 0 0 0 01 1 0 0 0 02 1 0 0 0 13 0 0 0 0 04 0 0 0 0 1

Mit M[i , j ] =

nmax1

(MR [i , k] ·MS [k , j ]).





R a b c d

0 0 0 0 01 1 1 0 02 0 1 1 03 0 0 0 04 0 0 1 0

×

S 5 6 7 8 9

a 0 0 0 0 0b 1 0 0 0 0c 0 0 0 0 1d 0 0 1 1 0

=

R ◦ S 5 6 7 8 9

0 0 0 0 0 01 1 0 0 0 02 1 0 0 0 13 0 0 0 0 04 0 0 0 0 1





Die Komposition von einfachen Verwandschaftbeziehungen1

kann verwendet werden, um weitere Komplexere Beziehungenzu definieren. So ist die Komposition der Vaterbeziehung mitder Elternbeziehung die Großvaterbeziehung. Die Kompositionder Kinderbeziehung mit sich selbst ergibt dann dieEnkelbeziehung.

Die Komposition der Relation “kennen” mit sich selbst ergibtdann die Relation der Personen, die eine Person uber eineandere kennt.

1Kinderbeziehung, Elternbeziehung, Vater- Mutterbeziehung usw.Florian Fink Mathematische Grundlagen der Computerlinguistik



Monotonie der Komposition

Lemma Monotonie der Komposition

Es seien A,B,C Mengen. Fur jeden Index i ∈ I ∪ {1, 2} seien stetsRi ⊆ A× B und Si ⊆ B × C Relationen. Es gilt:

R1 ⊆ R2 ∧ S1 ⊆ S2 → R1 ◦ S1 ⊆ R2 ◦ S2

R ⊆ A× B → R ◦ (⋃i∈I

Si ) =⋃i∈I

(R ◦ Si )

S ⊆ B × C → (⋃i∈I

Ri ) ◦ S =⋃i∈I

(Ri ◦ S)




Assoziativitat der Komposition

Lemma Assoziativitat der Komposition

Die Komposition zweistelliger Relationen ist assoziativ. SindR ⊆ A× B, S ⊆ B × C und T ⊆ C × D Relationen, so gilt

(R ◦ S) ◦ T = R ◦ (S ◦ T )

Beweis: Aus der Definition der Komposition folgt direkt:R ◦ (S ◦ T ) ⊆ A× D. Ebenso gilt (R ◦ S) ◦ T ⊆ A× D.Fur alle a ∈ A und d ∈ D gilt:

〈a, d〉 ∈ R ◦ (S ◦ T )⇔ ∃b ∈ B : (〈a, b〉 ∈ R ∧ 〈b, d〉 ∈ S ◦ T )

⇔ ∃b ∈ B, c ∈ C : (〈a, b〉 ∈ R ∧ 〈b, c〉 ∈ S ∧ 〈c , d〉 ∈ T )

⇔ ∃c ∈ C : (〈a, c〉 ∈ R ◦ S ∧ 〈c , d〉 ∈ T )

⇔ 〈a, d〉 ∈ (R ◦ S) ◦ T




Ketten

Definition Kette

Es sei R ⊆ A× A. Fur n ≥ 0 heißt einf Folge a0, a1, . . . , an von(nicht notwendigerweise verschiedenen) Elemente au A eineR-Kette der Lange n von a0 nach an genau dann wenn, R(ai , ai+1

fur i = 0, . . . , n − 1 gilt.




Zyklen

Definition Zyklus

Eine R-Kette heißt R-Zyklus genau dann wenn gilt: a0 = an. EinR-Zyklus heißt nicht trivial, genau dann, wenn er zumindest zweiverschiedene Elemente enthalt

In der Abbildung ist 1, 2, 3, 4, 5, 3, 4 eine R-Kette der Lange 7.Die Folge 3,4,5,3 ist ein nichttrivialer Zyklus.



Table of Contents

1 Operationen auf RelationenOperationen auf RelationenUmkehrrelationKomposition von RelationenKetten und Zyklen

2 Zusammenfassung



tl;dr

Die Umkehrrelation einer Relation sind die umgekehrten Tupelder Ursprungsrelation.

Das Urbild einer Relation ist das Bild der Umkehrrelation einerRelation.

Die Komposition zweier Relationen ergibt wiederum eineRelation.


Documents

Relationen und Funktionen (Teil II) Florian Finkfinkf/mm/slides/07_relationsII.pdfCentrum f ur Informations- und Sprachverarbeitung (CIS) 2. Juni 2014 Florian Fink Mathematische Grundlagen