Negation von Quantoren in der Prädikatenlogik (NNF). ¬(∀x(P(x)⇒Q(x))∧∃y∀xR(x,y))

Question

¬(∀x(P(x)⇒Q(x))∧∃y∀xR(x,y)) umformen zu
∃x(¬P(x)∧Q(x))∨∀y∃x¬R(x,y)

 

Meine Formel lautet:

--(Ax(P(x)->Q(x)) u EyAxR(x,y))


-- entspricht der Negation

A entspricht  dem Allquantor

E entspricht dem Existenzquantor und

u entspricht dem UND

Ich verstehe die Anwendung der Äquivalenzregeln mit Quantoren nicht richtig.  Klar ist:

--ExP(x,y) wird zu Ax--P(x,y)

Der Quantor wir also gewechselt und die Negation nach innen geschoben. Wie funktioniert das aber bei einem komplexeren Ausdruck wie dem obigen? Ich habe die äquivalente NNF und einige Äquivalenzregeln zwar vorliegen, verstehe die Zwischenschritte aber nicht. Wie ist die Negation bei einem solch langen Ausdruck nach innen zu verschieben?

Answer 1

Ich verwende folgende Zeichen:

\(\forall\) : Allquantor
\(\exists\) : Existenzquantor
\(\neg\) : logische Negation (NICHT)
\(\wedge\) : logisches UND
\(\wedge\) : logisches ODER

Dein Ausdruck sieht dann so aus:$$\neg (\forall x(P(x)\Rightarrow Q(x))\wedge \exists y\forall xR(x,y))$$Dieser Ausdruck hat die Form\(\neg (A\wedge B)\) die äquivalent zu \(\neg A \vee \neg B\) ist, sodass also dein Ausdruck äquivalent ist zu:$$\neg \forall x(P(x)\Rightarrow Q(x))\vee \neg \exists y\forall xR(x,y)$$Nun werden die Quantoren hinter den NICHT-Zeichen umgekehrt. Das NICHT "rutscht" dadurch weiter nach rechts. Der Ausdruck wird also zu: $$\exists x\neg (P(x)\Rightarrow Q(x))\vee \forall y\neg \forall xR(x,y)$$Der erste Teilausdruck enthält eine Aussage der Form \(\neg (A\Rightarrow B)\) . Das ist äquivalent zu  \(\neg A\wedge B\). Im zweiten Teilausdruck wird der Allquantor hinter dem NICHT-Zeichen umgekehrt und das NICHT rutscht weiter nach rechts. Insgesamt ergibt sich damit:$$\exists x(\neg P(x)\wedge Q(x))\vee \forall y\exists x\neg R(x,y)$$und damit ist man fertig.

Ich bevorzuge bei solchen Umformungen allerdings die Darstellung der Negation durch einen oberhalb des zu negierenden Ausdrucks angebrachten Querstrich. Dieser zeigt sehr übersichtlich die zu negierenden Teile des Ausdrucks an, übernimmt also auch eine Klammerungsfunktion.
In einer solchen Darstellung sehen dein Ausdruck und seine Umformungen so aus:

$$\overline { \forall x(P(x)\Rightarrow Q(x))\wedge \exists y\forall xR(x,y) }$$$$\overline { \forall x(P(x)\Rightarrow Q(x)) } \vee \overline { \exists y\forall xR(x,y) }$$$$\exists x\overline { (P(x)\Rightarrow Q(x)) } \vee \forall y\overline { \forall xR(x,y) }$$$$\exists x(\overline { P(x) } \wedge Q(x))\vee \forall y\exists x\overline { R(x,y) }$$

Comments

 Du hast mir sehr geholfen! Ich stimme Dir soweit überein. Aber ist ¬(A⇒B) nicht äquivalent zu A∧¬B ? Somit müste im ersten Teilausdruck Q(x) negiert sein und nicht P(x) ?

---

Du hast vollkommen recht, da habe ich mich vertan.

Richtig ist:$$\neg (A\Rightarrow B)\Leftrightarrow A\wedge \neg B$$bzw.$$\overline { A\Rightarrow B } \Leftrightarrow A\wedge \overline { B }$$sodass es also am Ende der Umformungen heißen muss:$$\exists x(P(x)\wedge \neg Q(x))\vee \forall y\exists x\neg R(x,y)$$bzw.$$\exists x(P(x)\wedge \overline { Q(x) } )\vee \forall y\exists x\overline { R(x,y) }$$