Semantische Folgerung

Der Begriff der semantischen Folgerung ist in der Modelltheorie eine Form der Implikation. Aus jeder Semantik, das heißt einem Raum möglicher Interpretationen der Sätze einer formalen, logischen Sprache, ergibt sich ein Begriff semantischer Folgerung. Diese ist so definiert, dass ein Satz genau dann aus einer Menge von Sätzen folgt, wenn in jeder Interpretation, in der die Sätze gelten (wahr sind), auch der Satz gilt (wahr ist). Gegenbegriff zur semantischen Folgerung ist die Deduktion, welche sich aus der Anwendung der Schlussregeln eines Beweiskalküls ergibt, das heißt – typischerweise berechenbaren – ohne Verweis auf Interpretationen definierte syntaktische Transformationen auf Sätzen. Zur Unterscheidung wird das Symbol für die semantische und für die syntaktische Folgerungsrelation (Deduktion) verwendet. Durch Vergleich mit einer semantischen Folgerungsrelation lassen sich dabei auch Rückschlüsse über die Verhältnisse und Eigenschaften von Beweiskalkülen gewinnen: So sind die Ableitungsrelationen und je nach Wahl der Semantik auf der einen Seite und des Kalküls auf der anderen Seite im Allgemeinen nicht gleich mächtig. Nur in besonderen, aber auch besonders wichtigen Fällen, wie in der klassischen Aussagen- und Prädikatenlogik erster Stufe mit der Tarski-Semantik auf der einen Seite und den üblichen Kalkülen auf der anderen Seite, sind sie äquivalent. In dem Fall, dass jede syntaktische Folgerung auch eine semantische Folgerung ist, spricht man von Korrektheit, im umgekehrten Fall, dass es zu jeder semantischen Folgerung auch eine syntaktische Ableitung gibt, von Vollständigkeit.

DefinitionBearbeiten

Die Relation  Bearbeiten

Seien   und   Mengen von Aussagen. Wenn jedes Modell von   ein Modell von   ist, so ist die semantische Folgerungsrelation erfüllt und man schreibt  .

In der Literatur üblich ist die Verwendung einer Struktur statt einer Aussagenmenge   auf der linken Seite von  . In diesem Fall wird gelesen: „  ist ein Modell von  “ oder auch „  ist in   erfüllt“. Genau genommen ist dies keine Folgerungsrelation im gerade genannten Sinn, sondern eine Erfüllbarkeitsrelation. Aber da die semantische Folgerung durch die Erfüllbarkeit von Aussagenmengen in Strukturen definiert wird, ist die Mehrdeutigkeit unproblematisch.

In der theoretischen Informatik ist die Menge   stets endlich und man betrachtet nur endliche Modelle. Daher ist es dort üblich, die Menge   als die endliche Menge der Zustände, die die Aussagen aus   erfüllen, zu definieren. Auch dies ist genau genommen keine Folgerungs-, sondern eine Erfüllbarkeitsrelation. Aber auch hier ist dieser Gebrauch kompatibel mit der mathematischen Definition.

TautologieBearbeiten

Ist eine Formel unter allen Belegungen erfüllt, also immer wahr, so ist sie eine Tautologie:

 

Dies ist das semantische Gegenstück zum Theorem. Ist eine Formel nie erfüllt, so handelt es sich um einen Widerspruch (Kontradiktion).

Alternative BezeichnungenBearbeiten

Die semantische Folgerung   wird auch „Mathematisches Schließen“ (besonders in der Prädikatenlogik) oder „modelltheoretische Folgerung“ genannt. Die Erfüllbarkeitsrelation   heißt auch „Modellrelation“ oder „Tarskis Erfüllbarkeitsrelation“.

Bezug zur syntaktischen FolgerungBearbeiten

Sei ein Kalkül mit Ableitungsrelation   gegeben. Seien   und   Formeln im Kalkül. Der Kalkül heißt

  • semantisch vollständig, falls aus   folgt  ,
  • semantisch widerspruchsfrei oder korrekt, falls aus   folgt  .[1]

Ist der Kalkül semantisch vollständig und widerspruchsfrei, so heißt er adäquat. Wichtige Beispiele hierfür sind die Prädikatenlogik erster Stufe und die Aussagenlogik.

Syntaktische und Semantische Folgerung in der AussagenlogikBearbeiten

Die syntaktische Ableitung sieht folgendermaßen aus:

 

Somit ist der Ausdruck   gültig.

In der Aussagenlogik lässt sich die semantische Folgerung anhand einer Wahrheitstabelle überprüfen. Um diese anzuwenden, überprüft man, ob die Konklusion bei allen Belegungen, bei denen die Prämissen wahr sind, wahr ist.

     
wahr wahr wahr
wahr falsch falsch
falsch wahr falsch
falsch falsch falsch

Immer wenn   erfüllt ist, so ist es auch  . Somit folgt  .

In der Mathematik ist die semantische Folgerung das Vorbild für Logikkalküle.

Weitere BeispieleBearbeiten

Formel gültig? Begründung
  ungültig Möglichkeit:  
  gültig immer:  
  gültig rechts keine Abhängigkeit von links

Siehe auchBearbeiten

LiteraturBearbeiten

  • Michael Schenke: Logikkalküle in der Informatik. Springer Vieweg, Wiesbaden 2013.
  • Michael Huth, Mark Ryan: Logic in Computer Science – Modelling and Reasoning about Systems, 2. Aufl., Cambridge University Press, 2005, ISBN 0-521-54310-X Website
  • Uwe Schöning: Logik für Informatiker, 5. Aufl., Spektrum Akademischer Verlag, 2000. Kapitel 1.1 und 2.1. (Nur Aussagenlogik und Prädikatenlogik).

ReferenzenBearbeiten

  1. Dirk W. Hoffmann: Die Grenzen der Mathematik. 3. Auflage. Springer Spektrum, Berlin, Heidelberg 2018, S. 76.