Benutzer:Dhanyavaada/Ableitung (Logik)

Unter Ableitung oder Herleitung, auch Deduktion, versteht man in der Logik die Gewinnung von Sätzen (den Konklusionen) aus anderen Sätzen (den Prämissen) in einem formalen Kalkül nach den im Kalkül zugelassenen Schlussregeln.

Beispiel: Prädikatenlogik

Der Sequenzenkalkül beschäftigt sich mit der Ableitung von Sequenzen der Gestalt

$\Gamma \phi \!\;$

mit Hilfe der Sequenzenregeln. Wenn die Sequenz $\Gamma \phi \!\;$ abgeleitet werden kann, schreibt man auch $\Gamma \vdash \phi \!\;$; hierbei ist $\vdash \!\;$ der Ableitungsoperator. Die einfache Anwendung einer solchen Regel auf Aussagen nennt man einen Ableitungsschritt. Eine Aussage $\phi$ heißt ableitbar oder beweisbar aus einer gegebenen Menge $\Theta$ von Aussagen, wenn sie durch eine endliche Folge von Ableitungsschritten erreicht werden kann, wobei man von einer (ggf. leeren) Aussagenmenge $\Theta$, den Prämissen oder Annahmen, ausgeht.

Fügt man alle ableitbaren Aussagen zur Aussagenmenge hinzu (man sagt, man bildet den deduktiven Abschluss), so erhält man eine Theorie.

Beispiel: Aussagenlogik

$\Theta \quad =\quad \{\phi ,\psi ,\zeta \}$

sei als Aussagenmenge gegeben und eine Ableitungsregel des Kalküls sei

$\phi \qquad \psi \over \phi \wedge \psi$,

so kann z. B. $\phi \wedge \psi$ und $\zeta \wedge \psi \wedge \phi$ abgeleitet werden.

Bei der Ableitbarkeitsrelation (bzw. dem Ableitbarkeitsbegriff, auch Inferenzrelation) handelt es sich um eine Relation zwischen einer Menge von Aussagen, den Prämissen, und einer einzelnen Aussage, der Konklusion. Zur Formalisierung der Ableitbarkeit wird oft der Ableitungsoperator $\,\vdash$ verwendet. $\Theta \vdash \phi$ ist dabei zu lesen als: "aus $\Theta$ ist $\phi$ ableitbar". Führen wir obiges Beispiel fort, so können wir schreiben:

$\{\phi ,\psi ,\zeta \}\vdash \phi$, $\{\phi ,\psi ,\zeta \}\vdash \psi$, $\{\phi ,\psi ,\zeta \}\vdash \zeta$, $\{\phi ,\psi ,\zeta \}\vdash \phi \wedge \phi$, $\{\phi ,\psi ,\zeta \}\vdash \phi \wedge \psi$, $\{\phi ,\psi ,\zeta \}\vdash \phi \wedge \zeta$, $\{\phi ,\psi ,\zeta \}\vdash \psi \wedge \phi$, $\{\phi ,\psi ,\zeta \}\vdash \psi \wedge \psi$ usw.

Unterschiedliche Logiken definieren jeweils einen unterschiedlichen Ableitbarkeitsbegriff. So gibt es einen aussagenlogischen Ableitbarkeitsbegriff, einen prädikatenlogischen, einen Intuitionistischen, einen modallogischen usw.

Eigenschaften von Ableitungsoperatoren

Es gibt eine Reihe von Eigenschaften, die den meisten Ableitbarkeitsrelationen (zumindest den obengenannten) gemeinsam sind

• Inklusion: $\Gamma \cup \{\mathrm {A} \}\vdash \mathrm {A}$ (Jede Annahme ist auch eine Folgerung).
• Idempotenz: Wenn $\Gamma \vdash \mathrm {A}$ und $\Gamma \cup \{\mathrm {A} \}\vdash \mathrm {B}$, dann $\Gamma \vdash \mathrm {B}$ (Durch Hinzunahme von Folgerungen zu den Annahmen erhält man keine neuen Folgerungen.)
• Monotonie: Wenn $\Gamma \vdash \mathrm {A}$, dann $\Gamma \cup \Delta \vdash \mathrm {A}$ (Hinzufügen von Annahmen erhält die bisher möglichen Folgerungen.)
• Kompaktheit; Wenn $\Gamma \vdash \mathrm {A}$, dann gibt es eine endliche Menge $\Delta$ mit $\Delta \subseteq \Gamma$, so dass $\Delta \vdash \mathrm {A}$. (Jede Folgerung aus einer unendlichen Annahmenmenge ist bereits aus einer endlichen Teilmenge zu erreichen.)

Siehe auch

Folgerung

Inferenzoperation

Kalkül