Die Prädikatenlogiken (auch Quantorenlogiken) bilden eine Familie logischer Systeme, die es erlauben, in der Praxis und in der Theorie vieler Wissenschaften wichtige Bereiche durch Argumente zu formalisieren und sie auf ihre Gültigkeit zu überprüfen. Auf Grund dieser Eigenschaft spielt die Prädikatenlogik eine große Rolle in der Logik sowie in Mathematik, Informatik, Linguistik und Philosophie.

Gottlob Frege und Charles Sanders Peirce entwickelten unabhängig voneinander die Prädikatenlogik. Frege entwickelte und formalisierte sein System in der 1879 erschienenen Begriffsschrift. Ältere logische Systeme, zum Beispiel die traditionelle Begriffslogik, sind hinsichtlich ihrer Ausdrucksstärke echte Teilmengen der Prädikatenlogik. Sie lassen sich vollständig in diese übersetzen.

Zentrale Begriffe

Die Prädikatenlogik ist eine Erweiterung der Aussagenlogik. In der Aussagenlogik werden zusammengesetzte Aussagen daraufhin untersucht, aus welchen einfacheren Aussagen sie zusammengesetzt sind. Zum Beispiel besteht die Aussage „Es regnet oder die Erde ist eine Scheibe“ aus den beiden Aussagen „Es regnet“ und „Die Erde ist eine Scheibe“. Diese beiden Aussagen lassen sich ihrerseits nicht in weitere Teilaussagen zerlegen – sie werden deshalb atomar oder elementar genannt. In der Prädikatenlogik werden atomare Aussagen hinsichtlich ihrer inneren Struktur untersucht.

Ein zentrales Konzept der Prädikatenlogik ist das Prädikat. In umgangssprachlicher Annäherung ist ein Prädikat eine Folge von Wörtern, die Leerstellen eröffnen; diese Folge wird zu einer wahren oder falschen Aussage, wenn in jede Leerstelle ein Eigenname eingesetzt wird. Zum Beispiel ist die Wortfolge „… ist ein Mensch“ ein Prädikat, weil durch Einsetzen eines Eigennamens – etwa „Sokrates“ – ein Aussagesatz, im Beispiel „Sokrates ist ein Mensch“, entsteht. Die Aussage „Die Erde ist eine Scheibe“ lässt sich prädikatenlogisch in den Eigennamen „die Erde“ und das Prädikat „… ist eine Scheibe“ zerlegen. Anhand der Definition und der Beispiele wird klar, dass der Begriff „Prädikat“ in der Logik, speziell in der Prädikatenlogik, nicht dieselbe Bedeutung hat wie in der Grammatik, auch wenn historisch und philosophisch ein Zusammenhang besteht. Statt eines Eigennamens kann in das Prädikat auch eine Variable eingesetzt werden, wodurch das Prädikat zu einer Satzfunktion wird: φ_(x)=„x ist ein Mensch“ ist eine Funktion, die in der klassischen Prädikatenlogik für die Eigennamen derjenigen Individuen, die Menschen sind, den Wahrheitswert wahr ausgibt und für alle anderen den Wahrheitswert falsch.

Das zweite charakteristische Konzept der Prädikatenlogik ist der Quantor. Quantoren geben an, von wie vielen Individuen des Diskursuniversums eine Satzfunktion erfüllt wird. Ein Quantor bindet die Variable einer Satzfunktion, so dass wieder ein Satz entsteht. Der Allquantor sagt aus, dass ein Prädikat auf alle Individuen zutreffen soll. Der Existenzquantor besagt, dass ein Prädikat auf mindestens ein Individuum zutrifft. Die Quantoren ermöglichen Aussagen wie „Alle Menschen sind sterblich“ oder „Es gibt mindestens einen rosa Elefanten“.

Gelegentlich werden zusätzlich numerische Quantoren verwendet, mit denen ausgesagt werden kann, dass ein Prädikat auf eine bestimmte Anzahl von Individuen zutrifft. Diese sind jedoch nicht unbedingt nötig, denn sie lassen sich auf den All- und den Existenzquantor sowie auf das Identitätsprädikat zurückführen.

Beispiele (Prädikatenlogik – Deutsch)

Prädikatenlogik – Deutsch	Erklärung
${\displaystyle \forall x({\text{Katze}}(x)\Rightarrow {\text{Säugetier}}(x))}$ „Alle Katzen sind Säugetiere“ (Es kann auch Säugetiere geben, die keine Katzen sind, aber keine Katzen, die keine Säugetiere sind)	${\displaystyle \forall x}$ ${\displaystyle {\text{Katze}}(x)}$ ${\displaystyle \Rightarrow }$ ${\displaystyle {\text{Säugetier}}(x)}$ Für alle x: (Gilt) x sei eine Katze dann sei x ein Säugetier
${\displaystyle \forall x({\text{Katze}}(x)\land {\text{Säugetier}}(x))}$ „Alles ist eine Katze und ein Säugetier“	${\displaystyle \forall x}$ ${\displaystyle {\text{Katze}}(x)}$ ${\displaystyle \land }$ ${\displaystyle {\text{Säugetier}}(x)}$ Für alle x gilt: x sei eine Katze und x sei ein Säugetier
${\displaystyle \exists x({\text{Stadt}}(x)\land {\text{nördlich}}(x,{\text{München}}))}$ „Es gibt mindestens eine Stadt nördlich von München“	${\displaystyle \exists x}$ ${\displaystyle ({\text{Stadt}}(x)}$ ${\displaystyle \land }$ ${\displaystyle {\text{nördlich}}(x,{\text{München}}))}$ Es gibt mindestens ein x das ist eine Stadt und nördlich von München liegt
${\displaystyle \neg \exists x({\text{Stadt}}(x)\land {\text{nördlich}}(x,x))}$ „Keine Stadt liegt nördlich ihrer selbst“	${\displaystyle \neg \exists x}$ ${\displaystyle ({\text{Stadt}}(x)}$ ${\displaystyle \land }$ ${\displaystyle {\text{nördlich}}(x,x))}$ Es gibt kein x das eine Stadt ist und nördlich von x liegt
${\displaystyle \exists x({\text{weiblich}}(x)\land {\text{vater}}({\text{Tom}},x)\land {\text{mutter}}({\text{Jenny}},x))}$ „Es existiert mindestens eine gemeinsame Tochter von Tom und Jenny“	${\displaystyle \exists x}$ ${\displaystyle ({\text{weiblich}}(x)}$ ${\displaystyle \land }$ ${\displaystyle {\text{vater}}({\text{Tom}},x)}$ ${\displaystyle \land }$ ${\displaystyle {\text{mutter}}({\text{Jenny}},x))}$ Es gibt mindestens ein x, das weiblich ist und Tom als Vater hat und Jenny als Mutter hat
${\displaystyle \forall x:\mathbb {Katzen} ({\text{Katze}}(x))}$ „Jede Katze ist eine Katze“	${\displaystyle \forall x:\mathbb {Katzen} }$ ${\displaystyle {\text{Katze}}(x)}$ Für Jedes x aus der Menge ${\displaystyle \mathbb {Katzen} }$ gilt: x ist eine Katze
${\displaystyle \neg \forall x:\mathbb {Autos} ({\text{grün}}(x))}$ „Nicht alle Autos sind grün“ (Es gibt mindestens ein Auto, das nicht-grün ist. Das heißt auch, dass es mindestens ein Auto im Diskursuniversum gibt. Falls es überhaupt keine Autos gäbe, dann wäre die All-Aussage „Alle Autos sind grün“ wahr, die vorliegende Verneinung dieser Aussage somit falsch. Es folgt also wiederum, dass es ein Auto geben muss.)	${\displaystyle \neg }$ ${\displaystyle \forall x:\mathbb {Autos} }$ ${\displaystyle ({\text{grün}}(x))}$ Nicht für jedes Auto gilt: es sei grün.

Einige prädikatenlogische Äquivalenzen

Die Logische Äquivalenz zwischen zwei prädikatenlogischen Aussagen ergibt sich durch den schematischen Austausch von Allquantor und Existenzquantor. Im Folgenden exemplarisch einige häufiger gebrauchte prädikatenlogische Äquivalenzen.

${\displaystyle \neg \forall xPx\leftrightarrow \exists x\neg Px}$	Die Verneinung der Aussage „Alles ist grün“ lässt sich wahlweise als „Nicht alles ist grün“ und als „Es gibt etwas, das nicht grün ist“ formulieren.
${\displaystyle \neg \exists xPx\leftrightarrow \forall x\neg Px}$	Wenn die Aussage „Es gibt etwas, das grün ist.“ verneint wird, so sind „Es gibt nicht ein Ding im Diskursuniversum, das grün ist.“ oder „Alles im Diskursuniversum ist nicht grün.“ wahr und umgekehrt.
${\displaystyle \exists x(Px\lor Qx)\leftrightarrow (\exists xPx\lor \exists xQx)}$	Distributivität des Existenzquantors über ODER.
${\displaystyle \forall x(Px\wedge Qx)\leftrightarrow (\forall xPx\wedge \forall xQx)}$	Distributivität des Allquantors über UND.
${\displaystyle \forall x(P\land Qx)\leftrightarrow (P\land \forall xQx)}$
${\displaystyle \exists x(P\wedge Qx)\leftrightarrow (P\wedge \exists xQx)}$
${\displaystyle (\exists xPx\rightarrow Q)\leftrightarrow \forall x(Px\rightarrow Q)}$	Wenn es ein Beispiel gibt, das einen Satz impliziert, so würde jedes Beispiel diesen Satz implizieren.
${\displaystyle (P\rightarrow \forall xQx)\leftrightarrow \forall x(P\rightarrow Qx)}$	Wenn ein Satz eine Allaussage impliziert, so gilt die Implikation für jedes einzelne Beispiel.

Wenn ausgeschlossen wird, dass das Diskursuniversum leer ist, gelten zudem:

${\displaystyle (\forall xPx\rightarrow Q)\leftrightarrow \exists x(Px\rightarrow Q)}$

${\displaystyle (P\rightarrow \exists xQx)\leftrightarrow \exists x(P\rightarrow Qx)}$

Arten von Prädikatenlogik

Wenn – wie bisher skizziert – Quantoren die Leerstellen von Prädikaten binden, dann spricht man von Prädikatenlogik erster Stufe oder Ordnung, englisch: first order logic, abgekürzt FOL; sie ist sozusagen das Standardsystem der Prädikatenlogik.

Eine naheliegende Variation der Prädikatenlogik besteht darin, nicht nur die Leerstellen von Prädikaten zu binden, also nicht nur über Individuen zu quantifizieren, sondern auch Existenz- und Allaussagen über Prädikate zu machen. Auf diese Weise kann man Aussagen wie „Es gibt ein Prädikat, für das gilt: es trifft auf Sokrates zu“ und „Für jedes Prädikat gilt: es trifft auf Sokrates zu, oder es trifft nicht auf Sokrates zu“ formalisieren. Zusätzlich zu den individuellen Leerstellen der Prädikate erster Stufe hätte man auf diese Weise Prädikatsleerstellen eingeführt, die zu Prädikaten zweiter Stufe führen, zum Beispiel eben zu „_ trifft auf Sokrates zu“. Von hier ist es nur ein kleiner Schritt zu Prädikaten dritter Stufe, in deren Leerstellen Prädikate zweiter Stufe eingesetzt werden können, und allgemein zu Prädikaten höherer Stufe. Man spricht in diesem Fall daher von Prädikatenlogik höherer Stufe, englisch higher order logic, abgekürzt HOL.

Die formal einfachste Erweiterung der Prädikatenlogik erster Stufe besteht jedoch in der Ergänzung um Mittel zur Behandlung von Identität. Das entstehende System heißt Prädikatenlogik der ersten Stufe mit Identität. Zwar lässt sich Identität in der Prädikatenlogik höherer Stufe definieren, d. h. ohne Spracherweiterung behandeln, doch ist man bestrebt, möglichst lange und möglichst viel auf der ersten Stufe zu arbeiten, weil es für diese einfachere und vor allem vollständige Kalküle gibt, d. h. Kalküle, in denen alle in diesem System gültigen Formeln und Argumente hergeleitet werden können. Für die Prädikatenlogik höherer Stufe gilt das nicht mehr, d. h., es ist für die höhere Stufe nicht möglich, mit einem einzigen Kalkül alle gültigen Argumente herzuleiten.

Umgekehrt kann man Prädikatenlogik der ersten Stufe einschränken, indem man sich zum Beispiel auf einstellige Prädikate beschränkt. Das aus dieser Einschränkung entstehende logische System, die monadische Prädikatenlogik, hat den Vorteil, entscheidbar zu sein; das bedeutet, dass es mechanische Verfahren (Algorithmen) gibt, die für jede Formel bzw. für jedes Argument der monadischen Prädikatenlogik in endlicher Zeit feststellen können, ob sie bzw. ob es gültig ist oder nicht. Für einige Anwendungszwecke ist monadische Prädikatenlogik ausreichend; zudem lässt sich die gesamte traditionelle Begriffslogik, namentlich die Syllogistik, in monadischer Prädikatenlogik ausdrücken.

Parallel zur bereits thematisierten Unterscheidung prädikatenlogischer Systeme nach ihrer Stufe bzw. Ordnung gibt es klassische und nichtklassische Ausprägungen. Von klassischer Prädikatenlogik bzw. allgemein von klassischer Logik spricht man genau dann, wenn die beiden folgenden Bedingungen erfüllt sind:

• das behandelte System ist zweiwertig, d. h., jede Aussage nimmt genau einen von genau zwei Wahrheitswerten, meist wahr und falsch an (Prinzip der Zweiwertigkeit); und
• der Wahrheitswert von Aussagen, die durch aussagenlogische Junktoren zusammengesetzt sind, ist durch die Wahrheitswerte der zusammengesetzten Aussagen eindeutig bestimmt (Extensionalitätsprinzip).

Weicht man von mindestens einem dieser Prinzipien ab, dann entsteht nichtklassische Prädikatenlogik. Selbstverständlich ist es auch innerhalb der nichtklassischen Prädikatenlogik möglich, sich auf einstellige Prädikate zu beschränken (nichtklassische monadische Prädikatenlogik), über Individuen zu quantifizieren (nichtklassische Prädikatenlogik der ersten Stufe), das System um Identität zu erweitern (nichtklassische Prädikatenlogik der ersten Stufe mit Identität) oder die Quantifikation auf Prädikate auszudehnen (nichtklassische Prädikatenlogik höherer Stufe). Ein häufig verwendetes nichtklassisches prädikatenlogisches System ist die modale Prädikatenlogik (siehe Modallogik).

Semantik der Prädikatenlogik

Für jedes prädikatenlogische System kann eine formale Semantik aufgestellt werden. Dazu wird eine Interpretationsfunktion definiert, eine Funktion im mathematischen Sinn, die den Prädikaten der formalen prädikatenlogischen Sprache einen Umfang und den atomaren Sätzen einen Wahrheitswert zuordnet. Zunächst wird ein Diskursuniversum festgelegt, das ist die Gesamtheit der unterscheidbaren Gegenstände („Individuen“), auf die sich die zu interpretierenden prädikatenlogischen Aussagen beziehen sollen. Für die klassische Prädikatenlogik werden dann die einzelnen Sprachelemente folgendermaßen interpretiert:

Individuenkonstanten

Jeder Individuenkonstante wird genau ein Element aus dem Diskursuniversum zugeordnet, das heißt, jede Individuenkonstante benennt genau ein Individuum.

Einstellige Prädikate

Jedem einstelligen Prädikat wird eine Menge von Individuen aus dem Diskursuniversum zugeordnet. Auf diese Weise wird festgelegt, auf welche Individuen das betroffene Prädikat zutrifft. Wird zum Beispiel dem einstelligen Prädikat ${\displaystyle F}$ die Menge ${\displaystyle \{a,b,c\}}$ zugeordnet, dann ist damit festgelegt, dass ${\displaystyle F}$ auf ${\displaystyle a}$, auf ${\displaystyle b}$ und auf ${\displaystyle c}$ zutrifft.

Mehrstellige Prädikate

Jedem ${\displaystyle n}$-stelligen Prädikat wird eine Menge von ${\displaystyle n}$-Tupeln von Individuen aus dem Diskursuniversum zugeordnet.

Aussagen

Um den Wahrheitswert von Aussagen bestimmen zu können, muss die Bewertungsfunktion die Menge aller wohlgeformten Aussagen in die Menge der Wahrheitswerte abbilden, also für jede Aussage der prädikatenlogischen Sprache festlegen, ob sie wahr oder falsch ist. Dies geschieht in der Regel rekursiv nach folgendem Muster (die Bewertungsfunktion wird hier mit B bezeichnet):

• B(${\displaystyle \neg \varphi }$) = wahr (${\displaystyle \varphi }$ ist hier eine prädikatenlogische Aussage), wenn B(${\displaystyle \varphi }$) = falsch; andernfalls ist B(${\displaystyle \neg \varphi }$) = falsch. Mit anderen Worten: Die Verneinung einer falschen Aussage ist wahr, die Verneinung einer wahren Aussage ist falsch.
• B(${\displaystyle \varphi \land \psi }$) = wahr (${\displaystyle \varphi ,\psi }$ sind hier prädikatenlogische Aussagen), wenn B(${\displaystyle \varphi }$) = B(${\displaystyle \psi }$) = wahr; andernfalls ist B(${\displaystyle \varphi \land \psi }$) = falsch. Mit anderen Worten: Eine Konjunktion ist genau dann wahr, wenn beide Konjunkte wahr sind; andernfalls ist sie falsch.
• Analoge Definitionen werden für alle anderen Junktoren aufgestellt.
• B(${\displaystyle \varphi (\alpha )}$), wobei ${\displaystyle \varphi }$ ein einstelliger Prädikatbuchstabe und ${\displaystyle \alpha }$ eine Individuenkonstante ist, liefert den Wahrheitswert „wahr“, wenn die Interpretation von ${\displaystyle \alpha }$ ein Element der Interpretation von ${\displaystyle \varphi }$ ist, mit anderen Worten: wenn das von ${\displaystyle \alpha }$ benannte Individuum unter das Prädikat ${\displaystyle \varphi }$ fällt. Andernfalls liefert B(${\displaystyle \varphi (\alpha )}$) den Wahrheitswert „falsch“.
• B(${\displaystyle \varphi (\alpha _{1},\dotsc ,\alpha _{n})}$), wobei ${\displaystyle \varphi }$ ein ${\displaystyle n}$-stelliger Prädikatbuchstabe ist und ${\displaystyle \alpha _{1}}$ bis ${\displaystyle \alpha _{n}}$ Individuenkonstanten sind, liefert den Wahrheitswert „wahr“, wenn das ${\displaystyle n}$-Tupel ${\displaystyle \langle \alpha _{1},\dotsc ,\alpha _{n}\rangle }$ Element der Interpretation des Prädikatbuchstaben ${\displaystyle \varphi }$ ist. Andernfalls liefert B(${\displaystyle \varphi (\alpha _{1},\dotsc ,\alpha _{n})}$) den Wahrheitswert „falsch“.
• B(${\displaystyle \forall \chi \varphi (\chi )}$), wobei ${\displaystyle \chi }$ eine Individuenvariable ist und ${\displaystyle \varphi (\chi )}$ ein einstelliges Prädikat, in dessen (ein- oder mehrfach vorkommender) Leerstelle ${\displaystyle \chi }$ eingetragen ist, liefert den Wahrheitswert „wahr“, wenn B(${\displaystyle \varphi \left({\beta \over \chi }\right)}$) den Wahrheitswert „wahr“ liefert – unabhängig davon, für welches Individuum ${\displaystyle \beta }$ steht. Dabei ist ${\displaystyle \beta }$ eine Individuenkonstante, die nicht in ${\displaystyle \varphi (\chi )}$ vorkommt und ${\displaystyle \varphi \left({\beta \over \chi }\right)}$ ist der Ausdruck, der entsteht, wenn man in ${\displaystyle \varphi (\chi )}$ jedes Vorkommnis der Individuenvariable ${\displaystyle \chi }$ durch die Individuenkonstante ${\displaystyle \beta }$ ersetzt. Andernfalls ist B(${\displaystyle \forall \chi \varphi (\chi )}$) = falsch. Mit anderen Worten: B(${\displaystyle \forall \chi \varphi (\chi )}$) ist genau dann wahr, wenn ${\displaystyle \varphi }$ tatsächlich auf alle Individuen des Diskursuniversums zutrifft.
• B(${\displaystyle \exists \chi \varphi (\chi )}$), wobei ${\displaystyle \chi }$ eine Individuenvariable ist und ${\displaystyle \varphi (\chi )}$ ein einstelliges Prädikat, in dessen (ein- oder mehrfach vorkommender) Leerstelle ${\displaystyle \chi }$ eingetragen ist, liefert den Wahrheitswert „wahr“, wenn ${\displaystyle \varphi }$ auf mindestens ein Individuum aus dem Diskursuniversum zutrifft, das heißt, wenn es möglich ist, einer in ${\displaystyle \varphi }$ nicht vorkommenden Individuenkonstante ${\displaystyle \beta }$ ein Individuum aus dem Diskursuniversum derart zuzuordnen, dass B(${\displaystyle \varphi \left({\beta \over \chi }\right)}$) den Wahrheitswert „wahr“ liefert.

Alternativen

Vor dem Aufblühen von Aussagenlogik und Prädikatenlogik dominierte die Begriffslogik in Gestalt der von Aristoteles entwickelten Syllogistik und darauf aufbauender relativ moderater Erweiterungen. Zwei in den 1960er-Jahren in der Tradition der Begriffslogik entwickelte Systeme werden von ihren Vertretern als der Prädikatenlogik gleichmächtig (Freytag) bzw. sogar überlegen (Sommers) bezeichnet, haben aber in der Fachwelt wenig Resonanz gefunden.

Die Gesetze der Prädikatenlogik gelten nur dann, wenn der Bereich der untersuchten Individuen nicht leer ist, d. h. wenn es überhaupt mindestens ein Individuum (welcher Art auch immer) gibt. Eine Modifikation der Prädikatenlogik, die dieser Existenzvoraussetzung nicht unterliegt, ist die Freie Logik.

Anwendung

Prädikatenlogiken sind von zentraler Bedeutung für verschiedene Grundlegungen der Mathematik.

Daneben gibt es einige konkrete Anwendungen in der Informatik: Sie spielt in der Konzeption und Programmierung von Expertensystemen und in der künstlichen Intelligenz eine Rolle. Logische Programmiersprachen basieren zu Teilen auf – oft eingeschränkten – Formen der Prädikatenlogik. Eine Form der Wissensrepräsentation kann mit einer Sammlung von Ausdrücken in Prädikatenlogik erfolgen.

Der Relationenkalkül, eine der theoretischen Grundlagen von Datenbankabfragesprachen wie etwa SQL, bedient sich ebenfalls der Prädikatenlogik als Ausdrucksmittel.

In der Linguistik, speziell der formalen Semantik, werden Formen der Prädikatenlogik zur Repräsentation von Bedeutung angewendet.

Spezielle Arten, Erweiterungen und Systeme

Siehe auch

• Konjunktive Anfrage

Literatur

Weblinks

• Uschi Robers: Formale Darstellung der Prädikatenlogik. Technische Universität Dortmund.
• Klaus Dethloff, Christian Gottschall: Einführung in die Prädikatenlogik. Universität Wien.
• Video: Prädikatenlogik. Pädagogische Hochschule Heidelberg (PHHD) 2012, zur Verfügung gestellt von der Technischen Informationsbibliothek (TIB), doi:10.5446/19823.

Einzelnachweise

1. ↑ Eric M. Hammer: Semantics for Existential Graphs. In: Journal of Philosophical Logic, Volume 27, Issue 5 (Oktober 1998), S. 489: „Development of first-order logic independently of Frege, anticipating prenex and Skolem normal forms“
2. ↑ Es gibt Erweiterungen der klassischen Prädikatenlogik, die Definitionslücken für Satzfunktionen vorsehen, oder zusätzliche Wahrheitswerte, um beispielsweise vagen Begriffen der natürlichen Sprache gerecht zu werden
3. ↑ Liste aller Formeln mit dreistelligen Prädikaten auf Wikiversity.
4. ↑ S. 4 in http://www2.informatik.uni-hamburg.de/wsv/teaching/vorlesungen/FGI1SoSe14/PL-Syntax-Semantik.pdf
5. ↑ S. 4 in http://www2.informatik.uni-hamburg.de/wsv/teaching/vorlesungen/FGI1SoSe14/PL-Syntax-Semantik.pdf
6. ↑ free logic in der englischsprachigen Wikipedia