$\lnot \exists x (\forall y (\alpha)\land \forall z(\beta) )\;$ is logically equivalent to which one of these?

Question

These are the options:

1. $\forall x(\exists z(\lnot \beta)\rightarrow \forall y(\alpha))$
2. $\forall x(\forall z(\beta)\to \exists y(\lnot\alpha))$
3. $\forall x(\forall y(\alpha)\to \exists z(\lnot \beta))$
4. $\forall x(\exists y(\lnot \alpha )\to \exists z(\lnot \beta))$

How will I conclude the expression? Thanks.

Answer 1

Four things you'll want to use here (and four things you'll need to know here and moving forward):

$\lnot \exists x P(x)$ is equivalent to $\forall x \lnot P(x)$.

Likewise, $\lnot \forall x P(x)$ is equivalent to $\exists x \lnot P(x)$.

$\lnot (P \land Q)$ is equivalent to $\lnot P \lor \lnot Q$

$\lnot P \lor Q \equiv P\rightarrow Q$.

$$\begin{align} \lnot\exists x\,(\forall y(\alpha) \land \forall z (\beta) & \equiv \forall x\,\Big(\lnot[\forall y(\alpha) \land \forall z (\beta)]\Big) \\ \\ &\equiv \forall x\Big(\lnot \forall y(\alpha) \lor \lnot \forall z(\beta)\Big)\\ \\ &\equiv \forall x\Big( \forall y(\alpha) \rightarrow \lnot \forall z(\beta)\Big)\\ \\ &\equiv \quad \cdots\end{align}$$

Can you take it from here?

Answer 2

We know that: $$\sim(\forall x, P(x))\equiv \exists x, \sim P(x),~~~~\forall x, \sim P(x))\equiv \sim(\exists x, P(x))$$ and $$P(x)\to Q(x)\equiv \sim P(x)\vee Q(x)$$ so $$\sim[\exists x\left(\forall y~\alpha~\wedge~\forall z~\beta\right)]\equiv\forall x(\exists y (\sim\alpha)~\vee~\exists z(\sim\beta))$$

Answer 3

There is a relationship between the universal and existential quantifiers. The proposition $\forall x(\phi(x))$ says that for every $x$ the formula $\phi(x)$ is true. The negation of that statement would read

It is not the case that for every $x$ the formula $\phi(x)$ is true

Which you could interpret as

There is an $x$ such that it is not the case that the formula $\phi(x)$ is true.

Knowing that you can interchange the quantifiers like that (and negating their formula) can you do the rest of this problem?

Answer 4

You must use , in turn, three "rules" :

(i) interrelationship between quantifiers, i.e.

$\lnot \exists x$ is "interchangable" with $\forall x \lnot$

and

$\lnot \forall x$ is "interchangable" with $\exists x \lnot$

(ii) De Morgan laws, i.e.

$\lnot (p \land q)$ is equivalent to $(\lnot p \lor \lnot q)$

and

$\lnot (p \lor q)$ is equivalent to $(\lnot p \land \lnot q)$

(iii)

definition of $\rightarrow$ in terms of $\lor$ and $\lnot$, i.e.

$(p \rightarrow q)$ is equivalent to $(\lnot p \lor q)$.