Funktionen

[ Zurück ] [ Zurück (Seitenende) ] [ Seitenende ] [ Überkapitel ] [ Bitte Skript-Fehler melden ]

12.3. Funktionen

Deﬁnition 12.3.1 (totale Funktion). Eine Funktion ist eine Relation R ⊆ M × N über dem Deﬁnitionsbereich M und dem Wertebereich N, welche folgende Eigenschaften hat:

Jedes Element aus dem Deﬁnitionsbereich M ist mit höchstens einem Element aus dem Wertebereich N verbunden. (rechtseindeutig )
Jedes Element von M ist mit einem Element aus N verbunden. (linkstotal )

Partielle Funktion

Falls nur Bedingung 1 erfüllt ist, nennt man die Funktion partiell .

$pict$

Abbildung 12.2:

Pfeildiagramm einer partiellen Funktion

Arten von Funktionen

Surjektiv (rechtstotal)

Jedes Element des Wertebereichs wird von mindestens einem Pfeil getroﬀen.

$pict$

Abbildung 12.3:

Pfeildiagramm einer surjektiven Funktion

Injektiv (linkseindeutig)

Jedes Element des Wertebereichs wird von höchstens einem Pfeil getroﬀen.

$pict$

Abbildung 12.4:

Pfeildiagramm einer injektiven Funktion

Bijektiv

Jedes Element des Wertebereichs wird von genau einem Pfeil getroﬀen.

$pict$

Abbildung 12.5:

Pfeildiagramm einer bijektiven Funktion

Übersicht: Relationen und Funktionen

pict

Abbildung 12.6:

Übersicht: Eigenschaften von Relationen und Funktionen

Notationen für Funktionen

Funktionsschreibweise

Statt f ⊆ M × N schreibt man f : M → N.
Statt 〈x,y〉∈ f schreibt man f(x) = y.
Statt 〈x,y〉∈ f schreibt man auch xy ∈ f.

Deﬁnitionsschreibweisen

Sei M = {a,b,c,d} und N = {1,2,3}

f : M → N = {〈a,1〉,〈b,3〉,〈c,2〉,〈d,3〉}
f(x) =

Rekursive Funktionsdeﬁnitionen
Funktionen über rekursiv deﬁnierten Mengen lassen sich oft besonders elegant rekursiv deﬁnieren.

Beispiel 12.3.2 (Zweistellige Additions-Funktion add : ℕ × ℕ → ℕ).

{ add(x,y) = x falls y = 0 s(add(x,z)) falls y = s(z)


Schritt	Term	y	z


	add(s(0),s(s(0)))	s(s(0))	s(0)

1	s(add(s(0),s(0)))	s(0)	0

2	s(s(add(s(0),0)))	0

3	s(s(s(0)))

Multimengen
Eine Multimenge M = {a : 3,b : 4,c : 1} mit a,b,c,… ∈ N ist eine (partielle) Funktion M : N → ℕ.

Beispiel 12.3.3 (Tokenvorkommen eines Satzes).
Wie notiert man die Multimenge der Token des Satzes “Wenn hinter Fliegen Fliegen ﬂiegen, ﬂiegt eine Fliege Fliegen nach.” als Menge von geordneten Paaren?

[ Zurück ] [ Zurück (Seitenende) ] [ Seitenbeginn ] [ Überkapitel ] [ Bitte Skript-Fehler melden ]