$\forall x (P(x) \wedge \neg Q(x)) \equiv \forall x P(x) \wedge \neg \exists x Q(x)$

Question

I'm supposed to determine whether or not these equivalences are valid for all predicates P and Q. I've written my assumptions but I've never done anything like this so it almost seems too simple and I feel as though my logic is incorrect:

a) $$ \forall x (P(x) \wedge \neg Q(x)) \equiv \forall xP(x) \wedge \neg \exists xQ(x)$$

This is how I interpreted it: For all x, P(x) is true and Q(x) is false. For all x, P(x) is true and there does not exist an x such that Q(x) is true (thus meaning Q(x) must always be false).

These equivalences appear to be valid.

b) $$\forall x (\neg P(x) \vee Q(x)) \equiv (\neg \exists xP(x)) \vee (\forall x Q(x))$$

This is how I interpreted this one: For all x, P(x) is false or Q(x) is true. There does not exist an x such that P(x) is true (thus P(x) must always be false) or for all x, Q(x) is true.

These equivalences appear to be valid.

Any help is appreciated :)

Answer 1

The second one is not valid.

Consider the interpretation with domain $\mathbb N$ and interpret both $P(x)$ and $Q(x)$ as "$x$ is Odd".

The LHS amounts to : $∀n \ (¬ \text {Odd}(n) ∨ \text {Odd}(n))$, which is true in $\mathbb N$, while the RHS will be :$¬∃n \ \text {Odd}(n) ∨ ∀n \ \text {Odd}(n)$, which is false.

In a nutshell, $\forall$ "distribute" over $∧$ but not over $∨$, and this is due to the fact that $\forall$ is like a "big and".

Answer 2

First of all remember this that:

• For all $\forall$ is distributive over $\land$ but not over $\lor$.
• There Exist $\exists$ is distributive over $\lor$ but not over $\land$.

Proof:

1. Proof of For all $\forall$ is distributive over $\land$ but not over $\lor$.
   Case-I:
   $\forall x\ (P(x)\ \land Q(x)) \equiv ((\forall x \ P(x) \land (\forall x\ Q(x)))$
   Let's say $Domain:(x_1,x_2)$
   $LHS: (P(x_1) \land Q(x_1)) \land (P(x_2) \land Q(x_2)) \; \ldots (i)$
   $RHS: (P(x_1) \land P(x_2)) \land (Q(x_1) \land Q(x_2)) \; \ldots (ii)$
   After re-arranging the terms of $(ii)$ equation, you can deduce that $(i) \equiv (ii).\\$
   Case-II:
   $\forall x\ (P(x)\ \lor Q(x)) \not\equiv ((\forall x \ P(x) \lor (\forall x\ Q(x)))$
   Let's say $Domain:(x_1,x_2)$
   $LHS: (P(x_1) \lor Q(x_1)) \land (P(x_2) \lor Q(x_2)) \\ ((P(x_1)\land P(x_2)) \lor (P(x_1) \land Q(x_2)) \lor (Q(x_1) \land P(x_2)) \lor (Q(x_1) \land Q(x_2)))\; \ldots (i) \\$
   $RHS: (P(x_1) \lor P(x_2)) \land (Q(x_1) \lor Q(x_2)) \\ ((P(x_1)\land Q(x_1)) \lor (P(x_1) \land Q(x_2)) \lor (Q(x_1) \land P(x_2)) \lor (P(x_2) \land Q(x_2)))\; \ldots (ii)\\$
   After re-arranging you can deduce that $(i) \not\equiv (ii)$
   From the above proof, you can see that, $\forall$ is distributive over $\land$ but not over $\lor$.
2. Proof of There Exist $\exists$ is distributive over $\lor$ but not over $\land$.
   Case-I:
   $\exists x\ (P(x)\ \land Q(x)) \not\equiv ((\exists x \ P(x) \land (\exists x\ Q(x)))$
   Let's say $Domain:(x_1,x_2)$
   $LHS: (P(x_1) \land Q(x_1)) \lor (P(x_2) \land Q(x_2)) \; \ldots (i) $
   $RHS: (P(x_1) \lor P(x_2)) \land (Q(x_1) \lor Q(x_2)) \; \ldots (ii)$
   $(i)$ is in DNF and $(ii)$ is in CNF. You can convert $(i)$ into CNF using De-Morgan's Law but it will not be equivalent to $(ii)$. Therefore, $(i) \not\equiv (ii)\\$
   Case-II:
   $\exists x\ (P(x)\ \lor Q(x)) \equiv ((\exists x \ P(x) \lor (\exists x\ Q(x)))$
   Let's say $Domain:(x_1,x_2)$
   $LHS: (P(x_1) \lor Q(x_1)) \lor (P(x_2) \lor Q(x_2)) \; \ldots (i)$
   $RHS: (P(x_1) \lor P(x_2)) \lor (Q(x_1) \lor Q(x_2)) \; \ldots (ii)$
   After re-arranging you can deduce that $(i) \equiv (ii)$

Let's come to Problem Statement to check whether the given FOL are valid or not.
$(i)\ \forall x(P(x)\land¬Q(x))≡∀xP(x)∧¬∃xQ(x) $
The statement is valid because RHS can be derived from LHS using.
$\forall x(P(x)\land¬Q(x)) \equiv (\forall xP(x) \land \forall x¬Q(x)) \equiv ∀xP(x)∧¬∃xQ(x) \; \text{(From De-Morgan's Law of Quantifiers)}$

$(ii)\ ∀x(¬P(x)∨Q(x))≡(¬∃xP(x))∨(∀xQ(x))$ Is not valid as mentioned by @Mauro ALLEGRANZA