Partielle Funktion

Eine partielle Funktion von der Menge nach der Menge ist eine rechtseindeutige Relation, das heißt eine Relation, in der jedem Element der Menge höchstens ein Element der Menge zugeordnet wird. Der Begriff der partiellen Funktion ist in der Theoretischen Informatik, insbesondere in der Berechenbarkeitstheorie verbreitet.

Der Begriff der partiellen Funktion ist eine Verallgemeinerung des Begriffs der Funktion. Unter einer Funktion von nach versteht man eine linkstotale, rechtseindeutige Relation, also eine Relation, in der jedem Element von genau ein Element von zugeordnet ist. Jede Funktion von nach ist also insbesondere eine partielle Funktion von nach , nämlich eine (links-)totale partielle Funktion, aber nicht umgekehrt. Insofern kann der Begriff der partiellen Funktion irreführend sein. Um auszudrücken, dass eine partielle Funktion sogar eine Funktion im eigentlichen Sinn ist, sagt man gelegentlich, es handle sich um eine totale Funktion. Der Unterschied zwischen partiellen Funktionen und (totalen) Funktionen ist: Für partielle Funktionen $f\colon \;X\rightharpoonup Y$ gilt $\operatorname {Def} (f)\subseteq X$ , für (totale) Funktionen $f\colon \;X\to Y$ gilt $\operatorname {Def} (f)=X$ .

Als Definitionsbereich $\operatorname {Def} (f)$ der partiellen Funktion bezeichnet man die Menge aller derjenigen Elemente aus , denen ein Element aus zugeordnet ist. Eine partielle Funktion ist also genau dann eine Funktion, wenn ${\mbox{Def}}(f)=X$ gilt.

Eine partielle Funktion von nach lässt sich auf zweierlei Arten als Funktion modellieren:

als Funktion $f|_{\operatorname {Def} (f)}\colon \;\operatorname {Def} (f)\to Y,x\mapsto f(x),\quad$ oder
als Funktion ${\bar {f}}\colon \;X\to Y\cup \{\bot \},\;x\mapsto {\begin{cases}f(x),&{\text{ falls }}x\in \operatorname {Def} (f),\\\bot ,&{\text{ sonst.}}\end{cases}}$

Der Wert sein.

Schreibweisen

Für „ ist eine partielle Funktion von nach “ schreibt man: $f\colon \;X\rightharpoonup Y$ oder $f\colon \;X\rightsquigarrow Y$ , alternativ auch $f\colon \;\subseteq X\to Y$ oder $f\colon \;X\to _{p}Y$ . Nicht empfehlenswert sind u.a. die Schreibweisen $f\colon \;X\to Y$ sowie $f\colon \;X\;{\,\,\shortmid \;\!\!\!\!\!\to }\;Y$ , denn erstere definiert als (totale) Funktion und zweitere ist leicht mit $f\colon \;X\nrightarrow Y$ zu verwechseln, was jedoch bedeutet, dass keine (totale) Funktion von nach ist. Dies ist aber wie ersteres im Allgemeinen nicht zutreffend.

Die Schreibweise „ f(x) ist undefiniert“ oder sogar „ $f(x)={\text{undefiniert}}$ “ ist problematisch, denn der Ausdruck f(x) ist ja dann gerade nicht zulässig. Klarer ist es zu sagen „ ist undefiniert an der Stelle “ oder als Formel „ $x\notin {\mbox{Def}}(f)$ “.

Beispiele

Die partielle Funktion $f\colon \;\mathbb {R} \rightharpoonup \mathbb {R} ,x\mapsto {\frac {1}{x}},$ ist an der Stelle undefiniert, weil die Division durch $0$ in den reellen Zahlen unzulässig ist. Man kann bilden

$f|_{\mathbb {R} \setminus \{0\}}\colon \;\mathbb {R} \setminus \{0\}\to \mathbb {R} ,x\mapsto {\tfrac {1}{x}},$

oder

${\bar {f}}\colon \;\mathbb {R} \to \mathbb {R} \cup \{\bot \},\;x\mapsto {\begin{cases}{\tfrac {1}{x}},&{\text{ falls }}x\neq 0,\\\bot ,&{\text{ sonst.}}\end{cases}}$

partiell-rekursive Funktionen
ein unbeschränkter linearer Operator

Anwendungen

Wenn ein Algorithmus Eingaben aus der Menge annimmt und Ausgaben aus der Menge liefert, dann berechnet er eine partielle Funktion von nach . Der Definitionsbereich dieser Funktion ist die Menge aller Elemente aus , für die der Algorithmus einen Wert liefert. Um einen Wert zu liefern, muss er insbesondere mit seiner Berechnung an ein Ende kommen (terminieren).

Basierend auf einem Artikel in:

Wikipedia.de