First order Language Universal Quantifier Distribution

140 Views Asked by At

I've got a quick question about Universal Quantifiers. Given the following:

$$ \forall x (p(x) \vee q(x)) $$

Can we do this: $$ \forall xp(x) \vee \forall xq(x) $$. i.e can we distribute the "for any" to the p and q?

2

There are 2 best solutions below

1
On BEST ANSWER

No. Every integer is either even or odd, but it is not true that every integer is even or that every integer is odd.

0
On

Let be $A = \forall x (p(x)\lor q(x))$ and $B = \forall x p(x) \lor \forall x q(x)$. It holds that

$$B\Rightarrow A\text{.}$$

The opposite direction may not hold, which can be seen from the answer of user1331281. However, if $q$ does not depend on $x$, then the opposite direction holds also. In that case we have $$A\Leftrightarrow B$$ and this is known as Frobenius law.