Hi guys I'm trying to learn natural deduction in predicate logic and I'm struggling with this proof.
$(∀x(P(x) ∨ Q(x))) → ((∃x(¬P(x))) → (∃x(Q(x))))$
I'm trying to follow my textbook but don't have many examples likes this one. Any help would be appreciated.
So far I have two assumptions:
$(∀x(P(x) ∨ Q(x)))$ and $¬((∃x(¬P(x))) → (∃x(Q(x))))$
Sketch of the proof:
From$$\exists x(\lnot P(x))$$ you'll get $$\lnot P(t)$$ for some $t$.
From $$\forall x (P(x)\lor Q(x))$$ you'll get $$P(t)\lor Q(t)$$ by using Spec (specialization).
You should now be able to conclude $Q(t)$, and by using Rule $\exists$, you get $\exists x Q(x)$.
This is just an outline, and you should be able to convert this to a formal natural deduction proof. The idea is: "if for all $x$, either $P(x)$ or $Q(x)$ holds, and for particular $x=t$, $P(t)$ does not hold, then $Q(t)$ holds."
Showing $$\vdash (∀x(P(x) ∨ Q(x))) → ((∃x(¬P(x))) → (∃x(Q(x))))$$ amounts to showing $$\{∀x(P(x) ∨ Q(x)), ∃x(¬P(x))\} \vdash ∃xQ(x)$$ using deduction theorem.