Quelltext der Seite Prädikatenlogik

[[Prädikate]][[-n-]][[Logik]] vgl. [[Prädikation]]


Die '''Prädikatenlogiken''' (auch '''Quantorenlogiken''') bilden eine Familie [[Logik|logischer]] Systeme, die es erlauben, in der [[Theorie und Praxis|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]], [[Sprachwissenschaft|Linguistik]] und [[Philosophie]].

[[Gottlob Frege]] und [[Charles S. Peirce|Charles Sanders Peirce]]<ref>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“</ref> 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 (Logik)|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 „…&nbsp;ist ein Mensch“ ein Prädikat, weil durch Einsetzen eines [[Eigenname]]ns –&nbsp;etwa „Sokrates“&nbsp;– 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 „…&nbsp;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 [[Prädikat (Grammatik)|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''.<ref>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</ref>

Das zweite charakteristische Konzept der Prädikatenlogik ist der ''[[Quantor]]''. Quantoren geben an, von wie vielen Individuen des [[Diskursuniversum]]s 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ät (Logik)|Identitätsprädikat]] zurückführen.

=== Prädikate ===
Die oben gegebene Definition eines Prädikats als Folge von Wörtern mit klar definierten Leerstellen, die zu einer Aussage wird, wenn in jede Leerstelle ein Eigenname eingesetzt wird, ist eine rein formale, inhaltsfreie Definition. Inhaltlich betrachtet können Prädikate ganz unterschiedliche Arten von [[Begriff (Philosophie)|Begriffen]] ausdrücken:
* Sorten von Individuen (Sortalbegriffe): „_&nbsp;ist ein Mensch“
* [[Eigenschaft]]en: „_&nbsp;ist rosa“
*[[Relation (Philosophie)|relationale Begriffe]], d.&nbsp;h. Beziehungen zwischen Individuen:z.&nbsp;B. „_<sub>1</sub>&nbsp;ist größer als&nbsp;_<sub>2</sub>“ oder „_<sub>1</sub>&nbsp;liegt zwischen&nbsp;_<sub>2</sub> und&nbsp;_<sub>3</sub>“.
Da die genaue Natur und der [[ontologisch]]e Status von Begriffen, Eigenschaften und Relationen von unterschiedlichen philosophischen Richtungen unterschiedlich betrachtet werden und da auch die genaue Abgrenzung von Begriffen, Eigenschaften und Relationen untereinander unterschiedlich gesehen wird, ist die eingangs genannte formale Definition die anwendungspraktisch günstigste, weil sie es erlaubt, Prädikatenlogik zu verwenden, ohne bestimmte ontologische bzw. metaphysische Voraussetzungen akzeptieren zu müssen.

Die Zahl der unterschiedlichen Leerstellen eines Prädikats wird seine Stelligkeit genannt. So ist ein Prädikat mit einer Leerstelle einstellig, eines mit zwei Leerstellen zweistellig usw. Gelegentlich werden Aussagen als nullstellige Prädikate, d.&nbsp;h. als Prädikate ohne Leerstellen betrachtet. Bei der Zählung der Leerstellen werden nur unterschiedliche Leerstellen berücksichtigt.

In formaler Prädikatenlogik werden Prädikate durch Prädikatbuchstaben ausgedrückt, meist Großbuchstaben vom Anfang des lateinischen Alphabets, zum Beispiel F_<sub>1</sub>_<sub>2</sub> für ein zweistelliges Prädikat, G_<sub>1</sub> für ein einstelliges Prädikat oder H_<sub>1</sub>_<sub>2</sub>_<sub>3</sub> für ein dreistelliges Prädikat. Oft werden die Argumente eines Prädikats in Klammern gesetzt und durch Kommata getrennt, sodass die genannten Beispiele als F(_<sub>1</sub>,_<sub>2</sub>) bzw. G(_<sub>1</sub>) und H(_<sub>1</sub>,_<sub>2</sub>,_<sub>3</sub>) geschrieben würden.

=== Eigennamen und Individuenkonstanten ===
In [[Sprachphilosophie]] und [[Sprachwissenschaft]] ist das Thema der [[Eigenname]]n ein durchaus komplexes. Für die Behandlung im Rahmen einer einleitenden Darstellung der Prädikatenlogik soll es ausreichen, solche Sprachausdrücke als Eigennamen zu bezeichnen, die genau ein Individuum bezeichnen; das Wort „Individuum“ wird hier in einem ganz allgemeinen Sinn verstanden und meint jedes „Ding“ (physikalischer Gegenstand, Zahl, Person …), das in irgendeiner erdenklichen Weise von anderen Dingen unterschieden werden kann. Eigennamen im genannten Sinn werden meistens eigentliche Eigennamen (z.&nbsp;B. „Gottlob Frege“) oder [[Kennzeichnung (Logik)|Kennzeichnungen]] (z.&nbsp;B. „der gegenwärtige Bundeskanzler von Österreich“) sein.

Das Gegenstück zu den Eigennamen der [[Natürliche Sprache|natürlichen Sprache]] sind die [[Individuenkonstante]]n der Prädikatenlogik; meist wählt man Kleinbuchstaben vom Anfang des lateinischen Alphabets, zum Beispiel a, b, c. Im Gegensatz zu natürlichsprachlichen Eigennamen bezeichnet jede Individuenkonstante tatsächlich genau ein Individuum. Dies bedeutet keine impliziten metaphysischen Voraussetzungen, sondern legt lediglich fest, dass nur solche natürlichsprachlichen Eigennamen mit Individuenkonstanten ausgedrückt werden, die tatsächlich genau ein Individuum benennen.

Mit dem Vokabular von Prädikatbuchstaben und Individuenkonstanten lassen sich aussagenlogisch atomare Sätze wie „Sokrates ist ein Mensch“ oder „Gottlob Frege ist Autor der ''Begriffsschrift''“ bereits in ihrer inneren Struktur analysieren: Übersetzt man den Eigennamen „Sokrates“ mit der Individuenkonstante a, den Eigennamen „Gottlob Frege“ mit der Individuenkonstante b, den Eigennamen bzw. Buchtitel „Begriffsschrift“ mit der Individuenkonstante c und die Prädikate „_ ist ein Mensch“ und „_<sub>1</sub> ist der Autor von _<sub>2</sub>“ mit den Prädikatbuchstaben F_ bzw. G_<sub>1</sub>_<sub>2</sub>, dann lässt sich „Sokrates ist ein Mensch“ als Fa und „Gottlob Frege ist der Autor der ‚Begriffsschrift‘“ mit Gbc ausdrücken.

=== Quantoren ===
{{Hauptartikel|Quantor}}
Mit Quantoren können Aussagen darüber gemacht werden, ob eine Satzfunktion auf keines, einige oder alle Individuen des Diskursuniversums zutrifft. Im einfachsten Fall ist die Satzfunktion ein einstelliges Prädikat. Setzt man in das Prädikat eine Individuenvariable ein und stellt den Existenzquantor und dieselbe Variable davor, so wird damit behauptet, dass es mindestens ein Individuum gibt, auf das das Prädikat zutrifft. Es muss also mindestens einen Satz der Form geben, dass in das Prädikat eine Individuenkonstante eingesetzt wird, der im betreffenden Diskursuniversum wahr ist. Der Allquantor sagt aus, dass ein Prädikat auf alle Individuen aus dem Diskursuniversum zutrifft. In der klassischen Prädikatenlogik sind daher alle atomaren, allquantifizierten Aussagen wahr, wenn das Diskursuniversum leer ist.

Der Existenzquantor wird in halbformaler Sprache als „es gibt mindestens ein Ding, sodass …“ oder „es gibt mindestens ein (Variablenname), für das gilt …“ ausgedrückt. In formaler Sprache werden die Zeichen <math>\exist</math> oder <math>\textstyle \bigvee</math> verwendet. Der Allquantor wird in halbformaler Sprache als „Für alle (Variablenname) gilt: …“ ausgedrückt, in formaler Sprache durch eines der Zeichen <math>\forall</math> oder <math>\textstyle \bigwedge</math>.

Unmittelbar einsichtig ist die Verwendung von Quantoren bei einstelligen Prädikaten, zum Beispiel „_ ist ein Mensch.“ Die existenzquantifizierte Aussage würde lauten „Es gibt mindestens ein Ding, für das gilt: es ist ein Mensch,“ in formaler Sprache: <math>\exists x \ Mx</math>. Dabei ist M_ die Übersetzung des einstelligen Prädikats „_ ist ein Mensch“ und <math>\exists</math> ist der Existenzquantor. Der Buchstabe x ist keine Individuenkonstante, sondern erfüllt dieselbe Funktion, die in der halbformalen Formulierung das Wort „es“ erfüllt: Beide kennzeichnen die Leerstelle, auf die sich der Quantor bezieht. Im gewählten Beispiel erscheint das als redundant, weil es nur einen Quantor und nur eine Leerstelle enthält und daher keine Mehrdeutigkeit möglich ist. Im allgemeinen Fall, in dem ein Prädikat mehr als eine Leerstelle und ein Satz mehr als einen Quantor und mehr als ein Prädikat enthalten kann, wäre ohne die Verwendung geeigneter „Querverweiszeichen“ keine eindeutige Lesart vorgegeben.

Zum Herstellen der Beziehung zwischen einem Quantor und der Leerstelle, auf die er sich bezieht, werden meist Kleinbuchstaben vom Ende des lateinischen Alphabets verwendet, zum Beispiel die Buchstaben x, y und z; sie werden als Individuenvariablen bezeichnet. Die Leerstelle, auf die sich ein Quantor bezieht, bzw. die Variable, die zum Herstellen dieser Verbindung verwendet wird, bezeichnet man als durch den Quantor [[Gebundene Variable|gebunden]].

Bindet man in einem mehrstelligen Prädikat eine Leerstelle durch einen Quantor, dann entsteht ein Prädikat von um eins niedrigerer Stelligkeit. Das zweistellige Prädikat L_<sub>1</sub>_<sub>2</sub>, „_<sub>1</sub>&nbsp;liebt&nbsp;_<sub>2</sub>“, das die Relation des Liebens ausdrückt, wird durch Binden der ersten Leerstelle durch den Allquantor zum einstelligen Prädikat <math>\forall x Lx\_</math>, sozusagen zur Eigenschaft, von jedem geliebt zu werden (der Allquantor bezieht sich auf die erste Leerstelle, in der das Individuum steht, von dem die Liebe ausgeht). Durch Binden der zweiten Leerstelle wird daraus hingegen das einstellige Prädikat <math>\forall x L\_x</math>, sozusagen die Eigenschaft, alles und jeden zu lieben (der Allquantor bindet die zweite Leerstelle, also jene, in der das Individuum steht, das die Rolle des oder der Geliebten innehat).

Interessant sind Sätze mit Prädikaten, in denen mehr als eine Leerstelle durch einen Quantor gebunden wird. Die Möglichkeit der Behandlung solcher Sätze macht die große Leistungsfähigkeit der Prädikatenlogik aus, ist aber zugleich der Punkt, an dem das System für den Neueinsteiger etwas kompliziert wird und intensiverer Auseinandersetzung und Übung bedarf. Als kleiner Einblick in die Möglichkeiten der Prädikatenlogik sollen für das einfache zweistellige Prädikat L_<sub>1</sub>_<sub>2</sub>, das zum Beispiel wie oben gelesen werden kann als „_<sub>1</sub>&nbsp;liebt&nbsp;_<sub>2</sub>“, alle Möglichkeiten aufgezählt werden, die Leerstellen durch Quantoren zu binden (in den folgenden Diagrammen sind _1 die „vertikalen“ a,b,c,d,e und _2 die „horizontalen“ a,b,c,d,e):

{| style="margin: 1em auto 1em auto;"
|-
|style="width:350px" |
<!--START-->{| style="text-align: center; border: 1px solid #A9A9A9; width:300px"
|-
|colspan="2" style="color:#A9A9A9;"| Keine Spalte/Zeile ist leer:
|- style="vertical-align:top;"
|[[Datei:Predicate logic; 2 variables; example matrix a2e1.svg|mini|zentriert|120px|1.<math>\forall x \exist y Lyx</math>:<br />Jeder wird von jemandem geliebt.]]
|[[Datei:Predicate logic; 2 variables; example matrix a1e2.svg|mini|zentriert|120px|2.<math>\forall x \exist y Lxy</math>:<br />Jeder liebt jemanden.]]
|}<!--END-->
|rowspan="2" style="width:210px" |
<!--START-->{| style="text-align: center; border: 1px solid #A9A9A9; width:160px"
|-
|colspan="2" style="color:#A9A9A9;"| Die Diagonale ist<br />nichtleer/voll:
|- style="vertical-align:top;"
|[[Datei:Predicate logic; 2 variables; example matrix e(12).svg|mini|zentriert|120px|5.<math>\exist x Lxx</math>:<br />Jemand liebt sich selbst.]]
|- style="vertical-align:top;"
|[[Datei:Predicate logic; 2 variables; example matrix a(12).svg|mini|zentriert|120px|6.<math>\forall x Lxx</math>:<br />Alle lieben sich selbst.]]
|}<!--END-->
|rowspan="2" style="width:250px" |
<!--START-->{| style="text-align: center; border: 1px solid #A9A9A9; width:160px"
|-
|colspan="2" style="color:#A9A9A9;"| Die Matrix ist<br />nichtleer/voll:
|- style="vertical-align:top;"
|[[Datei:Predicate logic; 2 variables; example matrix e12.svg|mini|zentriert|120px|7.<math>\exist x \exist y Lxy</math>:<br />Einer liebt einen.<br /><br />8. <math>\exist x \exist y Lyx</math>:<br />Einer wird von einem geliebt.]]
|- style="vertical-align:top;"
|[[Datei:Predicate logic; 2 variables; example matrix a12.svg|mini|zentriert|120px|9.<math>\forall x \forall y Lxy</math>:<br />Jeder liebt jeden.<br /><br />10. <math>\forall x \forall y Lyx</math>:<br />Jeder wird von jedem geliebt.]]
|}<!--END-->
|rowspan="2"|[[Datei:Cocoon concertina square graph; matrix sketches (deutsch).svg|mini|250px|[[Hasse-Diagramm]] der [[Implikation]]en]]
|-
|
<!--START-->{| style="text-align: center; border: 1px solid #A9A9A9; width:300px"
|-
|colspan="2" style="color:#A9A9A9;"| Eine Zeile/Spalte ist voll:
|- style="vertical-align:top;"
|[[Datei:Predicate logic; 2 variables; example matrix e1a2.svg|mini|zentriert|120px|3.<math>\exist x \forall y Lxy</math>:<br />Jemand liebt alle.]]
|[[Datei:Predicate logic; 2 variables; example matrix e2a1.svg|mini|zentriert|120px|4.<math>\exist x \forall y Lyx</math>:<br />Jemand wird von allen geliebt.]]
|}<!--END-->
|}

Die [[Matrix (Mathematik)|Matrizen]] veranschaulichen die Formeln für den Fall, dass fünf Individuen als Liebende und Geliebte in Frage kommen. Abgesehen von den Sätzen 6 und 9/10 handelt es sich um Beispiele. Die Matrix zu Satz 5 steht z.&nbsp;B. für „b liebt sich selbst“; die zu Satz 7/8 für „c liebt b“.

Wichtig und instruktiv ist es, zwischen den Sätzen 1, <math>\forall x \exist y Lyx</math>, und 3, <math>\exist x \forall y Lxy</math>, zu unterscheiden: In beiden Fällen wird jeder geliebt; im ersten Fall jedoch wird jeder von irgendjemandem geliebt, im zweiten Fall wird jeder von ein und demselben Individuum geliebt.

Zwischen einigen dieser Sätze bestehen Folgerungszusammenhänge – so folgt etwa Satz&nbsp;1 aus Satz&nbsp;3, aber nicht umgekehrt (Siehe Hasse-Diagramm).

Mit dreistelligen Prädikaten können Formeln wie <math>\exist x ~\forall y ~\exist z ~Pxyz</math> gebildet werden. Mit dem Prädikat „x will, dass y z liebt“ bedeutet diese Formel „Jemand wünscht allen jemanden zu lieben“.<ref>[[v:Prädikatenlogische Formeln#Dreistellige_Prädikate|Liste aller Formeln mit dreistelligen Prädikaten]] auf [[Wikiversity]].</ref>

In natürlicher Sprache treten Quantoren in sehr unterschiedlichen Formulierungen auf. Oft werden Wörter wie „alle“, „keine“, „einige“ oder „manche“ verwendet, manchmal ist die Quantifizierung nur aus dem Zusammenhang erkennbar – zum Beispiel meint der Satz „Menschen sind sterblich“ in der Regel die Allaussage, dass alle Menschen sterblich sind.

== Beispiele (Prädikatenlogik – Deutsch) ==
{| class="wikitable centered"
|-
! Prädikatenlogik – Deutsch !! Erklärung
|-
|style="max-width:50%;" | <math>\forall x(\text{Katze}(x)\Rightarrow\text{Säugetier}(x))</math>
„Alle Katzen sind Säugetiere“

(Es kann auch Säugetiere geben, die keine Katzen sind,<br />aber keine Katzen, die keine Säugetiere sind)
|
 {| class="wikitable center"
  |-
  | <math>\forall x</math>|| <math>\text{Katze}(x)</math>||<math>\Rightarrow</math>||<math>\text{Säugetier}(x)</math>
  |-
  | Für alle x: || (Gilt) x sei eine Katze || dann || sei x ein Säugetier
|}
|-
| <math>\forall x (\text{Katze}(x) \land \text{Säugetier}(x))</math>
„Alles ist eine Katze und ein Säugetier“
|
 {| class="wikitable center"
  |-
  |<math>\forall x</math>||<math>\text{Katze}(x)</math>||<math>\land</math>||<math>\text{Säugetier}(x)</math>
  |-
  | Für alle x gilt: || x sei eine Katze || und || x sei ein Säugetier
  |}
|-
| <math>\exists x (\text{Stadt}(x)\land\text{nördlich}(x,\text{München}))</math><ref>S. 4 in http://www2.informatik.uni-hamburg.de/wsv/teaching/vorlesungen/FGI1SoSe14/PL-Syntax-Semantik.pdf</ref>
„Es gibt mindestens eine Stadt nördlich von München“
|
 {| class="wikitable center"
  |-
  |<math>\exists x</math>||<math>(\text{Stadt}(x)</math>||<math>\land</math>||<math>\text{nördlich}(x,\text{München}))</math>
  |-
  | Es gibt mindestens ein x || das ist eine Stadt || und || nördlich von München liegt
  |}
|-
| <math>\neg\exists x (\text{Stadt}(x)\land\text{nördlich}(x,x))</math><ref>S. 4 in http://www2.informatik.uni-hamburg.de/wsv/teaching/vorlesungen/FGI1SoSe14/PL-Syntax-Semantik.pdf</ref>
„Keine Stadt liegt nördlich ihrer selbst“
|
 {| class="wikitable center"
  |-
  | <math>\neg\exists x</math>||<math>(\text{Stadt}(x)</math>||<math>\land</math>||<math>\text{nördlich}(x,x))</math>
  |-
  | Es gibt kein x || das eine Stadt ist || und || nördlich von x liegt
  |}
|-
|<math>\exists x(\text{weiblich}(x)\land \text{vater}(\text{Tom},x)\land\text{mutter}(\text{Jenny},x))</math>
„Es existiert mindestens eine gemeinsame Tochter von Tom und Jenny“
|
 {| class="wikitable center"
  |-
  |<math>\exists x</math>|| <math>(\text{weiblich}(x)</math>||<math>\land</math>|| <math>\text{vater}(\text{Tom},x)</math>||<math>\land</math>||<math>\text{mutter}(\text{Jenny},x))</math>
  |-
  | Es gibt mindestens ein x,|| das weiblich ist || und || Tom als Vater hat || und || Jenny als Mutter hat
  |}
|-
| <math>\forall x:\mathbb{Katzen}( \text{Katze}(x))</math>
„Jede Katze ist eine Katze“
|
 {| class="wikitable center"
  |-
  |<math>\forall x:\mathbb{Katzen}</math>||<math>\text{Katze}(x)</math>
  |-
  | Für Jedes x aus der Menge <math>\mathbb{Katzen}</math> gilt: || x ist eine Katze
  |}

|-
| <math>\neg\forall x:\mathbb{Autos}(\text{grün}(x))</math>
„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.)
|
 {| class="wikitable center"
  |-
  | <math>\neg</math>|| <math>\forall x: \mathbb{Autos}</math>|| <math>(\text{grün}(x))</math>
  |-
  | 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.
{|class="wikitable centered toptextcells" style="width:80%;"
| <math>\neg \forall x Px \leftrightarrow \exists x \neg Px</math>|| style="max-width:60%" | 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.
|-
| <math>\neg \exists x Px \leftrightarrow \forall x \neg Px</math>|| 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.
|-
|<math>\exists x ( Px \lor Qx ) \leftrightarrow (\exists x Px \lor \exists x Qx)</math>||[[Distributivität]] des Existenzquantors über ODER.
|-
| <math>\forall x ( Px \wedge Qx ) \leftrightarrow (\forall x Px \wedge \forall x Qx)</math>|| Distributivität des Allquantors über UND.
|-
| <math>\forall x (P \land Qx) \leftrightarrow (P \land \forall x Qx)</math>||
|-
| <math>\exists x (P \wedge Qx) \leftrightarrow (P \wedge \exists x Qx)</math>||
|-
| <math>(\exists x Px \rightarrow Q) \leftrightarrow \forall x (Px \rightarrow Q)</math>|| Wenn es ein Beispiel gibt, das einen Satz impliziert, so würde jedes Beispiel diesen Satz implizieren.
|-
| <math>(P \rightarrow \forall x Qx) \leftrightarrow \forall x (P \rightarrow Qx)</math>|| 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:
{|class="wikitable centered toptextcells" style="width:80%;"
|<math>(\forall x Px \rightarrow Q) \leftrightarrow \exists x (Px \rightarrow Q)</math>
|-
|<math>(P \rightarrow \exists x Qx) \leftrightarrow \exists x (P \rightarrow Qx)</math>
|}

== 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ädikatenlogik zweiter Stufe|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 (Logik)|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.&nbsp;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ül]]e gibt, d.&nbsp;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.&nbsp;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, [[Entscheidbarkeit|entscheidbar]] zu sein; das bedeutet, dass es mechanische Verfahren ([[Algorithmus|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 Logik|nichtklassische]] Ausprägungen. Von '''klassischer Prädikatenlogik''' bzw. allgemein von [[Klassische Logik|klassischer Logik]] spricht man genau dann, wenn die beiden folgenden Bedingungen erfüllt sind:
* das behandelte System ist zweiwertig, d.&nbsp;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 [[Junktor]]en 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 == <!-- Das ist mit Absicht eine einfache, halbformale Darstellung – ins Detail gehen kann der Hauptartikel -->
{{Hauptartikel|Interpretation (Logik)}}

Für jedes prädikatenlogische System kann eine [[Semantik (Logik)|formale Semantik]] aufgestellt werden. Dazu wird eine Interpretationsfunktion definiert, eine [[Funktion (Mathematik)|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 <math>F</math> die Menge <math>\{a,b,c\}</math> zugeordnet, dann ist damit festgelegt, dass <math>F</math> auf <math>a</math>, auf <math>b</math> und auf <math>c</math> zutrifft.
; Mehrstellige Prädikate
: Jedem <math>n</math>-stelligen Prädikat wird eine Menge von <math>n</math>-[[Tupel]]n 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'''(<math>\neg\varphi</math>) = wahr (<math>\varphi</math> ist hier eine prädikatenlogische Aussage), wenn '''B'''(<math>\varphi</math>) = falsch; andernfalls ist '''B'''(<math>\neg\varphi</math>) = falsch. Mit anderen Worten: Die [[Negation#Logik|Verneinung]] einer falschen Aussage ist wahr, die Verneinung einer wahren Aussage ist falsch.
:* '''B'''(<math>\varphi\land\psi</math>) = wahr (<math>\varphi, \psi</math> sind hier prädikatenlogische Aussagen), wenn {{nowrap|'''B'''(<math>\varphi</math>)}} = {{nowrap|'''B'''(<math>\psi</math>)}} = wahr; andernfalls ist {{nowrap|'''B'''(<math>\varphi\land\psi</math>)}} = falsch. Mit anderen Worten: Eine [[Konjunktion (Logik)|Konjunktion]] ist genau dann wahr, wenn beide Konjunkte wahr sind; andernfalls ist sie falsch.
:* Analoge Definitionen werden für alle anderen [[Junktor]]en aufgestellt.
:* '''B'''(<math>\varphi(\alpha)</math>), wobei <math>\varphi</math> ein einstelliger Prädikatbuchstabe und <math>\alpha</math> eine Individuenkonstante ist, liefert den Wahrheitswert „wahr“, wenn die Interpretation von <math>\alpha</math> ein Element der Interpretation von <math>\varphi</math> ist, mit anderen Worten: wenn das von <math>\alpha</math> benannte Individuum unter das Prädikat <math>\varphi</math> fällt. Andernfalls liefert '''B'''(<math>\varphi(\alpha)</math>) den Wahrheitswert „falsch“.
:* '''B'''(<math>\varphi(\alpha_1,\dotsc,\alpha_n)</math>), wobei <math>\varphi</math> ein <math>n</math>-stelliger Prädikatbuchstabe ist und <math>\alpha_1</math> bis <math>\alpha_n</math> Individuenkonstanten sind, liefert den Wahrheitswert „wahr“, wenn das <math>n</math>-Tupel <math>\langle\alpha_1,\dotsc,\alpha_n\rangle</math> Element der Interpretation des Prädikatbuchstaben <math>\varphi</math> ist. Andernfalls liefert '''B'''(<math>\varphi(\alpha_1,\dotsc,\alpha_n)</math>) den Wahrheitswert „falsch“.
:* '''B'''(<math>\forall \chi \varphi(\chi)</math>), wobei <math>\chi</math> eine Individuenvariable ist und <math>\varphi(\chi)</math> ein einstelliges Prädikat, in dessen (ein- oder mehrfach vorkommender) Leerstelle <math>\chi</math> eingetragen ist, liefert den Wahrheitswert „wahr“, wenn '''B'''(<math>\varphi\left({\beta\over\chi}\right)</math>) den Wahrheitswert „wahr“ liefert – unabhängig davon, für welches Individuum <math>\beta</math> steht. Dabei ist <math>\beta</math> eine Individuenkonstante, die nicht in <math>\varphi(\chi)</math> vorkommt und <math>\varphi\left({\beta\over\chi}\right)</math> ist der Ausdruck, der entsteht, wenn man in <math>\varphi(\chi)</math> jedes Vorkommnis der Individuenvariable <math>\chi</math> durch die Individuenkonstante <math>\beta</math> ersetzt. Andernfalls ist '''B'''(<math>\forall \chi \varphi(\chi)</math>) = falsch. Mit anderen Worten: '''B'''(<math>\forall\chi\varphi(\chi)</math>) ist genau dann wahr, wenn <math>\varphi</math> tatsächlich auf ''alle'' Individuen des Diskursuniversums zutrifft.
:* '''B'''(<math>\exists \chi \varphi(\chi)</math>), wobei <math>\chi</math> eine Individuenvariable ist und <math>\varphi(\chi)</math> ein einstelliges Prädikat, in dessen (ein- oder mehrfach vorkommender) Leerstelle <math>\chi</math> eingetragen ist, liefert den Wahrheitswert „wahr“, wenn <math>\varphi</math> auf ''mindestens ein'' Individuum aus dem Diskursuniversum zutrifft, das heißt, wenn es möglich ist, einer in <math>\varphi</math> nicht vorkommenden Individuenkonstante <math>\beta</math> ein Individuum aus dem Diskursuniversum derart zuzuordnen, dass '''B'''(<math>\varphi\left({\beta\over\chi}\right)</math>) 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.&nbsp;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]].<ref>''free logic'' in der englischsprachigen Wikipedia</ref>

== Anwendung ==
Prädikatenlogiken sind von zentraler Bedeutung für verschiedene [[Grundlagen der Mathematik|Grundlegungen der Mathematik]].

Daneben gibt es einige konkrete Anwendungen in der [[Informatik]]: Sie spielt in der Konzeption und Programmierung von [[Expertensystem]]en und in der [[Künstliche Intelligenz|künstlichen Intelligenz]] eine Rolle. [[Logische Programmiersprache]]n 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 [[Formale Semantik|formalen Semantik]], werden Formen der Prädikatenlogik zur Repräsentation von [[Bedeutung]] angewendet.

== Spezielle Arten, Erweiterungen und Systeme ==

=== Arten und Erweiterungen ===
Arten und Erweiterungen der Prädikatenlogik sind in folgenden vertiefenden Einzelartikeln beschrieben:

* Klassische Prädikatenlogik und ihre Erweiterungen
** [[Prädikatenlogik erster Stufe]]
** [[Prädikatenlogik zweiter Stufe]]
** [[Prädikatenlogik höherer Stufe]]

* Nichtklassische Erweiterungen der Prädikatenlogik
** [[Modallogik]] (modale Prädikatenlogik)
** [[Temporale Logik]]
** [[Aktionslogik]]
** [[Fixpunktlogik]]

=== Kalküle für prädikatenlogische Systeme ===
Kalküle für prädikatenlogische Systeme werden in folgenden weiterführenden Einzelartikeln angegeben:
* [[Hilbertkalkül]]e (axiomatischer Kalkül)
* [[Systeme natürlichen Schließens]], zum Beispiel der [[Fitch-Kalkül]], [[Sequenzenkalkül]]e
* [[Baumkalkül]]e
* [[Resolution (Logik)]]
* [[Existential Graphs]]
* [[Dialogische Logik]]

== Siehe auch ==
* [[Konjunktive Anfrage]]

== Literatur ==
=== Einführungen ===
* Jon Barwise, John Etchemendy: ''Sprache, Beweis und Logik. Band 1: Aussagen- und Prädikatenlogik.'' Mentis, Paderborn 2005, ISBN 3-89785-440-6.
* Jon Barwise, John Etchemendy: ''Sprache, Beweis und Logik. Band 2: Anwendungen und Metatheorie.'' Mentis, Paderborn 2006, ISBN 3-89785-441-4.
* [[Benson Mates]]: ''Elementare Logik – Prädikatenlogik der ersten Stufe.'' [[Vandenhoeck & Ruprecht]], Göttingen 1997, ISBN 3-525-40541-3.
* Wesley C. Salmon: ''Logik.'' Reclam (=Universal-Bibliothek), Stuttgart 1983, ISBN 3-15-007996-9.

=== Zur Geschichte ===
* [[Karel Berka]], Lothar Kreiser: ''Logik-Texte. Kommentierte Auswahl zur Geschichte der modernen Logik.'' 4. Auflage. Akademie-Verlag, Berlin 1986.
* [[William Kneale]], [[Martha Kneale]]: ''The Development of Logic.'' Clarendon Press, 1962, ISBN 0-19-824773-7. Standardwerk zur Geschichte der Logik (englisch)

== Weblinks ==
[[Kategorie:Wikipedia.de Artikel]]
{{Wiktionary}}
* Uschi Robers: [http://www-ai.cs.uni-dortmund.de:8765/lexikon/theorie/logik/node3.html ''Formale Darstellung der Prädikatenlogik''.] Technische Universität Dortmund.
* [[Klaus Dethloff (Philosoph)|Klaus Dethloff]], Christian Gottschall: [http://www.erpelstolz.at/~chris/skriptum/skriptum.pdf ''Einführung in die Prädikatenlogik''.] Universität Wien.
* {{TIBAV |19823 |Linktext=Prädikatenlogik |Herausgeber=PHHD |Jahr=2012 |DOI=10.5446/19823}}

== Einzelnachweise ==
<references />

{{Normdaten|TYP=s|GND=4046974-8}}

[[Kategorie:Logik]]
[[Kategorie:Prädikatenlogik| ]]
[[Kategorie:Sprachphilosophie]]