Can i change the order of quantifiers in this case?

831 Views Asked by At

In this sentence:

"No hero is cowardly and some soldiers are cowards."

Assuming h(x) = x is a hero

s(x) = x is a soldier

c(x) = x is a coward.

So the sentence is like this i think:

($\forall x\ (h(x) \longrightarrow \neg C(x)) \land (\exists y\ (s(y) \land C(y))$

In this case, are prenex formulas bellow the same thing?

$\forall x\ \exists y\ (\neg h(x) \lor \neg C(x)) \land ((s(y) \land C(y))$

$\exists y\ \forall x\ (\neg h(x) \lor \neg C(x)) \land ((s(y) \land C(y))$

2

There are 2 best solutions below

1
On

To clarify the other responses here,

$\forall x\ (h(x) \longrightarrow \neg C(x)) \land (\exists y\ (s(y) \land \neg C(y))$ is equivalent to $\forall x\ \exists y\ (\neg h(x) \lor \neg C(x)) \land ((s(y) \land \neg C(y))$, but not equivalent to $\exists x\ \forall y\ (\neg h(x) \lor \neg C(x)) \land ((s(y) \land \neg C(y))$

9
On

Quite generally, for any formulas $\alpha(x)$ and $\beta(y)$ with only the indicated free variables, the formula $$ (\forall x\,\alpha(x))\land(\exists y\,\beta(y)) $$ is equivalent to both of
$$ \forall x\exists y\,(\alpha(x)\land\beta(y)) $$ and $$ \exists y\forall x\,(\alpha(x)\land\beta(y)). $$