Quelltext der Seite Prädikatenlogik erster Stufe

Die '''Prädikatenlogik erster Stufe''' ist ein Teilgebiet der [[Mathematische Logik|mathematischen Logik]]. Sie befasst sich mit der Struktur gewisser mathematischer Ausdrücke und dem logischen Schließen, mit dem man von derartigen Ausdrücken zu anderen gelangt. Dabei gelingt es, sowohl die Sprache als auch das Schließen rein syntaktisch, das heißt ohne Bezug zu mathematischen Bedeutungen, zu definieren.
Das dadurch ermöglichte Zusammenspiel von rein syntaktischen Überlegungen einerseits und semantischen Betrachtungen andererseits führt zu wichtigen Erkenntnissen, die Bedeutung für die gesamte Mathematik haben, denn diese lässt sich mittels der [[Zermelo-Fraenkel-Mengenlehre]] in der [[Prädikatenlogik]] erster Stufe formulieren. Im Unterschied zur [[Aussagenlogik]] macht die Prädikatenlogik von [[Quantor]]en Gebrauch.

== Ein motivierendes Beispiel ==
Die unten aufzustellenden Definitionen sollen am Beispiel der Theorie der [[Geordnete abelsche Gruppe|geordneten abelschen Gruppen]] [[motiviert]] werden. Eine geordnete abelsche Gruppe besteht zunächst aus einer [[Abelsche Gruppe|abelschen Gruppe]] <math>(G,+)</math>, das heißt, man hat folgende Eigenschaften
* ''[[Assoziativgesetz]]'': Für alle <math>x,y,z\in G</math> gilt: <math>(x+y)+z\,=\,x+(y+z)</math>.
* ''[[Kommutativgesetz]]'': Für alle <math>x,y\in G</math> gilt: <math>x+y\,=\,y+x</math>.
* ''[[Neutrales Element]] 0'': Für alle <math>x\in G</math> gilt: <math>x+0\,=\,x</math>.
* ''[[Inverses Element]]'': Für alle <math>x\in G</math> gibt es ein <math>-x\in G</math>, sodass gilt: <math>x+(-x)\,=\,0</math>.
In mathematischer Kurzschreibweise kann man das auch als
:<math>\forall x y z\colon (x+y)+z=x+(y+z),\quad \forall x y\colon x+y=y+x,\quad \forall x\colon x+0=x,\quad \forall x\colon x+(-x)=0</math>
wiedergeben. Dabei schreiben wir <math>\forall x</math> an Stelle des oft verwendeten <math>\forall x\in G</math>, da wir hier ohnehin über nichts anderes als die Elemente der Gruppe etwas aussagen wollen. Ferner haben wir eine <math>\le</math>-Relation für die Ordnung auf der Gruppe, die den folgenden Axiomen genügen muss, die hier gleich in Kurzschreibweise angegeben werden:
* ''Reflexivität'': <math>\forall x\colon x\le x</math>
* ''Transitivität'': <math>\forall x y z\colon ((x\le y \land y\le z) \rightarrow x\le z )</math>
* ''Gruppenverträglichkeit'': <math>\forall x y z\colon (x\le y \rightarrow x+z\le y+z )</math>

Beispiele für geordnete abelsche Gruppen sind etwa <math>(\R,+,\le)</math> oder <math>(\Z,+,\le)</math>.

Insgesamt haben wir einige der sogenannten [[Liste mathematischer Symbole#Logik|logischen Symbole]] <math>\forall, \exists, \land, \lor, \rightarrow, \leftrightarrow, \neg</math> verwendet, Klammern als Hilfssymbole, ferner das [[Gleichheitszeichen]] und Variablen für die Elemente. Die für die Theorie der geordneten abelschen Gruppen charakteristischen Symbole sind die Konstante 0, die [[Funktion (Mathematik)|Funktionen]] + und − sowie die [[Relation (Mathematik)|Relation]] <math>\le</math>, wobei die in der Mathematik üblichen Schreibweisen benutzt wurden, das heißt <math>x+y</math> statt <math>+(x,y)</math> bzw. <math> x\le y</math> statt <math>(x,y)\in {\le}</math>. Die beiden Funktionen haben unterschiedliche [[Stelligkeit]], + ist zweistellig, die Inversenbildung − ist einstellig, die betrachtete Ordnungsrelation ist zweistellig. Damit sind die Symbole einer ganz bestimmten Sprache beschrieben, in der man die Theorie der geordneten abelschen Gruppen formulieren kann. Manche der aus den Symbolen gebildeten Zeichenketten sind „vernünftig“, d.&nbsp;h. nach gewissen Gesetzmäßigkeiten gebildet, und manche von diesen drücken darüber hinaus „wahre Aussagen“ aus. Dies wird im Folgenden verallgemeinert, insbesondere werden der Unterschied zwischen den nach Regeln gebildeten „vernünftigen“ Zeichenketten und einem möglichen „Wahrheitsgehalt“ solcher Zeichenketten herausgearbeitet sowie sich daraus ergebende Konsequenzen. Diese haben für die gesamte Mathematik Bedeutung.

== Die Sprache der Prädikatenlogik erster Stufe ==
Wir beschreiben hier die verwendete Sprache auf rein [[Syntax|syntaktische]] Weise, das heißt, wir legen die betrachteten Zeichenketten, die wir Ausdrücke der Sprache nennen wollen, ohne Bezug auf ihre Bedeutung fest.

=== Symbole ===
Eine Sprache erster Stufe wird aus folgenden Symbolen aufgebaut:<ref>Das Kommazeichen „,“ wird hier nur als Trennzeichen für die Aufzählung der Symbole benutzt, es ist nicht Symbol der Sprache.</ref><ref>Zur aussagenlogischen Entsprechung siehe [[Aussagenlogik#Bausteine der aussagenlogischen Sprache|Aussagenlogik §Bausteine der aussagenlogischen Sprache]].</ref><ref name="Grädel2009" details="S.&nbsp;45" />
* logische Symbole:
** [[Quantor]]en: <math>\forall, \exists</math>&nbsp;,
** [[Junktor]]en: <math>\land, \lor, \rightarrow, \leftrightarrow, \neg</math>&nbsp;,
** technische Zeichen: <math>(, ), \equiv</math>&nbsp;,
* [[Variable (Logik)|Variablensymbole]]: <math>v_0,v_1,v_2,\ldots</math>&nbsp;,
* eine (möglicherweise leere) Menge <math>\mathcal C</math> von Konstantensymbolen,
* eine (möglicherweise leere) Menge <math>\mathcal F</math> von Funktionssymbolen,
* eine (möglicherweise leere) Menge <math>\mathcal R</math> von Relationssymbolen.

=== Terme ===
Die nach folgenden Regeln aufgebauten Zeichenketten heißen [[Term#Formale Definition|Terme]]:<ref>H.-D. Ebbinghaus, J. Flum, W. Thomas: ''Einführung in die mathematische Logik'', Spektrum Akademischer Verlag, ISBN 3-8274-0130-5, II, Definition 3.1</ref><ref>Zur aussagenlogischen Entsprechung siehe [[Aussagenlogik#Formationsregeln|Aussagenlogik §Formationsregeln]].</ref><ref name="Grädel2009" details="S.&nbsp;45" />&nbsp;<ref name="VoglerWS2007-8" details="S.&nbsp;3" />&nbsp;<ref name="KruseBorgelt2008" details="S.&nbsp;4" />
* Ist <math>v</math> ein Variablensymbol, so ist <math>v</math> ein Term.
* Ist <math>c</math> ein Konstantensymbol, so ist <math>c</math> ein Term.
* Ist <math>f</math> ein einstelliges Funktionssymbol und ist <math>t_1</math> ein Term, so ist <math>ft_1</math> ein Term.
* Ist <math>f</math> ein zweistelliges Funktionssymbol und sind <math>t_1,t_2</math> Terme, so ist <math>ft_1t_2</math> ein Term.
* und so weiter für 3-, 4-, 5-,…-stellige Funktionssymbole.

;Anmerkungen
* Ist zum Beispiel <math>c</math> eine Konstante und sind <math>f</math> und <math>g</math> ein- bzw. zweistellige Funktionssymbole, so ist <math>fgv_2fc</math> ein Term, da er sich durch Anwendung obiger Regeln erstellen lässt: <math>c</math> ist ein Term, daher auch <math>fc</math>; <math>fc</math> und <math>v_2</math> sind Terme, daher auch <math>gv_2fc</math> und damit schließlich auch <math>fgv_2fc</math>.

* Wir verzichten hier auf Klammern und Kommata als Trennzeichen, das heißt, wir schreiben <math>fgv_2fc</math> und nicht <math>f(g(v_2,f(c)))</math>. Wir setzen damit implizit voraus, dass unsere Symbole derart beschaffen sind, dass eine eindeutige Lesbarkeit gewährleistet ist. Siehe [[Polnische Notation]]. Konstanten werden manchmal als nullstellige Funktionen aufgefasst, was in dieser Notation besonders naheliegend ist.

* Die Regeln für die Funktionssymbole fasst man oft so zusammen:
:<small>o</small>&nbsp; Ist <math>f</math> ein n-stelliges Funktionssymbol und sind <math>t_1,\ldots,t_n</math> Terme, so ist <math>ft_1\ldots t_n</math> ein Term.
:Damit ist nichts anderes als die oben angedeutete unendliche Folge von Regeln gemeint, denn die drei Punkte <math>\ldots</math> gehören nicht zu den vereinbarten Symbolen. Dennoch wird manchmal von dieser Schreibweise Gebrauch gemacht.

Über den Aufbau der Terme lassen sich weitere Eigenschaften definieren. So ist zunächst die Menge <math>\mathrm{var}(t)</math> der in einem Term <math>t</math> vorkommenden Variablen durch die folgenden drei Regeln rekursiv definiert:
* Ist <math>v</math> ein Variablensymbol, so sei <math>\mathrm{var}(v) \,=\, \{v\}</math>.
* Ist <math>c</math> ein Konstantensymbol, so sei <math>\mathrm{var}(c) \,=\, \emptyset</math>.
* Ist <math>f</math> ein n-stelliges Funktionssymbol und sind <math>t_1,\ldots,t_n</math> Terme, so sei <math>\mathrm{var}(ft_1\ldots t_n) \,=\, \mathrm{var}(t_1)\cup\ldots \cup \mathrm{var}(t_n)</math>.

=== Ausdrücke ===
Wir erklären nun durch Bildungsgesetze, welche Zeichenketten wir als Ausdrücke der Sprache ansehen wollen.<ref>H.-D. Ebbinghaus, J. Flum, W. Thomas: ''Einführung in die mathematische Logik'', Spektrum Akademischer Verlag, ISBN 3-8274-0130-5, II, Definition 3.2</ref><ref>Es findet sich auch die Bezeichnung ''Formel'', siehe [[Elementare Sprache#Formeln|Elementare Sprache §Formeln]] und [[Logische Formel]]. Entsprechend steht dann ''Atomformel'' für ''Atomaren Ausdruck''</ref><ref name="Grädel2009" details="S.&nbsp;46&nbsp;f" />&nbsp;<ref name="KruseBorgelt2008" details="S.&nbsp;4" />

''' Atomare Ausdrücke '''<ref name="VoglerWS2007-8" details="S.&nbsp;5" />

* Sind <math>t_1</math> und <math>t_2</math> Terme, so ist <math>t_1 \equiv t_2</math> ein Ausdruck.
* Ist <math>R</math> ein einstelliges Relationssymbol und ist <math>t_1</math> ein Term, so ist <math>Rt_1</math> ein Ausdruck.
* Ist <math>R</math> ein zweistelliges Relationssymbol und sind <math>t_1,t_2</math> Terme, so ist <math>Rt_1t_2</math> ein Ausdruck.
* und so weiter für 3-, 4-, 5-,…-stellige Relationssymbole.<ref>Gelegentlich werden nullstellige Relationen zugelassen, dies treten dann als logische Konstanten (im Prinzip Bezeichner für ''wahr'' oder ''falsch'') auf. Als alternativer Ausdruck für die Relationssymbole findet man auch ''Prädikate''. Siehe {{Literatur |Autor=Stefan Brass |Titel=Mathematische Logik mit Datenbank-Anwendungen |Verlag=Martin-Luther-Universität Halle-Wittenberg, Institut für Informatik |Ort=Halle |Datum=2005 |Seiten=176 |Fundstelle=hier S. 19 |Online=[http://users.informatik.uni-halle.de/~brass/db07/d2_logic.pdf uni-halle.de] |Format=PDF |KBytes=}}</ref>

Dabei gelten die oben zur Schreibweise bei Termen gemachten Bemerkungen.

'''Zusammengesetzte Ausdrücke'''<ref name="VoglerWS2007-8" details="S.&nbsp;6" />

Wir beschreiben hier, wie sich aus Ausdrücken weitere gewinnen lassen.<ref>Auch als ''[[Elementare Sprache#Aussagenlogische Verknüpfungen|Aussagenlogische Verknüpfungen]]'' bezeichnet.</ref>
* Ist <math>\varphi</math> ein Ausdruck, so ist auch <math>\neg \varphi</math> ein Ausdruck.
* Sind <math>\varphi</math> und <math>\psi</math> Ausdrücke, so sind auch <math>(\varphi \land \psi)</math>, <math>(\varphi \lor \psi)</math>, <math>(\varphi \rightarrow \psi)</math> und <math>(\varphi \leftrightarrow \psi)</math> Ausdrücke.
* Ist <math>\varphi</math> ein Ausdruck und ist <math>x</math> eine Variable, so sind auch <math>\forall x \varphi</math> und <math>\exists x \varphi</math> Ausdrücke.

Damit sind alle Ausdrücke unserer Sprache festgelegt. Ist zum Beispiel <math>f</math> ein einstelliges Funktionssymbol und <math>R</math> ein 2-stelliges Relationssymbol, so ist
: <math>\forall v_0((Rv_0v_1\lor v_0\equiv fv_1) \rightarrow \exists v_2 \neg Rv_0v_2)</math>
ein Ausdruck, da er sich durch Anwendung obiger Regeln aufbauen lässt. Es sei noch einmal darauf hingewiesen, dass wir die Ausdrücke mittels der genannten Regeln rein mechanisch erstellen, ohne dass die Ausdrücke zwangsläufig irgendetwas bezeichnen müssten.

=== 1. Stufe ===
Unterschiedliche Sprachen erster Stufe unterscheiden sich lediglich in den Mengen <math>\mathcal C</math>, <math>\mathcal F</math> und <math>\mathcal R</math>, die man üblicherweise zur Symbolmenge <math>S</math> zusammenfasst und auch die ''[[Signatur (Modelltheorie)|Signatur]]'' der Sprache nennt. Man spricht dann auch genauer von <math>S</math>-Termen bzw. <math>S</math>-Ausdrücken. Die Sprache, das heißt die Gesamtheit aller nach obigen Regeln gebildeten Ausdrücke, wird mit <math>L(S)</math>, <math>L^S</math> oder <math>L_I^S</math> bezeichnet. Bei letzterem steht die römische <math>I</math> für die erste Stufe. Dies bezieht sich auf den Umstand, dass gemäß letzter Erzeugungsregel für zusammengesetzte Ausdrücke nur über Variablen quantifiziert werden kann. <math>L_I^S</math> sieht nicht vor, über alle Teilmengen einer Menge, über Relationen<ref>mit dem Spezialfall einstelliger Relationen = Teilmengen</ref> oder über Funktionen zu quantifizieren. So lassen sich die üblichen [[Peano-Axiome]] nicht in <math>L_I^S</math> ausdrücken, da das Induktionsaxiom eine Aussage über alle Teilmengen der [[Natürliche Zahl|natürlichen Zahlen]] macht. Das kann als Schwäche dieser Sprache angesehen werden, allerdings sind die Axiome der [[Zermelo-Fraenkel-Mengenlehre]] sämtlich in der ersten Stufe mit dem einzigen Symbol <math>\in</math> formulierbar, so dass die erste Stufe prinzipiell für die Mathematik ausreicht.<ref>H.-D. Ebbinghaus, J. Flum, W. Thomas: ''Einführung in die mathematische Logik'', Spektrum Akademischer Verlag, ISBN 3-8274-0130-5, VII: ''Zur Tragweite der ersten Stufe''</ref>

=== Freie Variablen ===
Weitere Eigenschaften von Ausdrücken der Sprache <math>L_I^S</math> lassen sich ebenfalls rein syntaktisch definieren. Gemäß dem oben beschriebenen Aufbau durch Bildungsregeln wird die Menge <math>\mathrm{frei}(\varphi)</math> der im Ausdruck <math>\varphi</math> frei vorkommenden Variablen wie folgt rekursiv definiert:<ref>H.-D. Ebbinghaus, J. Flum, W. Thomas: ''Einführung in die mathematische Logik'', Spektrum Akademischer Verlag, ISBN 3-8274-0130-5, II, Definition 5.1</ref><ref name="Grädel2009" details="S.&nbsp;48&nbsp;f" />&nbsp;<ref name="KruseBorgelt2008" details="S.&nbsp;6" />
* <math>\mathrm{frei}(t_1\equiv t_2) = \mathrm{var}(t_1)\cup \mathrm{var}(t_2)</math>
* <math>\mathrm{frei}(Rt_1\ldots t_n) = \mathrm{var}(t_1)\cup\ldots \cup \mathrm{var}(t_n)</math>
* <math>\mathrm{frei}(\neg \varphi) = \mathrm{frei}(\varphi)</math>
* <math>\mathrm{frei}(\varphi \land \psi) = \mathrm{frei}(\varphi)\cup \mathrm{frei}(\psi)</math> und genauso für <math>\lor, \rightarrow, \leftrightarrow</math>
* <math>\mathrm{frei}(\forall x\varphi) = \mathrm{frei}(\varphi)\setminus \{x\}</math>
* <math>\mathrm{frei}(\exists x\varphi) = \mathrm{frei}(\varphi)\setminus \{x\}</math>

Nicht-freie Variable heißen ''gebundene Variable''. Ausdrücke <math>\varphi</math> ohne freie Variable, das heißt solche mit <math>\mathrm{frei}(\varphi)=\emptyset </math>, nennt man ''Sätze''. Sämtliche in obigem motivierenden Beispiel angegebenen Axiome der geordneten abelschen Gruppen sind bei entsprechender Übersetzung in die Sprache <math>L_I^{\{0,+,-,\le\}}</math> Sätze, so zum Beispiel <math>\forall v_0 \forall v_1 +\!v_0v_1\equiv +v_1v_0</math> für das Kommutativgesetz.

=== Metasprachliche Ausdrücke ===
Das gerade gegebene Beispiel <math>\forall v_0 \forall v_1 +\!v_0v_1\equiv +v_1v_0</math> als Symbolisierung des Kommutativgesetzes in der Sprache <math>L_I^{\{0,+,-,\le\}}</math> zeigt, dass die entstehenden Ausdrücke oft schwer lesbar sind. Daher kehrt der Mathematiker, und oft auch der Logiker, gern zur klassischen Schreibweise <math>\forall x,y: x+y = y+x</math> zurück. Letzteres ist aber kein Ausdruck der Sprache <math>L_I^{\{0,+,-,\le\}}</math>, sondern nur eine Mitteilung eines solchen Ausdrucks unter Verwendung anderer Symbole einer anderen Sprache, hier der sogenannten [[Metasprache]], das heißt derjenigen Sprache, in der man über <math>L_I^{\{0,+,-,\le\}}</math> spricht. Aus Gründen der besseren Lesbarkeit lässt man auch gern überflüssige Klammern weg. Das führt nicht zu Problemen, solange klar bleibt, dass man die leichter lesbaren Zeichenketten jederzeit zurückübersetzen könnte.

=== Substitutionen ===
Häufig werden in der Mathematik Variablen durch Terme ersetzt. Auch das lässt sich hier rein syntaktisch auf Basis unserer Symbole erklären. Durch folgende Regeln legen wir fest, was es bedeuten soll, den Term <math>t</math> für eine Variable <math>x</math> einzusetzen. Die Substitution wird für Terme <math>s</math> als <math>[s]\frac{t}{x}</math> und für Ausdrücke <math>\varphi</math> als <math>[\varphi]\frac{t}{x}</math> gleichermaßen durch eckige Klammern notiert. Die eckigen Klammern dürfen auch weggelassen werden.

Für Terme <math>s</math> wird die Substitution <math>s\frac{t}{x}</math> wie folgt definiert:
* Ist <math>v</math> ein Variablensymbol, so ist <math>v\frac{t}{x}</math> gleich <math>t</math>, falls <math>v=x</math>, und <math>v</math> sonst.
* Ist <math>c</math> ein Konstantensymbol, so ist <math>c\frac{t}{x}:=c</math>.
* Sind <math>f</math> ein ''n''-stelliges Funktionssymbol und <math>t_1,\ldots,t_n</math> Terme, so ist <math>[ft_1\ldots t_n]\frac{t}{x} := ft_1\frac{t}{x}\ldots t_n\frac{t}{x}</math>.

Für Ausdrücke <math>\varphi</math> legen wir fest:
* <math>[t_1\equiv t_2]\frac{t}{x} := t_1\frac{t}{x} \equiv t_2\frac{t}{x}</math>
* <math>[Rt_1\ldots t_n]\frac{t}{x} := Rt_1\frac{t}{x}\ldots t_n\frac{t}{x}</math>
* <math>[\neg\varphi]\frac{t}{x} := \neg [\varphi]\frac{t}{x}</math>
* <math>[(\varphi \lor \psi)]\frac{t}{x} := ([\varphi]\frac{t}{x} \lor [\psi]\frac{t}{x})</math>
* analog für die Junktoren <math>\land, \rightarrow, \leftrightarrow</math>
* <math>[\exists y\varphi]\frac{t}{x}:=\begin{cases}
\exists y\varphi & \text{für }x=y\\
\exists y[\varphi]\frac{t}{x} & \text{für }x\neq y\text{ und }y\notin\operatorname{var}(t)\\
\exists u[\varphi]\frac{u}{y}\frac{t}{x} & \text{für }x\neq y\text{ und }y\in\operatorname{var}(t)
\end{cases}</math>,
dabei sei <math>u</math> eine Variable, die nicht in <math>\varphi</math> oder <math>t</math> vorkommt, zum Beispiel die erste der Variablen <math>v_0,v_1,v_2,\ldots</math>, die diese Bedingung erfüllt. Bei dieser Definition wurde darauf geachtet, dass Variablen nicht unbeabsichtigt in den Einflussbereich eines Quantors geraten. Falls die gebundene Variable <math>x</math> im Term auftritt, so wird diese zuvor durch eine andere ersetzt, um so die Variablenkollision zu vermeiden.
* analog für den Quantor <math>\forall</math>.

=== Schlussbemerkung zur Syntax ===
Es sei noch einmal betont, dass alles bisher Gesagte nur den Aufbau beziehungsweise die Manipulation gewisser Zeichenketten beschreibt, es handelt sich um rein syntaktische Begriffe. Weder den Zeichenketten noch ihren Manipulationen sind irgendwelche Bedeutungsinhalte zugeordnet. Selbstverständlich liest man unwillkürlich die „Bedeutungen“ mit, die durch obiges Beispiel suggeriert sind, das heißt, man liest ein <math>\forall</math> als „für alle“ und ein <math>\land</math> als „und“ und kann sich nur schwer von ihren „umgangssprachlichen Bedeutungen“ frei machen. Man sollte sich aber darüber im Klaren sein, dass eine solche „Bedeutung“ für die vorgestellten Begriffsbildungen nicht erforderlich ist und an keiner Stelle verwendet wird. Es ist ein wesentlicher Punkt, dass die intendierte Bedeutung dieser Zeichenketten, ihre Semantik, erst in einem im Folgenden vorgestellten Schritt hinzugefügt wird.

== Semantik ==
Wir gehen von einer Sprache <math>L_I^S</math> aus.
Die nach obigen Regeln in dieser Sprache gebildeten Ausdrücke sollen nun mit mathematischen Strukturen in Verbindung gebracht werden.
In diesen Strukturen kann man die Ausdrücke dann auf ihren Wahrheitsgehalt hin untersuchen, was im Folgenden präzisiert wird.

=== Strukturen ===
Eine [[Struktur (erste Stufe)|Struktur]] <math>\mathcal A</math> über einer [[Signatur (Modelltheorie)|Signatur]] <math>S</math> ist eine nicht-leere Menge <math>A</math> zusammen mit
* einem Element <math>c^{\mathcal A}\in A</math> für jedes Konstantensymbol <math>c\in S</math>,
* einer Funktion <math>f^{\mathcal A}:A^n\rightarrow A</math> für jedes <math>n</math>-stellige Funktionssymbol <math>f\in S</math>,
* einer Relation <math>R^{\mathcal A}\subset A^n</math> für jedes <math>n</math>-stellige Relationssymbol <math>R\in S</math>.

Im eingangs gegebenen Beispiel geordneter abelscher Gruppen ist <math>(\R,0,+,-,\le)</math>  eine <math>\{0,+,-,\le\}</math>-Struktur. Durch {{nowrap|<math>S</math>-Strukturen}} werden also die Symbole aus <math>S</math> mit „echten“ Konstanten, Funktionen und Relationen in Zusammenhang gebracht.

=== Interpretationen ===
Eine [[Interpretation (Logik)|Interpretation]] von <math>L_I^S</math> ist ein Paar <math>{\mathcal I} = ({\mathcal A},\beta)</math> bestehend aus einer <math>S</math>-Struktur <math>\mathcal A</math> und einer Abbildung <math>\beta:\{v_i;\,i\in \N_0\}\rightarrow A</math>.

Man verbindet damit die Vorstellung, dass die Struktur das mathematische Objekt ist, das mit der Sprache beschrieben werden soll, während <math>\beta</math> die Variablen mit Werten aus der Grundmenge <math>A</math> belegt, weshalb man diese Abbildung auch ''Belegung'' nennt. Die Belegung einer Interpretation kann leicht auf Terme ausgedehnt werden, diese Ausdehnung hängt von der Interpretation der Konstantensymbole und Funktionssymbole ab und wird daher ebenfalls mit <math>\mathcal I</math> bezeichnet; man legt fest:
* Ist <math>v</math> eine Variable, so sei <math>{\mathcal I}(v) := \beta(v)</math>.
* Ist <math>c</math> ein Konstantensymbol, so sei <math>{\mathcal I}(c) := c^{\mathcal A}</math>.
* Ist <math>f</math> ein n-stelliges Funktionssymbol und sind <math>t_1,\ldots,t_n</math> Terme, so sei <math>{\mathcal I}(ft_1\ldots t_n) := f^{\mathcal A}({\mathcal I}(t_1),\ldots,{\mathcal I}(t_n))</math>.

Setzt man etwa <math>\beta(v_i) = i\in \R</math>, so ist <math>{\mathcal I} = ((\R,0,+,-,\le),\beta)</math> eine solche Interpretation. Dann gilt
<math>{\mathcal I}(+v_1-v_7) = +^{\mathcal A}({\mathcal I}(v_1),-^{\mathcal A}({\mathcal I}(v_7)) = 1+(-7) = -6</math>.

Ändern wir eine Belegung nur an der Stelle <math>x</math> ab und bilden dieses <math>x</math> auf <math>a\in A</math> ab, so schreiben wir <math>\beta \frac{a}{x}</math> für die so abgeänderte Belegung und <math>{\mathcal I}\frac{a}{x} := ({\mathcal A},\beta\frac{a}{x})</math>. Oft ist die Belegung der Variablen klar oder unwichtig; dann nennen wir, etwas unsauber, aber praktisch, auch die Struktur <math>\mathcal A</math> eine Interpretation.

=== Modelle ===
Wir wollen sagen, dass eine Interpretation <math>{\mathcal I} = ({\mathcal A},\beta)</math> ein ''Modell'' für einen <math>S</math>-Ausdruck <math>\varphi</math> ist, und dafür <math>{\mathcal I} \vDash \varphi</math> schreiben, wenn sich dies auf Grund folgender Regeln ergibt:<ref>H.-D. Ebbinghaus, J. Flum, W. Thomas: ''Einführung in die mathematische Logik'', Spektrum Akademischer Verlag, ISBN 3-8274-0130-5, III, Definition 3.2</ref><br />
<math>\begin{matrix}
{\mathcal I} \vDash t_1\equiv t_2 & :\Leftrightarrow & {\mathcal I}(t_1) = {\mathcal I}(t_2) \\
{\mathcal I} \vDash Rt_1\ldots t_n & :\Leftrightarrow & ({\mathcal I}(t_1),\ldots, {\mathcal I}(t_n)) \text{ ist Element von } R^{\mathcal A}\\
{\mathcal I} \vDash \neg\varphi & :\Leftrightarrow & \text{nicht }{\mathcal I} \vDash \varphi\\
{\mathcal I} \vDash (\varphi\land \psi) & :\Leftrightarrow & {\mathcal I} \vDash \varphi \text{ und }{\mathcal I} \vDash \psi\\
{\mathcal I} \vDash (\varphi\lor \psi) & :\Leftrightarrow & {\mathcal I} \vDash \varphi \text{ oder }{\mathcal I} \vDash \psi\\
{\mathcal I} \vDash (\varphi\rightarrow \psi) & :\Leftrightarrow & \text{wenn }{\mathcal I} \vDash \varphi, \text{ dann auch }{\mathcal I} \vDash \psi\\
{\mathcal I} \vDash (\varphi\leftrightarrow \psi) & :\Leftrightarrow & {\mathcal I} \vDash \varphi \text{ genau dann, wenn }{\mathcal I} \vDash \psi\\
{\mathcal I} \vDash \forall x\varphi & :\Leftrightarrow & {\mathcal I}\frac{a}{x} \vDash \varphi \mbox{ für alle } a\in A\\
{\mathcal I} \vDash \exists x\varphi & :\Leftrightarrow & \text{es gibt ein }a\in A \text{ mit }{\mathcal I}\frac{a}{x} \vDash \varphi
\end{matrix}</math>

Diese Definition orientiert sich wieder am regelhaften Aufbau der Ausdrücke der Sprache <math>L_I^S</math>. Die Pünktchenschreibweise in der zweiten Regel steht hier wieder für eine Liste von Regeln, für jede Stelligkeit eine.

Durch den Begriff der Interpretation wurden die Variablen und die Symbole aus <math>S</math> mit einer Bedeutung versehen. Durch die gerade definierte Modellbeziehung werden erstmals auch die logischen Symbole interpretiert.

Für eine Menge <math>\Phi</math> von Ausdrücken schreiben wir <math>{\mathcal I} \vDash \Phi</math>, wenn <math>{\mathcal I} \vDash \varphi</math> für alle <math>\varphi \in \Phi</math> gilt, und sagen, <math>{\mathcal I}</math> sei ein Modell von <math>\Phi</math>. Bezeichnet <math>\Phi</math> etwa die oben genannten Axiome der geordneten abelschen Gruppen, so gilt <math>{\mathcal I}=({\mathcal A},\beta) \vDash \Phi</math> genau dann, wenn <math>{\mathcal A}</math> eine geordnete abelsche Gruppe ist. Dabei scheint die Belegung <math>\beta</math> keine Rolle zu spielen, da <math>\Phi</math> nur aus Sätzen besteht, also keine freien Variablen enthält. Das ist tatsächlich der Fall, wie das sogenannte [[Koinzidenzlemma]] aussagt. In einem solchen Fall kann man <math>\beta</math> weglassen und einfach <math>{\mathcal A} \vDash \Phi</math> schreiben. Damit ist dann ausgesagt, dass <math>{\mathcal I}=({\mathcal A},\beta) </math> für jede Belegung <math>\beta</math> ein Modell aller Ausdrücke aus <math>\Phi</math> ist.

=== Gleichheit ===
Zur Verwendung der Gleichheit ist anzumerken, dass wir in der Sprache erster Stufe das Symbol <math>\equiv</math> eingeführt haben. Ein Ausdruck der Form <math>\varphi = \psi</math> ist kein Ausdruck der Sprache erster Stufe, sondern die metasprachliche Behauptung der Gleichheit der beiden Ausdrücke <math>\varphi</math> und <math>\psi</math>. Letzteres lässt sich in der Sprache erster Stufe gar nicht symbolisieren, dort können nur Terme gleich sein. Parallel zum  hier betrachteten Aufbau gibt es auch die ''Prädikatenlogik erster Stufe ohne Gleichheit'', dazu entfernt man das Symbol <math>\equiv</math> und die es betreffende Bildungsregel. Zwar kann man die Gleichheit dann über eine Relation wieder ins Spiel bringen, setzt diese dann aber Interpretationen aus, so dass man nicht dasselbe erhält wie eine Logik mit Gleichheit. Die logische Gleichheit <math>\equiv</math> hingegen bedeutet in jeder Interpretation Gleichheit von Individuen, und das ist der Grund, warum man Logiken mit Gleichheit betrachtet.<ref>Philipp Rothmaler: ''Einführung in die Modelltheorie'', Spektrum Akademischer Verlag 1995, ISBN 978-3-86025-461-5, Ende des Absatzes 3.1.</ref>

== Mathematisches Schließen ==
=== Folgerungen ===
Es sei <math>\Phi</math> eine gegebene Menge von Ausdrücken, zum Beispiel obige Axiome der geordneten abelschen Gruppen. Der Mathematiker interessiert sich dafür, welche Folgerungen aus ihnen gezogen werden können. Wir sagen, der Ausdruck <math>\varphi</math> folge aus <math>\Phi</math>, und schreiben dafür <math>\Phi \vDash \varphi</math>, wenn jedes Modell von <math>\Phi</math> auch Modell von <math>\varphi</math> ist. Das ist die sogenannte semantische Schlussweise, da sie Bezug auf alle möglichen Interpretationen der Symbole nimmt.

=== Sequenzenkalkül ===
{{Hauptartikel|Sequenzenkalkül}}
In der Regel schließt der Mathematiker nicht semantisch, sondern er wendet gewisse Schlussregeln an, mit denen er sich von einer Aussage zur nächsten bis zur Behauptung vorarbeitet. Ausgehend von einer gegebenen Folge <math>\Phi</math> von Ausdrücken geht er zu neuen Folgen <math>\Phi \,\varphi \,\psi \,\ldots </math> über, um am Ende mit einer Folge <math>\Phi\, \varphi </math> „bewiesen“ zu haben, dass <math>\varphi</math> aus <math>\Phi</math> folgt. Der „Beweis“ ist dabei eine endliche Liste solcher Folgen. Hier werden einige solcher Schlussregeln vorgestellt, ihr inhaltlicher Hintergrund beleuchtet und anschließend mit der semantischen Schlussweise verglichen. In <math>\Phi \,\varphi \,\psi \,\ldots </math> nennt man <math>\Phi</math> das ''Antezedens'' und die nachfolgenden Ausdrücke das ''Sukzedens''.

'''Voraussetzungsregel''': <math>\Phi \,\varphi</math> ist eine erlaubte Folge, wenn <math>\varphi \in \Phi</math>. Dahinter steckt der einfache Tatbestand, dass man jederzeit eine der Voraussetzungen aus <math>\Phi</math> verwenden darf.

'''Antezedensregel''': Falls man <math>\Phi \,\varphi</math> bereits hat, so kann man  zu <math>\Phi' \,\varphi</math> übergehen, falls <math>\Phi \subset \Phi'</math> (das soll bedeuten, dass jedes Glied aus <math>\Phi</math> auch in <math>\Phi'</math> vorkommt). Wenn man nämlich von <math>\Phi</math> auf <math>\varphi</math> schließen kann, so kann man das erst recht unter noch umfangreicheren Voraussetzungen tun.

'''Fallunterscheidung''': Falls man <math>\Phi \,\psi \,\varphi</math> und <math>\Phi \,\neg\psi\, \varphi</math> bereits hat, so kann man zu <math>\Phi \varphi</math> übergehen. Man kann im Falle <math>\psi</math> von <math>\Phi</math> auf <math>\varphi</math> schließen, und auch im Falle von <math>\neg \psi</math>. Daher kann man in jedem Fall von <math>\Phi</math> auf <math>\varphi</math> schließen.

'''Widerspruch''': Falls man <math>\Phi \,\neg\varphi \,\psi</math> und <math>\Phi \,\neg\varphi \, \neg \psi</math> bereits hat, so kann man zu <math>\Phi \,\varphi</math> übergehen. Nimmt man nämlich im Sinne eines Widerspruchsbeweises an, dass <math>\neg \varphi</math> gilt, so ergibt sich aus den Voraussetzungen sowohl <math>\psi</math> als auch <math>\neg\psi</math>, insgesamt also ein Widerspruch. Daher war die Annahme <math>\neg\varphi</math> falsch und man kann auf <math>\varphi</math> schließen.

'''Odereinführung im Antezedens''': Falls man <math>\Phi \,\varphi \,\chi</math> und <math>\Phi \,\psi \,\chi</math> bereits hat, so kann man zu <math>\Phi \,(\varphi\lor\psi) \,\chi</math> übergehen. Unter den Voraussetzungen <math>\Phi</math> ergibt sich <math>\chi</math> sowohl aus <math>\varphi</math> als auch aus <math>\psi</math>. Daher ergibt sich <math>\chi</math> bereits, wenn <math>\varphi</math> oder <math>\psi</math> gilt.

'''Odereinführung im Sukzedens''':  Falls man <math>\Phi \,\varphi</math> bereits hat, so kann man  zu <math>\Phi \,(\varphi\lor\psi)</math> übergehen. Das ist klar, da mit <math>\varphi</math> erst recht <math>\varphi\lor\psi</math> gilt. Entsprechend kann man auch zu <math>\Phi \,(\psi\lor\varphi)</math> übergehen.

'''Gleichheit''': Man kann jederzeit den Ausdruck <math>t\equiv t</math> hinschreiben, wobei <math>t</math> ein beliebiger Term ist. Diese Regel bedarf keiner Erläuterung.

Die noch folgenden drei Schlussregeln verwenden die oben definierte Substitution von Variablen durch Terme:

'''Substitution''': Falls man <math>\Phi \,\varphi\frac{t}{x}</math> bereits hat, so kann man  zu <math>\Phi \,t\!\equiv\!s\,\varphi\frac{s}{x}</math> übergehen. Wenn man aus  <math>\Phi</math> auf <math>\varphi\frac{t}{x}</math>, das heißt auf <math>\varphi</math> mit der Ersetzung <math>t</math> an Stelle von <math>x</math>, schließen kann, so auch auf <math>\varphi</math> mit der Ersetzung <math>s</math> an Stelle von <math>x</math>, falls <math>t</math> gleich <math>s</math> ist.

'''Existenzeinführung im Antezedens''': Falls man <math>\Phi \,\varphi\frac{y}{x} \,\psi</math> bereits hat, so kann man  zu <math>\Phi \, \exists x \varphi\, \psi</math> übergehen. Um mit der Existenzvoraussetzung <math>\exists x \varphi</math> arbeiten zu können, darf man ein <math>y</math> verwenden, für das <math>\varphi\frac{y}{x}</math> gilt. In Beweisen, die diese Regel verwenden, heißt dann nach der Existenzvoraussetzung: Sei <math>y</math> so ein ...

'''Existenzeinführung im Sukzendens''': Falls man <math>\Phi \,\varphi\frac{t}{x} </math> bereits hat, so kann man  zu <math>\Phi \, \exists x \varphi</math> übergehen. Auch diese Regel ist einsichtig, denn wenn man mit <math>t</math> ein Beispiel für <math>\varphi</math> gefunden hat, so kann man auf die Existenzaussage schließen und braucht das Beispiel dabei nicht mehr zu erwähnen.

Die hier vorgestellten Regeln, die den sogenannten Sequenzenkalkül bilden, sind logisch schlüssig, wie als Zusatz zu jeder Regelnennung ausgeführt wurde. Mathematiker verwenden noch einige andere Schlussregeln, von denen aber gezeigt werden kann, dass sie alle aus den oben genannten hergeleitet werden können, das heißt, ihre Anwendung kann durch eine endliche Kette obiger Regeln ersetzt werden. Wenn man ausgehend von <math>\Phi</math> nach endlich vielen Anwendungen dieser Regeln zu <math>\Phi\, \varphi</math> gelangt ist, so ist damit <math>\varphi</math> aus <math>\Phi</math> logisch schlüssig abgeleitet, wir schreiben dafür <math>\Phi\vdash \varphi</math>.

Im Gegensatz zur oben erklärten semantischen Schlussweise sind die „Beweise“ <math>\Phi\vdash \varphi</math> rein syntaktischer Natur, man kann sie als Manipulation von Zeichenketten der betrachteten Sprache ansehen. Um die Schlussregeln anwenden zu können, muss man nicht wissen, was die Symbole bedeuten.

=== Vollständigkeit und Korrektheit ===
{{Hauptartikel|Vollständigkeit (Logik)|Gödelscher Vollständigkeitssatz}}
Ist die Interpretation <math>\mathcal I</math> ein Modell für eine Menge <math>\Phi</math> von Ausdrücken der Sprache <math>L_I^S</math> und ist <math>\Phi \vdash \varphi</math>, so ist <math>\mathcal I</math> auch ein Modell für <math>\varphi</math>, denn der mit <math>\Phi\vdash \varphi</math> einhergehende Beweis lässt sich ja ohne Weiteres direkt im Modell ausführen. Es gilt also der sogenannte ''[[Korrektheit (Logik)|Korrektheitssatz]]'', dass aus <math>\Phi \vdash \varphi</math> stets <math>\Phi \vDash \varphi</math> folgt.

Umgekehrt wäre es durchaus denkbar, dass es zu einer Ausdrucksmenge <math>\Phi</math> nur einige wenige Modelle gibt, die zufällig eine in der Sprache erster Stufe ausdrückbare Eigenschaft <math>\varphi</math> gemeinsam haben, ohne dass es dazu eine Möglichkeit gäbe, sie durch obige syntaktische Zeichenkettenoperationen aus <math>\Phi</math> ableiten zu können. Dass dies nicht der Fall ist, sondern dass semantische und syntaktische Schlussweisen gleichwertig sind, ist als Gödelscher Vollständigkeitssatz bekannt und ein zentrales Ergebnis der Prädikatenlogik erster Stufe. Man kann zeigen, dass sich zu einer [[Prädikatenlogik zweiter Stufe]], in der man Quantifizierungen über Relationen zulässt, kein zur semantischen Schlussweise gleichwertiger Sequenzenkalkül finden lässt.

== Eigenschaften ==

=== Erfüllbarkeitssatz ===
Eine Menge <math>\Phi</math> von Ausdrücken der Sprache <math>L_I^S</math> heißt widerspruchsfrei, wenn sich kein Ausdruck der Form <math>(\varphi\land \neg\varphi)</math> aus <math>\Phi</math> ableiten lässt. Damit ist Widerspruchsfreiheit ein rein syntaktischer Begriff. Es gilt folgender Erfüllbarkeitssatz, der sich aus dem [[Satz von Henkin]] herleiten lässt und eng mit dem Gödelschen Vollständigkeitssatz verbunden ist:

* Zu jeder widerspruchsfreien Menge <math>\Phi</math> gibt es ein Modell.

=== Kompaktheitssatz ===
* [[Kompaktheitssatz (Logik)|Kompaktheitssatz]]: Ist <math>\Phi</math> eine Menge von Ausdrücken der Sprache <math>L_I^S</math> und gibt es zu jeder endlichen Teilmenge von <math>\Phi</math> ein Modell, so gibt es auch ein Modell für <math>\Phi</math><ref>H.-D. Ebbinghaus, J. Flum, W. Thomas: ''Einführung in die mathematische Logik'', Spektrum Akademischer Verlag, ISBN 3-8274-0130-5, VI.2.1</ref>.

Gäbe es nämlich kein Modell für <math>\Phi</math>, so wäre <math>\Phi</math> nach dem Erfüllbarkeitssatz nicht widerspruchsfrei, und es gäbe dann eine Ableitung <math>\Phi\vdash (\varphi\land \neg\varphi)</math>. Da ein Beweis aber nur eine endliche Länge hat und daher auch nur endlich viele der Ausdrücke aus <math>\Phi</math> involvieren kann, muss es bereits eine endliche Teilmenge <math>\Phi_0</math> geben mit <math>\Phi_0\vdash (\varphi\land \neg\varphi)</math>. Nach dem Vollständigkeitssatz folgt <math>\Phi_0\vDash \varphi\land \neg\varphi</math>, das heißt, es kann für <math>\Phi_0</math> kein Modell geben, im Widerspruch zur Voraussetzung.

Der Endlichkeitssatz wird auch Kompaktheitssatz genannt: Man wähle zu jeder widerspruchsfreien Menge <math>\Phi</math> von Sätzen ein Modell <math>{\mathcal A}_\Phi</math> und fasse die so gefundenen Modelle zu einer Menge <math>\mathcal X</math> zusammen. Für einen Satz <math>\varphi</math> sei <math>X_\varphi := \{{\mathcal A}\in {\mathcal X};\, {\mathcal A}\vDash \varphi \}</math>. Dann bilden die Mengen <math>X_\varphi</math> die [[Basis (Topologie)|Basis einer Topologie]] auf <math>\mathcal X</math> und der Endlichkeitssatz ist zur [[Kompakter Raum|Kompaktheit]] dieses Raums äquivalent.

=== Isomorphien ===
Aus dem [[Kompaktheitssatz (Logik)|Kompaktheitssatz]] folgt:
* Gibt es zu einer Menge <math>\Phi</math> von Ausdrücken der Sprache <math>L_I^S</math> ein unendliches Modell, so gibt es Modelle beliebig hoher Mächtigkeit.

Ist nämlich <math>\Phi</math> gegeben und ist <math>\kappa</math> eine [[Kardinalzahl (Mathematik)|Kardinalzahl]], so sei <math>\{c_\alpha;\, \alpha < \kappa\}</math> eine Menge von nicht in <math>S</math> enthaltenen Konstantensymbolen. Jede endliche Teilmenge von <math>\Phi\cup \{\neg c_\alpha\equiv c_\beta;\, \alpha < \beta < \kappa\}</math> hat dann ein Modell in der Sprache <math>L_I^{\tilde{S}}</math>, wobei <math>\tilde{S}</math> die um die neuen Konstantensymbole erweiterte Symbolmenge sei. Wegen des Endlichkeitssatzes gibt es dann ein Modell für <math>\Phi\cup \{\neg c_\alpha\equiv c_\beta;\, \alpha < \beta < \kappa\}</math>, und das hat mindestens die Mächtigkeit <math>\kappa</math>. Mit etwas genauerer Argumentation kann man sogar ein Modell der Mächtigkeit <math>\kappa</math> finden, falls die Mächtigkeit von <math>\Phi</math> kleiner gleich <math>\kappa</math> ist.

Hier zeigt sich eine Schwäche der Prädikatenlogik erster Stufe. Mittels der Sprache der ersten Stufe kann für Ausdrucksmengen mit unendlichen Modellen niemals eine Charakterisierung bis auf Isomorphie gelingen, denn die Klasse aller Modelle zu einer solchen widerspruchsfreien Menge von Ausdrücken enthält stets Modelle beliebig hoher Mächtigkeit, also auch nicht isomorphe Modelle. Man nennt zwei Modelle ''elementar äquivalent'', wenn die Mengen der Ausdrücke, für die sie Modelle sind, übereinstimmen. Die Sprachen erster Stufe können daher unendliche Strukturen bzw. Modelle nur bis auf [[elementare Äquivalenz]] charakterisieren.

=== Satz von Löwenheim-Skolem ===
{{Hauptartikel|Satz von Löwenheim-Skolem}}
Ebenfalls aus dem [[Satz von Henkin]] lässt sich der [[Satz von Löwenheim-Skolem]] ableiten:
* Gibt es zu einer höchstens abzählbaren Menge <math>\Phi</math> von Ausdrücken der Sprache <math>L_I^S</math> ein unendliches Modell, so gibt es auch ein [[Abzählbarkeit|abzählbares]] Modell.

Im einleitenden Beispiel ist <math>(\Z,+,-,\le)</math> ein abzählbares Modell. In vielen mathematischen Theorien lassen sich diese sehr leicht finden, in der [[Modelltheorie]] hat das Löwenheim-Skolem-Theorem aber tiefgehende Anwendungen.

=== Satz von Lindström ===
Wegen oben genannter Schwächen der Sprache erster Stufe kann man nach geeigneten Erweiterungen suchen. Wenn man auf diese Weise echt ausdrucksstärkere Sprachen findet, was natürlich noch zu präzisieren wäre, so zeigen die [[Sätze von Lindström]], dass man dann auf den Endlichkeitssatz oder auf den Satz von Löwenheim-Skolem verzichten muss. Will man beide Sätze beibehalten, so ist die Prädikatenlogik erster Stufe also „das Beste“, was man erreichen kann.

== Siehe auch ==
* [[Logik höherer Stufe]] für weitere Erweiterungen der Logik
* [[Lokalität (Logik)]] zu Grenzen der Ausdrucksstärke der Prädikatenlogik erster Stufe
* [[Gödelscher Unvollständigkeitssatz]], ein grundlegender Satz der Prädikatenlogik erster Stufe und der mathematischen Logik überhaupt

== Literatur ==
* H.-D. Ebbinghaus, J. Flum, W. Thomas: ''Einführung in die mathematische Logik'', Spektrum Akademischer Verlag 1996, ISBN 3-8274-0130-5
* {{Literatur
   |Autor=[[Wolfgang Rautenberg]]
   |Titel=Einführung in die Mathematische Logik
   |Auflage=3.
   |Verlag=Vieweg+Teubner
   |Ort=Wiesbaden
   |Datum=2008
   |ISBN=978-3-8348-0578-2
   |DOI=10.1007/978-3-8348-9530-1}}

== Einzelnachweise und Anmerkungen ==
<references>
<ref name="Grädel2009">
{{Literatur
 |Autor=Erich Grädel
 |Titel=Mathematische Logik
 |Band=Mathematische Grundlagen der Informatik, SS 2009
 |Verlag=RWTH
 |Ort=Aachen
 |Datum=
 |Seiten=129
 |Online=[https://fldit-www.cs.uni-dortmund.de/~peter/LogikGraedel.pdf uni-dortmund.de]
 |Format=PDF
 |KBytes=}}
</ref>
<ref name="KruseBorgelt2008">
{{Literatur
 |Autor=R. Kruse, C. Borgelt
 |Titel=Grundbegriffe der Prädikatenlogik
 |Band=Computational Intelligence
 |Verlag=Otto-von-Guericke Universität
 |Ort=Magdeburg
 |Datum=2008
 |Seiten=14
 |Online=[http://fuzzy.cs.ovgu.de/studium/ise/txt_05/logic.pdf fuzzy.cs.ovgu.de]
 |Format=PDF
 |KBytes=}}
</ref>
<ref name="VoglerWS2007-8">
{{Literatur
 |Autor=W. Vogler
 |Titel=Logik für Informatiker
 |Band=WS 2007/2008
 |Verlag=Univ. Augsburg, Institut für Informatik
 |Ort=Augsburg
 |Datum=
 |Seiten=49
 |Online=[https://www.informatik.uni-augsburg.de/lehrstuehle/swt/ti/lehre/ws0708/logik/Skript/logik-stud.pdf uni-augsburg.de]
 |Format=PDF
 |KBytes=}}
</ref>
</references>

{{SORTIERUNG:Pradikatenlogik Erster Stufe}}
[[Kategorie:Mathematische Logik]]
[[Kategorie:Prädikatenlogik]]