4. Abbildungen Was ist eine Abbildung - Hochschule Trier

4. Abbildungen
Rolf Linn
Was ist eine Abbildung?
Eigenschaften:
injektiv
surjektiv
bijektiv
Umkehrabbildung
4. Abbildungen
GM 4-1
Wozu Abbildungen?
Rolf Linn
In der Mathematik
In fast allen Gebieten der Mathematik spielen Abbildungen eine wichtige
Rolle.
In der Informatik
•  Definition: Ein endlicher Automat ist ein System A = (Σ, S, δ, s0, F). Dabei ist
Σ das Eingabealphabet und S die Zustandsmenge von A, s0∈S ist der
Startzustand, F⊆S die Menge der Endzustände und die Abbildung δ:S×Σ→S
die Zustandsüberführungsfunktion von A.
•  Funktion
Funktionale Programmierung
4. Abbildungen
GM 4-2
Abbildung
Rolf Linn
Eine Abbildung ist eine Vorschrift, die jedem Element aus
einem Definitionsbereich ein Element aus einem Wertebereich zuordnet.
Beispiele:
Einkommen → Steuer
Wasserstand → Ventilstellung
x, y
→ x+y
Eingabe
→ Ausgabe
Ähnlich wie Relation, aber:
1. 
2. 
4. Abbildungen
Jedem Element des Definitionsbereiches ist etwas aus dem
Wertebereich zugeordnet.
Jedem Element des Definitionsbereiches ist aber nur ein
Element des Wertebereiches zugeordnet.
GM 4-3
Definition 4.1: Linkstotal und rechtstotal
Rolf Linn
Seien A und B Mengen sowie R ⊆ A×B eine Relation
zwischen A und B.
R heißt linkstotal, falls gilt: ∀x∈A ∃y∈B: (x,y)∈R
R heißt rechtstotal, falls gilt: ∀y∈B ∃x∈A: (x,y)∈R
Beispiele:
A
B
a1
b1
a2
b2
a3
b3
a4
b4
nicht linkstotal
¬∃y∈B: (a4,y)∈R
4. Abbildungen
GM 4-4
Definition 4.1: Linkstotal und rechtstotal
Rolf Linn
Seien A und B Mengen sowie R ⊆ A×B eine Relation
zwischen A und B.
R heißt linkstotal, falls gilt: ∀x∈A ∃y∈B: (x,y)∈R
R heißt rechtstotal, falls gilt: ∀y∈B ∃x∈A: (x,y)∈R
Beispiele:
A
B
a1
b1
a2
b2
a3
b3
a4
b4
linkstotal
4. Abbildungen
GM 4-5
Definition 4.1: Linkstotal und rechtstotal
Rolf Linn
Seien A und B Mengen sowie R ⊆ A×B eine Relation
zwischen A und B.
R heißt linkstotal, falls gilt: ∀x∈A ∃y∈B: (x,y)∈R
R heißt rechtstotal, falls gilt: ∀y∈B ∃x∈A: (x,y)∈R
Beispiele:
A
B
A
B
a1
b1
a1
b1
a2
b2
a2
b2
a3
b3
a3
b3
a4
b4
a4
b4
linkstotal
4. Abbildungen
nicht rechtstotal
¬∃x∈A: (x,b4)∈R
GM 4-6
Definition 4.1: Linkstotal und rechtstotal
Rolf Linn
Seien A und B Mengen sowie R ⊆ A×B eine Relation
zwischen A und B.
R heißt linkstotal, falls gilt: ∀x∈A ∃y∈B: (x,y)∈R
R heißt rechtstotal, falls gilt: ∀y∈B ∃x∈A: (x,y)∈R
Beispiele:
A
B
A
B
a1
b1
a1
b1
a2
b2
a2
b2
a3
b3
a3
b3
a4
b4
a4
b4
linkstotal
4. Abbildungen
rechtstotal
GM 4-7
Definition 4.2: Linkseindeutig und rechtseindeutig
Rolf Linn
Seien A und B Mengen sowie R ⊆ A×B eine Relation zwischen
A und B.
R heißt linkseindeutig, falls gilt: (x1,y)∈R ∧ (x2,y)∈R ⇒ x1=x2
R heißt rechtseindeutig, falls gilt: (x,y1)∈R ∧ (x,y2)∈R ⇒ y1=y2
Beispiele:
A
B
a1
b1
a2
b2
a3
b3
a4
b4
nicht linkseindeutig
(a2,b1)∈R ∧ (a3,b1)∈R, aber a2≠a3
4. Abbildungen
GM 4-8
Definition 4.2: Linkseindeutig und rechtseindeutig
Rolf Linn
Seien A und B Mengen sowie R ⊆ A×B eine Relation zwischen
A und B.
R heißt linkseindeutig, falls gilt: (x1,y)∈R ∧ (x2,y)∈R ⇒ x1=x2
R heißt rechtseindeutig, falls gilt: (x,y1)∈R ∧ (x,y2)∈R ⇒ y1=y2
Beispiele:
A
B
a1
b1
a2
b2
a3
b3
a4
b4
linkseindeutig
4. Abbildungen
GM 4-9
Definition 4.2: Linkseindeutig und rechtseindeutig
Rolf Linn
Seien A und B Mengen sowie R ⊆ A×B eine Relation zwischen
A und B.
R heißt linkseindeutig, falls gilt: (x1,y)∈R ∧ (x2,y)∈R ⇒ x1=x2
R heißt rechtseindeutig, falls gilt: (x,y1)∈R ∧ (x,y2)∈R ⇒ y1=y2
Beispiele:
A
B
A
B
a1
b1
a1
b1
a2
b2
a2
b2
a3
b3
a3
b3
a4
b4
a4
b4
linkseindeutig
4. Abbildungen
nicht rechtseindeutig
(a3,b1)∈R ∧ (a3,b3)∈R, aber b1≠b3
GM 4-10
Definition 4.2: Linkseindeutig und rechtseindeutig
Rolf Linn
Seien A und B Mengen sowie R ⊆ A×B eine Relation zwischen
A und B.
R heißt linkseindeutig, falls gilt: (x1,y)∈R ∧ (x2,y)∈R ⇒ x1=x2
R heißt rechtseindeutig, falls gilt: (x,y1)∈R ∧ (x,y2)∈R ⇒ y1=y2
Beispiele:
A
B
A
B
a1
b1
a1
b1
a2
b2
a2
b2
a3
b3
a3
b3
a4
b4
a4
b4
linkseindeutig
4. Abbildungen
rechtseindeutig
GM 4-11
Definition 4.3: Abbildung
Rolf Linn
Seien A und B Mengen. Eine Relation f ⊆ A×B heißt
Abbildung (oder Funktion) von A in B, falls f linkstotal und
rechtseindeutig ist.
Wir schreiben dann f: A → B.
Beispiele:
A
B
A
B
A
B
a1
b1
a1
b1
a1
b1
a2
b2
a2
b2
a2
b2
a3
b3
a3
b3
a3
b3
a4
b4
a4
b4
a4
b4
Abbildung
4. Abbildungen
Keine Abbildung
nicht linkstotal
¬∃y∈B: (a4,y)∈f
Keine Abbildung
nicht rechtseindeutig
(a4,b2)∈f ∧ (a4,b4)∈f aber b2≠b4
GM 4-12
Definition 4.3: Abbildung
Rolf Linn
Seien A und B Mengen. Eine Relation f ⊆ A×B heißt
Abbildung (oder Funktion) von A in B, falls f linkstotal und
rechtseindeutig ist.
Wir schreiben dann f: A → B.
Beispiele:
A
B
a1
b1
Eine Relation f ⊆ A×B ist genau dann eine Abbildung,
wenn gilt
a2
b2
Für alle x∈A gibt es genau ein y∈B mit (x,y)∈f
a3
b3
a4
b4
Abbildung
4. Abbildungen
Wir schreiben statt (x,y)∈f wie üblich y = f(x).
Abbildung von { 12, 87, 90, 115 } in Typ
Rolf Linn
Typ
Wagen- Typ
nummer
12 VW Golf
VW Golf ●
●
●
●
●
Audi A4 ●
●
●
●
●
Citroën C2 ●
●
●
●
●
●
12
●
90
90 Audi A4
87 VW Golf
115 Citroën C2
●
●
87 115
Wagennummer
f = { (12, VW Golf), (90, Audi A4), (87, VW Golf), (115, Citroën C2) }
3.2 Zweistellige Relationen
GM 4-14
Keine Abbildung
Rolf Linn
Lackfarbe
Mondsilber
Meteorgrau
Dschungelgrün
Tiefseeblau
Vulkanrot
3.2 Zweistellige Relationen
Schneeweiß
Ziegelrot
Oasengrün
Petrol
Kaskadenblau
Blauviolett
Floraviolett
Glutrot
Polsterfarbe
Schiefergrau
"   " "  "   
"
"
 
"
  
" 
 
GM 4-15
Definition 4.4: Bezeichnungen bei Abbildungen
Rolf Linn
Sei f: A → B eine Abbildung.
A heißt Definitionsbereich (oder Urbildbereich) und B
Wertebereich (oder Bildbereich).
Ist y = f(x), so heißt x Urbild von y und y Bild von x bezüglich f.
{ f(x) | x∈A } heißt Bildmenge von f (oder Bild von A unter f).
Beispiel:
A
B
a1
b1
a2
b2
a3
b3
a4
b4
4. Abbildungen
Definitionsbereich: A = { a1, a2, a3, a4 }
Wertebereich: B = { b1, b2, b3, b4 }
a2 ist Urbild von b1
b1 ist Bild von a2
{ b1, b2, b3 } ist die Bildmenge von f
(oder das Bild von A unter f)
GM 4-16
Definition 4.5: Injektivität
Rolf Linn
Eine Abbildung f: A → B heißt injektiv,
falls sie linkseindeutig ist.
Beispiele:
A
a1
a2
a3
B
b1
b2
b3
b4
injektive Abbildung
A
a1
a2
a3
B
b1
b2
b3
b4
nicht injektiv
da nicht linkseindeutig:
f(a1)=f(a2)=b1 aber a1≠a2
4. Abbildungen
GM 4-17
Abbildung von { 12, 87, 90, 115 } in Typ
Rolf Linn
Typ
Wagen- Typ
nummer
12 VW Golf
VW Golf ●
●
●
●
●
Audi A4 ●
●
●
●
●
Citroën C2 ●
●
●
●
●
●
12
●
90
90 Audi A4
87 VW Golf
115 Citroën C2
●
●
87 115
Wagennummer
f = { (12, VW Golf), (90, Audi A4), (87, VW Golf), (115, Citroën C2) }
Injektiv?
Nein, den f(12)=f(87) aber 12≠87
3.2 Zweistellige Relationen
GM 4-18
Definition 4.6: Surjektivität
Rolf Linn
Eine Abbildung f: A → B heißt eine surjektive Abbildung von A
auf B, falls sie rechtstotal ist.
Beispiele:
A
a1
a2
a3
a4
B
b1
b2
b3
surjektive Abbildung
A
a1
a2
a3
a4
B
b1
b2
b3
nicht surjektiv
da nicht rechtstotal
¬∃x∈A: f(x)=b2
Übungsaufgaben 4.1 bis 4.6
4. Abbildungen
GM 4-19
Definition 4.7: Bijektivität
Rolf Linn
Eine Abbildung f: A → B heißt bijektiv, falls sie injektiv und
surjektiv ist.
Beispiele:
A
B
a1
b1
a2
b2
a3
b3
a4
b4
surjektiv und injektiv,
daher auch bijektiv
4. Abbildungen
A
a1
a2
a3
B
A
b1
a1
b2
a2
b3
a3
b4
a4
injektiv aber nicht surjektiv
(nicht rechtstotal),
daher nicht bijektiv
B
b1
b2
b3
surjektiv aber nicht injektiv
(nicht linkseindeutig),
daher nicht bijektiv
GM 4-20
Definition 4.8: Umkehrabbildung
Rolf Linn
g:B→A heißt Umkehrabbildung zu f:A→B, falls gilt:
a)
∀x∈A: g(f(x)) = x
b)
∀y∈B: f(g(y)) = y
A
B
f
g(f(x)) = x ●
● f(x)
g
4. Abbildungen
GM 4-21
Definition 4.8: Umkehrabbildung
Rolf Linn
g:B→A heißt Umkehrabbildung zu f:A→B, falls gilt:
a)
∀x∈A: g(f(x)) = x
b)
∀y∈B: f(g(y)) = y
A
B
f
●
g(y)
● y = f(g(y)
g
4. Abbildungen
GM 4-22
Satz 4.1: Umkehrabbildung
Rolf Linn
Es existiert genau dann eine Umkehrabbildung zu f:A→B,
wenn f bijektiv ist.
Übungsaufgaben 4.7 bis 4.13
4. Abbildungen
GM 4-23

Download Report