Man bezeichnet zwei ganz unterschiedliche Eigenschaften formaler Systeme bzw. Kalküle mit dem Begriff Vollständigkeit. Zur Unterscheidung werden die Begriffe
- syntaktische Vollständigkeit bzw.
- semantische Vollständigkeit
verwendet.
Syntaktische Vollständigkeit
Eine Menge von Ausdrücken eines formallogischen Systems (eines Kalküls), in dem eine Negation erklärt ist, heisst vollständig, wenn für jeden Ausdruck entweder oder gilt. Aus ist also entweder ein Ausdruck oder seine Negation herleitbar; das gilt für alle beliebigen Ausdrücke .
Für die Prädikatenlogik erster Stufe gilt der Satz von Lindenbaum : Jede konsistente (widerspruchsfreie) Ausdrucksmenge der Prädikatenlogik kann zu einer vollständigen Ausdrucksmenge erweitert werden.
Semantische Vollständigkeit
Umgangssprachlich ausgedrückt heisst ein formales System (ein Kalkül) semantisch vollständig, wenn jedes richtige Theorem auch abgeleitet werden kann. Präziser kann man das wie folgt beschreiben. Sei die Ableitungsbeziehung; sie wird rein syntaktisch mit Hilfe der Regeln eines syntaktischen Systems definiert, im Falle der Prädikatenlogik z.B. durch den Sequenzenkalkül. Hierbei handelt es sich um Regeln für die Zeichenmanipulation.
Dazu gibt es die Ebene der Semantik, z.B. in der Semantik der Aussagenlogik oder der Semantik der Prädikatenlogik. Auf der semantischen Ebene gibt es den Begriff der logischen Folgerung , ausgedrückt durch das Symbol , der im Rahmen der auf Alfred Tarski zurückgehenden Modelltheorie erklärt wird.
Von zentralem Interesse in der formalen Logik ist nun das Verhältnis zwischen (syntaktischer) Ableitung und (semantischer) Folgerung : Semantische Vollständigkeit bedeutet, dass aus stets folgt.
Die Umkehrung, dass also aus stets folgt, bezeichnet man als Korrektheit (auch semantische Korrektheit) eines formalen Systems.
Für konkrete formale Systeme ist die Korrektheit meist einfach zu beweisen, denn man achtet schon bei der Konstruktion des formalen Systems darauf, dass jede einzelne Regel in diesem Sinne korrekt ist. Ein Vollständigkeitsbeweis erfordert meist tiefliegendere Untersuchungen. Der Vollständigkeitssatz für die Prädikatenlogik erster Stufe wurde 1928 von Gödel bewiesen. Eine wichtige Beweismethode stammt von Henkin aus dem Jahre 1949.
Funktionale Vollständigkeit von Junktoren
Mit funktionaler Vollständigkeit bezeichnet man die Eigenschaft einer Menge von Junktoren eines logischen Systems, alle Junktoren des Systems darstellen zu können. In der klassischen Aussagenlogik ist zum Beispiel die Junktorenmenge funktional vollständig, d. h. es lassen sich alle denkbaren Junktoren alleine aus Konjunktion und Negation ausdrücken. -->
