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 unter Verwendung der im Kalkül zugelassenen Schlussregeln.

Inhaltsverzeichnis

Beispiel: Aussagen- und Prädikatenlogik

Der Sequenzenkalkül beschäftigt sich mit der Ableitung von Sequenzen der Gestalt \Gamma \varphi\!\; mit Hilfe der Sequenzenregeln. Zur Illustration nehmen wir die Herleitung des Satzes vom ausgeschlossenen Dritten. Die verwendeten Regeln (Ann),(\vee -Kon1),(\vee -Kon2),(FU) werden in [1] beschrieben.


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

Genaugenommen haben wir damit eine neue Sequenzenregel abgeleitet, und zwar die abgeleitete Regel

\quad\left(AD\right)\qquad\frac{}{\varphi\vee\neg\varphi}\,,

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

Die Ableitbarkeitsrelation und der Ableitbarkeitsoperator

Definition

Zur Formalisierung der Ableitbarkeit wird oft der Ableitungsoperator (auch Inferenzoperation) verwendet, der über die Ableitungsrelation (auch Inferenzrelation)  \vdash \!\; definiert wird.

Wenn - gemäß den Regeln eines konkreten Kalküls - der Ausdruck φ (die Konklusion oder die Konsequenz) aus der Menge Θ (den Prämissen) in endlich vielen Schritten abgeleitet werden kann, schreibt man dafür \Theta \vdash \varphi \!\;; hierbei ist  \vdash \!\; 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. \Theta \vdash \varphi ist dabei zu lesen als: "φ ist aus Θ ableitbar".

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

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: \Theta \cup \{\varphi\}\vdash \varphi (Jede Annahme ist auch eine Folgerung).
  • Idempotenz: Wenn \Theta \vdash \varphi und \Theta \cup \{\varphi\} \vdash \psi, dann \Theta \vdash \psi (Durch Hinzunahme von Folgerungen zu den Annahmen erhält man keine neuen Folgerungen.)
  • Monotonie: Wenn \Theta \vdash \varphi, dann \Theta \cup \Delta \vdash \varphi (Hinzufügen von Annahmen erhält die bisher möglichen Folgerungen.)
  • Kompaktheit; Wenn \Theta \vdash \varphi, dann gibt es eine endliche Menge Δ mit \Delta \subseteq \Theta, so dass \Delta \vdash \varphi. (Jede Folgerung aus einer unendlichen Annahmenmenge ist bereits aus einer endlichen Teilmenge zu erreichen.)

Aus den ersten drei dieser Eigenschaften lässt sich folgern, dass H ein Hüllenoperator ist, d.h. eine extensive, monotone, idempotente Abbildung.

Quellen

  1. Regeln des Sequenzenkalküls

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Ableitung — ist Fachbegriff in unterschiedlichen Zusammenhängen: Mathematik: Ableitung einer Funktion, siehe Differentialrechnung Ableitung einer Menge im Teilgebiet Topologie Ableitung (Logik), eine formale Folgerung von neuen aus gegebenen Aussagen in der… …   Deutsch Wikipedia

  • Logik der Forschung — (Impressum 1935, tatsächlich 1934) bzw. The Logic of Scientific Discovery (1959) ist das erkenntnistheoretische Hauptwerk von Karl Popper. Er charakterisiert darin empirische Wissenschaft über das Abgrenzungskriterium der Falsifizierbarkeit und… …   Deutsch Wikipedia

  • Lōgik — (lat. logica, v. griech. logos, »Vernunft, Vernunftschluß«), Denklehre, d.h. die Wissenschaft, die sich mit der Erforschung der dem Denken innewohnenden und seine mannigfaltigen Betätigungen beherrschenden Gesetze beschäftigt. Daß es solche geben …   Meyers Großes Konversations-Lexikon

  • Logik — (v. gr.), ist die Wissenschaft von den Gesetzen. u. Formen des richtigen Denkens. Indem nämlich das Denken das Instrument alles Erkennens ist, entstand schon sehr früh das Bedürfniß, die Frage zu entscheiden, ob alle Arten der Gedankenbestimmung… …   Pierer's Universal-Lexikon

  • Ableitung — Dissipation; Herleitung; Derivation; Deduktion; Suffigierung (fachsprachlich) * * * Ab|lei|tung [ aplai̮tʊŋ], die; , en: 1. das Ableiten: die Ableitung der Formel war dann einfach. 2. (Sprachwiss.) von einem anderen Wort abgeleitetes Wort …   Universal-Lexikon

  • Aristotelische Logik — Gregor Reisch, „Die Logik präsentiert ihre zentralen Themen“, Margarita Philosophica, 1503/08 (?). Die beiden Hunde veritas und falsitas jagen de …   Deutsch Wikipedia

  • Interpretation (Logik) — Eine Interpretation (von lat. interpretatio: Auslegung, Erklärung, Deutung) im Sinn der mathematischen Logik ordnet allen zunächst bedeutungslosen oder unbestimmten Ausdrücken einer formalen Sprache einen konkreten Wert zu. Dadurch erhält die… …   Deutsch Wikipedia

  • Vollständigkeit (Logik) — Man bezeichnet ganz unterschiedliche Eigenschaften formaler Systeme bzw. Kalküle mit dem Begriff Vollständigkeit. Zur Unterscheidung werden die Begriffe Vollständigkeit von Theorien Vollständigkeit von Sequenzenkalkülen verwendet. Daneben wird… …   Deutsch Wikipedia

  • Einsetzungsregel (Logik) — Die Einsetzungsregel oder Ableitung durch Substitution ist eine Schlussregel vieler logischer Kalküle, die es erlaubt, aus einem Satz (einer allgemeingültigen Aussage) weitere abzuleiten und zu einer Aussage äquivalente Aussagen zu finden:… …   Deutsch Wikipedia

  • Ableitbar — Ableitung steht für: Ableitung einer Funktion in der Mathematik, siehe Differentialrechnung Ableitung einer Menge (im mathematischen Teilgebiet der Topologie) Ableitung (Logik), eine formale Folgerung von neuen aus gegebenen Aussagen in der… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”