Prädikatenlogik

12.07.2012, 12:55

Jonnys

Prädikatenlogik

Hallo, ich hoffe ich bin mit meiner Frage im richtigen Bereich gelandet. Ich bin im Rahmen meiner Klausurvorbereitung auf einige Fragen gestoßen und hoffe das ihr mir vll. weiterhelfen könnt.

Mit Boolischer Algebra hatte ich bisher eigentlich keine Probleme aber Allquantor und Existenzquantor machen mir beim Umformen das Leben schwer.

Bsp.:

Aufgabe: Bilden Sie die Negation der folgenden Aussagen der Prädikatenlogik und formen Sie sie so um, dass das Negationszeichen nur unmittelbar vor den einzelnen Prädikaten steht.

$\begin{eqnarray*} \exists x\forall yp(x,y) \end{eqnarray*}$

Mir fehlt hier einfach jeglicher Ansatz und ich habe leider auch keine Beispielaufgabe mit Lösung zu diesem Thema. Wieso sind im Prädikat x und y durch ein "," getrennt. Ich hätte z.B. ein "<" bzw. irgend eine andere logische Verknüpfung erwartet ?

Mein..."Lösungsansatz" $\begin{eqnarray*} \forall x\exists yp(x,y) \end{eqnarray*}$

12.07.2012, 13:53

Mazze

Auf diesen Beitrag antworten »

Zitat:

$\begin{eqnarray*} \forall x\exists yp(x,y) \end{eqnarray*}$

Du hast die Quantoren richtig aufgelößt für die Negation. Aber wo ist das negations zeichen hin?

Zitat:

Wieso sind im Prädikat x und y durch ein "," getrennt.

Du hast hier ein zweistelliges Prädikat. Ein Prädikat ordnet Elementen einer Menge einen Wahrheitswert zu (etwas salopp formuliert). Für dein Beispiel etwa, könnte man

$\begin{eqnarray*} p(x,y) := x < y \end{eqnarray*}$

definieren.

Anderes Beispiel

$\begin{eqnarray*} p(x,y,z) := x + y + z = 10 \end{eqnarray*}$ (ist wahr wenn x,y,z in der Summe 10 ergeben , sonst falsch)

Wir haben hier halt ein allgemeines Prädikat das wir p nennen, und kein spezielles Prädikat wie etwa "<".

12.07.2012, 13:59

Kiwiatmb

Auf diesen Beitrag antworten »

Für All- und Existenzquantor und deren Negationen gibt es relativ einfache Umformungsregeln, die man sich folgendermaßen klar machen kann:

Negation des Existenzquantors:
"Es ist nicht der Fall, dass es ein x gibt, sodass p(x)." ist ja wohl äquivalent zu "Für alle x gilt, dass es kein x gibt, sodass p(x)."

Kannst du das mal in eine Formel umwandeln? (Wenn nicht, helf' ich dir smile

.)

Analog geht das Ganze dann auch für den Allquantor.

p(x,y) ist einfach ein zweistelliges Prädikat. In der natürlichen Sprache z.B. p(x,y)="... interessiert sich für..." im Gegensatz zu einem einstelligen Prädikat p(x)="... ist interessant.".
Ein zweistelliges Prädikat ordnet einfach abhängig von 2 Elementen einen Wahrheitswert zu, ein einstelliges hängt nur von 1 Element ab usw..

Edit: Boah sorry, viel zu langsam.

12.07.2012, 14:28

Jonnys

Auf diesen Beitrag antworten »

Zitat:

Wir haben hier halt ein allgemeines Prädikat das wir p nennen, und kein spezielles Prädikat wie etwa "<".

Ah, das bringt schonmal Licht ins Dunkel Augenzwinkern

Allerdings bin ich mir beim Umformen immernoch unsicher. Ich gehe mal Schritt für Schritt vor...

$\begin{eqnarray*} \exists x\forall yp(x,y) \end{eqnarray*}$ =

$\begin{eqnarray*} !\left(\exists x \forall yp(x,y)\right) \end{eqnarray*}$ =

$\begin{eqnarray*} !\exists x!\forall y!p(x,y) \end{eqnarray*}$ =

$\begin{eqnarray*} \forall x\exists y!p(x,y) \end{eqnarray*}$

Zitat:

Kannst du das mal in eine Formel umwandeln? (Wenn nicht, helf' ich dir smile .)

"Für alle x gilt, dass es kein x gibt, sodass p(x)."

In diesem Sinne... $\begin{eqnarray*} \exists x!p(x) \end{eqnarray*}$

Ist das korrekt ?

Danke schonmal an euch beide Wink

12.07.2012, 14:31

Jonnys

Auf diesen Beitrag antworten »

Zitat:

"Für alle x gilt, dass es kein x gibt, sodass p(x)."

Sry Quatsch, wenn überhaupt dann so:

$\begin{eqnarray*} \forall x!p(x) \end{eqnarray*}$

12.07.2012, 14:44

Mazze

Auf diesen Beitrag antworten »

Der Schritt

Zitat:

$\begin{eqnarray*} !\left(\exists x \forall yp(x,y)\right) \end{eqnarray*}$ = $\begin{eqnarray*} !\exists x!\forall y!p(x,y) \end{eqnarray*}$ =

ist so nicht richtig. Korrekt wäre es :

$\begin{eqnarray*} !\left(\exists x \forall yp(x,y)\right) = \forall x !\forall y p(x,y) \end{eqnarray*}$

Der Ausdruck

$\begin{eqnarray*} !\exists x!\forall y!p(x,y) \end{eqnarray*}$

ist prädikatenlogisch ein anderer. Denk mal drüber nach Augenzwinkern

12.07.2012, 14:58

Kiwiatmb

Auf diesen Beitrag antworten »

Mit

Zitat:

Kannst du das mal in eine Formel umwandeln?

meinte ich eigentlich das gesamte:

Zitat:

"Es ist nicht der Fall, dass es ein x gibt, sodass p(x)." ist ja wohl äquivalent zu "Für alle x gilt, dass es kein x gibt, sodass p(x)."

Denn das liefert dir die allgemeine Regel.
Im Prinzip hat das Mazze ja schon geschrieben und die rechte Seite hast du ja auch richtig erkannt, aber ich formalisiere jetzt zur Sicherheit nochmal explizit die Regel:

$\begin{eqnarray*} !\exists x ~\Phi \Leftrightarrow \forall x ~ !\Phi \end{eqnarray*}$
Für den negierten Allquantor geht das ganz genauso.
(Phi ist hier eine beliebige prädikatenlogische Formel, kann also auch wiederum Quantoren und alles drum und dran enthalten.)

Damit solltest du dann Schritt für Schritt alles auflösen können. smile

So, jetzt bin ich aber still und klaue Mazze nicht weiter die Antworten.

12.07.2012, 15:28

Jonnys

Auf diesen Beitrag antworten »

Ok... ich versuche das ganze nochmal in Worte zu fassen:

Zitat:

$\begin{eqnarray*} \forall x !\forall y p(x,y) \end{eqnarray*}$

Für alle x gilt (jeweils) das nicht alle y für p(x,y) gültig sind.

Zitat:

$\begin{eqnarray*} !\exists x!\forall y!p(x,y) \end{eqnarray*}$

Es gibt kein x mit dem nicht alle y für p(x,y) nicht gültig sind. (D.h. egal welches x ... p(x,y) ist immer falsch)

wenn das stimmt, hättest du natürlich recht.

*hust* mir brummt der Schädel Hammer

Die finale Lösung

Zitat:

$\begin{eqnarray*} \forall x\exists y!p(x,y) \end{eqnarray*}$

sollte aber trotzdem stimmen oder ? Würde auch hierzu passen

Zitat:

$\begin{eqnarray*} !\exists x ~\Phi \Leftrightarrow \forall x ~ !\Phi \end{eqnarray*}$

12.07.2012, 15:42

Mazze

Auf diesen Beitrag antworten »

Zitat:

Die finale Lösung Zitat: $\begin{eqnarray*} \forall x\exists y!p(x,y) \end{eqnarray*}$

Ja, das ist korrekt. Und noch als Hinweis :

$\begin{eqnarray*} !\exists x !\forall y ! p(x,y) = \forall x!! \forall y ! p(x,y) = \forall x \forall y !p(x,y) \end{eqnarray*}$

Zitat:

(D.h. egal welches x ... p(x,y) ist immer falsch)

Naja dort steht erstmal nur !p(x,y), wir wissen ja nicht ob p(x,y) nun wahr oder falsch ist, gibt es etwa ein Paar x,y mit p(x,y) = F, so wäre obige Aussage falsch.

12.07.2012, 16:53

Jonnys

Auf diesen Beitrag antworten »

Alles klar, dann möchte ich nochmal meine Lösung zu Aufgabe b) zum Besten geben, in der Hoffnung das es passt ?

"Bilden Sie die Negation der folgenden Aussagen der Prädikatenlogik und formen Sie sie so um, dass
das Negationszeichen nur unmittelbar vor den einzelnen Prädikaten steht."

Aufgabe:
$\begin{eqnarray*} \forall x!\left(\exists y\left(p\left(x,y\right)\Rightarrow p\left(y,x\right) \right) \right) \end{eqnarray*}$

Lösung:
$\begin{eqnarray*} \exists x\left(\exists y\left(p\left(x,y\right)\Rightarrow p\left(y,x\right) \right) \right) \end{eqnarray*}$

Scheint mir fast schon zu simpel...

Das Negationszeichen steht jetzt allerdings nicht "unmittelbar" vor den Prädikaten... natürlich kann man die Implikation noch auflösen, aber das würde mich auch nicht ans Ziel bringen. Hat jemand eine Idee wie das gemeint ist?

12.07.2012, 17:21

Mazze

Auf diesen Beitrag antworten »

Zitat:

Scheint mir fast schon zu simpel...

Vertraue ruhig deiner Argumentation, die ist nämlich richtig Augenzwinkern

. Wenns kein Negationzeichen gibt , stehen wohl alle vor den Prädikaten.

12.07.2012, 17:43

Jonnys

Auf diesen Beitrag antworten »