Prove using Natural Deduction in predicate logic $(\forall x\ P(x))\to Q ⊢ \exists x (P(x)\to Q)$ I couldn't find a proper answer. I am pretty sure the universal quantifier elimination rule can't be applied directly and I tried proving by contradiction, but couldn't complete it. 
 A: Following @Matthew Daly's hint,
here would be the general structure of the proof:
$\def\fitch#1#2{\quad\begin{array}{|l}#1\\\hline#2\end{array}}$
$$\fitch{~~1.~(\forall xP(x))\to Q}
{\fitch{~~2.~\neg(\forall xP(x)\lor\neg\forall xP(x))}{
\fitch{~~3.~\forall xP(x)}{~~
4.~(\forall xP(x))\lor(\neg(\forall x P(x)))\hspace{10ex}{\lor}~\textsf{Intro}~3\\~~
5.~\bot\hspace{32.6ex}{\bot}~\textsf{Intro}~2,4}\\~~
6.~\neg(\forall xP(x))\hspace{27.2ex}{\neg}~\textsf{Intro}~3-5\\~~
7.~(\forall xP(x))\lor(\neg(\forall xP(x)))\hspace{13.5ex}{\lor}~\textsf{Intro}~6\\~~
8.~\bot\hspace{36.4ex}{\bot}~\textsf{Intro}~2,7}\\~~
9.~(\forall xP(x))\lor(\neg(\forall xP(x)))\hspace{17ex}{\neg}~\textsf{Intro}~2-8\\
\fitch{~~
10.~\forall xP(x)}{
\fitch{~~
11.~P(a)}{~~
12.~Q\hspace{31.5ex}{\to}~\textsf{Elim}~1,10}\\~~
13.~P(a)\to Q\hspace{26.5ex}{\to}~\textsf{Intro}~11-12\\~~
14.~\exists x(P(x)\to Q)\hspace{23.1ex}{\exists}~\textsf{Intro}~13
}\\\fitch{~~
15.~\neg(\forall xP(x))}{\fitch{~~
16.~\neg\exists x(P(x)\to Q)}{\fitch{~~
17.~\boxed{a}}{\fitch{~~
18.~\neg P(a)}{\fitch{~~
19.~P(a)}{~~
20.~\bot\hspace{21ex}{\bot}~\textsf{Intro}~18,19~\\~~
21.~Q\hspace{21ex}{\bot}~\textsf{Elim}~20~}\\~~
22.~P(a)\to Q\hspace{16ex}{\to}\textsf{Intro}~19-21~\\~~
23.~\exists x(P(x)\to Q)\hspace{12ex}{\exists}~\textsf{Intro}~22~\\~~
24.~\bot\hspace{25ex}{\bot}~\textsf{Intro}~16,23~}\\~~
25.~\neg\neg P(a)\hspace{22.5ex}{\neg}~\textsf{Intro}~18-24~\\~~
26.~P(a)\hspace{25.5ex}{\neg}~\textsf{Elim}~25~}\\~~
27.~\forall xP(x)\hspace{26.5ex}{\forall}~\textsf{Intro}~17-26~\\~~
28.~\bot\hspace{32ex}{\bot}~\textsf{Intro}~15,27~}\\~~
29.~\exists x(P(x)\to Q)\hspace{22.5ex}{\neg}~\textsf{Intro}~16-28~}\\~~
30.~\exists x(P(x)\to Q)\hspace{26ex}{\lor}~\textsf{Elim}~9,10-14,15-29}$$
From line $1-9$ we proved:
"either ∀x P(x) is true or it isn't."
From line $10-14$ we proved:
"If it is true, then $Q$ is true and your $P(x)→Q$ is true for any value of x."
From line $15-29$ we proved:
"If it is not true, then you can choose some x such that $¬P(x)$. Then $P(x)→Q$ is vacuously true for that value of $x$."
And line $30$ we finishes the prove.
A: Hint: either $\forall x\  P(x)$ is true or it isn't.  


*

*If it is true, then $Q$ is true and your $P(x)\to Q$ is true for any value of $x$.  

*If it is not true, then you can choose some $x$ such that $\neg P(x)$.  Then $P(x)\to Q$ is vacuously true for that value of $x$.

A: 
I am pretty sure the universal quantifier elimination rule can't be applied directly 

Correct: you cannot apply universal elimination on part of a larger statement. 

I tried proving by contradiction, but couldn't complete it. 

Too bad ... it's typically a good strategy for whenever you have to prove an existential and you can;t have an existential already to work with. In fact, below is a completed proof by Contradiction in Fitch. It does not use any equivalence principles.

A: The following is a proof using natural deduction and, per your request, without using DeMorgan's law, null quantification laws, or contrapositive law:
$1$. $\forall x P(x) \rightarrow Q$ ---- premise
$2$. $\neg \forall x P(x) \vee Q$ ---- implication law $1$
$3$. $Q \vee \neg \forall x P(x) $ ---- commutative law $2$
$4$. $\neg \neg Q \vee \neg \forall x P(x) $ ---- double negation law $3$
$5$. $\neg Q \rightarrow \neg \forall x P(x) $ ---- implication law $4$
_____ $6$. $\neg Q$ ---- ACP
_____ $7$. $\neg \forall x P(x)$ ---- modus ponens $5,6$
__________ $8$. $\neg \exists x \neg P(x)$ ---- AIP
_________________ $9$. $\neg P(x)$ ---- AIP
_________________ $10$. $\exists x \neg P(x)$ ---- $\exists$ intro $9$
_________________ $11$. $\exists x \neg P(x) \wedge \neg \exists x \neg P(x)$ ---- conjunction intro $8,10$
__________ $12$. $\neg \neg P(x)$ ---- IP $9$-$11$
__________ $13$. $P(x)$ ---- double negation $12$
__________ $14$. $\forall x P(x)$ ---- $\forall$ intro $13$
__________ $15$. $\forall x P(x) \wedge \neg \forall x P(x)$ ---- conjunction intro $7,14$
_____ $16$. $\neg \neg \exists x \neg P(x)$ ---- IP $8$-$15$
_____ $17$. $\exists x \neg P(x)$ ---- double negation $16$
$18$. $\neg Q \rightarrow \exists x \neg P(x)$ ---- CP $6$-$17$
_____ $19$. $\neg Q$ ---- ACP
_____ $20$. $\exists x \neg P(x)$ ---- modus ponens $18,19$
_____ $21$. $\neg P(b)$ ---- $\exists$ elim $20$
$22$. $\neg Q \rightarrow \neg P(b)$ ---- CP $19$-$21$
$23$. $\neg \neg Q \vee \neg P(b)$  ---- implication law $22$
$24$. $Q \vee \neg P(b)$  ---- double negation law $23$
$25$. $\neg P(b) \vee Q$  ---- commutative law $24$
$26$. $P(b) \rightarrow Q$  ---- implication law $25$
$27$. $\exists x (P(x) \rightarrow Q)$ ---- $\exists$ intro $26$
