Prädikatenlogik

Category: 

Die Prädikatenlogik (auch Quantorenlogik) ist ein Teilgebiet der Logik und erweitert die Aussagenlogik. Zentrales Element ist dabei das Prädikat, welches für übergebene Argumente einen Wahrheitswert liefert.

Prädikate

Ein Prädikat ist eine Folge von Wörtern mit Leerstellen, welche zu einer wahren oder falschen Aussage wird, wenn in die Leerstellen entsprechende Objekte eingefügt werden. Der Satz "... ist eine Primzahl" ist ein Prädikat, welches durch Einsetzen entweder wahr oder falsch wird. Setzt man nun den Wert 3 ein, so wäre die Aussage korrekt. Im Allgemeinen wird ein Prädikat als Funktion dargestellt, wie z.B. \( P(x) = \) "x ist eine Primzahl".

Quantoren

Ein weiteres wichtiges Konzept der Prädikatenlogik, ist das Konzept der Quantoren.
Mit Quantoren können Aussagen darüber gemacht werden, für wie viele Objekte eine Aussage zutrifft. Grundsätzlich unterscheidet man zwei Quantoren:
Allquantor
Für alle Elemente gilt die Bedingung. \(\forall x P(x) \) bedeutet soviel wie: Für alle x gilt die Aussage P(x).
Existenzquantor
Es gibt mindestens ein Element, sodass die Bedingung gilt. \(\exists x P(x) \) bedeutet soviel wie: Es gibt mindestens ein x, für das P(x) wahr ist.
Wenn man ausdrücken möchte, dass die Bedingung für exakt ein Element gilt, so schreibt man: \(\exists ! x P(x) \)

Die beiden Quantoren sind gewissermaßen das Gegenteil voneinander. Denn wenn eine Bedingung nicht für alle gilt, ist dies gleichbedeutend damit, dass die Bedingung für mindestens einen eben nicht gilt.
\( \lnot \forall x~P(x) = \exists x~\lnot P(x) \)
\( \lnot \exists x~Q(x) = \forall x~\lnot Q(x) \)

Quantoren haben die gleiche Präzedenz wie der Negationsoperator \( \lnot \), also eine höhere Präzedenz als z.B. \( \land \).
Dementsprechend gilt z.B.: \( \forall x~P(x) \land Q(x) = (\forall x~P(x)) \land Q(x) \)
In diesem Beispiel sieht man auch, dass verschiedene Variablen den gleichen Namen haben können!

Vorkommen von Variablen

Eine Variable hat einen Namen, welcher ggf. auch mehrfach vergeben sein kann. Zum besseren Verständnis sollte man die mehrfache Verwendung des gleichen Namens vermeiden. Wenn nötig kann man eine konsistente Umbenennung durchführen. Das obige Beispiel kann man z.B. auch wie folgt schreiben:

  1. \( (\forall x~P(x)) \land Q(y) \)
  2. bzw. \( (\forall y~P(y)) \land Q(x) \)

Eine Variable in einer prädikatenlogischen Formel kann entweder gebunden oder ungebunden sein. Sie ist genau dann gebunden, wenn sie innerhalb des Wirkungsbereiches eines Quantors steht. In der ersten Formel ist demnach die Variable \(x\) an den Allquantor gebunden. Die Variable \(y\) ist hingegen ungebunden und wird als freie Variable bezeichnet.

Beispiele

Für die folgenden Beispiele seien die folgenden Prädikate gegeben:
\(Prime(x) := \) "x ist eine Primzahl"
\(Even(x) := \) "x ist gerade"
\(Odd(x) := \) "x ist ungerade"

Die Aussage \( \exists x \in \mathbb{N}~Prime(x) \) ist eine wahre Aussage, da es offensichtlich mindestens eine Primzahl gibt.
\( \forall x \in \mathbb{N}~ (Even(x) \lor Odd(x)) \)
Diese Aussage ist eine wahre Aussage, da eine natürliche Zahl entweder gerade oder ungerade ist.
\( \forall x \in \mathbb{N}~ Even(x) \lor \forall x \in \mathbb{N}~ Odd(x) \)
Diese Aussage ist falsch, denn sie sagt aus, dass jede Zahl gerade ist oder jede Zahl ungerade.

Auf der folgenden Seite findet ihr ein paar Aufgaben zum Thema Prädikatenlogik.