Prädikatenlogik

Prädikatenlogik oder Quantorenlogik ist eine Familie logischer Systeme, die es erlauben, einen weiten und in der Praxis vieler Wissenschaften und deren Anwendungen wichtigen Bereich von Argumenten zu formalisieren und auf ihre Gültigkeit zu überprüfen. Auf Grund dieser Eigenschaft spielt die Prädikatenlogik eine große Rolle in der formalen und nicht formalen Logik sowie in Mathematik, Informatik, Linguistik und Philosophie.

Prädikatenlogik ist eine Erweiterung der Aussagenlogik. In der Aussagenlogik werden zusammengesetzte Aussagen daraufhin untersucht, aus welchen einfacheren Aussagen sie mit Hilfe von aussageverknüpfenden Bindewörtern – in der Logik: Junktoren – 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.

Das zentrale Konzept der Prädikatenlogik ist das Prädikat. Ein Prädikat in diesem prädikatenlogischen Sinn ist eine Folge von Wörtern mit klar definierten Leerstellen (Auslassungen), die zu einer – wahren oder falschen – Aussage wird, wenn in jede Leerstelle ein Eigenname eingesetzt wird. Zum Beispiel ist die deutsche Wortfolge „_ ist ein Mensch“ ein Prädikat, weil durch Einsetzen eines Eigennamens – etwa „Sokrates“ – ein Aussagesatz, zum Beispiel „Sokrates ist ein Mensch“, entsteht. In diesem Sinn lässt sich die elementare Aussage „Die Erde ist eine Scheibe“ prädikatenlogisch in das Prädikat „_ ist eine Scheibe“ und den Eigennamen „die Erde“ 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 traditionellen Grammatik bzw. Schulgrammatik (auch wenn historisch und philosophisch ein Zusammenhang besteht).

Das charakteristische und wichtigste Sprachmittel der Prädikatenlogik ist der Quantor oder Quantifikator. Quantoren erlauben es, Aussagen darüber zu machen, auf wie viele Individuen ein Prädikat zutrifft. Der Allquantor oder Universalquantifikator sagt aus, dass ein Prädikat auf alle Individuen zutrifft; der Existenzquantor oder Existenzialquantifikator sagt aus, dass ein Prädikat auf mindestens ein Individuum zutrifft. Damit ermöglichen es die Quantoren, Aussagen wie „Alle Menschen sind sterblich“, „Es gibt rosa Elefanten“ oder „Es gibt genau einen Gott“ in ihrer Struktur zu analysieren. Gelegentlich werden zusätzlich numerische Quantoren verwendet, mit denen ausgesagt werden kann, dass ein Prädikat zum Beispiel auf genau vier Individuen zutrifft; numerische Quantoren lassen sich allerdings auf den All- und den Existenzquantor sowie das Zeichen „=“ für Identität zurückführen.

Gottlob Frege und Charles Sanders Peirce^[1] entwickelten unabhängig voneinander die Prädikatenlogik. Frege entwickelt und formalisiert sein System in der 1879 erschienenen Begriffsschrift. Ältere logische Systeme, zum Beispiel die traditionelle Begriffslogik seit ihrer Begründung in der aristotelischen Syllogistik oder auch der modernere Relationenkalkül von Charles S. Peirce, sind hinsichtlich ihrer Ausdrucksstärke echte Teilmengen der Prädikatenlogik, d.h. sie lassen sich vollständig in dieser ausdrücken bzw. in diese übersetzen.

Prädikate

Die in der Einführung 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 Gegebenheiten ausdrücken, zum Beispiel Begriffe (z.B. „_ ist ein Mensch“), Eigenschaften (z.B. „_ ist rosa“) oder Relationen, d.h. Beziehungen zwischen Individuen (z.B. „_₁ ist größer als _₂“ oder „_₁ liegt zwischen _₂ und _₃“). Da die genaue Natur und der ontologische Status von Begriffen, Eigenschaften und Relationen umstritten sind bzw. von unterschiedlichen philosophischen Richtungen unterschiedlich betrachtet werden und da auch die genaue Abgrenzung von Begriffen, Eigenschaften und Relationen untereinander unterschiedlich gesehen wird, ist diese 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.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_₁_₂ für ein zweistelliges Prädikat, G_₁ für ein einstelliges Prädikat oder H_₁_₂_₃ für ein dreistelliges Prädikat.

Eigennamen und Individuenkonstanten

In Sprachphilosophie und Sprachwissenschaft ist das Thema der Eigennamen 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.B. „Gottlob Frege“) oder Kennzeichnungen (z.B. „der gegenwärtige Bundeskanzler von Österreich“) sein.

Das Gegenstück zu den Eigennamen der natürlichen Sprache sind die Individuenkonstanten 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. Es bedeutet dies keine impliziten metaphysischen Voraussetzungen, sondern legt die Verwenderinnen von Prädikatenlogik lediglich darauf fest, nur solche natürlichsprachlichen Eigennamen mit Individuenkonstanten auszudrücken, die auch 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 „_₁ ist der Autor von _₂“ mit den Prädikatbuchstaben F_ bzw. G_₁_₂, 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

Quantoren ermöglichen es, Aussagen darüber zu machen, auf wie viele Individuen ein Prädikat zutrifft. Der Existenzquantor sagt aus, dass ein Prädikat auf mindestens ein Individuum zutrifft, beschreibt also die Existenz mindestens eines unter das Prädikat fallenden Gegenstandes. Der Allquantor sagt aus, dass ein Prädikat auf alle Individuen zutrifft.

Der Existenzquantor wird in halbformaler Sprache als „es gibt mindestens ein Ding, sodass...“ oder „es gibt mindestens ein Ding, für das gilt...“ ausgedrückt. In formaler Sprache werden die Zeichen $\exists$ oder $\bigvee$ verwendet. Der Allquantor wird in halbformaler Sprache als „Für jedes Ding gilt: ...“ ausgedrückt, in formaler Sprache durch eines der Zeichen $\forall$ oder $\bigwedge$ .

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: $\exists xMx$ . Dabei ist M_ die Übersetzung des einstelligen Prädikats „_ ist ein Mensch“ und ist $\exists$ 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 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_₁_₂, „_₁ liebt _₂“, das die Relation des Liebens ausdrückt, wird durch Binden der ersten Leerstelle durch den Allquantor zum einstelligen Prädikat $\forall xLx\_$ , 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 $\forall xL\_x$ , 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_₁_₂, das zum Beispiel wie oben gelesen werden kann als„_₁ liebt _₂“, alle Möglichkeiten aufgezählt werden, die Leerstellen durch Quantoren zu binden:

$\forall xLxx$ : „für jedes Ding gilt: es liebt es (=sich selbst)“: Alles und jede/r liebt sich selbst
$\exists xLxx$ : „für mindestens ein Ding gilt: es liebt es (=sich selbst)“: Mindestens eine/r liebt sich selbst.
$\forall x\forall yLxy$ : Jede/r liebt jede/n.
$\forall x\forall yLyx$ : Jede/r wird von jede/m geliebt.
$\forall x\exists yLxy$ : Jede/r liebt mindestens eine/n.
$\forall x\exists yLyx$ : Jede/r wird von mindestens einer/einem geliebt.
$\exists x\forall yLxy$ : Es gibt jemanden, der/die alle liebt.
$\exists x\forall yLyx$ : Es gibt jemanden, der/die von allen geliebt wird.
$\exists x\exists yLxy$ : Mindestens eine/r liebt mindestens eine/n.

Wichtig und instruktiv ist es, zwischen den Sätzen 6, $\forall x\exists yLyx$ , und 7, $\exists x\forall yLxy$ , zu unterscheiden: In beiden Fällen wird jedermann und –frau geliebt; im ersten Fall jedoch wird jede/r von irgendjemandem geliebt, im zweiten Fall wird jede/r von ein und demselben Individuum geliebt.

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.

Einige prädikatenlogische Äquivalenzen

Dieses Kapitel stellt exemplarisch einige häufiger gebrauchte prädikatenlogische Äquivalenzen, angezeigt durch den Doppelpfeil, dar.

$\neg \forall xPx\leftrightarrow \exists x\neg Px$

Sprich: die Verneinung der Aussage „Alle Autos sind grün“ lässt sich wahlweise als „Nicht alle Autos sind grün“ oder als „Es gibt mindestens ein Auto, das nicht grün ist“ formulieren.

$\neg \exists xPx\leftrightarrow \forall x\neg Px$

Diese Äquivalenz zeigt auf, dass die Verneinung der Aussage „Es gibt mindestens einen Ostfriesen, der die Wahrheit sagt“ wahlweise als „Es ist nicht der Fall, dass es mindestens einen Ostfriesen gibt, der die Wahrheit sagt“ oder als „Alle Ostfriesen sagen nicht die Wahrheit“ ausgedrückt werdern kann.

$\exists x(Px\vee Qx)\leftrightarrow (\exists xPx\vee \exists xQx)$
$\forall x(Px\wedge Qx)\leftrightarrow (\forall xPx\wedge \forall xQx)$
$\forall x(P\vee Qx)\leftrightarrow (P\vee \forall xQx)$
$\exists x(P\wedge Qx)\leftrightarrow (P\wedge \exists xQx)$
$(\forall xPx\rightarrow Q)\leftrightarrow \exists x(Px\rightarrow Q)$
$(\exists xPx\rightarrow Q)\leftrightarrow \forall x(Px\rightarrow Q)$
$(P\rightarrow \forall xQx)\leftrightarrow \forall x(P\rightarrow Qx)$
$(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 der ersten 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 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).

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 1960-er-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 (siehe Artikel Begriffslogik).

Anwendung

Neben der Anwendung als Hilfsmittel vor allem für Informatik, Mathematik und Linguistik spielt die Prädikatenlogik insbesondere in der Konzeption und Programmierung von Expertensystemen und in der künstlichen Intelligenz eine Rolle. In den beiden letztgenannten Gebieten wird oft sogar eine Form angewandter Prädikatenlogik, Prolog („programming in logic“), als Programmiersprache verwendet.

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.

Siehe auch

Arten und Erweiterungen

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

Klassische Prädikatenlogik und ihre Erweiterungen

Nichtklassische Erweiterungen der Prädikatenlogik
- Modallogik (modale Prädikatenlogik)
- Temporale Logik
- Dialogische Logik
- Aktionslogik
- Fixpunktlogik

Kalküle für prädikatenlogische Systeme

Konkrete Kalküle für prädikatenlogische Systeme werden in folgenden weiterführenden Einzelartikeln angegeben:

Quellen

↑ Eric M. Hammer: Semantics for Existential Graphs, Journal of Philosophical Logic, Volume 27, Issue 5 (Oktober 1998), Seite 489

Literatur

Jon Barwise, John Etchemendy: The Language of First Order Logic, Stanford: CSLI 1991 (=CSLI Lecture Notes; 23) (in englischer Sprache) ISBN 0-937073-74-1
Jon Barwise, John Etchemendy: Band 1: Aussagen- und Prädikatenlogik Mentis 2005 ISBN 3897854406; Band 2: Anwendungen und Metatheorie, Mentis 2006 ISBN 3897854414
Benson Mates: Elementare Logik - Prädikatenlogik der ersten Stufe, Göttingen: Vandenhoeck & Ruprecht 1997 ISBN 3525405413
Wesley C. Salmon: Logik, Stuttgart: Reclam 1983 (=Universal-Bibliothek) ISBN 3-15-007996-9
Melvin Fitting: First-Order Logic and Automated Theorem Proving, New York: Springer ²1995, ISBN 0387945938
Wolfgang Bibel: Deduktion. Automatisierung der Logik, München: Oldenbourg 1992 (=Handbuch der Informatik 6.2) ISBN 3-486-20785-7
Lothar Kreiser, Siegfried Gottwald, Werner Stelzner: Nichtklassische Logik. Eine Einführung, Berlin: Akademie ²1990 ISBN 3-05-000274-3
Karel Berka, Lothar Kreiser: Logik-Texte. Kommentierte Auswahl zur Geschichte der modernen Logik, Berlin: Akademie ⁴1986

Weblinks

[1] Eric M. Hammer: Semantics for Existential Graphs, Journal of Philosophical Logic, Volume 27, Issue 5 (Oktober 1998), Seite 489

[1]