Prädikatenlogik negieren

08.01.2018, 15:52

Krischon

Prädikatenlogik negieren

Meine Frage:
Moin,

ich werde mit prädikatenlogischen Formeln nicht ganz warm.
Übersetzen vom Text in Formel ist wesentlich leichter (bisher), als nur mit Formeln zu hantieren.
Es geht um folgende Formel:

$\begin{eqnarray*} \forall v_{1},...,v_{n} \in V: ( \forall i < n<img src="images2/smilies/frown2.gif" border="0" alt="unglücklich" title="unglücklich" /> v_{i},v_{i+1}) \in E) \Rightarrow ( \forall j,h \leq n : j \neq h \Rightarrow (v_{i} \neq v_{h} )) \end{eqnarray*}$

Meine Ideen:
So. $\begin{eqnarray*} \forall \end{eqnarray*}$ wird zu $\begin{eqnarray*} \exists \end{eqnarray*}$ .
Dann habe ich eine Formel der Form $\begin{eqnarray*} A\Rightarrow (B\Rightarrow C) \end{eqnarray*}$ , die ich negieren kann zu $\begin{eqnarray*} A\wedge B\wedge -C \end{eqnarray*}$ . (DeMorgan und Reformulation der Implikation)

Ich Versuche das mal zu übersetzen:

$\begin{eqnarray*} \exists v\in V: ( \forall i < n: (v_{i},v_{i+1})\in E) \wedge (\forall j,h \leq n: j\neq h) \wedge (v_{i}=v_{h}) \end{eqnarray*}$

Falls das richtig sein sollte... Wie kann ich das noch vereinfachen?

Lieben Gruß

PS: Keine Ahnung, warum er Probleme bei der ersten Formel macht... Ich hab sie mal als Foto mit angehängt.

08.01.2018, 17:23

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Krischon
Keine Ahnung, warum er Probleme bei der ersten Formel macht...

Altbekanntes Problem im Board: Der Parser durchsucht auch LaTeX-Formeln nach Smilies - und erkennt er einen wie bei dir :(, so stellt er ihn auch dar.

Ausweg: Leerzeichen einbauen, d.h. : ( .

08.01.2018, 20:39

Dopap

Auf diesen Beitrag antworten »

RE: Prädikatenlogik negieren

Zitat:

Original von Krischon
[...]
Es geht um folgende Formel:

$\begin{eqnarray*} \forall v_{1},...,v_{n} \in V: ( \forall i < n: (v_{i},v_{i+1}) \in E) \Rightarrow ( \forall j,h \leq n : j \neq h \Rightarrow (v_{i} \neq v_{h} )) \end{eqnarray*}$

Meine Ideen:
So. $\begin{eqnarray*} \forall \end{eqnarray*}$ wird zu $\begin{eqnarray*} \exists \end{eqnarray*}$ .
Dann habe ich eine Formel der Form $\begin{eqnarray*} A\Rightarrow (B\Rightarrow C) \end{eqnarray*}$ , die ich negieren kann zu $\begin{eqnarray*} A\wedge B\wedge -C \end{eqnarray*}$ . (DeMorgan und Reformulation der Implikation)

Ich Versuche das mal zu übersetzen:

$\begin{eqnarray*} \exists v\in V: ( \forall i < n: (v_{i},v_{i+1})\in E) \wedge (\forall j,h \leq n: j\neq h) \wedge (v_{i}=v_{h}) \end{eqnarray*}$

Falls das richtig sein sollte... Wie kann ich das noch vereinfachen? [...]

bei dir ist anscheinend alles eine Formel Augenzwinkern

Die erste "Formel" ist eine Aussage. $\begin{eqnarray*} A\rightarrow (B\rightarrow C) \end{eqnarray*}$ ist ein logischerTerm.

$\begin{eqnarray*} \lnot (A\rightarrow (B\rightarrow C)) \Leftrightarrow A\land B \land \lnot C \end{eqnarray*}$ ist jetzt tatsächlich eine Formel, eine Tautologie.

08.01.2018, 21:20

Krischon

Auf diesen Beitrag antworten »

RE: Prädikatenlogik negieren

Zitat:

Original von Dopap

bei dir ist anscheinend alles eine Formel Augenzwinkern

Falls unklar: Ich hab versucht die Prädikatenlogik mal in Aussagenlogik umzuwandeln, damit ich weiß, wohin ich arbeiten muss.
Es geht eigentlich um das, was oben so blöd auseinandergerissen ist und ich nicht mehr editieren kann:

$\begin{eqnarray*} \forall v_{1},...,v_{n} \in V: ( \forall i < n: (v_{i},v_{i+1}) \in E) \Rightarrow ( \forall j,h \leq n : j \neq h \Rightarrow (v_{i} \neq v_{h} )) \end{eqnarray*}$

Das möchte ich gerne negieren. Oben mein Ansatz.

08.01.2018, 22:42

Dopap

Auf diesen Beitrag antworten »

RE: Prädikatenlogik negieren
Wenn die Aussagen A B C definiert sind, dann ist

$\begin{eqnarray*} \lnot (A\rightarrow (B\rightarrow C)) \Leftrightarrow A\land B \land \lnot C \end{eqnarray*}$

eigentlich kein Problem. Aber die Aussagen A B C sind aber im ganzen Text, voll mit $\begin{eqnarray*} \forall \end{eqnarray*}$ und $\begin{eqnarray*} \exists \end{eqnarray*}$ schwer auszumachen.

Die Zuordnung der Mengen zu den Aussageformen ist mir nicht klar.

Welche Menge gehört zu A? Was ist die Struktur? unter Verwendung von $\begin{eqnarray*} \bigwedge_{Menge} \end{eqnarray*}$ und $\begin{eqnarray*} \bigvee_{Menge} \end{eqnarray*}$ könnte man das Ganze bestimmt lesbarer gestalten.

$\begin{eqnarray*} \bigwedge_{v_1\dots v_n\in V} \end{eqnarray*}$ $\begin{eqnarray*} \left( \bigwedge_{v_i,v_{i+1}\in E} \dots \Rightarrow \dots \right) \end{eqnarray*}$ verwirrt

08.01.2018, 22:47

Krischon

Auf diesen Beitrag antworten »

RE: Prädikatenlogik negieren

Zitat:

Original von Dopap
Wenn die Aussagen A B C definiert sind, dann ist

$\begin{eqnarray*} \lnot (A\rightarrow (B\rightarrow C)) \Leftrightarrow A\land B \land \lnot C \end{eqnarray*}$

eigentlich kein Problem. Aber die Aussagen A B C sind aber im ganzen Text, voll mit $\begin{eqnarray*} \forall \end{eqnarray*}$ und $\begin{eqnarray*} \exists \end{eqnarray*}$ schwer auszumachen.

Die Zuordnung der Mengen zu den Aussageformen ist mir nicht klar.

Welche Menge gehört zu A? Was ist die Struktur? unter Verwendung von $\begin{eqnarray*} \bigwedge_{Menge} \end{eqnarray*}$ und $\begin{eqnarray*} \bigvee_{Menge} \end{eqnarray*}$ könnte man das Ganze bestimmt lesbarer gestalten.

$\begin{eqnarray*} \bigwedge_{v_1\dots v_n\in V} \end{eqnarray*}$ $\begin{eqnarray*} \left( \bigwedge_{v_i,v_{i+1}\in E} \dots \Rightarrow \dots \right) \end{eqnarray*}$ verwirrt

Ich weiß ja nichtmal ob das überhaupt Sinn ergibt. Vielleicht kann man die ja auch ganz einfach direkt negieren (Die Lange Aussage). Einen Versuch habe ich unternommen, aber ob das so gelten kann...?

08.01.2018, 23:07

Dopap

Auf diesen Beitrag antworten »

RE: Prädikatenlogik negieren

Zitat:

Original von Krischon

Ich weiß ja nichtmal ob das überhaupt Sinn ergibt. Vielleicht kann man die ja auch ganz einfach direkt negieren (Die Lange Aussage). Einen Versuch habe ich unternommen, aber ob das so gelten kann...?

Meistens versteht man ja zuerst die Aussage und schreibt diese dann entsprechend auf. Geht hier aber nicht, da ich die Aussage nicht verstehe. Und eine formale direkte Negation ist mir bei der nicht einheitlichen Schreibmaschinen-Schreibweise schlecht möglich.
sorry

08.01.2018, 23:31

Krischon

Auf diesen Beitrag antworten »

RE: Prädikatenlogik negieren

Zitat:

Original von Dopap

Meistens versteht man ja zuerst die Aussage und schreibt diese dann entsprechend auf. Geht hier aber nicht, da ich die Aussage nicht verstehe. Und eine formale direkte Negation ist mir bei der nicht einheitlichen Schreibmaschinen-Schreibweise schlecht möglich.
sorry

Ich versteh sie auch nicht wirklich. :P Macht aber ja nix. Vielleicht hat aber ja sonst jemand anderes ne Idee. smile

09.01.2018, 18:15

Dopap

Auf diesen Beitrag antworten »

ich habe mich erkundigt und HAL meint

Zitat:

Ich könnte mir vorstellen, dass stattdessen

$\begin{eqnarray*} \forall v_1,\ldots,v_n \in V: \left( \forall i < n: (v_i,v_{i+1}) \in E\right) \Rightarrow \left( \forall j,h \leq n : j \neq h \Rightarrow (v_j \neq v_h)\right) \end{eqnarray*}$

gemeint ist, in Worten: Liegt ein Kantenzug von $\begin{eqnarray*} v_1 \end{eqnarray*}$ bis $\begin{eqnarray*} v_n \end{eqnarray*}$ vor, so sind alle Knoten darauf voneinander verschieden. Bin etwas wacklig bei den Begriffen der Graphentheorie, aber sowas nennt man wohl "kreisfrei".

was man auch so schreiben kann:
$\begin{eqnarray*} \bigwedge_{v_1 ,\ldots ,v_n\in V} \,\,\bigwedge_{i<n} (v_i,v_{i+1}) \in E \Rightarrow \left(\bigwedge_{j,h\leq n}j\neq h \Rightarrow v_j\neq v_h \right) \end{eqnarray*}$

09.01.2018, 23:23

Dopap

Auf diesen Beitrag antworten »

[...] Es war ja die Negation der Aussage :

$\begin{eqnarray*} \bigwedge_{v_1 ,\ldots ,v_n\in V} \,\,\bigwedge_{i<n} (v_i,v_{i+1}) \in E \Rightarrow \left(\bigwedge_{j,h\leq n}j\neq h \Rightarrow v_j\neq v_h \right) \end{eqnarray*}$

gesucht, was formal erst mal zu

$\begin{eqnarray*} \bigwedge_{v_1 ,\ldots ,v_n\in V} \,\,\bigwedge_{i<n} (v_i,v_{i+1}) \in E \, \land \, \lnot \left(\bigwedge_{j,h\leq n}j\neq h \Rightarrow v_j\neq v_h \right) \end{eqnarray*}$

und letztendlich zu

$\begin{eqnarray*} \bigwedge_{v_1 ,\ldots ,v_n\in V} \,\,\bigwedge_{i<n} (v_i,v_{i+1}) \in E \, \land \, \bigwedge_{j,h\leq n}j\neq h \,\land \, v_j = v_h \end{eqnarray*}$

führt.

10.01.2018, 07:37

Krischon

Auf diesen Beitrag antworten »

Zitat:

Original von Dopap
[...] Es war ja die Negation der Aussage :

$\begin{eqnarray*} \bigwedge_{v_1 ,\ldots ,v_n\in V} \,\,\bigwedge_{i<n} (v_i,v_{i+1}) \in E \, \land \, \bigwedge_{j,h\leq n}j\neq h \,\land \, v_j = v_h \end{eqnarray*}$

führt.

Ich bin nicht vertraut mit dem großen "und"-Zeichen.
Dann dachte ich, dass die Umformung einer Implikation zu $\begin{eqnarray*} \vee \end{eqnarray*}$ führt, dem Oder-Zeichen. So in etwa hab ich mir das dann auch rausgeschrieben (also mit dem Unterschied des und/oder).

Zitat:

Original von Dopap
Eine Frage noch: entstammt das Original einem Script über Graphentheorie oder nur als Beispiel für die Negation einer Prädikaten-Aussage?

(kopiert aus PM ; )

Mir ging es nur um Prädikaten-Aussagen, da ich Schwierigkeiten habe, die für mich verständlich zu übersetzen. Da hast du in vorherigem Post schon große Hilfe gezeigt, indem du die Logik mal in Worten formuliert hast smile

Graphentheorie ist gar nicht Thema bei uns. (das ganze kommt aus den Diskreten Strukturen).
Danke für deine Hilfe!
Lieben Gruß
Krischon

Neue Frage »

Antworten »

Prädikatenlogik negieren

Verwandte Themen