Logik: Prädikatenlogik

Achtung.svg

Dieses Kapitel wird gerade überarbeitet!

VorbemerkungenBearbeiten

Die Prädikatenlogik ist eine Erweiterung der Aussagenlogik. In der Aussagenlogik werden mit Junktoren zusammengesetzte Aussagen betrachtet. Die Aussagen selbst werden nicht näher untersucht. Das erfolgt nun in der Prädikatenlogik: wie werden Aussagen gebildet? Dazu drei einfache Beispiele:

(1)  
(2)  
(3)  

In diesen Aussagen gibt es sogenannte Individuenkonstante nämlich: , und . Das sind Namen, die bestimmte Zahlen bzw. Menschen oder Gegenstände bezeichnen. In der Prädikatenlogik werden diese Objekte Individuen genannt. Im Beispiel (3) kommt die Variable vor. Variable bezeichnen auch Individuen, aber es ist nicht festgelegt welche das genau sein sollen. Üblich ist deshalb auch der Ausdruck Unbekannte. Des Weiteren kommen Prädikate vor: ist ein Prädikat, ebenso . Prädikate bezeichnen Eigenschaften die auf Individuen zutreffen können oder nicht. Zu Prädikaten gehören Leerstellen, die mit drei Punkten gekennzeichnet sind. Die Anzahl der Leerstellen ist die Stellenzahl des Prädikats.

Schliesslich kommt im Beispiel (3) das Funktionszeichen und das Gleichheitszeichen vor. Wie die Prädikate haben die Funktionszeichen Leerstellen, in die Namen für Individuen eingesetzt werden. Funktionszeichen haben also auch eine Stellenzahl. Aber während die Prädikate mit den eingesetzten Namen Aussagen ergeben, liefern die Funktionszeichen mit den Namen wieder einen Namen für ein Individuum. Das Gleicheitszeichen verbindet ebenfalls zwei Namen und macht daraus eine Aussage.

Aber das ist noch nicht alles: zur Prädikatenlogik gehören auch noch die Quantoren, und zwar der Allquantor (für alle ...) und der Existenzquantor (es gibt ...). Beispiele:

(4)  
(5)  

GeschichteBearbeiten

Entwickelt wurde die Prädikatenlogik von Gottlob Frege und Charles Sanders Peirce unabhängig voneinander. Frege entwickelte sein System der Prädikatenlogik in der 1879 erschienenen Begriffsschrift[1]. Freges Notation sah damals sehr anders aus als die heutige, sie bestand aus mit Linien verbundenen Prädikaten, die auch abzweigen konnten, außerdem gab es in seiner Notaion weniger Junktoren und keinen Existenzquantor, trotzdem konnte man mit seiner Prädikatenlogik alles sagen, was man auch mit der modernen ausdrücken kann, auch wenn es teilweise etwas umständlicher ist. Peirces Notation ähnelte aber schon der modernen.

Eine formale SpracheBearbeiten

Für die Prädikatenlogik erweitern wir die Sprache der Aussagenlogik.

AlphabetBearbeiten

In der Prädikatenlogik gibt es 9 Arten von Zeichen:

  1. Aussagenkonstante , , , ...
  2. Junktoren , , , , , ,
  3. Klammern ,
  4. Individuenkonstanten , , , ...
  5. Prädikate , , , ...
  6. Funktionszeichen , , , ...
  7. Gleichheitszeichen
  8. Variable , , , ...
  9. Quantoren ,

Die ersten drei Arten von Zeichen entsprechen denen der Aussagenlogik.

GrammatikBearbeiten

In der Prädikatenlogik gibt es zwei Arten von wohlgeformten Zeichenreihen, nämmlich Formeln und Terme. Die ersten drei Regeln entsprechen denen der Aussagenlogik:

  1. Jede Aussagenkonstante ist eine Formel, und sind Formeln.
  2. Ist eine Formel, so ist auch eine Formel.
  3. Sind sowohl als auch Formeln, so sind auch , , und Formeln.
  4. Jede Individuenkonstante und jede Variable ist ein Term.
  5. Ist ein -stelliges Funktionszeichen und sind Terme, so ist ein Term.
  6. Ist ein -stelliges Prädikat, und sind Terme, so ist eine Formel.
  7. Sind und Terme, so ist eine Formel.
  8. Ist eine Formel und eine Variable, so sind und Formeln.

Es gibt keine weiteren Formeln und Terme. Aus dieser Definition ergibt sich sofort:

Lemma: Jede Formel der Aussagenlogik ist auch eine Formel der Prädikatenlogik.

Die Regeln 1. bis 3. der Grammatik stimmen zwar wörtlich mit denen der Aussaglogik überein, aber ihr Anwendungsbereich ist sehr viel umfangreicher. Ist ein 1-stelliges Prädikat, eine Individuenkonstante und eine Variable, so sind beispielsweise und Formeln nach den Regeln 6. und 8. Mit der Regel 3. können wir daraus die Formel bilden.

Die Anzahl der Formeln und Terme hängt nun nicht allein von der Anzahl der Aussagenkonstanten ab, wie das in der Aussagenlogik war. Vielmehr hängt es auch von der Anzahl der Individuenkonstanten, der Relationen, der Funktionszeichen und der Variablen ab, wieviele Formeln und Terme es gibt.

BeispieleBearbeiten

In den folgenden Beispielen seien:

  • Individuenkonstanten:
  • Funktionszeichen: (1-stellig), (2-stellig)
  • Prädikate: (einstellig), (1-stellig), (einstellig), (grösser als, 2-stellig)
Ausdruck Art Begründung
Term nach Regel 1, weil eine Individuenkonstante ist
Term nach Regel 5
Formel nach Regel 6
Formel nach Regel 6
Formel nach Regel 6 und Regel 2
- ein Funktionszeichen ist kein Term und keine Formel
Term nach Regel 5
Formel nach Regel 7
- ist ein 2-stelliges Prädikat
Formel nach Regel 6
- es fehlt die Variable des Quantors
Formel nach den Regeln 6, 2 und 8
Formel nach den Regeln 5, 7 und 8

KlammerersparnisBearbeiten

Wir erweitern die Klammerersparnisregeln der Aussagenlogik wie folgt:

  1. Aussenklammern können weggelassen werden,
  2. bindet stärker als die Quantoren und die Junktoren,
  3. und binden stärker als die Junktoren,
  4. und binden stärker als und ,
  5. bindet stärker als .

Ist eine Individuenkonstante, so ist wie folgt zu lesen: . Beachte, dass sich der Quantor nur auf die unmittelbar folgende Formel bezieht, im Beispiel nur auf die Gleichung.

SchreibweisenBearbeiten

Wir lassen Aussenklammern und weitere Klammern weg, wenn sie inhaltlich ohne Bedeutung sind, wie beispielsweise hier: . 2-stellige Funktionszeichen und 2-stellige Prädikate schreiben wir zwischen die Argumente: und . Wir setzen auch zusätzliche Klammern, wenn dieses die Verständlichkeit erhöht. Aus dem Zusammenhang sollte aber immer klar hervorgehen, wie die Formel nach den ursprünglichen Regeln zusammengesetzt ist.

Die BedeutungBearbeiten

In der Prädikatenlogik muss nicht nur den Formeln einer der Wahrheitswerte Wahr oder Falsch zugeordnet werden, sondern es muss auch für die Terme eine Bedeutung festgelegt werden.

Interpretation, BewertungBearbeiten

Definition:

Eine Bewertung  
  1. legt eine nichtleere Menge   als Individuenbereich fest,
  2. ordnet allen Individuenkonstanten   ein Element von   zu,
  3. ordnet jedem  -stelligen Funktionszeichen   eine  -stellige Funktion von   in   zu,
  4. ordnet jeder  -stelligen Relation   eine  -stellige Relation über   zu,
  5. ordnet allen Variablen   ein Element aus   zu,
  6. ordnet allen Aussagenkonstanten   einen Wahrheitswert   oder   zu.

Es gilt also für eine Bewertung  :

  1.  
  2.  
  3.  
  4.  
  5.  
  6.  

Insbesondere ordnet also   den Variablen Werte zu. Dieser Teil von   wird Belegung genannt. Die Bewertung   sei wie   definiert, nur dass der Variablen   der Wert   zugeordnet wird. Wir setzen die Bewertung   wie folgt auf alle Terme und Formeln fort:

  1.  
  2.  
  3.  
  4.     und    
  5.  
  6.  
  7.  
  8.  
  9.  
  10.  
  11.  

Feststellung:

Schränken wir eine Interpretation der Prädikatenlogik auf die Formeln ein, die auch Formeln der Aussagenlogik sind, so erhalten wir eine Interpretation im Sinne der Aussagenlogik!

Redeweisen:

Für die Interpretation der Prädikatenlogik sind die gleichen Redeweisen wie bei der Aussagenlogik üblich:

  erfüllt eine Formel  , wenn   der Formel   den Wert Wahr zuordnet.   erfüllt die Formelmenge  , wenn   alle Formeln aus   mit Wahr belegt. Eine andere Redeweise lautet:   ist ein Modell von   bzw. von  .

  widerlegt eine Formel  , wenn   die Formel   mit Falsch bewertet.   wird dann auch Gegenbeispiel für   genannt.

Logische FolgerungBearbeiten

Auch die Definitionen und Sätze zur logischen Folgerung   können aus der Aussagenlogik übernommen werden:

Definition: Seien   und   Formelmengen.

Dann folgt   aus  , wenn für alle Bewertungen gilt: sind alle Formeln aus   Wahr, dann ist wenigstens eine Formel aus   Wahr.
Schreibweisen:   (aus   folgt  ) und   (aus   folgt nicht  ).

Damit   gilt, muss es also eine Bewertung   geben, die alle Formeln aus   mit   und alle Formeln aus   mit   belegt.

SchreibweisenBearbeiten

Statt   schreiben wir einfach  , lassen also die Klammern   weg.
Mit       ist       gemeint.
Ein wichtiger Spezialfall ist       (aus   folgt  ).
    steht für       (  ist die leere Menge).


Satz: Es gilt       genau dann, wenn    

Beweis:
Es gelte   und es sei   eine Bewertung, die alle Formeln aus   Wahr macht.
Wenn   die Formel   mit Falsch bewertet, sind wir fertig, weil dann   die Formel   erfüllt. Wenn   die Formel   mit Wahr bewertet, ist es nach Voraussetzung die Formel   oder eine Formel aus   Wahr. Im zweiten Fall ist nichts weiter zu zeigen und im ersten Fall ist auch   Wahr.

Gelte nun umgekehrt   und   erfülle alle Formeln aus  .
Wenn   eine Formel aus   Wahr macht, sind wir fertig. Wenn   die Formel   Wahr macht, gibt es zwei Möglichkeiten:   bewertet   mit Falsch, dann ist alles klar. Bewertet   die Formel   mit Wahr, bewertet sie auch die Formel   mit Wahr. Also gilt  . ✔

KalkülBearbeiten

EinzelnachweiseBearbeiten

  1. Gottlob Frege: Begriffsschrift. 1879. (Nachdruck: Olms, Hildesheim 1998, ISBN 3-487-00623-5)