Verschoben! Pränexe Normalform und Skolemform

15.09.2012, 16:18	Em	Auf diesen Beitrag antworten »
Pränexe Normalform und Skolemform Hallo Gemeinde, ich habe folgende Aufgabenstellung: a) Geben Sie zum Ausdruck A1 jeweils einen Ausdruck in Skolemform an. b) Geben Sie zum Ausdruck A1 jeweils einen Ausdruck in bereinigter Skolemform an. Soweit meine ich auch damit klarzukommen (Ergebnisse folgen). Zu meinen Ergebnissen: Sind die richtig? Und zum anderen: Die Reihenfolge der Quantoren spielt eine Rolle. Sowohl rein von der Bedeutung des Ausdrucks her als auch bei der Bildung der Skolemform. Leider sind in der mir vorhandenen Literatur ausschließlich Beispiele angegeben, bei denen die Quantoren gleicher Art und somit kommutativ sind. In welcher Reihenfolge werden die Quantoren denn nun richtig aufgeschrieben? In meinem Lösungsweg habe ich mich danach gerichtet, wann ein Quantor zum ersten mal greift und ihn entsprechend in dieser Reihenfolge notiert. $\begin{eqnarray} <br /> A_1 = ((\forall x \exists y p(x, g(y, f(x))) \wedge \neg q(x)) \vee \neg \forall x r(x,y))<br /> \end{eqnarray}$ Die Pränexe Normalform: $\begin{eqnarray} <br /> A_1 \equiv((\forall x' \exists y' p(x', g(y', f(x'))) \wedge \neg q(x)\vee \neg \forall x'' r(x'',y))<br /> <br /> A_1 \equiv((\forall x' \exists y' p(x', g(y', f(x'))) \wedge \neg q(x)) \vee \exists x'' \neg r(x'',y))<br /> <br /> A_1 \equiv(\forall x' \exists y' \exists x''((p(x', g(y', f(x'))) \wedge \neg q(x')) \vee \neg r(x'',y))) = A_1p<br /> \end{eqnarray}$ Der Übersicht halber nenne ich die gewonnene Normalform $\begin{eqnarray} A_1p \end{eqnarray}$ . Die Skolemform $\begin{eqnarray} <br /> sk(A_1p, h) = (\forall x' \exists x''((p(x', g(h(x'), f(x'))) \wedge \neg q(x)) \vee \neg r(x'',y))) <br /> <br /> sk(sk(A_1p, h), m) = (\forall x' ((p(x', g(h(x'), f(x'))) \wedge \neg q(x)) \vee \neg r(m(x'),y))) = A_1sk<br /> \end{eqnarray}$ Die bereinigte Skolemform: $\begin{eqnarray} <br /> sk(A_1sk, n) = (\forall x' ((p(x', g(h(x'), f(x'))) \wedge \neg q(n(x'))) \vee \neg r(m(x'),y))) <br /> <br /> sk(sk(A_1sk, n),o) = (\forall x' ((p(x', g(h(x'), f(x'))) \wedge \neg q(n(x'))) \vee \neg r(m(x'), o(x')))) <br /> \end{eqnarray}$ Vielen Dank für eure Anregungen!
15.09.2012, 16:53	Em	Auf diesen Beitrag antworten »
RE: Pränexe Normalform und Skolemform Die vorliegende Lösung ist offensichtlich falsch. Ich schrieb, dass die Quantoren in der Reihenfolge notiert werden, in der sie greifen. Es liegt ein Ausdruck der Form $\begin{eqnarray} A_1 = ((Q_1 B \wedge \neg Q_2 C) \vee Q_3 D) \end{eqnarray}$ vor, wobei $\begin{eqnarray} Q_n \end{eqnarray}$ für einen oder mehrere Quantoren des nachfolgenden Ausdrucks stehen. Das Ergebnis müsste also in der Form $\begin{eqnarray} (Q_3 Q_1 Q_2 ((B \wedge \neg C) \vee D)) \end{eqnarray}$ vorliegen (ggf. ändern sich Negationssymbole durch äquivalentes Umformen. Aber grob sollte der entstehende Ausdruck so aussehen. Der Grund für die Reihenfolge erschließt sich aus der Reihenfolge, in der man auf die Ausdrücke zugreifen kann. Geht man nämlich noch etwas abstrakter an den vorliegenden Ausdruck heran, sieht man, dass dieser in der Form $\begin{eqnarray} (A \vee B) \end{eqnarray}$ gegeben ist, wobei vor B ein oder mehrere Quantoren stehen und A selbst keine Quantoren vorangestellt sind. Die anderen Quantoren treten nämlich erst in A (d.h. in der Klammer) auf und können folglich nicht vor dem Quantor von B stehen. Ich lade gleich eine korrigierte Fassung meiner Lösungen hoch.
15.09.2012, 17:24	Em	Auf diesen Beitrag antworten »
Ich kann meinen Beitrag leider auch nach Ablauf der 15 Minutenfrist immer noch nicht korrigieren. Darum jetzt ein Tripple-Post... Bei der Korrektur fiel mir auf, dass ich versehentlich $\begin{eqnarray} \neg q(x') \end{eqnarray}$ notiert habe. Es müsste aber $\begin{eqnarray} \neg q(x) \end{eqnarray}$ heißen... Eventuell hätte das jemanden verwirrt, der den Post über eine Suchmaschine findet. Korrigierte Fassung: $\begin{eqnarray} <br /> A_1 = ((\forall x \exists y p(x, g(y, f(x))) \wedge \neg q(x)) \vee \neg \forall x r(x,y))<br /> \end{eqnarray}$ $\begin{eqnarray} <br /> A_1 \equiv((\forall x' \exists y' p(x', g(y', f(x'))) \wedge \neg q(x)\vee \neg \forall x'' r(x'',y))<br /> <br /> A_1 \equiv((\forall x' \exists y' p(x', g(y', f(x'))) \wedge \neg q(x)) \vee \exists x'' \neg r(x'',y))<br /> <br /> A_1 \equiv(\ \exists x'' \forall x' \exists y'((p(x', g(y', f(x'))) \wedge \neg q(x)) \vee \neg r(x'',y))) = A_1p<br /> \end{eqnarray}$ Skolemform $\begin{eqnarray} <br /> sk(A_1p, a) = (\forall x' \exists y'((p(x', g(y', f(x'))) \wedge \neg q(x)) \vee \neg r(a,y))) <br /> <br /> sk(A_1p, h) = (\forall x' ((p(x', g(h(x'), f(x'))) \wedge \neg q(x)) \vee \neg r(a,y))) = A_1sk<br /> \end{eqnarray}$ Bereinigte Skolemform $\begin{eqnarray} <br /> sk(A_1sk, m) = (\forall x '((p(x', g(h(x'), f(x'))) \wedge \neg q(m(x')) \vee \neg r(a,y))) <br /> <br /> sk(sk(A_1sk, m),n) =(\forall x '((p(x', g(h(x'), f(x'))) \wedge \neg q(m(x')) \vee \neg r(a,n(x')))) <br /> \end{eqnarray}$

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »