"The domain of the propositional function P(X) is {0, 1, 2, 3, 4}. Write an formula equivalent to ∃x(P(X)) using conjunction and implication and not using negation before parenthesis."
I had this on my exam. I wrote: ¬P(0)^¬P(1)^¬P(2)^¬P(3)^¬P(4) -> ¬P(X) but I'm not sure that it is correct. Please explain.
First, $\exists x(P(x))$ is equivalent to $P(0)\lor P(1)\lor P(2)\lor P(3)\lor P(4)$. Unfortunately, we need conjunctions, not disjunctions. De Morgan’s law says that
$$\neg\big(P(0)\lor P(1)\lor P(2)\lor P(3)\lor P(4)\big)$$
is equivalent to, $\neg P(0)\land\neg P(1)\land\neg P(2)\land\neg P(3)\land\neg P(4)$, so we could use
$$\neg\big(\neg P(0)\land\neg P(1)\land\neg P(2)\land\neg P(3)\land\neg P(4)\big)$$
if we were allowed to use negation before a parenthesis. Unfortunately, we’re not, so it’s back to the drawing board: we need a new idea. We are allowed to use implication; how could that help?
Suppose that you knew that $P(0),P(1),P(2)$, and $P(3)$ were all false; what could you conclude from $\exists x(P(x))$? You’d know that $P(4)$ had to be true. In symbols:
$$\big(\neg P(0)\land\neg P(1)\land\neg P(2)\land\neg P(3)\big)\to P(4)\;.\tag{1}$$
(Your syntax rules may not require the big parentheses on the lefthand side of the implication.) $(1)$ is certainly a consequence of $\exists x(P(x))$; is it actually equivalent? Yes. It’s clearly true if $P(4)$ is true. If $P(4)$ is not true, it’s true exactly when
$$\neg P(0)\land\neg P(1)\land\neg P(2)\land\neg P(3)$$
is false. And since $\neg P(0)\land\neg P(1)\land\neg P(2)\land\neg P(3)$ is equivalent to
$$\neg\big(P(0)\lor P(1)\lor P(2)\lor P(3)\big)$$
by De Morgan’s law, it’s false when $\neg\big(P(0)\lor P(1)\lor P(2)\lor P(3)\big)$ is false, i.e., when
$$P(0)\lor P(1)\lor P(2)\lor P(3)$$
is true. Thus, $(1)$ is true whenever at least one of $P(0),P(1),P(2),P(3)$, and $P(4)$ is true, which is exactly what we wanted.
Your answer has a free variable on the righthand side of the implication, which should be a bit of a red flag. I suspect that your idea was that $\exists x(P(x))$ on the domain $\{0,1,2,3,4\}$ is equivalent to
$$\big(\neg P(0)\land\neg P(1)\land\neg P(2)\land\neg P(3)\land\neg P(4)\big)\to\forall x\,(\neg P(x))\;;$$
that’s true, but it uses the universal quantifier, and while it’s not entirely clear from the statement of the problem whether this is permissible, I suspect that you were intended not to use any quantifiers at all.