# Distributive Property of Quantifiers

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))$$

• What do you mean with "simplified to" : logical equivalence ? – Mauro ALLEGRANZA Nov 10 '15 at 7:47

here are some basic distributive properties in quantifiers, hope it might help someone.

∀x(P(x) ∧ Q(x)) ≡ (∀xP(x) ∧ ∀xQ(x))

∃x(P(x) ∧ Q(x)) → (∃xP(x) ∧ ∃xQ(x))

∀x(P(x) ∨ Q(x)) ← (∀xP(x) ∨ ∀xQ(x))

∃x(P(x) ∨ Q(x)) ≡ (∃xP(x) ∨ ∃xQ(x))

∀x(P(x) → Q(x)) ← (∃xP(x) → ∀xQ(x))

∃x(P(x) → Q(x)) ≡ (∀xP(x) → ∃xQ(x))

∀x¬P(x) ≡ ¬∃xP(x)

∃x¬P(x) ≡ ¬∀xP(x)

∀x∃yT(x,y) ← ∃y∀xT(x,y)

∀x∀yT(x,y) ≡ ∀y∀xT(x,y)

∃x∃yT(x,y) ≡ ∃y∃xT(x,y)

∀x(P(x) ∨ R) ≡ (∀xP(x) ∨ R)

∃x(P(x) ∧ R) ≡ (∃xP(x) ∧ R)

∀x(P(x) → R) ≡ (∃xP(x) → R)

∃x(P(x) → R) → (∀xP(x) → R)

∀x(R → Q(x)) ≡ (R → ∀xQ(x))

∃x(R → Q(x)) → (R → ∃xQ(x))

∀xR ← R

∃xR → R

The following formulas are not valid.

   A                B           counterexample


∃x(P(x) ∧ Q(x)) ← (∃xP(x) ∧ ∃xQ(x)) D = {a, b}, M = {P(a), Q(b)}

∀x(P(x) ∨ Q(x)) → (∀xP(x) ∨ ∀xQ(x)) D = {a, b}, M = {P(a), Q(b)}

∀x(P(x) → Q(x)) → (∃xP(x) → ∀xQ(x)) D = {a, b}, M = {P(a), Q(a)}

∀x∃yT(x,y) → ∃y∀xT(x,y) D = {a, b}, M = {T(a,b), T(b,a)}

∃x(P(x) → R) ← (∀xP(x) → R) D = Ø, M = {R}

∃x(R → Q(x)) ← (R → ∃xQ(x)) D = Ø, M = Ø

∀xR → R D = Ø, M = Ø

∃xR ← R D = Ø, M = {R}

Note: if empty domains are not allowed, then the last four implications are in fact valid.

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.

They are not equivalent, all we have is $$∀xP(x)∧∀xQ(x)\underset{\not\leftarrow}{\to}∀x(P(x)∨Q(x))$$ $$¬∀xP(x)∧¬∀xQ(x)\underset{\not\leftarrow}{\to}¬∀x(P(x)∧Q(x))$$ $$¬∃x(P(x)∨Q(x))\underset{\not\leftarrow}{\to}¬∃xP(x)∨¬∃xQ(x)$$

Additionally, if you had a hard time to deal with those quantifiers, here is my method

Since $$\exists,\forall~(2\text{ choices})$$ either distribute in or distribute out$$~(2\text{ choices})$$ over $$\land,\lor,\to~(3\text{ choices})$$, therefore there should be about $$2\cdot2\cdot3=12$$ implications in total. What i did is divide $$12$$ implications into $$3$$ collections, that each of them contains $$3,3$$ and $$6$$ implications, such that choose one implication from any collection, then we can easily derive other implications in that collection. For example as following:

$$1.$$ First we start from $$\exists$$ distribute in over $$\land$$ $$\exists x(Px\land Qx)\underset{\not\leftarrow}{\to}\exists xPx\land\exists xQx\tag*{\exists distribute in over \land}$$ Consider the contrapositive, it's clear that $$\forall xPx\lor\forall xQx\underset{\not\leftarrow}{\to}\forall x(Px\lor Qx)\tag*{\forall distribute out over \lor}$$ That is $$\exists xPx\to\forall xQx\underset{\not\leftarrow}{\to}\forall x(Px\to Qx)\tag*{\forall distribute out over \to}$$ $$2.$$ In part one, we had see that in some sense $$\exists$$ can only distribute in over $$\land$$ but not distribute out. however we know that $$\exists xPx\land\forall xQx\underset{\not\leftarrow}{\to}\exists x(Px\land Qx)\tag*{\exists distribute out over \land}$$ Consider the contrapositive then we get $$\forall x(Px\lor Qx)\underset{\not\leftarrow}{\to}\forall xPx\lor\exists xQx\tag*{\forall distribute in over \lor}$$ That is $$\forall x(Px\to Qx)\underset{\not\leftarrow}{\to}\forall xPx\to\forall xQx\tag*{\forall distribute in over \to}$$ $$3.$$ Then consider $$\forall$$ distribute over $$\land$$ that $$\forall x(Px\land Qx)\leftrightarrow\forall xPx\land\forall xQx\tag*{\forall distribute over \land}$$ Then clearly $$\exists x(Px\lor Qx)\leftrightarrow\exists xPx\lor\exists xQx\tag*{\exists distribute over \lor}$$ and $$\exists x(Px\to Qx)\leftrightarrow\forall xPx\to\exists xQx\tag*{\exists distribute over \to}$$ Here in the same order, if $$x$$ not appear in $$Q$$, these hold for both directions:

$$i.$$ $$\exists x(Px\land Q)\leftrightarrow\exists xPx\land Q\tag*{\exists distribute over \land}$$ $$\forall x(Px\lor Q)\leftrightarrow\forall xPx\lor Q\tag*{\forall distribute over \lor}$$ $$\forall x(Px\to Q)\leftrightarrow\exists xPx\to Q\tag*{\forall distribute over \to}$$ $$\forall x(Q\to Px)\leftrightarrow Q\to\forall xPx$$ $$ii.$$

Same as $$i$$.

$$iii.$$ $$\forall x(Px\land Q)\leftrightarrow\forall xPx\land Q\tag*{\forall distribute over \land}$$ $$\exists x(Px\lor Q)\leftrightarrow\exists xPx\lor Q\tag*{\exists distribute over \lor}$$ $$\exists x(Px\to Q)\leftrightarrow\forall xPx\to Q\tag*{\exists distribute over \to}$$ $$\exists x(Q\to Px)\leftrightarrow Q\to\exists xPx$$

• Also note $A\underset{\not\leftarrow}{\to} B$ doesn't means $(A\to B)\land\neg(B\to A)$, here i just want to say that the implication only work for one direction, but the other direction not necessarily always true or false. – Manx Apr 23 '20 at 3:15