logic, Statement manipulation with Quantifiers

75 Views Asked by At

$x,y$ are rational numbers

$$\forall x((x^2 \geq 0) ∨ \neg \exists y( y^2 = -6 ))$$

If I manipulate the above statement the following way, are they equivalent?

$$\forall x\neg \exists y((x^2 ≥ 0) ∨ ( y^2 = -6 ))$$

More generally:

$$\forall x(P(x) \% \neg \exists y Q(y)) := \forall x \neg \exists y(P(x) \% Q(y)),$$

where $P,Q$ are predicates and $\%$ is some logical connective.

Since I've been taught that the range of a quantifier is the inside of the brackets it shouldn't matter. However, I'm afraid that once I use De Morgan for both cases I end up with logically different statements.

1

There are 1 best solutions below

12
On BEST ANSWER

$x,y$ are rational numbers

$$\forall x((x^2 \geq 0) ∨ \neg \exists y( y^2 = -6 ))\tag1$$

If I manipulate the above statement the following way, are they equivalent?

$$\forall x\neg \exists y((x^2 ≥ 0) ∨ ( y^2 = -6 ))\tag2$$

No, unfortunately. $(1)$ is logically equivalent to $$\forall x\;((x^2 \geq 0) ∨ \forall y( y^2 \ne -6 )),$$ which is logically equivalent to $$\forall x\forall y\;((x^2 \geq 0) ∨ ( y^2 \ne -6 )).$$

On the other hand, $(2)$ is logically equivalent to $$\forall x\forall y\;((x^2 < 0) ∧ ( y^2 \ne -6 )).$$

More generally:

$$\forall x(P(x) \% \neg \exists y Q(y)) := \forall x \neg \exists y(P(x) \% Q(y)),$$

Correction: $$\forall x(P(x) \:\%\: \neg \exists y Q(y)) \equiv \forall x \;(P(x) \:\%\: \forall y ¬Q(y)).$$

The correct way to pull $\forall y$ to the front of the sentence depends on what connective $\%$ is. Prenex normal form contains more information.