Eine partielle Funktion von der Menge nach der Menge ist eine binäre, rechtseindeutige Relation, das heißt eine Relation, in der jedem Element der Menge höchstens ein Element der Menge zugeordnet wird. Im Unterschied zum üblichen Funktionsbegriff der Mathematik kann bei einer partiellen Funktion der Definitionsbereich eine echte Teilmenge von sein – eine partielle Funktion kann demnach auf einen undefinierten Ausdruck abbilden. Der Begriff der partiellen Funktion ist in der Theoretischen Informatik, insbesondere in der Berechenbarkeitstheorie verbreitet.

Beschreibung

Bearbeiten

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. Falls 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   gilt  , für (totale) Funktionen   gilt  .[1]

Als Definitionsbereich   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   gilt.

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

  1. als Funktion   oder
  2. als Funktion  
Der Wert   („undefiniert“) darf dazu nicht in   sein.[2]

Schreibweisen

Bearbeiten

Für „  ist eine partielle Funktion von   nach  “ schreibt man:  [2] oder  , alternativ auch  ,   oder  . Nicht empfehlenswert sind u. a. die Schreibweisen   sowie  , denn erstere definiert   als (totale) Funktion und zweitere ist leicht mit   zu verwechseln, was jedoch bedeutet, dass   keine (totale) Funktion von   nach   ist. Dies ist aber wie ersteres im Allgemeinen nicht zutreffend.

Die Schreibweise „  ist undefiniert“ oder sogar „ “ ist problematisch, denn der Ausdruck   ist ja dann gerade nicht zulässig. Klarer ist es zu sagen „  ist undefiniert an der Stelle  “ oder als Formel „ “.

Beispiele

Bearbeiten
  • Die partielle Funktion   ist an der Stelle   undefiniert, weil die Division durch   in den reellen Zahlen unzulässig ist. Man kann bilden
 
oder
 

Anwendungen

Bearbeiten

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).

Einzelnachweise

Bearbeiten
  1. Technische Universität Braunschweig Partielle und totale Funktionen (PDF; 112 kB).
  2. a b Thomas Holder: partial map classifier, auf: nLab, 3. Juli 2015