Relationen und Funktionen (Teil I)finkf/mm/slides/06_relationsI.pdf · Centrum f ur Informations- und Sprachverarbeitung (CIS) 2. Juni 2014 Florian Fink Mathematische Grundlagen der

Tupel kartesische Produkte und WorterRelationen

Zusammenfassung

Mathematische Grundlagen der ComputerlinguistikRelationen und Funktionen (Teil I)

Florian Fink

Centrum fur Informations- und Sprachverarbeitung (CIS)

2. Juni 2014

Florian Fink Mathematische Grundlagen der Computerlinguistik


Zusammenfassung

Tupelkartesisches ProduktWorter

Table of Contents

1 Tupel kartesische Produkte und WorterTupelkartesisches ProduktWorter

2 RelationenDarstellung von RelationenEinschrankungen und Bilder von Relationen

3 Zusammenfassung



Zusammenfassung


Tupel I

Bei den Mengen konnten wir bisher doppelte Elemente undReihenfolgen nicht unterscheiden. Will man nun aber Zuordnungeneinzelner Elemente zu anderen (nicht notwendigerweiseunterschiedlichen) Elementen betrachten, benotigen wir den Begriffdes geordneten Paars bzw. Tupel 〈a, b〉 zweier Elemente a und b.Beachten Sie, dass anders als bei Tupeln bei Mengen im Fallea = b stets {a, b} = {a} = {b} gilt.



Zusammenfassung


Tupel II

Definition geordnetes Paar

Seien a und b Elemente einer Menge M. Das geordete Paar 〈a, b〉von a und b ist dann definiert als:

〈a, b〉 := {{a}, {a, b}}

Lemma geordnetes Paar

Fur beliebige Elemente a, b, c , d ∈ M gilt stets:

{a, c} = {b, c} → a = b

〈a, b〉 = 〈c , d〉 → a = c ∧ b = d



Zusammenfassung


Tupel III

Es gelte {a, c} = {b, c}. Wir unterscheiden nun 2 Falle:1 Es gilt a = c :

b ∈ {b, c}b ∈ {a, c} = {a}b = a

2 Es gilt a 6= c :

a ∈ {a, c} = {b, c}a ∈ {b, c}a = b



Zusammenfassung


Tupel IV

Es gelte 〈a, b〉 = 〈c , d〉{a} ∈ 〈a, b〉 = 〈c , d〉{a} = {c} ∨ {a} = {c , d}{a} = {c} → a = c

{a} = {c , d} → a = c = d

Es gilt somit immer {a} = {c}.Desweiteren gilt {{a}, {a, b}} = {{c}, {c, d}}Somit gilt {a, b} = {c, d} = {a, d}Daraus folgt b = d



Zusammenfassung


Kartesisches Produkt

Definition kartesisches Produkt

Seien A und B Mengen. Die Menge

A× B := {〈a, b〉|a ∈ A, b ∈ B}

heißt kartesisches Produkt der Mengen A und B.

Das kartesische Produkt zweier Mengen A× B ist die Menge allerTupel, deren rechtes Element aus der Menge A stammen undderen linkes Element aus der Menge B stammen.



Zusammenfassung


Beispiele fur das kartesische Produkt

1 Sei A = {1, 2} und B = {k , l ,m}.A× B ={〈1, k〉, 〈1, l〉, 〈1,m〉, 〈2, k〉, 〈2, l〉, 〈2,m〉}

2 Sei A = {0, 1}. A× A ={〈0, 0〉, 〈0, 1〉, 〈1, 0〉, 〈1, 1〉}3 Die ubliche Schreibkonvention fur Schachbrettfelder basiert

darauf, dass das Schachbrett als kartesisches Produkt derMengen {1, 2, 3, 4, 5, 6, 7, 8} und {a, b, c , d , e, f , g , h}betrachtet wird. Feldbezeichnungen wie f6 stellen dann eineKurznotation fur das entsprechende geordnete Paare 〈f , 5〉.

Wieviele Elemente enthalt die Menge A× B, mit m, respektive nElementen?



Zusammenfassung


Lemma kartesisches Produkt

Lemma kartesisches Produkt

Fur beliebige Mengen A,B,C und D gilt stets:

(A× B) ∩ (C × D) = (A ∩ B)× (C ∩ D)

(A× B) ∪ (A× C ) = A× (B ∪ C )



Zusammenfassung


Beweis I

Zum Beweis von Mengengleichheit, muss immer gezeigt werden,dass alle Elemente (bzw. ein generisches Element) der einen Mengeauch Element der andern sind und umgekehrt.Sei x ∈ (A× B) ∩ (C × D). Dann gilt:

x ∈ A× B (1)

x ∈ C × D (2)

Aus der Definition des kartesischen Produktes folgt:

∃a ∈ A, b ∈ B : x = 〈a, c〉 (3)

∃c ∈ C , d ∈ D : x = 〈c , d〉 (4)

Daraus folgt:

〈a, b〉 = 〈c, d〉, und a = c ∈ A ∩ C , b = d ∈ B ∩ D (5)



Zusammenfassung


Beweis II

Um zu zeigen dass (A× B) ∪ (A× C ) = A× (B ∪ C ) gilt, zeigenwir zuerst, dass (A× B) ∪ (A× C ) ⊆ A× (B ∪ C ) gilt, und dannA× (B ∪ C ) ⊆ (A× B) ∪ (A× C ).

Warum beweist dieses Vorgehen ebenfalls die Mengengleichheit?



Zusammenfassung


Beweis III

Nach der Definition der Vereinigung gilt fur(A× B) ∪ (A× C ) ⊆ A× (B ∪ C ):

d ∈ A× B

∃a ∈ A, b ∈ B : d = 〈a, b〉

d ∈ A× B → d ∈ A× (B ∪ C )

oderd ∈ A× C

∃a ∈ A, c ∈ C : d = 〈a, c〉

d ∈ A× C → d ∈ A× (B ∪ C )

In Beiden Fallen gilt d ∈ A× (B ∪ C ).



Zusammenfassung


Beweis IV

Nach der Definition der Vereinigung gilt furA× (B ∪ C ) ⊆ (A× B) ∪ (A× C ):

d ∈ A× (B ∪ C )

∃a ∈ A, e ∈ B ∪ C : d = 〈a, e〉

Falls e ∈ B:

d = 〈a, e〉 ∈ A× B → d ∈ (A× B) ∪ (A× C )

Falls e ∈ C :

d = 〈a, e〉 ∈ A× C → d ∈ (A× C ) ∪ (A× C )

In beiden Fallen gilt d ∈ (A× B) ∪ (A× C ). MitA ⊆ B ∧ B ⊆ A→ A = B ist die Gleichheit bewiesen.



Zusammenfassung


Beweis V

Die Vorherige Argumentation lasst sich noch wesentlich kompakterdarstellen:

d ∈ A× (B ∪ C )

⇔∃a ∈ A,∃e ∈ B ∪ C : d = 〈a, e〉⇔∃a ∈ A,∃e : ((e ∈ B ∨ e ∈ C ) ∧ d = 〈a, e〉)⇔∃a ∈ A,∃e : ((e ∈ B ∧ d = 〈a, e〉) ∨ (e ∈ C ∧ d = 〈a, e〉))

⇔(∃a ∈ A, ∃e ∈ B : d = 〈a, e〉) ∨ (∃a ∈ A,∃e ∈ C : d = 〈a, e〉)⇔(d ∈ A× B) ∨ (d ∈ A× C )

⇔d ∈ (A× B) ∪ (A× C )



Zusammenfassung


Reihen von kartesische Produkten

Es ist naturlich moglich, mehrere kartesische Produkte aneinanderzu reihen: A× B × C = (A× B)× C .

Wie sehen die Tupel der Ergebnismenge aus?Gilt (A× B)× C = A× (B × C )?Gilt (A× B) = (B × A)?



Zusammenfassung


n-Tupel

Um auf naturliche Weise kartesische Produkte mit n ≥ 0verwenden zu konnen, mussen wir zwei spezielle Tupel definieren:

Das leere Tupel 〈〉Das Eintupel aus der Menge A 〈a〉 oder einfach a.

Fur beliebige Elemente a1, . . . , an+1 mit n ≥ 2 definieren wirdie n-Tupel:

〈a1, . . . , an, an+1〉 := 〈〈a1, . . . , an〉, an+1〉



Zusammenfassung


kartesische Produkte mit n Faktoren

Definition kartesisches Produkt

Es sei n ∈ N und A1, . . . ,An Mengen. Die Menge

n∏i=1

Ai := {〈a1, . . . , an〉|ai ∈ Ai}

heißt kartesisches Produkt der Mengen A1, . . . ,An.

Oftmals wird das kartesische Produkt auch in der FormA1 × A2 × · · · × An notiert. Gilt A1 = A2 = · · · = An =: A soschreibt man fur

∏ni=1 Ai auch kurzer An.



Zusammenfassung


Beispiele

1 Es gilt stets: A0 ={〈〉}2 A1 ={〈a〉|a ∈ A} = {a|a ∈ A}3 Sei A = {1, 2},B = {b} und C = {c}. Dann ist

A× B × C ={〈1, b, c〉, 〈2, b, c〉}.4 Sei A = {a, b} dann ist A2 = {〈a, a〉〈a, b〉〈b, a〉〈b, b〉}.



Zusammenfassung


Worter

Die Definition von Wortern, macht klar warum vorher auch leereTupel und Eintupel definiert wurden.

Definition Menge der Worter

Es sei A eine Menge. Dann heißt

A∗ :=⋃n∈N

An

die Menge der Worter uber der Menge A. Jedes Element w ∈ An

heißt ein Wort der Lange n uber A.

Wieviele Worter (Elemente) enthalt A∗ mit A = {a, b}?Welches besondere Wort (Element) enthalt A∗?



Zusammenfassung


Worter und Alphabete

Formal gesehen sind Worter einfach nur n-Tupel mit Elementenaus einer Menge A und die Schreibweise a1a2 . . . an einfach nureine vereinfachte Form von 〈a1, a2, . . . , an〉. Worter sind alsoeinfach Zeichenfolgen unterschiedlicher Langen. Die Basismengeaus denen diese Worter zusammengesetzt werden wird dabei meistals Alphabet bezeichnet.



Zusammenfassung


Formale Sprachen

Definition Sprache

Es sei A eine Menge. Dann heißt jede Teilmenge L von A∗ eineformale Sprache uber dem Alphabet A. Mit L(A) wird die Mengealler formalen Sprachen uber A bezeichnet.

Was fur eine spezielle Menge ist L(A)?



Zusammenfassung


Beispiele

Sei A = {0, 1, . . . , 9, a, b, c , d , e, f }. Dann ist die Menge allerzweistelligen Hexadezimalzahlen eine formale Sprache uberdem Alphabet A.

Sei A das Alphabet aller Buchstaben der deutschen Sprache.Dann ist die Menge aller Wochentage{Montag,Dienstag,Mittwoch,Donnerstag,Freitag,Samsag,Sonntag}eine Formale Sprache (Montag ist dabei nur eine abkurzendeSchreibweise fur das Tupel 〈M, o, n, t, a, g〉 . . . ).

Eine Menge Wortern W kann selbst wieder als Alphabetdienen. Ist also W := {Max,raucht,lacht}, so ist die Mengemit den Wortern (Satzen) uber W Max raucht, Max lachteine formale Sprache uber W . In diesem Sinn kann jedeMenge von Satzen der deutschen Sprache als eine formaleSprache uber einem Wortalphabet beschrieben werden.



Zusammenfassung

Darstellung von RelationenEinschrankungen und Bilder von Relationen

Table of Contents



3 Zusammenfassung



Zusammenfassung


Relationen

Relationen formalisieren Beziehungen von Elementenuntereinander. Von einer Relation spricht man genauer, wennimmer dieselbe Anzahl von Elementen in einer Beziehung stehen.

Definition Relation

Eine Menge R wird n-stellige Relation genannt genau dann, wennes Mengen A1,A2, . . . ,An mit n ≥ 1 gibt und gilt:

R ⊆n∏

i=1

Ai

Anstatt 〈a1, a2, . . . , an〉 ∈ R schreibt man kurzer: R(a1, a2, . . . , an).Gilt A1 = A2 = · · · = An =: A, so heißt R eine n-stellige Relationauf A.



Zusammenfassung


Beispiel Datenbanken

Name Geschlecht Dienstalter Geburtsdatum Gehaltsklasse

Maier m 7 11.02.63 I

Maier w 10 12.12.74 III

Muller w 3 28.05.85 I

. . . . . . . . . . . . . . .

Die Tabellen von Datenbanksystemen stellen Relationen dar. DieZahl der Tabellenspalten bestimmt die Stelligkeit der dargestelltenRelation.Das Beispiel entalt 5-Tupel aus dem kartesischen Produkt derMenge A1 × A2 × A3 × A4 × A5.In der Informatik werden solche relationalen Tabellen inDatenbanksystemen verwendet.



Zusammenfassung


Relationen

Viele in der Mathematik auftretenden Relationen sind zweistellig.Zur Darstellung von zweistelligen Relationen auf endlichen Mengenverwendet man haufig Schaubilder mit Pfeilen. Ein Pfeil von einemElement x zu einem (nicht notwendigerweise anderen) Element ybedeutet dass R(x , y) bzw. 〈x , y〉 ∈ R gilt.

Abbildung : Darstellung von Relationen



Zusammenfassung


Matrixdarstellung von Relationen

Relationen auf endlichen Mengen konnen auch als Matrix vonWahrheitswerten dargestellt werden. Man schreibt dabei M[i , j ] furden Eintrag in Zeile i und Spalte j der Matrix M. Ein Eintragm[i , j ] = 1 (bzw. 0) steht fur R(i , j) (bzw. ¬R(i , j)).

R a b c d e

a 0 0 0 0 0

b 0 0 0 1 0

c 0 0 0 1 0

d 0 1 0 1 0

e 0 0 1 1 0



Zusammenfassung


Darstellung von Relationen

Abbildung : Darstellung von Relationen

Die hier dargestellte Relation enthalt die Paare〈1, a〉, 〈1, c〉, 〈2, a〉, 〈4, a〉, 〈4, b〉, 〈4, c〉. In Matrixschreibweise ergibtsich folgende Tabelle:

R a b c

1 1 0 1

2 1 0 0

3 0 0 0

4 1 1 1



Zusammenfassung


Beispiele fur Relationen

Eine wichtige Eigenschaft von Relationen – im Gegensatz zu dennachfolgenden Funktionen – ist, dass ein gegebenes Element mitmehreren anderen Elementen in Beziehung stehen kann.

Die Relation die einem Wort alle seine Prafixe zuordnet.

Die Relation die einem Wort alle seine Suffixe zuordnet.

Die kleinergleich Relation. Anstatt ≥ (a, b) schreibt man inder Infixnotation a ≥ b.

Die Teilbarkeitsrelation.

Die Eltern- bzw. Kindsrelation von Menschen.

Einfache Transitive Verben wie lieben oder kennenentsprechen zweistelligen Relationen von Personen.



Zusammenfassung


Bilder von Relationen

Definition Bild

Sei R ⊆ A× B eine zweistellige Relation, X ⊆ A und Y ⊆ B. DieMenge

R(X ) := {y ∈ B|∃x ∈ X : R(x , y)}

heißt Bild von X unter R.



Zusammenfassung


Beispiel Bilder von Relationen I

Abbildung : Die Relation R ⊆ {1, 2, 3, 4} × {a, b, c , d , e, f }

In der Abbildung ist das Bild {a, c , d , f } der Menge {1, 3, 4}dargestellt.Um das Bild einer Menge zu erhalten, mussen alle hinterenEintrage y all derjenigen geordneten Paare 〈x , y〉 aus Rzusammengefasst werden, deren vorderer Eintrag x aus {1, 3, 4}ist. Das Urbild von {c , d , e} unter R ist {1, 3, 4}.



Zusammenfassung


Beispiel Bilder von Relationen II


Das Bild von {2, 4} in R: {b, d , f }.Das Bild von {1} in R: {a, c}.Das Urbild von {c , d} unter R: {1, 3, 4}.

Was ist das Bild von {1, 2} in der kleinergleich Relation?Was ist das Urbild von {1, 2} unter der kleinergleich Relation?



Zusammenfassung


Einschrankungen von Relationen

Definition Einschrankung

Sei R ⊆ A× B eine zweistellige Relation, X ⊆ A und Y ⊆ B. DieMenge

RdX := {〈x , y〉 ∈ R|x ∈ X}

heißt Einschrankung von R auf X .



Zusammenfassung


Beispiel Einschrankung von Relationen


Die Einschrankung von R auf {1, 2, 3} ist die Menge aus denTupeln {〈1, a〉, 〈1, c〉, 〈2, b〉, 〈3, c〉}.



Zusammenfassung


Unterschied zwischen Bild und Einschrankung vonRelationen

Die Mengen RdX und R(X ) sollten nicht verwechselt werden.Man sollte im Kopf behalten, dass die Einschrankung RdX eineTeilmenge der Relation – und damit eine Menge von Tupeln – ist.Das Bild R(X ) ist eine einfache Teilmenge von B – und damit eineMenge von Elementen.



Zusammenfassung

Table of Contents



3 Zusammenfassung



Zusammenfassung

tl;dr

Tupel ermoglichen Zuordnungen einzelner Elementezueinander.

Das Kartesische Produkt zweier Mengen sind alle Tupel, diesich (unter Beachtung der Reihenfolge) aus den jeweiligenElementen der Mengen bilden lassen.

Worter sind unterschiedlich lange n-Tupel uber einemAlphabet.

Formale Sprachen sind Teilmengen der Menge aller Worteruber einem Alphabet.

Relationen stellen Beziehungen von Elementen dar.

n-stellige Relationen sind Teilmengen von n-stelligenkartesischen Produkten, die Elemente zueinander in Beziehungstellen.


Documents

Relationen und Funktionen (Teil I)finkf/mm/slides/06_relationsI.pdf · Centrum f ur Informations- und Sprachverarbeitung (CIS) 2. Juni 2014 Florian Fink Mathematische Grundlagen der