Signatur (Modelltheorie)

In der mathematischen Logik besteht eine Signatur aus der Menge der Symbole, die in der betrachteten Sprache zu den üblichen, rein logischen Symbolen hinzukommt, und einer Abbildung, die jedem Symbol der Signatur eine Stelligkeit eindeutig zuordnet. Während die logischen Symbole wie ${\displaystyle \forall ,\exists ,\land ,\lor ,\rightarrow ,\leftrightarrow ,\neg }$ stets als „für alle“, „es gibt ein“, „und“, „oder“, „folgt“, „äquivalent zu“ bzw. „nicht“ interpretiert werden, können durch die semantische Interpretation der Symbole der Signatur verschiedene Strukturen (insbesondere Modelle von Aussagen der Logik) unterschieden werden. Die Signatur ist der spezifische Teil einer elementaren Sprache.

Beispielsweise lässt sich die gesamte Zermelo-Fraenkel-Mengenlehre in der Sprache der Prädikatenlogik erster Stufe und dem einzigen Symbol ${\displaystyle \in }$ (neben den rein logischen Symbolen) formulieren; in diesem Fall ist die Symbolmenge der Signatur gleich ${\displaystyle \{\in \}}$.

Motivation

Sollen Aussagen über ein bestimmtes Gebiet formalisiert werden, ist zunächst zu entscheiden, über welche Objekte und welche Beziehungen Aussagen getroffen werden sollen. Für jedes benennbare Objekt wird eine Konstante eingeführt und für jede Beziehung ein Relationssymbol. Beispielsweise, um über die Anordnung von natürlichen Zahlen zu sprechen, wird für jede Zahl eine Konstante eingeführt und Relationssymbole ${\displaystyle <}$ (kleiner als) und ${\displaystyle >}$ (größer als).

Meistens braucht man darüber hinaus noch Funktionen, mit denen man über den Konstanten rechnen kann, z. B. ein Symbol ${\displaystyle (+)}$ für die Addition der natürlichen Zahlen.[1]

Somit g​ibt es d​rei Arten v​on Symbolen, d​ie in Signaturen vorkommen können:

• Konstantensymbole: Sie stehen für genau einen Wert.
• Funktionssymbole: Sie stehen jeweils für eine eindeutige Zuordnung von Werten auf andere.
• Relationssymbole (Prädikate): Sie stehen jeweils für eine Beziehung, also für eine Zuordnung von Werten zueinander, die nicht eindeutig sein muss. Eine Beziehung wird oft ausgedrückt als die Teilmenge aller Tupel, für die das Prädikat gilt.

Einordnung und Abgrenzung

Nicht zur Signatur gehören Variablensymbole, deren Wert in der Formel nicht interpretiert wird, und weitere Zeichen, die dem Aufbau einer Aussage bzw. Formel dienen. Alle diese Zeichen gemeinsam bilden die von der Signatur erzeugte „elementare Sprache“. Eine Sprache ${\displaystyle L}$ umfasst also mehr Zeichen als die zugehörige Signatur ${\displaystyle {\boldsymbol {S}}(L).}$

Die z​ur Bildung logischer Aussagen u​nd Formeln erlaubten Zeichen k​ann man s​omit grob einteilen in[2]

• Zeichen, die die Struktur (den Aufbau) der Aussage oder Formel definieren:
  • Junktorensymbole, zum Beispiel ${\displaystyle \land ,\lor ,\rightarrow ,\leftrightarrow ,\neg }$
  • Quantorensymbole, zum Beispiel ${\displaystyle \forall ,\exists ,\exists ^{1}}$
• Terminale Zeichen, die für Werte und deren Beziehungen stehen:
  • Variablen, zum Beispiel ${\displaystyle x_{0},x_{1},x_{2},\ldots }$
  • Symbole der Signatur
    • Konstantensymbole, zum Beispiel ${\displaystyle 0,1,e}$
    • Funktionssymbole, zum Beispiel ${\displaystyle +,{}^{-1},f}$
    • Relationssymbole (Prädikate), zum Beispiel ${\displaystyle \sim ,<,\in }$
• Technische Zeichen
  • Gliederungszeichen,[3] wie die Klammern ${\displaystyle (,)}$
  • andere, wie ${\displaystyle {\boldsymbol {,}}}$ (Komma) ${\displaystyle \dots }$

Manche Autoren verzichten auf einen Teil der Junktoren und Quantoren, z. B. kann ${\displaystyle \exists ^{1}}$ mit Hilfe der anderen dieser Zeichen erklärt werden. Unter Ausnutzung der Dualität können ${\displaystyle \land ,\forall }$ (oder umgekehrt ${\displaystyle \lor ,\exists }$) entfallen.[4]

Terme gehören n​icht zur Signatur, d​iese werden a​ber aus d​en logischen Symbolen, d​en Variablen u​nd den Funktionen- u​nd Konstantensymbolen d​er Signatur u​nd aus Variablen n​ach festen Bildungsregeln aufgebaut.[5]

Werden Terme als Argumente in die Relationssymbole eingesetzt, entstehen atomare Aussagen der Prädikatenlogik. Auch Vergleiche von Termen ${\displaystyle t_{1}=t_{2}}$ gelten in der Prädikatenlogik als atomare Aussagen. Aus ihnen können durch Verknüpfungen (Junktoren und Quantoren) zusammengesetzte Aussagen gebildet werden, siehe Prädikatenlogik erster Stufe §Ausdrücke.[6]

Definition

Es seien ${\displaystyle {\mathcal {C}},{\mathcal {F}}}$ und ${\displaystyle {\mathcal {R}}}$ paarweise disjunkte Mengen von nichtlogischen Zeichen. Man nennt dann jedes Zeichen in ${\displaystyle {\mathcal {S}}:={\mathcal {C}}\cup {\mathcal {F}}\cup {\mathcal {R}}}$ ein Symbol und ${\displaystyle {\mathcal {S}}}$ eine Symbolmenge, wenn durch eine Abbildung ${\displaystyle \sigma \colon {\mathcal {S}}\to \mathbb {N} _{0}}$ jedem Zeichen in ${\displaystyle {\mathcal {S}}}$ wie folgt eine Stelligkeit genannte Zahl eindeutig zugeordnet wird:[7]

• ${\displaystyle \sigma (c)=0}$ für alle ${\displaystyle c\in {\mathcal {C}},}$
• ${\displaystyle \sigma (f)\in \mathbb {N} }$ für alle ${\displaystyle f\in {\mathcal {F}}}$ und
• ${\displaystyle \sigma (R)\in \mathbb {N} }$ für alle ${\displaystyle R\in {\mathcal {R}}.}$

${\displaystyle {\boldsymbol {S}}:=({\mathcal {S}},\sigma )}$ heißt dann eine Signatur und jedes ${\displaystyle c\in {\mathcal {C}}}$ wird als ein Konstantensymbol, jedes ${\displaystyle f\in {\mathcal {F}}}$ als ein Funktionssymbol und jedes ${\displaystyle R\in {\mathcal {R}}}$ als ein Relationssymbol bezeichnet.

Eine Signatur ${\displaystyle {\boldsymbol {S}}=({\mathcal {S}},\sigma )}$ heißt endlich, falls ${\displaystyle {\mathcal {S}}}$ eine endliche Menge ist. Wenn eine Signatur keine Relationssymbole hat, wird sie eine algebraische Signatur genannt, wenn sie dagegen keine Konstanten- und keine Funktionssymbole besitzt, eine relationale Signatur.

Anmerkungen

1. Die Konstantensymbole können auch zu den Funktionssymbolen gezählt werden, so dass sich ${\displaystyle {\mathcal {S}}={\mathcal {F}}_{0}\cup {\mathcal {R}}}$ mit ${\displaystyle {\mathcal {F}}_{0}:={\mathcal {C}}\cup {\mathcal {F}}}$ ergibt.
2. Gelegentlich werden auch Symbole für nullstellige Relationen zugelassen, diese entsprechen aussagenlogischen (booleschen) Konstanten (siehe Relationen §Relationen und Funktionen sowie Brass (2005), S. 19). Mirt der Menge dieser Symbole ${\displaystyle {\mathcal {B}}}$ erweitert sich ${\displaystyle {\mathcal {R}}}$ zu ${\displaystyle {\mathcal {R}}_{0}:={\mathcal {B}}\cup {\mathcal {R}}}$ und die komplette Symbolmenge ist dann ${\displaystyle {\mathcal {S}}={\mathcal {F}}_{0}\cup {\mathcal {R}}_{0}}$.
3. Manche Autoren betrachten statt der Abbildung ${\displaystyle \sigma }$, die jedem Symbol seine Stelligkeit zuordnet, deren Urbildfasern, konkret die Folgen ${\displaystyle {\boldsymbol {\mathcal {R}}}:\mathbb {N} _{0}\to {\mathcal {R}}_{0}}$ und ${\displaystyle {\boldsymbol {\mathcal {F}}}:\mathbb {N} _{0}\to {\mathcal {F}}_{0}}$, die jeder natürlichen Zahl die Relations- bzw. Funktionssymbole der betreffenden Stelligkeit zuweisen. Für die Kennzeichnung der Signatur genügt dann die Angabe dieser beiden Folgen ${\displaystyle {\boldsymbol {\mathcal {S}}}=({\boldsymbol {\mathcal {R}}},{\boldsymbol {\mathcal {F}}})}$.[8][9]
4. Das gleiche Relationssymbol kann für Relationen unterschiedlicher Stelligkeit, und das gleiche Funktionssymbol kann für Funktionen unterschiedlicher Stelligkeit verwendet werden. Man nennt das Symbol dann überladen[10] oder polymorph.[11] Die Mengen der Relationssymbole ${\displaystyle {\boldsymbol {\mathcal {R}}}_{n}}$ für die verschiedenen Stelligkeiten n einerseits, und die Mengen der Funktionssymbole ${\displaystyle {\boldsymbol {\mathcal {F}}}_{n}}$ andererseits sind dann jeweils unter sich nicht mehr notwendig disjunkt, die Menge aller Relationssymbole ${\displaystyle {\mathcal {R}}_{0}}$ ist aber weiterhin von der aller Funktionssymbole ${\displaystyle {\mathcal {F}}_{0}}$ disjunkt.[10]
   Die Stelligkeitsabbildung ${\displaystyle \sigma }$ ist in diesem Fall eine Multifunktion (${\displaystyle \sigma$ :{\mathcal {S}}\multimap \mathbb {N} _{0}} statt ${\displaystyle \sigma$ :{\mathcal {S}}\to \mathbb {N} _{0}} );[12] die Einschränkungen auf eine bestimmte Stelligkeit (${\displaystyle \sigma _{n}:=\sigma |_{{\boldsymbol {\mathcal {R}}}_{n}\cup {\boldsymbol {\mathcal {F}}}_{n}}}$) sind jedoch eindeutig.
   Ein Beispiel sind die Funktionen max und min, die jeweils für alle n-Tupel mit ${\displaystyle n\in \mathbb {N} }$ als Argument definiert sind, d. h. ${\displaystyle \operatorname {max} ,\operatorname {min}$ :\mathbb {R} ^{+}\to \mathbb {R} } ; sowie kgV, ggT: ${\displaystyle {\mathbb {N} _{0}}^{+}\to \mathbb {N} _{0}}$.[13]
5. In der Literatur wird häufig nicht zwischen einer Signatur und ihrer Symbolmenge unterschieden, die Stelligkeitsabbildung wird dann nicht als solche angegeben.

Semantik einer Signatur

Strukturen

${\displaystyle {\boldsymbol {S}}=({\mathcal {S}},\sigma )}$ sei eine Signatur und es bestehe die Menge ${\displaystyle {\mathcal {C}}}$ aus allen Konstantensymbolen ${\displaystyle c\in {\mathcal {S}},}$ die Menge ${\displaystyle {\mathcal {F}}}$ aus allen Funktionssymbolen ${\displaystyle f\in {\mathcal {S}}}$ sowie die Menge ${\displaystyle {\mathcal {R}}}$ aus allen Relationssymbolen ${\displaystyle R\in {\mathcal {S}}.}$ Weiterhin bezeichne ${\displaystyle A}$ eine nichtleere Menge und ${\displaystyle {\boldsymbol {A}}:=A\cup \{B\mid B\subseteq A^{n}{\text{ für ein }}n\in \mathbb {N} \}=A\cup \textstyle \bigcup _{n\in \mathbb {N} }}$ ${\displaystyle {\mathcal {P}}(A^{n})}$. Ist dann ${\displaystyle \alpha \colon {\mathcal {S}}\to {\boldsymbol {A}}}$ eine Abbildung, sodass

• ${\displaystyle \alpha (c)\in A}$ eine Konstante ist für jedes ${\displaystyle c\in {\mathcal {C}},}$
• ${\displaystyle \alpha (f)\colon \,A^{\sigma (f)}\to A}$ eine Funktion ist für jedes ${\displaystyle f\in {\mathcal {F}}}$ [14] und
• ${\displaystyle \alpha (R)\subseteq A^{\sigma (R))}}$ eine Relation ist für jedes ${\displaystyle R\in {\mathcal {R}},}$[15]

so nennt man ${\displaystyle \alpha }$ Interpretationsfunktion[16] und ${\displaystyle {\mathcal {A}}:=(A,\alpha )={\bigl (}A,(\alpha (s))_{s\in S}{\bigr )}={\bigl (}A,(\alpha (c))_{c\in {\mathcal {C}}}\cup (\alpha (f))_{f\in {\mathcal {F}}}\cup (\alpha (R))_{R\in {\mathcal {R}}}{\bigr )}}$[17] eine Struktur der Signatur ${\displaystyle {\boldsymbol {S}}}$ oder kurz eine ${\displaystyle {\boldsymbol {S}}}$-Struktur. Man findet dann auch die Bezeichnungsweisen ${\displaystyle c^{\mathcal {A}}=\alpha (c),R^{\mathcal {A}}=\alpha (R),f^{\mathcal {A}}=\alpha (f)}$.[18] ${\displaystyle A}$ ist dann die Grundmenge, die Trägermenge oder kurz der Träger von ${\displaystyle {\mathcal {A}}.}$ [19] Falls ${\displaystyle A}$ eine endliche Menge ist, so heißt ebenso ${\displaystyle {\mathcal {A}}}$ endlich, sonst unendlich.

Anmerkungen

1. Eine Konstante ${\displaystyle \alpha (c)}$ lässt sich als die nullstellige Funktion ${\displaystyle 0\mapsto \alpha (c)}$ auffassen, sodass für ${\displaystyle {\mathcal {F}}_{0}:={\mathcal {C}}\cup {\mathcal {F}}}$ gilt:

   ${\displaystyle {\mathcal {A}}={\bigl (}A,(\alpha (f_{0}))_{f_{0}\in {\mathcal {F}}_{0}}\cup (\alpha (R))_{R\in {\mathcal {R}}}{\bigr )}}$ mit Funktionen ${\displaystyle \alpha (f_{0})}$ und mit Relationen ${\displaystyle \alpha (R).}$[20]

2. Jede ${\displaystyle n}$-stellige Funktion ${\displaystyle (n\in \mathbb {N} )}$ ist auch stets eine ${\displaystyle n+1}$-stellige Relation (mit dem Funktionswert an letzter Position). Daher kann jede ${\displaystyle {\boldsymbol {S}}}$-Struktur dargestellt werden als

   ${\displaystyle {\mathcal {A}}={\bigl (}A,(\alpha (S))_{S\in {\mathcal {S}}}{\bigr )}}$ mit Relationen ${\displaystyle \alpha (S).}$[21]

3. Wenn eine Struktur nur Funktionen (algebraische Struktur) oder nur Relationen (relationale Struktur, insbesondere Ordnungsstruktur) enthält, dann hat sie oft spezielle Eigenschaften.
4. Die Definition kann auf partielle Funktionen ${\displaystyle \alpha (f):A^{\sigma (f)}\not \to A}$ ausgedehnt werden, um z. B. partielle Algebren zu erfassen.
5. Im Fall von Überladung der Relations- und/oder Funktionssymbole wird Eindeutigkeit hergestellt, indem zum jeweiligen Symbol noch die Stelligkeit angegeben wird:
   • ${\displaystyle \alpha _{n}(f)\colon \,A^{n}\to A}$ und
   • ${\displaystyle \alpha _{n}(R)\subseteq A^{n}}$.

Es handelt sich um partielle Abbildungen, nur für Stelligkeiten ${\displaystyle R\in {\boldsymbol {\mathcal {R}}}_{n}}$ bzw. ${\displaystyle f\in {\boldsymbol {\mathcal {F}}}_{n}}$ kann es überhaupt Zuweisungen der Symbole zu Relationen bzw. Funktionen gegeben.

Interpretationen

Die Signatur ${\displaystyle {\boldsymbol {S}}}$ erhält durch eine ${\displaystyle {\boldsymbol {S}}}$-Struktur ${\displaystyle {\mathcal {A}}=(A,\alpha )}$ und eine Deutung oder Interpretation von Variablen eine bestimmte semantische Bedeutung:

Sei ${\displaystyle {\mathcal {V}}=\{x_{0},x_{1},x_{2},\dots \}}$ die Menge der Variablensymbole. Eine Variablenbelegung ist dann eine (eventuell auch nur partielle) Abbildung ${\displaystyle \beta \colon {\mathcal {V}}\not \to A}$.[22] wird eine Belegung der ${\displaystyle {\boldsymbol {S}}}$-Struktur ${\displaystyle {\mathcal {A}}}$ genannt. ${\displaystyle {\boldsymbol {I}}:=({\mathcal {A}},\beta )}$ heißt dann eine Interpretation der Signatur ${\displaystyle {\boldsymbol {S}}}$ oder kurz eine ${\displaystyle {\boldsymbol {S}}}$-Interpretation.

Vielsortige Signaturen

→ Hauptartikel: Sortenlogik §Vielsortige Signaturen

Für d​ie Beschreibung vielsortiger Strukturen, w​ie z. B. heterogener Algebren (Moduln, Vektorräume, K-Algebren, Lie-Algebren etc.) m​it mehreren Trägermengen k​ann man mehr- o​der vielsortige Signaturen einführen. Bei diesen kommen z​u den Funktions- u​nd Relationssymbolen kommen n​och die Sorten, Bezeichnungen für d​ie Trägermengen hinzu. Eine n-stellige Relation i​st eine Teilmenge d​es n-fachen kartesischen Produktes e​iner Sequenz d​er Trägermengen. Der Argumentbereich e​iner n-stelligen Funktion i​st ein ebensolches Produkt, d​azu kommt n​och eine d​er Trägermengen für d​en Wertebereich.

Mehrsortigkeit kann zwar immer auf Einsortigkeit zurückgeführt werden, indem man die Sortenzugehörigkeit für jede Sorte als einstellige Relation (Sortenprädikat) hinzunimmt. Im Gegensatz zur Prädikatenlogik zweiter Stufe mit Relationsvariablen bedeutet Vielsortigkeit keine Steigerung der Mächtigkeit der Theorie, etwa in Bezug auf Fragen nach Beweisbarkeit. Dafür genügt es, den einsortigen Fall zu betrachten.[23] Falsche Sortenzuordnungen (wie ${\displaystyle a={\overrightarrow {b}}}$, wenn ${\displaystyle a}$ und ${\displaystyle {\overrightarrow {b}}}$ verschiedenen Sorten zugehören, z. B. Skalar und Vektor) erscheinen dann aber nicht mehr als syntaktische Fehler. Mehrsortige Strukturen bilden ein mengentheoretisches Modell für die Datentypen in der Informationstechnologie, insbesondere bei Datenbanken, weshalb ihnen eine erheblich praktische Bedeutung zukommt.[24] Darüber hinaus ist Mehrsortigkeit eine Möglichkeit, den mit Typentheorien verbundenen Belangen auf mengentheoretischer Basis Rechnung zu tragen.

Zu den Mengen ${\displaystyle {\mathcal {F}}_{0}}$ für die Funktions- und ${\displaystyle {\mathcal {R}}_{0}}$ für die Relationssymbole[25] kommt noch eine weitere endliche, nichtleere Sortenmenge ${\displaystyle T}$ nichtlogischer Zeichen hinzu. Die Signatur eines Funktions- oder Relationssymbols ist jetzt nicht mehr einfach eine Zahl von Argumenten aus ${\displaystyle \mathbb {N} _{0}}$, sondern hat deren Sorten zu respektieren. Die Argumentsorten bilden daher n-Tupel mit der Stelligkeit n. Für Funktionen kommt noch die Bildsorte hinzu, so dass sich insgesamt ein (n+1)-Tupel ergibt. Die Tupel können als Wörter über dem Sortenalphabet ${\displaystyle T}$ verstanden werden, d. h. als Elemente der Kleeneschen Hülle ${\displaystyle T^{*}}$.[26] Sie werden als Typ des Relations- bzw. Funktionssymbols bezeichnet: ${\displaystyle \tau (R),\tau (S)}$. Die Signatur setzt sich dann aus der Sortenmenge, der Symbolmenge ${\displaystyle {\mathcal {S}}={\mathcal {F}}_{0}\cup {\mathcal {R}}_{0}}$, und der Typ-Abbildung ${\displaystyle \tau }$ zusammen: ${\displaystyle {\boldsymbol {S}}:=(T,{\mathcal {S}},\tau )}$.

Literatur

• Heinz-Dieter Ebbinghaus, Jörg Flum, Wolfgang Thomas: Einführung in die mathematische Logik. 3., vollst. überarb. u. erw. Auflage. Band 1: Grundlagen, Algebra und Geometrie. Bibliographisches Institut, Mannheim u. a. 1992, ISBN 3-411-15603-1, Kapitel II: Syntax der Sprachen erster Stufe, Kapitel III: Semantik der Sprachen erster Stufe.
• Walter Gellert, Herbert Küstner, Manfred Hellwich, Herbert Kästner (Hrsg.): Kleine Enzyklopädie Mathematik. 10. (völlig überarb. 2.) Auflage. Harri Deutsch, Thun / Frankfurt a. M. 1984, ISBN 3-87144-323-9, S. 361–363.
• Philipp Rothmaler: Einführung in die Modelltheorie. Spektrum Akademischer Verlag, 1995, ISBN 978-3-86025-461-5.
• Erich Grädel: Mathematische Logik. Mathematische Grundlagen der Informatik, SS 2009. RWTH, Aachen, S. 129 (fldit-www.cs.uni-dortmund.de [PDF]).
• W. Vogler: Logik für Informatiker. WS 2007/2008. Univ. Augsburg, Institut für Informatik, Augsburg, S. 49 (informatik.uni-augsburg.de [PDF]).

• Uwe Kastens: Prädikatenlogik. Universität Paderborn, Institut für Informatik, Paderborn 2008, S. 31 (cs.uni-paderborn.de [PDF]).

• Thomas Worsch: Prädikatenlogik. Einheit 18: Logik, WS 2008/2009. Universität Karlsruhe, Fakultät für Informatik, Karlsruhe, S. 35 (cs.uni-paderborn.de [PDF]).
• Armin B. Cremers, Ulrike Griefahn, Ralf Hinze: Typsysteme. In: Deduktive Datenbanken. Artificial Intelligence. Vieweg+Teubner, Wiesbaden 1994, ISBN 978-3-528-04700-9, Kapitel 5: Typsysteme, S. 147–182, doi:10.1007/978-3-663-09572-9_5.

Der mehr- o​der vielsortige Fall w​ird in d​en folgenden Quellen behandelt:

• Arnold Oberschelp: Untersuchungen zur mehrsortigen Quantorenlogik. In: Mathematische Annalen. Band 145, Nr. 4. Springer, 1962, S. 297–333, doi:10.1007/BF01396685 (eudml.org).
• Arnold Oberschelp; Hrsg.: Karl Hans Bläsius,Ulrich Hedtstück,Claus-Rainer Rollinger: Order Sorted Predicate Logic. Lecture Notes in Computer Science (LNCS), Band 418: Sorts and Types in Artificial Intelligence, Workshop, Eringerfeld, FRG, April 24–26, 1989 Proceedings. Springer-Verlag, Berlin Heidelberg 1990, ISBN 978-3-540-52337-6, S. 307, doi:10.1007/3-540-52337-6.
• François Bry: Exkurs: Mehrsortige Prädikatenlogik erster Stufe. Band 2.9. LMU, Institut für Informatik, pms, München 1999 (en.pms.ifi.lmu.de).
• Stefan Brass: Mathematische Logik mit Datenbank-Anwendungen. Martin-Luther-Universität Halle-Wittenberg, Institut für Informatik, Halle 2005, S. 176 (users.informatik.uni-halle.de [PDF]).
• R. Kruse, C. Borgelt: Grundbegriffe der Prädikatenlogik. Computational Intelligence. Otto-von-Guericke Universität, Magdeburg 2008, S. 14 (fuzzy.cs.ovgu.de [PDF]).
• R. Hartwig: Syntax Semantik Spezifikation – Grundlagen de Informatik. WS 2009/2010. Universität Leipzig, Institut für Informatik, Leipzig, S. 219 (informatik.uni-leipzig.de [PDF]).
• Reinhold Letz: Prädikatenlogik. WS 2004/2005. Technische Universität München, Fakultät für Informatik, Lehrstuhl Informatik IV, München, S. 47 (tcs.ifi.lmu.de [PDF]).
• Friedrich Steimann: Ordnungssortierte Feature-Logik und Dependenzgrammatiken in der Computerlinguistik. Monographien. FernUni, Fakultät Mathematik und Informatik, LG Programmiersysteme, Hagen 31. Januar 2011, S. 104 (fernuni-hagen.de – Diplomarbeit)., bei: FernUni Hagen, fernuni-hagen.de (PDF; 6,3 MB). Original bei: Universität Karlsruhe 1992, Institut für Logik, Komplexität und Deduktionssysteme

Einzelnachweise und Anmerkungen

1. Die Argumente der Relationen und Funktionen sind Stellungsparameter (auch Positionsparameter genannt). In der Informationstechnologie weit verbreitete Logiken, in denen den Argumenten Namen gegeben werden (Schlüsselwortparameter), nennt man Feature-Logiken, siehe auch: Parameter (Informatik) §Unterschiedliche Parameter-Begriffe und Steimann (1992), S. 4.
2. Siehe E. Grädel (2009) S. 45.
3. siehe Aussagenlogik §Bausteine der aussagenlogischen Sprache
4. Zum Beispiel Kruse, Borgelt (2008) S. 3
5. Siehe E. Grädel (2009) S. 45 f
6. E. Grädel (2009) S. 46 f
7. In der englischsprachigen Literatur findet sich auch die Bezeichnung ${\displaystyle \operatorname {ar} }$ (von arity, Stelligkeit) anstelle von ${\displaystyle \sigma }$.
8. Die beiden Folgen definieren sich als die Urbildfasern der Einschränkungen von ${\displaystyle \alpha }$ auf die beiden Symbolmengen ${\displaystyle {\mathcal {R}}_{0}}$ und ${\displaystyle {\mathcal {F}}_{0}}$:  ${\displaystyle {\boldsymbol {\mathcal {R}}}_{n}=(\alpha |_{{\mathcal {R}}_{0}})^{-1}(\{n\}),\;{\boldsymbol {\mathcal {F}}}_{n}=(\alpha |_{{\mathcal {F}}_{0}})^{-1}(\{n\})}$. Siehe W. Vogler (2007/2008) S. 3.
9. Stefan Brass (2005) S. 16. Die dortigen Ausführungen für mehrsortige Signaturen wurden hier vereinfacht. An die Stelle der Kleeneschen Hülle ${\displaystyle {\mathcal {S}}}$ über den Sorten tritt hier die Menge der natürlichen Zahlen ${\displaystyle \mathbb {N} _{0}}$. Konstanten sind als nullstellige Funktionen aufgefasst, nullstellige Relationen zugelassen. Der Autor verwendet den Ausdruck Prädikatsymbole mit Bezeichnungen ${\displaystyle {\mathcal {P}}}$, ${\displaystyle {\mathcal {F}}}$ und ${\displaystyle \Sigma }$ statt ${\displaystyle {\boldsymbol {\mathcal {R}}}}$, ${\displaystyle {\boldsymbol {\mathcal {F}}}}$ und ${\displaystyle {\boldsymbol {\mathcal {S}}}}$.
10. Stefan Brass (2005), S. 20
11. Cremers et al., (1994), Seite 148; siehe auch Polymorphie (Programmierung).
12. Siehe auch Korrespondenz
13. Das oben angehängte Sternchen meint hier die positive Hülle.
14. Mengentheoretisch ausgedrückt sind Funktionen spezielle Relationen: ${\displaystyle \alpha (f)\in [A^{\sigma (f)}\to A]\subseteq {\mathcal {P}}(A^{\sigma (f)}\times A)={\mathcal {P}}(A^{\sigma (f)+1})\subseteq {\boldsymbol {A}}}$, wobei ${\displaystyle {\mathcal {P}}}$ die Potenzmenge (Menge aller Teilmengen) bezeichnet.
15. Mengentheoretisch äquivalent: ${\displaystyle \alpha (R)\in {\mathcal {P}}(A^{\sigma (R)})}$, insbesondere ist für einstellige Relationen ${\displaystyle \alpha (R)\subseteq A}$ (Teilmengen) oder äquivalent ${\displaystyle \alpha (R)\in {\mathcal {P}}(A)\subseteq {\boldsymbol {A}}}$. Falls nullstellige Relationen (logische Konstanten) zugelassen sind, ist für diese ${\displaystyle \alpha (R)\subseteq A^{0}=\{\emptyset \}}$ bzw. ${\displaystyle \alpha (R)\in {\mathcal {P}}(\{\emptyset \})=\{\emptyset ,\{\emptyset \}\}}$.
16. R. Letz (2004) S. 6. Der Autor benutzt für die Interpretationsfunktion die Notation ${\displaystyle \iota }$ anstelle von ${\displaystyle \alpha }$.
17. ${\displaystyle \alpha }$ ist hier als Familie geschrieben. Diese entsteht durch disjunkte Vereinigung der drei Teile, so dass man äquivalent auch mit Hilfe der Einschränkungen ${\displaystyle {\mathcal {A}}:=(A,\alpha |_{\mathcal {C}},\alpha |_{\mathcal {F}},\alpha |_{\mathcal {R}},)={\bigl (}A,(\alpha (c))_{c\in {\mathcal {C}}},(\alpha (f))_{f\in {\mathcal {F}}},(\alpha (R))_{R\in {\mathcal {R}}}{\bigr )}}$ definieren kann.
18. Siehe Prädikatenlogik erster Stufe §Semantik
19. Manchmal spricht man auch von einem Bereich (Werte- oder Objektbereich), z. B. wenn es sich um einen Zahlbereich handelt.
20. Für die Interpretationsfunktion auf der Menge der Konstanten bedeutet dies, dass ihr Bildbereich ${\displaystyle A}$ durch die Einermengen ${\displaystyle \{\{a\}|a\in A\}\subseteq {\mathcal {P}}(A)}$ ersetzt wird, wodurch sich der Wertebereich zu ${\displaystyle {\boldsymbol {A}}==A\cup \textstyle \bigcup _{n\in \mathbb {N} }{\mathcal {P}}(A^{n})}$ vereinfacht.
    Manchmal werden nullstellige Relationen zugelassen. Diese lassen sich als logische Konstanten auffassen. ${\displaystyle {\mathcal {R}}_{0}}$ bezeichnet dann alle Relationssymbole einschließlich der nullstelligen. In der obigen Beziehung für die Signatur ${\displaystyle {\mathcal {A}}}$ ist entsprechend ${\displaystyle {\mathcal {R}}}$ durch ${\displaystyle {\mathcal {R}}_{0}}$ zu ersetzen; der Wertebereich wird mit nullstelligen Funktionen und Relationen zu ${\displaystyle {\boldsymbol {A}}=\textstyle \bigcup _{n\in \mathbb {N} _{0}}{\mathcal {P}}(A^{n}).}$
21. A. Oberschelp (1962), S. 298
22. Die Menge der Variablensymbole ${\displaystyle {\mathcal {V}}}$ kann endlich oder abzählbar unendlich sein (siehe Stefan Brass (2005) S. 13), im zweiten Fall werden aus mehreren Zeichen zusammengesetzte Variablennamen benutzt, die gewissen Regenl unterworfen sind, damit sie als Variablennamen erkennbar sind, informationstheoretisch handelt es sich bei ${\displaystyle {\mathcal {V}}}$ in diesem Fall um eine formale Sprache. Partielle Abbildungen als Belegung lässt man dann zu, wenn ${\displaystyle {\mathcal {V}}}$ unendlich ist.
23. Näheres siehe A. Oberschelp (1962) S. 297f
24. Beispielsweise können Fehler bei Datentyp-Zuweisungen schnell (zur Compilezeit) als Sytaxfehler erkannt werden.
25. Konstanten seien hier als nullstellige Funktionen aufgefasst, logische Konstantem ggf. als nullstellige Relationen
26. ${\displaystyle T^{*}=\bigcup \{T^{n}|n\in \mathbb {N} _{0}\}}$. Im Fall der Funktionssymbole, wo eine weitere Sorte für den Wertebereich benötigt wird, liegen die Werte von ${\displaystyle \sigma }$ in der positiven Hülle ${\displaystyle T^{+}=T^{*}\setminus \{\emptyset \}=T^{*}\setminus \epsilon }$. Die Stelligkeit ist die Wortlänge des Typs (minus 1 bei Funktionssymbolen).