Logik: Prädikatenlogik

Aus Wikibooks

Dieses Kapitel wird gerade überarbeitet!

Vorbemerkungen[Bearbeiten]

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)  

Geschichte[Bearbeiten]

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 Sprache[Bearbeiten]

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

Alphabet[Bearbeiten]

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.

Grammatik[Bearbeiten]

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.

Beispiele[Bearbeiten]

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

Klammerersparnis[Bearbeiten]

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.

Schreibweisen[Bearbeiten]

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 Bedeutung[Bearbeiten]

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, Bewertung[Bearbeiten]

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 :

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.   und  

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 Folgerung[Bearbeiten]

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.

Schreibweisen[Bearbeiten]

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ül[Bearbeiten]

Einzelnachweise[Bearbeiten]

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