Benutzer:Jürgen-Michael Glubrecht/Prädikatenlogik

Aus Wikibooks
Zur Navigation springen Zur Suche springen

Prädikatenlogik[Bearbeiten]

Für den Umgang mit Junktoren habe wir mit den Wahrheitstaellen ein Verfahren kennengelernt, mit dem wir immer ermitteln können, ob eine Aussage allgemeingültig ist. Für Aussagen, in denen Quantoren vorkommen, reicht das nicht. Was macht uns also sicher, dass die Äquivalenz

immer richtig ist, egal was genau bedeutet? Betrachten wir als Beispiel die folgende Aussage über die natürlichen Zahlen: :

Alle ungeraden Zahlen ab 3 sind Primzahlen.

Wir können anfangen, das der Reihe nach zu testen: 3 ist eine Primzahl, 5 ist eine Primzahl, 7 ist eine Primzahl, usw. Aber da es bekanntlich unendlich viele natürliche Zahlen gibt, werden wir damit nicht fertig. Im Beispiel haben wir Glück, denn schon die nächste Zahl liefert ein Gegenbeispiel: 9 ist keine Primzahl. Also ist die Aussage falsch. Da wir nicht unendlich viele Aussagen durchprobieren können, müssen wir uns für die Quantoren einen anderen Weg suchen, Aussagen zu beweisen.

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. Variable , , , ...
  7. 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 Prädikat, und sind Terme, so ist eine Formel.
  6. 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.

Frei und gebundene Variablen[Bearbeiten]

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.

Definition:

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

Es gilt als für eine Bewertung :

Wir setzen die Bewertung wie folgt auf alle Terme und Formeln fort:

  1.   und  

Kalkül[Bearbeiten]

Grundregeln[Bearbeiten]

Regeln für den Allquantor

wenn nicht frei in und
Regeln für den Existenzquantor

wenn nicht frei in und