2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ What do you mean with "simplified to" : logical equivalence ? $\endgroup$ – Mauro ALLEGRANZA Nov 10 '15 at 7:47
9
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – Manx Apr 23 '20 at 3:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.