How do I prove this sequent using First Order Logic?
$∃x(¬P(x) \land ¬Q(x)) \vdash ∃x(¬(P(x) \land Q(x)))$
Thinking, according to DeMorgan: $ \lnot(¬p \lor ¬q) = \lnot(p \land q) $ this is true, so, why the other one is true? how do I prove it?
EDIT:
I'm using Predicate logic and i got the problem from the book: Logic in Computer Science 2nd ed.
This is a direct natural deduction proof. The basic idea is, since $\lnot Px \land \lnot Qx \vdash \lnot (Px \land Qx)$ (lines 2 through 7), use Or elimination to remove the first $\exists$ and Or intro to introduce the final $\exists$ (the remaining lines).
$$\begin{array} {rll} % (1) & \exists x ~(\lnot Px \land \lnot Qx) & \text{Premise} \\ % (2) & \quad \quad \lnot Py \land \lnot Qy & \text{Premise} \\ % (3) & \quad \quad \lnot Py & \text{And Elimination of 2} \\ % (4) & \quad \quad \quad \quad Py \land Qy & \text{Premise} \\ % (5) & \quad \quad \quad \quad Py & \text{And Elimination of 4} \\ % (6) & \quad \quad \quad \quad \bot & \text{Contradiction of 3 and 5} \\ % (7) & \quad \quad \lnot (Py \land Qy) & \text{Not Introduction of 4 through 6} \\ % (8) & \quad \quad \exists x ~ \lnot (Py \land Qy) & \text{Exists Intro of 7} \\ % (9) & \exists x ~ \lnot (Px \land Qx) & \text{Exists Elimination of 1, and 2 through 8} \\ % \end{array}$$