Quelltext der Seite Ableitung (Logik)

Eine '''Ableitung''', '''Herleitung''', oder [[Deduktion]] ist in der [[Logik]] die Gewinnung von [[Aussage (Logik)|Aussagen]] aus anderen Aussagen. Dabei werden [[Schlussregel]]n auf [[Prämisse]]n angewandt, um zu [[Konklusion]]en zu gelangen. Welche Schlussregeln dabei erlaubt sind, wird durch den verwendeten [[Kalkül]] bestimmt.<ref>Ein Beispiel für eine Definition geben Kruse und Borgelt (2008) auf S. 8.</ref>

Die Ableitung ist zusammen mit der [[Semantische Folgerung|semantischen Folgerung]] eine der zwei logischen Methoden, um auf die Konklusion zu kommen.

== Beispiel: Aussagen- und Prädikatenlogik ==
Der [[Sequenzenkalkül]] beschäftigt sich mit der Ableitung von Sequenzen der Gestalt <math>\Gamma \varphi</math>
mit Hilfe der Sequenzenregeln.
Zur Illustration nehmen wir die Herleitung des [[Satz vom ausgeschlossenen Dritten|Satzes vom ausgeschlossenen Dritten]]. Die verwendeten Regeln <math>(Ann),(\vee -Kon1),(\vee -Kon2),(FU)</math> werden in den [[Sequenzenkalkül#Im Sequenzenkalkül gültige Regeln|Regeln des Sequenzenkalküls]] der [[Prädikatenlogik erster Stufe]] beschrieben.

<math>
\begin{alignat}{3}
 \text {1. Ableitungsschritt:}\quad & \varphi\varphi &\quad & (Ann)\\
 \text {2. Ableitungsschritt:} \quad & \varphi (\varphi\vee\neg\varphi ) &\quad & (\vee -Kon1):\, 1.\\
 \text {3. Ableitungsschritt:} \quad & \neg\varphi\neg\varphi &\quad & (Ann)\\
 \text {4. Ableitungsschritt:} \quad & \neg\varphi (\varphi\vee\neg\varphi ) &\quad & (\vee -Kon2):\, 3.\\
 \text {5. Ableitungsschritt:} \quad & (\varphi\vee\neg\varphi ) &\quad & (FU):\, 2.,4.
\end{alignat}
</math>

Damit wurde die folgende neue Sequenzenregel abgeleitet:

<math>\quad\left(AD\right)\qquad\frac{}{\varphi\vee\neg\varphi}</math>

Sie kann nun genau wie die Grundregeln des Kalküls verwendet werden.

== Die Ableitbarkeitsrelation und der Ableitbarkeitsoperator ==
=== Definition ===
Zur Formalisierung der Ableitbarkeit wird oft der '''Ableitungsoperator''' (auch Inferenzoperation) verwendet, der über die ''Ableitungsrelation'' (auch ''Inferenzrelation'') <math> \vdash</math> definiert wird.

Wenn – gemäß den Regeln eines konkreten Kalküls – der Ausdruck <math>\varphi</math> (die Konklusion oder die Konsequenz) aus der Menge <math>\Theta</math> (den Prämissen) in endlich vielen Schritten abgeleitet werden kann, schreibt man dafür
<math>\Theta \vdash \varphi</math>; hierbei ist <math> \vdash</math> die ''Ableitungsrelation''.

Bei dieser ''Ableitbarkeitsrelation'' (auch ''Inferenzrelation'') handelt es sich um eine Relation zwischen einer Menge von Aussagen, den Prämissen, und einer einzelnen Aussage, der Konklusion. <math>\Theta \vdash \varphi</math> ist dabei zu lesen als: „<math>\varphi</math> ist aus <math>\Theta</math> ableitbar“.

Fügt man einer gegebenen Menge <math>\Theta</math> von Ausdrücken ''alle'' aus <math>\Theta</math> ableitbaren Ausdrücke hinzu (man sagt, man bilde den deduktiven Abschluss), so wird dadurch der Ableitungsoperator (auch [[Inferenzoperation]]) <math>H</math> definiert:
<math>H(\Theta)=\{ \varphi |\Theta\vdash \varphi \}</math>

Unterschiedliche Logiken definieren jeweils einen unterschiedlichen Ableitbarkeitsbegriff. So gibt es einen [[Aussagenlogik|aussagenlogischen]] Ableitbarkeitsbegriff, einen [[Prädikatenlogik|prädikatenlogischen]], einen [[Intuitionismus|intuitionistischen]], einen [[Modallogik|modallogischen]] usw.

=== Eigenschaften von Ableitungsoperatoren ===

Es gibt eine Reihe von Eigenschaften, die den Ableitbarkeitsrelationen [[Klassische Logik|klassischer]] und auch zahlreicher [[Nichtklassische Logik|nichtklassischer]] Logiken  gemeinsam sind

* Inklusion: <math>\Theta \cup \{\varphi\}\vdash \varphi</math> (Jede Annahme ist auch eine Folgerung).
* Idempotenz: Wenn <math>\Theta \vdash \varphi</math> und <math>\Theta \cup \{\varphi\} \vdash \psi</math>, dann <math>\Theta \vdash \psi</math> (Durch Hinzunahme von Folgerungen zu den Annahmen erhält man keine neuen Folgerungen.)
* [[Monotonie (Logik)|Monotonie]]: Wenn <math>\Theta \vdash \varphi</math>, dann <math>\Theta \cup \Delta \vdash \varphi</math> (Hinzufügen von Annahmen erhält die bisher möglichen Folgerungen.)
* [[Kompaktheit (Logik)|Kompaktheit]]; Wenn <math>\Theta \vdash \varphi</math>, dann gibt es eine endliche Menge <math>\Delta</math> mit <math>\Delta \subseteq \Theta</math>, so dass <math>\Delta \vdash \varphi</math>. (Jede Folgerung aus einer [[unendlich]]en Annahmenmenge ist bereits aus einer endlichen [[Teilmenge]] zu erreichen.)

Aus den ersten drei dieser Eigenschaften lässt sich folgern, dass <math>H</math> ein [[Hüllenoperator]] ist, d.&nbsp;h. eine [[Extensive Abbildung|extensive]], [[Monotone Abbildung|monotone]], [[Idempotenz|idempotente]] [[Abbildung (Mathematik)|Abbildung]].

== Einzelnachweise und Anmerkungen ==
<references />

== Literatur ==
* {{Literatur
   |Autor=R. Kruse, C. Borgelt
   |Titel=Grundbegriffe der Prädikatenlogik
   |Band=Computational Intelligence
   |Verlag=Otto-von-Guericke Universität
   |Ort=Magdeburg
   |Datum=2008
   |Seiten=14
   |Online=http://fuzzy.cs.ovgu.de/studium/ise/txt_05/logic.pdf
   |Format=PDF
   |KBytes=164}}

[[Kategorie:Mathematische Logik]]