Negation von Quantoren in der Prädikatenlogik (NNF)

Wissenschaft Mathematik
#1

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 wird 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? Kann mir jemand helfen? Vielen Dank!

#2

Ja, zunächst kann man über die Regel --E-- = A und --A-- = E Negationen sozusagen von außen nach Innen bringenn. Dort kann man dann Distributionsregeln für aussagenlogische Formeln anwenden, z.B. --(AuB) = (–Av–B), wobei v für die Disjunktion steht.

#3

Die Aussage
\neg \Bigl( ( \forall x : P(x) \to Q(x) ) \wedge (\exists y \forall y : R(x,y) ) \Bigr)

ist zunächst von der Form \neg \Bigl( A \wedge B \Bigr)
mit A := \forall x : P(x) \to Q(x) und B:= \exists y \forall y : R(x,y) .

Dies ist äquivalent zu der Aussage:
\neg A \vee \neg B

Auf die einzelnen Teile kannst Du jetzt die von Dir genannten Regeln anwenden.
Für A gilt:
\neg A = \exists x : \neg( P(x) \to Q(x) )
bzw.
\neg A = \exists x : P(x) \wedge \neg Q(x)
Für B gilt:
\neg B = \forall y \neg \Bigl( \forall y : R(x,y) \Bigr)
bzw.
\neg B = \forall y \exists y : \neg R(x,y) .

Insgesamt ist die Aussage äquivalent zu:
(\exists x : P(x) \wedge \neg Q(x) ) \vee ( \forall y \exists y : \neg R(x,y))

Beste Grüße
Zwergenbrot