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

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 Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikibooks.org/v1/“:): {\displaystyle \alpha} , Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikibooks.org/v1/“:): {\displaystyle \beta} ,  , ...
  2. Junktoren  ,  ,  ,  , Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikibooks.org/v1/“:): {\displaystyle \lor} ,  ,  
  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 Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikibooks.org/v1/“:): {\displaystyle \bot} 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  :

  1.  
  2.  
  3.  
  4.  
  5.  

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

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

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