www.wikidata.de-de.nina.az

Semantische Folgerung Der Begriff der semantischen Folgerung ist in der Modelltheorie eine Form der Implikation Aus jede

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.

Definition Bearbeiten

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.

Tautologie Bearbeiten

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 Bezeichnungen Bearbeiten

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 Folgerung Bearbeiten

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

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 Aussagenlogik Bearbeiten

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 Beispiele Bearbeiten

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

Siehe auch Bearbeiten

Literatur Bearbeiten

  • 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).

Einzelnachweise Bearbeiten

  1. Dirk W. Hoffmann: Die Grenzen der Mathematik. 3. Auflage. Springer Spektrum, Berlin, Heidelberg 2018, S. 76.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Der Begriff der semantischen Folgerung ist in der Modelltheorie eine Form der Implikation Aus jeder Semantik das heisst einem Raum moglicher Interpretationen der Satze einer formalen logischen Sprache ergibt sich ein Begriff semantischer Folgerung Diese ist so definiert dass ein Satz B displaystyle B genau dann aus einer Menge von Satzen A 1 A 2 displaystyle A 1 A 2 ldots folgt wenn in jeder Interpretation in der die Satze A 1 A 2 displaystyle A 1 A 2 ldots gelten wahr sind auch der Satz B displaystyle B gilt wahr ist Gegenbegriff zur semantischen Folgerung ist die Deduktion welche sich aus der Anwendung der Schlussregeln eines Beweiskalkuls ergibt das heisst typischerweise berechenbaren ohne Verweis auf Interpretationen definierte syntaktische Transformationen auf Satzen Zur Unterscheidung wird das Symbol displaystyle models fur die semantische und displaystyle vdash fur die syntaktische Folgerungsrelation Deduktion verwendet Durch Vergleich mit einer semantischen Folgerungsrelation lassen sich dabei auch Ruckschlusse uber die Verhaltnisse und Eigenschaften von Beweiskalkulen gewinnen So sind die Ableitungsrelationen displaystyle models und displaystyle vdash je nach Wahl der Semantik auf der einen Seite und des Kalkuls auf der anderen Seite im Allgemeinen nicht gleich machtig Nur in besonderen aber auch besonders wichtigen Fallen wie in der klassischen Aussagen und Pradikatenlogik erster Stufe mit der Tarski Semantik auf der einen Seite und den ublichen Kalkulen auf der anderen Seite sind sie aquivalent 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 Vollstandigkeit Inhaltsverzeichnis 1 Definition 1 1 Die Relation 1 2 Tautologie 1 3 Alternative Bezeichnungen 2 Bezug zur syntaktischen Folgerung 3 Syntaktische und Semantische Folgerung in der Aussagenlogik 3 1 Weitere Beispiele 4 Siehe auch 5 Literatur 6 EinzelnachweiseDefinition BearbeitenDie Relation Bearbeiten Seien F displaystyle Phi nbsp und PS displaystyle Psi nbsp Mengen von Aussagen Wenn jedes Modell von F displaystyle Phi nbsp ein Modell von PS displaystyle Psi nbsp ist so ist die semantische Folgerungsrelation erfullt und man schreibt F PS displaystyle Phi models Psi nbsp In der Literatur ublich ist die Verwendung einer Struktur statt einer Aussagenmenge F displaystyle Phi nbsp auf der linken Seite von F PS displaystyle Phi models Psi nbsp In diesem Fall wird gelesen F displaystyle Phi nbsp ist ein Modell von PS displaystyle Psi nbsp oder auch PS displaystyle Psi nbsp ist in F displaystyle Phi nbsp erfullt Genau genommen ist dies keine Folgerungsrelation im gerade genannten Sinn sondern eine Erfullbarkeitsrelation Aber da die semantische Folgerung durch die Erfullbarkeit von Aussagenmengen in Strukturen definiert wird ist die Mehrdeutigkeit unproblematisch In der theoretischen Informatik ist die Menge F displaystyle Phi nbsp stets endlich und man betrachtet nur endliche Modelle Daher ist es dort ublich die Menge F displaystyle Phi nbsp als die endliche Menge der Zustande die die Aussagen aus PS displaystyle Psi nbsp erfullen zu definieren Auch dies ist genau genommen keine Folgerungs sondern eine Erfullbarkeitsrelation Aber auch hier ist dieser Gebrauch kompatibel mit der mathematischen Definition Tautologie Bearbeiten Ist eine Formel unter allen Belegungen erfullt also immer wahr so ist sie eine Tautologie ps displaystyle models psi nbsp Dies ist das semantische Gegenstuck zum Theorem Ist eine Formel nie erfullt so handelt es sich um einen Widerspruch Kontradiktion Alternative Bezeichnungen Bearbeiten Die semantische Folgerung displaystyle models nbsp wird auch Mathematisches Schliessen besonders in der Pradikatenlogik oder modelltheoretische Folgerung genannt Die Erfullbarkeitsrelation displaystyle models nbsp heisst auch Modellrelation oder Tarskis Erfullbarkeitsrelation Bezug zur syntaktischen Folgerung BearbeitenSei ein Kalkul mit Ableitungsrelation displaystyle vdash nbsp gegeben Seien ϕ displaystyle phi nbsp und ps displaystyle psi nbsp Formeln im Kalkul Der Kalkul heisst semantisch vollstandig falls aus ϕ ps displaystyle phi models psi nbsp folgt ϕ ps displaystyle phi vdash psi nbsp semantisch widerspruchsfrei oder korrekt falls aus ϕ ps displaystyle phi vdash psi nbsp folgt ϕ ps displaystyle phi models psi nbsp 1 Ist der Kalkul semantisch vollstandig und widerspruchsfrei so heisst er adaquat Wichtige Beispiele hierfur sind die Pradikatenlogik erster Stufe und die Aussagenlogik Syntaktische und Semantische Folgerung in der Aussagenlogik BearbeitenDie syntaktische Ableitung sieht folgendermassen aus 1 Ableitungsschritt p q A n n 2 Ableitungsschritt p E l i m i n a t i o n displaystyle begin alignedat 3 text 1 Ableitungsschritt quad amp p wedge q amp quad amp Ann text 2 Ableitungsschritt quad amp p amp quad amp wedge Elimination end alignedat nbsp Somit ist der Ausdruck p q p displaystyle p wedge q vdash p nbsp gultig In der Aussagenlogik lasst sich die semantische Folgerung anhand einer Wahrheitstabelle uberprufen Um diese anzuwenden uberpruft man ob die Konklusion bei allen Belegungen bei denen die Pramissen wahr sind wahr ist p displaystyle p nbsp q displaystyle q nbsp p q displaystyle p wedge q nbsp wahr wahr wahrwahr falsch falschfalsch wahr falschfalsch falsch falschImmer wenn p q displaystyle p wedge q nbsp erfullt ist so ist es auch p displaystyle p nbsp Somit folgt p q p displaystyle p wedge q models p nbsp In der Mathematik ist die semantische Folgerung das Vorbild fur Logikkalkule Weitere Beispiele Bearbeiten Formel gultig Begrundungp q p displaystyle p vee q models p nbsp ungultig Moglichkeit p f q t p q t displaystyle p f q t p vee q t nbsp q p q p displaystyle neg q p vee q models p nbsp gultig immer q f p q t p t displaystyle q f Longrightarrow p vee q t longrightarrow p t nbsp p q q displaystyle p models q vee neg q nbsp gultig rechts keine Abhangigkeit von linksSiehe auch BearbeitenModelltheorie Korrektheit Logik Vollstandigkeit Logik Literatur BearbeitenMichael Schenke Logikkalkule 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 Schoning Logik fur Informatiker 5 Aufl Spektrum Akademischer Verlag 2000 Kapitel 1 1 und 2 1 Nur Aussagenlogik und Pradikatenlogik Einzelnachweise Bearbeiten Dirk W Hoffmann Die Grenzen der Mathematik 3 Auflage Springer Spektrum Berlin Heidelberg 2018 S 76 Abgerufen von https de wikipedia org w index php title Semantische Folgerung amp oldid 227386535