Seite parallel anzeigen





Du befindest dich hier: Logik Einführung / Beweis & Schluss

Korrektheit & Vollständigkeit

(Logik Einführung Kapitel 7.3)

Diese Seite nimmt Bezug auf

(Seite parallel anzeigen)
Liste überspringen
Zum Seitenanfang

Da wir in der Logik ein semantisches Konzept der Schlussfolgerung formalisieren wollen, sind wir natürlich bestrebt, den semantischen Folgerungsoperator |= durch einen syntaktischen Ableitungsoperator |-- nachzubilden.

Wir sagen
  • ein Kalkül ist korrekt, wenn sich nur semantisch gültige Sätze der zugrunde liegenden Logik ableiten lassen.
    D.h. wenn Γ|--γ gilt, gilt auch Γ|=γ.
     
  • ein Kalkül ist vollständig, wenn sich alle semantisch gültige Sätze der zugrunde liegenden Logik ableiten lassen.
    D.h. wenn Γ|=γ gilt, gilt auch Γ|--γ.

Ein Kalkül ist adäquat, wenn er vollständig und korrekt ist

Ist ein Kalkül adäquat, können in ihm genau alle gültigen Aussagen der zugrunde liegenden Logik abgeleitet werden.

Selbstverständlich sind wir bestrebt, einen adäquaten Kalkül für unsere Problemstellung zu finden.
Wie Kurt Gödel jedoch in seinem Unvollständigkeitssatz bewiesen hat, ist es für alle Systeme, die so mächtig sind wie die Arithmetik, nicht mehr möglich solch einen Kalkül zu definieren.

Außerdem ist zu bemerken, dass ein korrekter Kalkül immer widerspruchsfrei ist - denn wäre ein Widerspruch vorhanden bzw. ableitbar, wäre in weiterer Folge alles ableitbar und damit auch alle nichtgültigen Formeln.