Prädikatenlogik

1

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.

2


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:

)4(: >∃ xx

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

3


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:

)4(: >∀ xx 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:

)(: xyxx >+∀

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 )4(: >∀ xx z.b. ist immer entscheidbar.

Sie ist immer "falsch". Das Beispiel )(: xyxx >+∀ 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.

4


Kapitel 2

Nun gibt es aber auch Aussageformen, die immer entscheidbar sind. So zum Beispiel:

( ) Ν∈≥+∀ yxxyxx ,: 2

Diese Aussageform ist noch keine Aussage, obwohl sie jedoch immer denselben Wahrheitswert hat. Sie ist lediglich eine Tautologie!

Rechenregeln für Quantoren

)(:)(: xFxxFx ¬∃⇔¬∀

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

)(:)(: xFxxFx ¬∀⇔¬∃

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 )()( xGxxF ∧∃ nicht alle x

gebunden sind. Der Existenzquantor bezieht sich hier nur auf das )(xF .

Mehrere Quantoren hintereinander

Wird mehr als ein Quantor hintereinander verwendet, wie z.b. in der folgenden Formel ),(: yxFxy∃∀ , ist es bei unterschiedlichen Quantoren, wie

in dem genannten Beispiel wichtig, in welcher Reihenfolge die Quantoren in dem Ausdruck stehen. Sei ),( yxF hier ein Prädikat "x liebt y", dann bedeutet das Beispiel

),(: yxFyx∃∀ in Umgangssprache:

"Für alle 'x' gibt es ein 'y', welches 'x' liebt.". Dabei muss das 'y' nicht unbedingt immer dasselbe sein.

5


Kapitel 2

Drehen wir die Reihenfolge der Quantoren um, so dass der Ausdruck ),( yxxFy∀∃ 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:

),(: yxFyx∃∃ ⇔ ),(: yxFxy∃∃

Das gleiche gilt auch für den Allquantor:

),(: yxFyx∀∀ ⇔ ),(: yxFxy∀∀

Ausgehend von einer Formel mit unterschiedlichen hintereinander geschalteten Quantoren kann man allerdings gewisse Folgerungen ableiten:

),(: yxFyx∀∃ ⇒ ),(: yxFxy∃∀

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:

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

x y

6


Kapitel 2

Die rechte Seite kann ebenfalls graphisch veranschaulicht werden:

(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 ),(: yxFyx∀∃ gilt, also es zu jedem 'y'

immer ein und dasselbe 'x' gibt, dass dann die rechte Seite ),(: yxFxy∃∀ ,

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.

)()( xxGxxF ∀∨∀ ⇒ ))()((: xGxFx ∨∀

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:

)(xF - x ist eine Frau

)(xG - x ist Schüler

Mx ∈ , 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.

x y

7


Kapitel 2

))()((: xGxFx ∧∀ ⇔ )()( xxGxxF ∀∧∀

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:

))()((: xGxFx ∨∃ ⇔ )()( xxGxxF ∃∧∃

)()( xxGxxF ∃∧∃ ⇐ ))()((: xGxFx ∧∃

Diese Regel wollen wir mal wieder durch eine Graphik darstellen:

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 ))()((: xGxFx ∧∃ der Implikation ausgedrückt.

Wir können lediglich den umgekehrten Weg folgern:

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.

x

F erfüllt G erfüllt

x

F erfüllt G erfüllt

F und G werden von demselben 'x' erfüllt.

F und G werden von unterschiedlichen 'x' erfüllt.

8


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:

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

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

),(:: yxrarbeitetFüGyNx ∈∃∈∀

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 Nx ∈ und Gy ∈

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.

9


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:

:)(xistMensch "x ist ein Mensch"

In Kurzform würde dieser Ausdruck wie folgt aussehen:

)(: xistMenschFx ∈∀

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:

)(: xistMenschFxx →∈∀

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

),(:: yxrarbeitetFüGyNx ∈∃∈∀ , dann würden wir nun schreiben:

),(:: yxrarbeitetFüGyNxx ∈∃→∈∀

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: ),(:: yxrarbeitetFüGyyNxx ∧∈∃→∈∀

Documents

Prädikatenlogik