Moderne Termlogik: Standardsemantik der Termlogik: Korrektheit und Vollständigkeit

Aus Wikibooks
Zur Navigation springen Zur Suche springen
Nuvola apps bookcase.svg Hoch zum Inhaltsverzeichnis


Moderne Termlogik[Bearbeiten]

Standardsemantik der Termlogik[Bearbeiten]

Korrektheit und Vollständigkeit[Bearbeiten]

Es gibt jetzt zwei unterschiedliche Folgerungsbegriffe: Die syntaktische Folgerung , die auf dem Kalkül mit Zeichenketten beruht, und die semantische Folgerung , die mit der Mengenlehre arbeitet. Es ist nicht verwunderlich, dass wir die genauen Zusammenhänge zwischen diesen beiden Begriffen untersuchen wollen. Dazu werden zwei wichtige Begriffe eingeführt.

Definition: Ein Kalkül (mit dem die syntaktische Folgerung definiert wird), zusammen mit einer Semantik (durch die man die semantische Folgerung definiert) heisst korrekt, wenn gilt:

Aus folgt .


Definition: Ein Kalkül (mit dem die syntaktische Folgerung definiert wird), zusammen mit einer Semantik (durch die man die semantische Folgerung definiert) heisst vollständig, wenn gilt:

Aus folgt .

Nun lässt sich der Haupsatz beweisen, durch den die Bedeutung der klaren Unterscheidung zwischen Syntax und Semantik deutlich wird:

Satz: Der Kalkül der Termlogik, zusammen mit der Semantik der nichtleeren Mengen, ist korrekt und vollständig.

*Beweis: Korrektheit. Gegeben sei eine Menge von Aussagen. Wir nehmen an, dass mit Hilfe des Regelsystems des Kalküls eine syntaktische Folgerung gewonnnen wurde, dass also gilt. Wir müssen zeigen, dass auch gilt. Dazu gehen wir alle vier Grundregeln durch. Nehmen wir z.B. an, bei der Ableitung sei die Regel , benutzt worden; d.h. es gibt Terme , so dass gilt, und dass . Anders ausgedrückt: Aus wird abgeleitet. Wir können nun zeigen, dass auch gilt: Sei ein beliebiges Modell von ; d.h. es gelte . Dann ist , und es gilt auf jeden Fall . Das bedeutet, dass tatsächlich gilt. -- Mit der gleichen Methode kann man die Korrektheit der anderen drei Regeln beweisen (was wir hier nicht ausführen, sondern als Übungsaufgabe stellen). Da sich alle syntaktischen Ableitungen aus diesen vier Regeln nacheinander ausführen lassen, ist damit die Korrektheit des Kalküls und der Semantik bewiesen.

*Beweis: Vollständigkeit. Wie gewöhnlich ist der Beweis der Vollständigkeit schwieriger. Hier müssen wir beweisen, dass aus folgt.

Um den Beweis übersichtlich zu halten, werden wir den Beweisschritt 1 gesondert in einem Hilfssatz im Anschluss beweisen. Ein wichtiger Begriff ist der der Konsistenz einer Aussagenmenge: Eine Aussagenmenge heisst konsistent, wenn es keine Aussgae gibt mit und .

Beweisschritt 1. Es gelte . Dann ist inkonsistent.

Beweisschritt 2. Die Inkonsistenz von bedeutet, dass es eine Aussage gibt mit und . Die Beweismethode des indirekten Beweises ergibt, dass gilt, was zu beweisen war.

Zum Beweisschritt 1: Wir werden den folgenden Hilfssatz jetzt (noch nicht) beweisen, da er einige sehr "technische" Hilfsmittel erfordert, sondern den beweis im Anhang des Buches führen. Hier ist es wichtiger, die Stellung dieses wichtigen Ergebnisses im Kontext des Vollständigkeitsbeweises zu verstehen.

Hilfssatz. Für jede konsistente Menge von Aussagen gibt es ein Modell; d.h. eine Interpretation , die alle Aussagen von wahr macht.

Der Beweisschritt 1 ergibt sich nun aus dem Hilfssatz wie folgt: Sei im Gegensatz zur Folgerung im Beweisschritt 1 konsistent. Nach dem Hilfssatz gibt es dann ein Modell für , d.h eine Interpretation , die sowhl alle Aussagen von als auch wahr macht; d.h. interpretiert als wahr, aber als falsch. Daher ist nicht richtig im Gegensatz zur Annahme von Beweisschritt 1.