Korrektheit (Logik)

Korrektheit (englisch soundness) ist eine wichtige Eigenschaft formaler Systeme oder Kalküle und betrifft den Zusammenhang zwischen Syntax und Semantik, der umgangssprachlich lautet: Was ableitbar ist, ist auch semantisch richtig.

In der mathematischen Sprache wird die Korrektheit mit dem syntaktischen Ableitbarkeitsoperator $\vdash$ und dem semantischen Folgerungsoperator $\models$ ausgedrückt: Ein Kalkül heißt korrekt, wenn aus $\Sigma \vdash \Psi$ stets $\Sigma \models \Psi$ folgt. Dabei wird die Semantik des Kalküls festgelegt durch eine Klasse von Modellen. $\Sigma \models \Psi$ bedeutet, dass jede Interpretation, die Modell von $\,\Sigma$ ist, auch Modell von $\,\Psi$ ist.

Die Korrektheit ist eine Mindestanforderung an einen Kalkül. Sie wird hergestellt, indem jede Regel des Kalküls korrekt gewählt wird. Aus der Korrektheit folgt die Widerspruchsfreiheit des Kalküls: Man muss nur eine einzige Formel angeben, die in irgendeinem Modell falsch ist, dann kann sie in einem korrekten Kalkül auch nicht ableitbar sein. In der klassischen Logik ist ein Widerspruch $A\ \and \neg A$ solch eine falsche Formel, in der Prädikatenlogik mit Gleichheit etwa die Formel $A\neq A$.

Das Gegenstück zur Korrektheit ist die Vollständigkeit eines formalen Systems. Sie besagt: Was semantisch richtig ist, lässt sich auch ableiten. Vollständigkeitssätze sind meist weitaus schwieriger zu beweisen als Korrektheitssätze; so bereitet der Beweis für die Korrektheit des Sequenzenkalküls der Prädikatenlogik keine Probleme,^[1] während der Vollständigkeitssatz schwieriger ist.

Siehe auch

• Allgemeingültigkeit
• Gültigkeit
• Fehlschluss

Einzelnachweis

1. ↑ Ebbinghaus, Einführung in die mathematische Logik, Mannheim-Leipzig-Wien-Zürich 1992, S. 74

Quellen

• H.D. Ebbinghaus, J. Flum, W. Thomas: Einführung in die mathematische Logik. Mannheim-Leipzig-Wien-Zürich; BI-Wiss. Verlag, 1992, ISBN 3-411-15603-1
• Hans-Peter Tuschik, Helmut Wolter: Mathematische Logik - kurzgefasst. Grundlagen, Modelltheorie, Entscheidbarkeit, Mengenlehre. Mannheim-Leipzig-Wien-Zürich; BI-Wiss. Verlag, 1994, ISBN 3-411-16731-9