Post on 19-Aug-2019
transcript
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 RelationenZusammenfassung
Operationen auf RelationenUmkehrrelationKomposition von RelationenKetten und Zyklen
Table of Contents
1 Operationen auf RelationenOperationen auf RelationenUmkehrrelationKomposition von RelationenKetten und Zyklen
2 Zusammenfassung
Florian Fink Mathematische Grundlagen der Computerlinguistik
Operationen auf RelationenZusammenfassung
Operationen auf RelationenUmkehrrelationKomposition von RelationenKetten und Zyklen
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.
Florian Fink Mathematische Grundlagen der Computerlinguistik
Operationen auf RelationenZusammenfassung
Operationen auf RelationenUmkehrrelationKomposition von RelationenKetten und Zyklen
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.
Florian Fink Mathematische Grundlagen der Computerlinguistik
Operationen auf RelationenZusammenfassung
Operationen auf RelationenUmkehrrelationKomposition von RelationenKetten und Zyklen
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
Florian Fink Mathematische Grundlagen der Computerlinguistik
Operationen auf RelationenZusammenfassung
Operationen auf RelationenUmkehrrelationKomposition von RelationenKetten und Zyklen
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 }).
Florian Fink Mathematische Grundlagen der Computerlinguistik
Operationen auf RelationenZusammenfassung
Operationen auf RelationenUmkehrrelationKomposition von RelationenKetten und Zyklen
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
Florian Fink Mathematische Grundlagen der Computerlinguistik
Operationen auf RelationenZusammenfassung
Operationen auf RelationenUmkehrrelationKomposition von RelationenKetten und Zyklen
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.
Florian Fink Mathematische Grundlagen der Computerlinguistik
Operationen auf RelationenZusammenfassung
Operationen auf RelationenUmkehrrelationKomposition von RelationenKetten und Zyklen
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
Florian Fink Mathematische Grundlagen der Computerlinguistik
Operationen auf RelationenZusammenfassung
Operationen auf RelationenUmkehrrelationKomposition von RelationenKetten und Zyklen
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
Florian Fink Mathematische Grundlagen der Computerlinguistik
Operationen auf RelationenZusammenfassung
Operationen auf RelationenUmkehrrelationKomposition von RelationenKetten und Zyklen
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).
Florian Fink Mathematische Grundlagen der Computerlinguistik
Operationen auf RelationenZusammenfassung
Operationen auf RelationenUmkehrrelationKomposition von RelationenKetten und Zyklen
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
Florian Fink Mathematische Grundlagen der Computerlinguistik
Operationen auf RelationenZusammenfassung
Operationen auf RelationenUmkehrrelationKomposition von RelationenKetten und Zyklen
Beispiel Komposition von Relationen
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).
Florian Fink Mathematische Grundlagen der Computerlinguistik
Operationen auf RelationenZusammenfassung
Operationen auf RelationenUmkehrrelationKomposition von RelationenKetten und Zyklen
Beispiel Komposition von Relationen
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 ]).
Florian Fink Mathematische Grundlagen der Computerlinguistik
Operationen auf RelationenZusammenfassung
Operationen auf RelationenUmkehrrelationKomposition von RelationenKetten und Zyklen
Beispiel Komposition von Relationen
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
Florian Fink Mathematische Grundlagen der Computerlinguistik
Operationen auf RelationenZusammenfassung
Operationen auf RelationenUmkehrrelationKomposition von RelationenKetten und Zyklen
Beispiel Komposition von Relationen
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
Operationen auf RelationenZusammenfassung
Operationen auf RelationenUmkehrrelationKomposition von RelationenKetten und Zyklen
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)
Florian Fink Mathematische Grundlagen der Computerlinguistik
Operationen auf RelationenZusammenfassung
Operationen auf RelationenUmkehrrelationKomposition von RelationenKetten und Zyklen
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
Florian Fink Mathematische Grundlagen der Computerlinguistik
Operationen auf RelationenZusammenfassung
Operationen auf RelationenUmkehrrelationKomposition von RelationenKetten und Zyklen
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.
Florian Fink Mathematische Grundlagen der Computerlinguistik
Operationen auf RelationenZusammenfassung
Operationen auf RelationenUmkehrrelationKomposition von RelationenKetten und Zyklen
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.
Florian Fink Mathematische Grundlagen der Computerlinguistik
Operationen auf RelationenZusammenfassung
Table of Contents
1 Operationen auf RelationenOperationen auf RelationenUmkehrrelationKomposition von RelationenKetten und Zyklen
2 Zusammenfassung
Florian Fink Mathematische Grundlagen der Computerlinguistik
Operationen auf RelationenZusammenfassung
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.
Florian Fink Mathematische Grundlagen der Computerlinguistik