Distributive Property of Quantifiers

8.8k Views Asked by At

I know that given $$ \forall x \;\; P(x) \wedge \forall x \;\; Q(x) $$ can be simplified to $$ \forall x \;\; (P(x) \vee Q(x)) $$ but does the same apply if its $ \neg \forall x P(x) \wedge \neg \forall x \;\; Q(x) $ ? Can you simplify that to $ \neg\forall x \;\; (P(x) \wedge Q(x)) $ ?

My main question is whether the distributive property applies when all the quantifiers are negated?

Also can the same work with the existential quantifier?

does $$ \neg \exists x P(x) \vee \neg \exists x Q(x) = \neg \exists x(P(x)\vee Q(x))$$

1

There are 1 best solutions below

0
On

No, not as you have it. $$\neg \forall x\;P(x)\;\wedge\; \neg \forall x\;Q(x) \iff \neg(\forall x\;P(x)\vee\forall x\;Q(x))$$

$$\neg \forall x\;P(x)\;\wedge\; \neg \forall x\;Q(x) \iff \exists x\;\neg P(x)\wedge\exists x\;\neg Q(x))$$

However:

$$\neg \forall x\;P(x)\;\vee\; \neg \forall x\;Q(x) \iff \neg(\forall x\;P(x)\wedge\forall x\;Q(x)) \iff \neg \forall x\;(P(x)\wedge Q(x))$$

$$\neg \forall x\;P(x)\;\vee\; \neg \forall x\;Q(x) \iff \exists x\;\neg P(x)\vee\exists x\;\neg Q(x))\iff \exists x\;(\neg P(x)\vee\neg Q(x))$$

In short: remember your Dual Negation rules.