I need some help proving $$\neg(p \to q)\vdash p \wedge \neg q$$ using natural deduction.
So far I've tried using the Law of excluded middle ($p \lor \neg p$). With this approach, I can complete the first half but have no clue how to finish the rest.
The solution can make use of and, or, not, implies introduction/elimination and the law of excluded middle.
Any idea or help is appreciated!
Hint:
first prove that $$\neg p\vdash p\rightarrow q$$ and $$ q\vdash p\rightarrow q.$$
From here it must be easy to show that $$\neg(p \to q)\vdash p$$ and $$\neg(p \to q)\vdash \neg q.$$
Then the result follows from $\wedge I$.
To prove $\neg p\vdash p\rightarrow q$, assuming $\neg p$ we have to deduce $p \rightarrow q$. assuming $p$ and using $\neg E$ we get $\bot$, and from there using $\bot$ law, we can deduce $q$, and then deduce $p\rightarrow q$ by $\rightarrow I$ and discharge the assumption $p$. The proof is complete.