Vorlesungsbegleitung: Grundlagen der theoretischen Informatik

Kapitel 2

Kapitel 2.2
Prädikatenlogik

Was ist Prädikatenlogik ?

Wikipedia definiert Prädikatenlogik wie folgt:

"Prädikatenlogik oder Quantorenlogik ist eine Familie logischer Systeme, die
es erlauben, einen weiten und in der Praxis vieler Wissenschaften und deren
Anwendungen wichtigen Bereich von Argumenten zu formalisieren und auf
ihre Gültigkeit zu überprüfen."

Die Prädikatenlogik ist also ein Formalisierungsinstrument, was es uns

erlaubt, bestimmte Sachverhalte exakt formal zu notieren.
Das alleine schafft die Aussagenlogik nicht. Deswegen wird die
Aussagenlogik noch um folgende Bestandteile erweitert:

Variablen

"In eine Variable dürfen beliebige Elemente eingesetzt werden."

Variablen können, wie Literale, als Symbole für bestimmte Werte stehen.
Anders als ein Literal kann eine Variable allerdings Werte jedes beliebigen
Wertebereiches annehmen.

Prädikate

"Ein Prädikat ist eine Aussage, die von anderen Werten abhängt."

Ein Prädikat kann als eine Art spezielle Funktion gesehen werden, die eine
beliebig viele, aber dennoch fest definierte, Anzahl von Parametern besitzt
und in Abhängigkeit der Werte der Parameter entweder "wahr" oder "falsch"
ergibt.
Ein Prädikat ist also eine Funktion, dessen Definitionsbereich beliebig ist,
aber dessen Wertebereich immer nur "wahr" und "falsch" beinhaltet.

1
 Vorlesungsbegleitung: Grundlagen der theoretischen Informatik
Kapitel 2

Funktionen

"Eine Funktion ist eine Zuordnung, die einer Menge von Werten einen neuen
Wert eindeutig zuordnet."

Eine Funktion ist also wie ein Prädikat, nur mit beliebigem Definitionsbereich
und beliebigem Wertebereich.
Aus diesem Grund darf eine Funktion niemals innerhalb eines
prädikatenlogischen Ausdrucks stehen, sondern nur innerhalb eines
Prädikats, da nicht sichergestellt ist, dass die Funktion "wahr" oder "falsch"
zurückliefert, bzw. sie tut es auch nicht!
Würde sie "wahr " oder "falsch" zurückliefern, wäre sie ein Prädikat.

Quantoren (Existenzquantor)

"Der Existenzquantor ∃x(...) beschreibt die Aussage, dass es (mindestens)

einen Wert für x gibt, der die dahinter stehende Aussageform in x zu einer
wahren Aussage macht."

Der Existenzquantor wird also dazu benutzt, auszusagen, dass es mindestens

einen Wert für die durch ihn "gebundene" Variable in der dahinter stehenden
Formel gibt, für die die Formel "wahr" wird.

Ein Beispiel:
∃x : ( x > 4)
Übersetzen wir diesen Ausdruck in Umgangssprache, würden wir erhalten:
"Es gibt ein 'x' für das gilt, dass dieses spezielle 'x' größer als 4 ist".

Die Aussage ist im Ganzen "wahr", da man sagen kann, dass es ein x (implizit
hier aus dem Bereich der reellen Zahlen) gibt, welches größer als 4 ist.

Beschränkt man den Wertebereich der Variablen 'x', dann heisst das, dass es
jetzt aus einer "kleineren" Menge mindestens ein 'x' geben muss, was noch
größer ist als 4.
Somit ist die Beschränkung des Wertebereiches eine Verschärfung für den
Existenzquantor.

2
 Vorlesungsbegleitung: Grundlagen der theoretischen Informatik
Kapitel 2

Quantoren (Allquantor)

"Der Allquantor ∀x(...) beschreibt die Aussage, dass jeder Wert für x die
dahinter stehende Aussageform in x zu einer wahren Aussage macht."

Um eine Formel mit einem Allquantor zu bewahrheiten, muss also für jeden
möglichen einsetzbaren Wert für 'x' (oder generell für die durch ihn
gebundene Variable) die dahinter stehende Formel "wahr" werden!

Ein Beispiel:
∀x : ( x > 4) Die Aussage ist im Ganzen "falsch", da es natürlich Zahlen
gibt, die nicht größer als 4 sind.

Schränkt man hier den Wertebereich von 'x' ein, dann heisst das, dass die
Formel nun nur noch für weniger 'x' wahr sein muss.
Somit ist eine Beschränkung des Wertebereiches der gebundenen
Variablen 'x' für den Allquantor eher eine Abschwächung der Aussage.

Freie und gebundene Variablen

Eine Variable in einem Prädikatenlogischen Ausdruck ist genau dann frei,

wenn sie durch keinen Quantor (Existenzquantor oder Allquantor)
"gebunden" ist.

Beispiel:
∀x : ( x + y > x)
In diesem Ausdruck ist die Variable 'x' gebunden, da man durch den
Allquantor nicht mehr in der Lage ist, selbst zu entscheiden, welchen Wert 'x'
bekommen soll.
Es ist durch den Allquantor festgelegt, dass für alle Werte, die 'x' jemals
annehmen kann, der dahinterstehende Ausdruck "wahr" sein soll.
Das 'y' ist allerdings frei. Das heisst, man kann hier einsetzen, was man will.
Aus dem Grund ist das genannte Beispiel auch keine Aussage, sondern nur
eine Aussageform, da nicht alle vorkommenden Variablen durch einen
Quantor gebunden sind.

Eine Aussage ist immer bezüglich ihres Wertes entscheidbar!

Die Aussage ∀x : ( x > 4) z.b. ist immer entscheidbar.
Sie ist immer "falsch".
Das Beispiel ∀x : ( x + y > x) ist allerdings nicht entscheidbar, da man immer
noch frei beim Belegen der Variable 'y' ist und die Aussageform "wahr"
machen kann, indem man für 'y' eine Zahl größer Null einsetzt oder man
macht sie "falsch", indem man für 'y' eine Zahl kleiner gleich Null einsetzt.

3
 Vorlesungsbegleitung: Grundlagen der theoretischen Informatik
Kapitel 2

Nun gibt es aber auch Aussageformen, die immer entscheidbar sind.

So zum Beispiel:
(
∀x : x + y 2 ≥ x) x, y ∈ Ν
Diese Aussageform ist noch keine Aussage, obwohl sie jedoch immer
denselben Wahrheitswert hat.
Sie ist lediglich eine Tautologie!

Rechenregeln für Quantoren

¬∀x : F ( x) ⇔ ∃x : ¬F ( x)
Am einfachsten kann man sich dieses Beispiel veranschaulichen, indem man
es in einem Satz formuliert.
F sei hier ein Prädikat mit der Bedeutung "x ist eine Frau" und 'x' sei eine
beliebige Person.
Dann heisst die obige Aussage in Umgangssprache:
"Nicht für jede Person gilt, dass sie eine Frau ist. [das ist dasselbe wie]
Es gibt eine Person, die keine Frau ist."

¬∃x : F ( x) ⇔ ∀x : ¬F ( x)
Dieses Beispiel als Satz formuliert würde lauten:
"Es gibt keine Person, die eine Frau ist. [das ist dasselbe wie]
Alle Personen sind keine Frauen."

Operator-Prioritäten

Die Quantoren besitzen dieselbe Bindungsstärke, wie die Negation.

Das heißt, dass in der folgenden Formel ∃xF ( x) ∧ G ( x) nicht alle x
gebunden sind. Der Existenzquantor bezieht sich hier nur auf das F ( x) .

Mehrere Quantoren hintereinander

Wird mehr als ein Quantor hintereinander verwendet, wie z.b. in der
folgenden Formel ∀y∃x : F ( x, y ) , ist es bei unterschiedlichen Quantoren, wie
in dem genannten Beispiel wichtig, in welcher Reihenfolge die Quantoren in
dem Ausdruck stehen.

Sei F ( x, y ) hier ein Prädikat "x liebt y", dann bedeutet das Beispiel
∀x∃y : F ( x, y ) in Umgangssprache:
"Für alle 'x' gibt es ein 'y', welches 'x' liebt.". Dabei muss das 'y' nicht
unbedingt immer dasselbe sein.

4
 Vorlesungsbegleitung: Grundlagen der theoretischen Informatik
Kapitel 2
Drehen wir die Reihenfolge der Quantoren um, so dass der Ausdruck
∃y∀xF ( x, y ) ensteht, bedeutet dies:
"Es existiert ein 'y', so dass für alle 'x' gilt, dass alle 'x' dieses eine 'y' lieben."
Das heißt also, dass ein und dasselbe 'y' von allen 'x' geliebt wird.
Man muss also, wie bei allen aussagenlogischen Formeln, immer von links
nach rechts lesen.

Allgemeine Regeln

Bei mehreren gleichartigen hintereinander geschalteten Quantoren ist es

egal, in welcher Reihenfolge sie notiert werden.
Das heißt, die beiden folgenden Formeln sind äquivalent zueinander:
∃x∃y : F ( x, y ) ⇔ ∃y∃x : F ( x, y )

Das gleiche gilt auch für den Allquantor:

∀x∀y : F ( x, y ) ⇔ ∀y∀x : F ( x, y )

Ausgehend von einer Formel mit unterschiedlichen hintereinander

geschalteten Quantoren kann man allerdings gewisse Folgerungen ableiten:

∃x∀y : F ( x, y ) ⇒ ∀y∃x : F ( x, y )

Dieses Beispiel verdeutlicht den Fall, dass, wenn es ein 'x' gibt, so dass für
dieses eine 'x' und alle 'y' die folgende Formel erfüllt ist, dann kann man
daraus schließen, dass es auch für alle 'y' immer ein 'x' gibt, für das dieselbe
Formel erfüllt ist.
Diesen etwas komplizierten Sachverhalt kann man sich auch anschaulich
darstellen:

y
x

(Die Menge von 'y' bestehe hier nur einmal aus 5 Elementen.)

Dieses Schaubild verdeutlicht die linke Seite der Implikation und sagt aus,
dass es ein Element 'x' gibt, welches mit allen Elementen in 'y' in einer
Beziehung steht, so dass F erfüllt ist.

5
 Vorlesungsbegleitung: Grundlagen der theoretischen Informatik
Kapitel 2
Die rechte Seite kann ebenfalls graphisch veranschaulicht werden:

y
x

(Die Menge von 'y' bestehe hier wieder aus denselben 5 Elementen.)

Hier wird lediglich dargestellt, dass es für alle Elemente aus 'y' immer ein 'x'
geben muss, für das F erfüllt ist.
Dieses 'x' muss allerdings nicht immer dasselbe 'x' sein.

Aus dieser Darstellung kann man sich leicht überlegen, dass, wenn die linke
Seite der oben genannten Implikation ∃x∀y : F ( x, y ) gilt, also es zu jedem 'y'
immer ein und dasselbe 'x' gibt, dass dann die rechte Seite ∀y∃x : F ( x, y ) ,
also die Existenz eines 'x' für jedes 'y', daraus gefolgert werden kann.
Die umgekehrte Richtung gilt natürlich nicht.
Denn es kann nicht angenommen werden, dass, wenn es für jedes 'y' ein 'x'
gibt, dass dies immer dasselbe 'x' sein muss.

∀xF ( x) ∨ ∀xG ( x) ⇒ ∀x : ( F ( x) ∨ G ( x))

Diese beiden Formeln sind ebenfalls nicht äquivalent. Das kann man sich
einfach in einem "umgangssprachlichen" Satz überlegen:
"Es soll für alle 'x' F gelten, oder es soll für alle 'x' G gelten (oder beides).
Daraus kann man folgern, dass für jedes einzelne 'x' immer F oder G gelten
muss."
Ein etwas anschaulicheres Beispiel wäre z.b., wenn wir definieren würden:

F ( x) - x ist eine Frau

G ( x) - x ist Schüler
x ∈ M , wobei M die Menge aller Menschen sein

Aus der Tatsache, dass alle Menschen Frauen sind oder alle Menschen sind
Schüler (oder beides) kann man durchaus folgern, dass für jeden Menschen
gilt, dass er/sie eine Frau ist oder ein Schüler (oder beides).
Die umgekehrte Richtung gilt allerdings nicht.
Aus der Tatsache, dass jeder einzelne Mensch eine Frau oder ein Schüler ist
(oder beides) kann nicht darauf geschlossen werden, dass alle Menschen
Frauen oder alle Menschen Schüler sind.

6
 Vorlesungsbegleitung: Grundlagen der theoretischen Informatik
Kapitel 2
∀x : ( F ( x) ∧ G ( x)) ⇔ ∀xF ( x) ∧ ∀xG ( x)

Dieses "Gesetz" kann man sich einfach damit merken, dass der Allquantor
sozusagen distributiv über der Konjunktion ist.
Also man kann "ausmultiplizieren", wie beim Distributivgesetz bei
aussagenlogischen Formeln.

Dasselbe gilt auch für den Existenzquantor und die Disjunktion:

∃x : ( F ( x) ∨ G ( x)) ⇔ ∃xF ( x) ∧ ∃xG ( x)

∃xF ( x) ∧ ∃xG ( x) ⇐ ∃x : ( F ( x) ∧ G ( x))

Diese Regel wollen wir mal wieder durch eine Graphik darstellen:

F und G werden von

unterschiedlichen 'x'
x erfüllt.

F erfüllt G erfüllt
Es gibt also aus der Menge ein 'x' für das F erfüllt ist. Genauso gibt es aus der
Menge ein 'x' für das G erfüllt ist.
Hieraus können wir allerdings nicht folgern, dass dies dasselbe 'x' sein muss,
wie in der rechten Seite ∃x : ( F ( x) ∧ G ( x)) der Implikation ausgedrückt.

Wir können lediglich den umgekehrten Weg folgern:

F und G werden von

demselben 'x' erfüllt.
x

F erfüllt G erfüllt
Im Falle, dass es ein und dasselbe 'x' gibt, für das F und G erfüllt sind,
können wir schließen, dass es ein 'x' gibt, was F erfüllt und eins, welches G
erfüllt.

7
 Vorlesungsbegleitung: Grundlagen der theoretischen Informatik
Kapitel 2

Lange/kurze Schreibweise

"Was bedeuten eingeschränkte Definitionsbereiche für Quantoren ?"

Häufig kommt es vor, dass man prädikatenlogische Ausdrücke mit

Quantoren verwendet dessen gebundene Variablen schon in ihrem
Definitionsbereich eingeschränkt werden sollen.

Z.b. im folgenden Satz:

"Alle Arbeitnehmer arbeiten für mindestens einen Arbeitgeber."

Wir definieren die Mengen:

N : Die Menge aller Arbeitnehmer
G : Die Menge aller Arbeitgeber

Und ein Prädikat:

arbeitetFür ( x, y ) : "x arbeitet für y"

Dann würde unser Satz als prädikatenlogischer Ausdruck (in Kurzform) so

aussehen:
∀x ∈ N : ∃y ∈ G : arbeitetFür ( x, y )

Dieser Ausdruck ist in "Kurzform". Das heißt, die verwendeten Variablen sind
bereits bei ihrer Nennung hinter dem Quantor in ihrem Definitionsbereich
eingeschränkt.
Damit ist es nicht mehr möglich, diesen Ausdruck auf andere Personen, als
Arbeitnehmer oder Arbeitgeber, anzuwenden. Das bedeutet, wir könnten
auch nicht bestimmen, welchen Wahrheitswert der Ausdruck nun für ein x
hat, welches nicht aus der Menge der Arbeitnehmer stammt.
Besser wäre es, wenn wir diese Einschränkung als Bestandteil des Ausdrucks
selbst verlagern würden.

Das bedeutet, wir schränken ersteinmal nicht den Definitionsbereich von x

und y ein, sondern prüfen später im Ausdruck, ob x ∈ N und y ∈ G
tatsächlich erfüllt ist.
Das hat den Vorteil, dass wir nun alle möglichen x und y einsetzen können,
für die es gerade zu prüfen gilt, ob x aus der Menge der Arbeitnehmer und y
aus der Menge der Arbeitnehmer stammt. Falls diese beiden Bedingungen
erfüllt sind und zusätzlich noch x für y arbeitet, dann soll der Ausdruck
"wahr" werden.

8
 Vorlesungsbegleitung: Grundlagen der theoretischen Informatik
Kapitel 2
Auf der anderen Seite müssen wir festlegen, was denn gelten soll, wenn x
nicht aus der Menge der Arbeitnehmer stammt.
Da wir hier nur eine Aussage über alle Arbeitnehmer treffen wollen, für die es
mindestens einen Arbeitgeber gibt, soll die Aussage für ein x welches nicht
aus N ist, "wahr" sein.

Um sich das klar zu machen, benutzen wir zuerst einmal einen einfacheren
Ausdruck:

"Alle Frauen sind Menschen".

Wir definieren wieder die Mengen:

F : Die Menge aller Frauen

Und ein Prädikat:

istMensch(x) : "x ist ein Mensch"

In Kurzform würde dieser Ausdruck wie folgt aussehen:

∀x ∈ F : istMensch( x)

Es soll also für jede Frau gelten, dass 'sie' gleichzeitig ein Mensch ist.
Was ist jetzt jedoch, wenn wir ein x einsetzen, welches keine Frau ist.
Wir hatten oben definiert, dass dann der Ausdruck ebenfalls wahr sein soll,
denn wir können nichts verneinen, was wir nicht explizit aussagen wollen.

In "Langschreibweise" würde unser Ausdruck also so aussehen:

∀x : x ∈ F → istMensch( x)

Diese Implikation ist offensichtlich für alle x erfüllt, die wirklich Frauen sind
und gleichzeitig Menschen.
Da wir wissen, dass eine Implikation auch immer dann erfüllt ist, wenn die
linke Seite "falsch" ist, also in unserem Beispiel, wenn x keine Frau ist, haben
wir auch die oben genannte Bedingung erfüllt.

Kommen wir nun zurück zu unserem ersten Beispiel

∀x ∈ N : ∃y ∈ G : arbeitetFür ( x, y ) , dann würden wir nun schreiben:
∀x : x ∈ N → ∃y ∈ G : arbeitetFür ( x, y )

Was jetzt noch stört ist der eingeschränkte Definitionsbereich vom y .

Beim Existenzquantor soll für mindestens ein y gelten, dass es aus der
Menge der Arbeitgeber stammt und gleichzeitig x für y arbeitet.
Wir schreiben nun den Ausdruck vollständig mit:
∀x : x ∈ N → ∃y : y ∈ G ∧ arbeitetFür ( x, y )