Ableitung (Logik) - LinkFang.de





Ableitung (Logik)


Eine Ableitung, Herleitung, oder Deduktion ist in der Logik die Gewinnung von Aussagen aus anderen Aussagen. Dabei werden Schlussregeln auf Prämissen angewandt, um zu Konklusionen zu gelangen. Welche Schlussregeln dabei erlaubt sind, wird durch das verwendete Kalkül bestimmt.

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 Satzes vom ausgeschlossenen Dritten. Die verwendeten Regeln [math](Ann),(\vee -Kon1),(\vee -Kon2),(FU)[/math] werden in [1] 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 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: [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: 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; 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 unendlichen 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.h. eine extensive, monotone, idempotente Abbildung.

Quellen

  1. Regeln des Sequenzenkalküls

Kategorien: Mathematische Logik

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Ableitung (Logik) (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.