finding a DNF with an expression that contains quantifiers

102 Views Asked by At

I am supposed to use equivalencies to find the prenex DNF for the wff:

$\exists xp(x) \land \exists xq(x) \rightarrow \exists x(p(x) \land q(x))$

It's been awhile since I've done something like this so I might need a refresher, but the answer I am getting is:

$\lnot \exists xp(x) \lor \lnot \exists xq(x) \lor \exists x(p(x) \land q(x))$

I got this answer by converting the original equation into $\lnot (\exists xp(x) \land \exists xq(x)) \lor \exists x(p(x) \land q(x))$ using the equivalency $A \rightarrow B \equiv \lnot A \lor B$. From there I distributed the $\lnot$ in and flipped the $\land$ to $\lor$. Is this correct? I can't help but feel like there is more that I am forgetting to do.

1

There are 1 best solutions below

0
On BEST ANSWER

What you did is correct, but there is more to do — you can simplify further. Recall that $\neg\exists \equiv \forall\neg$, and that although you can coalesce $\exists$ quantifiers across a disjunction, you can't do that with $\forall$ quantifiers. To put the sentence into prenex normal form, you have to rename variables and move the quantifiers to the outside.

$$\begin{align} \lnot \exists x p(x) \lor \lnot \exists x q(x) \lor \exists x(p(x) \land q(x)) &\iff \forall x \lnot p(x) \lor \forall x \neg q(x) \lor \exists x(p(x) \land q(x))\\ &\iff \forall x \lnot p(x) \lor \forall y \neg q(y) \lor \exists z\,(p(z) \land q(z))\\ &\iff \forall x \forall y\exists z\,[ \lnot p(x) \lor \neg q(y) \lor (p(z) \land q(z))].\\ \end{align}$$ The inner formula $[...]$ is in DNF. The order of the quantifiers is not unique: we could have moved them in any order, so the sentence is also equivalent to $\exists z\forall x\forall y[...]$, for example, as well as to $\forall x\exists z\forall y[...]$.