17
Relationen und Funktionen Relationen und Funktionen Quick Start Informatik Theoretischer Teil WS2011/12 11. Oktober 2011 QSI - Theorie - WS2011/12

Relationen und Funktionen - Benutzer-Homepageslz_inf/Vorkurs/WiSe11/uploads/files/tag... · Relationen und Funktionen > Relationen Wozu braucht man Relationen? Es wird die Beziehung

Embed Size (px)

Citation preview

Page 1: Relationen und Funktionen - Benutzer-Homepageslz_inf/Vorkurs/WiSe11/uploads/files/tag... · Relationen und Funktionen > Relationen Wozu braucht man Relationen? Es wird die Beziehung

Relationen und Funktionen

Relationen und Funktionen

Quick Start InformatikTheoretischer Teil

WS2011/12

11. Oktober 2011

QSI - Theorie - WS2011/12

Page 2: Relationen und Funktionen - Benutzer-Homepageslz_inf/Vorkurs/WiSe11/uploads/files/tag... · Relationen und Funktionen > Relationen Wozu braucht man Relationen? Es wird die Beziehung

Relationen und Funktionen > Relationen

Relationen

QSI - Theorie - WS2011/12

Page 3: Relationen und Funktionen - Benutzer-Homepageslz_inf/Vorkurs/WiSe11/uploads/files/tag... · Relationen und Funktionen > Relationen Wozu braucht man Relationen? Es wird die Beziehung

Relationen und Funktionen > Relationen

Was ist eine Relation?

Eine Relation steht fur eine Beziehung zwischen Objekten - imformalen Kontext Elementen einer Menge. Zwei Elemente aus denbetroffenen Mengen konnen entweder die Beziehung zueinanderbesitzen (die Relation erfullen) oder nicht.Beispiele:

enthalt den Buchstaben Eine Relation zwischen Worten undBuchstaben.

ist verwandt mit Eine Relation zwischen Personen und Personen.

hat die Farbe Eine Relation zwischen Gegenstanden und Farben.

QSI - Theorie - WS2011/12

Page 4: Relationen und Funktionen - Benutzer-Homepageslz_inf/Vorkurs/WiSe11/uploads/files/tag... · Relationen und Funktionen > Relationen Wozu braucht man Relationen? Es wird die Beziehung

Relationen und Funktionen > Relationen

Wozu braucht man Relationen?

Es wird die Beziehung von Objekten formalisiert; darauf basiert zumBeispiel das gangigste Modell fur Datenbanken. Besonders haufig istauch die “Kantenrelation”, die die Verbindungen zwischenKnotenpunkten in einem Graphen enthalt.

A B C

Knotenmenge: {A,B,C}, Kantenrelation: {(A,B) , (B,C ) , (B,B)}

QSI - Theorie - WS2011/12

Page 5: Relationen und Funktionen - Benutzer-Homepageslz_inf/Vorkurs/WiSe11/uploads/files/tag... · Relationen und Funktionen > Relationen Wozu braucht man Relationen? Es wird die Beziehung

Relationen und Funktionen > Relationen

Tupel

Definition (Das Tupel)

Sei n ∈ N eine naturliche Zahl. Fur n Objekte a1, . . . , an bezeichnet(a1, . . . , an) ein geordnetes Tupel mit den Komponenten a1, a2, . . . , an.

Ein Tupel ist nicht dasselbe wie eine Menge - {a1, a2, . . . , an}:Reihenfolge Die Reihenfolge ist wichtig: {a1, a2} = {a2, a1}, aber

(a1, a2) 6= (a2, a1).

Wiederholungen Ein Objekt kann beliebig oft vorkommen, und dasTupel andert sich dadurch: (a1, a2) 6= (a1, a2, a1).

QSI - Theorie - WS2011/12

Page 6: Relationen und Funktionen - Benutzer-Homepageslz_inf/Vorkurs/WiSe11/uploads/files/tag... · Relationen und Funktionen > Relationen Wozu braucht man Relationen? Es wird die Beziehung

Relationen und Funktionen > Relationen

Das Tupel (2)

Fur ein Tupel (a1, . . . , an) heißt n die Lange (nicht Kardinalitatoder Machtigkeit) des Tupels.

Ein Tupel der Lange n heißt auch “n-Tupel”. 2-Tupel und 3-Tupelnennt man auch “Paare” und “Tripel”.

Zwei Tupel (a1, . . . , an) und (b1, . . . , bn) sind gleich, genau dannwenn sie die gleiche Lange haben, und an jeder Positionubereinstimmen (fur 1 ≤ i ≤ n gilt: ai = bi ).

QSI - Theorie - WS2011/12

Page 7: Relationen und Funktionen - Benutzer-Homepageslz_inf/Vorkurs/WiSe11/uploads/files/tag... · Relationen und Funktionen > Relationen Wozu braucht man Relationen? Es wird die Beziehung

Relationen und Funktionen > Relationen

Das kartesische Produkt

Definition (Das kartesische Produkt)

Seien A und B Mengen. Das kartesische Produkt von A,B ist dieMenge A× B := {(a, b) |a ∈ A, b ∈ B}.

Beispiel: Sei M = {1, 2, 3} und N = {a, b}, dann ist

M × N = {(1, a), (1, b), (2, a), (2, b), (3, a), (3, b)}. Es wird jedesElement mit jedem Element kombiniert.

QSI - Theorie - WS2011/12

Page 8: Relationen und Funktionen - Benutzer-Homepageslz_inf/Vorkurs/WiSe11/uploads/files/tag... · Relationen und Funktionen > Relationen Wozu braucht man Relationen? Es wird die Beziehung

Relationen und Funktionen > Relationen

Relation

Definition (Paar-Relation)

Seien A,B Mengen. Eine Relation uber A,B ist eine TeilmengeR ⊆ A× B; die Elemente der Relation sind daher Tupel.

Eine Relation kann auch zwischen mehr als zwei Mengen definiert sein.Beispiel:

a2 + b2 = c2 Ganzzahlige Seitenlangen von rechtwinkligen Dreiecken:R ⊆ N× N× N. Die Relation istR = {(3, 4, 5) , (4, 3, 5) , (5, 12, 13) , . . .}.

Fur eine Relation uber n Mengen heißt n die Stelligkeit von R.

QSI - Theorie - WS2011/12

Page 9: Relationen und Funktionen - Benutzer-Homepageslz_inf/Vorkurs/WiSe11/uploads/files/tag... · Relationen und Funktionen > Relationen Wozu braucht man Relationen? Es wird die Beziehung

Relationen und Funktionen > Funktionen

Funktionen

QSI - Theorie - WS2011/12

Page 10: Relationen und Funktionen - Benutzer-Homepageslz_inf/Vorkurs/WiSe11/uploads/files/tag... · Relationen und Funktionen > Relationen Wozu braucht man Relationen? Es wird die Beziehung

Relationen und Funktionen > Funktionen

Was ist eine Funktion?

Funktionen kennt man in der Mathematik und in Programmen alsRegeln, die fur jede Eingabe eine bestimmte Ausgabe festlegen. Formalsagt man, dass sie die Eingabe auf die Ausgabe abbilden.Beispiele:

f (x) = x2 ist eine Funktion, die Zahlen auf andere Zahlenabbildet.

g (wort) = “Anfangsbuchstabe von wort′′ bildet Worte aufBuchstaben ab.

h (M) = “Kardinalitat der Menge M” bildet Mengen auf Zahlenab.

QSI - Theorie - WS2011/12

Page 11: Relationen und Funktionen - Benutzer-Homepageslz_inf/Vorkurs/WiSe11/uploads/files/tag... · Relationen und Funktionen > Relationen Wozu braucht man Relationen? Es wird die Beziehung

Relationen und Funktionen > Funktionen

Funktionen als Relation

Man kann die Funktion als Relation mit speziellen Eigenschaftenbetrachten:

Definition (Funktion)

Seien X und Y Mengen. Eine Funktion von X nach Y ist eine Relationf ⊆ X × Y mit der Eigenschaft, dass fur jedes Element a ∈ X genauein Element b ∈ Y existiert mit (a, b) ∈ f .

Beispiel: Folgenden Relationen sind Funktionen:

{(m, n) ∈ N× N|n = m3 − 1}.{(x , y) ∈ R≥0 × R≥0|x2 + y2 = 1}. Bzw.: y =

√1− x2.

QSI - Theorie - WS2011/12

Page 12: Relationen und Funktionen - Benutzer-Homepageslz_inf/Vorkurs/WiSe11/uploads/files/tag... · Relationen und Funktionen > Relationen Wozu braucht man Relationen? Es wird die Beziehung

Relationen und Funktionen > Funktionen

Sind alle Relationen auch Funktionen?

Nein:

Eine n-stellige Relation mit n 6= 2 ist keine Funktion.

Die Relation {(a, b) ∈ N× N|b = ±a} ist keine Funktion, da zumBeispiel (1,−1) und (1, 1) darin enthalten sind. (Keine eindeutigeAusgabe.)

Die Relation{

(x , y) ∈ R× R|y = 1x

}ist keine Funktion, da sie

kein Tupel (0, y) enthalt. (Nicht vollstandig definiert.)

QSI - Theorie - WS2011/12

Page 13: Relationen und Funktionen - Benutzer-Homepageslz_inf/Vorkurs/WiSe11/uploads/files/tag... · Relationen und Funktionen > Relationen Wozu braucht man Relationen? Es wird die Beziehung

Relationen und Funktionen > Funktionen

Notation von Funktionen

Definition

Seien X und Y Mengen.

Wir schreiben f : X → Y um auszudrucken, dass f eine Funktionvon X nach Y ist.

Fur eine Funktion f : X → Y und ein Element a ∈ X schreibenwir auch f (a) = b, wenn (a, b) ∈ f das fur a eindeutige Tupel in fist.

Ist f : X → Y eine Funktion, so heißt die zugehorige Relation{(a, f (a))|a ∈ X} ⊆ X × Y auch der Graph der Funktion f .

Ist f : X → Y eine Funktion, so ist X der Definitionsbereichvon f und Y der Bildbereich von f .

QSI - Theorie - WS2011/12

Page 14: Relationen und Funktionen - Benutzer-Homepageslz_inf/Vorkurs/WiSe11/uploads/files/tag... · Relationen und Funktionen > Relationen Wozu braucht man Relationen? Es wird die Beziehung

Relationen und Funktionen > Funktionen

Vergleich von Funktionen

Definition

Seien X und Y Mengen, und seien f , g : X → Y Funktionen.

Die Funktionen f und g sind gleich, wenn fur alle x ∈ X gilt:f (x) = g(x).

Seien X ,Y ⊆ R. Die Funktion f ist kleiner oder gleich g, inZeichen f ≤ g, wenn fur alle x ∈ X gilt: f (x) ≤ g(x).Die Funktion f ist kleiner als g , in Zeichen f < g, wenn fur allex ∈ X gilt: f (x) < g(x).

”f ≥ g “und

”f > g “sind analog definiert.

Beispiel: Fur die Funktionen f (x) = ex , g(x) = x2 und h(x) = 1 giltf > g , g < f , h ≤ f und f ≥ h.

QSI - Theorie - WS2011/12

Page 15: Relationen und Funktionen - Benutzer-Homepageslz_inf/Vorkurs/WiSe11/uploads/files/tag... · Relationen und Funktionen > Relationen Wozu braucht man Relationen? Es wird die Beziehung

Relationen und Funktionen > Funktionen

Eigenschaften von Funktionen

Definition (Eigenschaften von Funktionen)

Sei f : X → Y eine Funktion.

f heißt injektiv, falls es fur jedes y ∈ Y hochstens ein x ∈ X gibtmit f (x) = y.

f heißt surjektiv, falls es fur jedes y ∈ Y mindestens ein x ∈ Xgibt mit f (x) = y.

f heißt bijektiv, falls es fur jedes y ∈ Y genau ein x ∈ X gibt mitf (x) = y.

QSI - Theorie - WS2011/12

Page 16: Relationen und Funktionen - Benutzer-Homepageslz_inf/Vorkurs/WiSe11/uploads/files/tag... · Relationen und Funktionen > Relationen Wozu braucht man Relationen? Es wird die Beziehung

Relationen und Funktionen > Funktionen

Beispiele

Beispiel:

Die Funktion f : R→ R, f (x) = ex , ist injektiv, aber nichtsurjektiv.

Die Funktion g : R→ R, g(x) = x3 − 2x , ist surjektiv, aber nichtinjektiv.

Die Funktion h : R→ R, h (x) = x − 2, ist injektiv und surjektiv,und daher auch bijektiv.

Die Funktion i : R→ R, i(x) = x2, ist nicht injektiv und nichtsurjektiv.

QSI - Theorie - WS2011/12

Page 17: Relationen und Funktionen - Benutzer-Homepageslz_inf/Vorkurs/WiSe11/uploads/files/tag... · Relationen und Funktionen > Relationen Wozu braucht man Relationen? Es wird die Beziehung

Relationen und Funktionen > Funktionen

Eigenschaften von Funktionen im Bild

injektivnicht surjektiv

surjektivnicht injektiv

bijektiv

QSI - Theorie - WS2011/12