[Math] How should I proceed in proving this tautology

logic

I know that following is a tautology because I've checked its truth table. I am now attempting to prove that it is a tautology by using the rules of logic, which is more difficult. How should I proceed?

$(p\land(p\implies q))\implies q$

$(p\land(\lnot p \lor q))\implies q$

$(p\land \lnot p) \lor (p\land q) \implies q$ This step is where I'm getting stuck at. I know that $(p\land \lnot p)$ is false. So it seems to me that the truth value of everything to the left of the $\implies$ operator depends on the truth value of $(p\land q)$ So what I want to do is this:

FALSE $\lor (p\land q) \implies q$ which reduces to

$(p\land q) \implies q$

Is my thinking correct so far? If so, then I want to rewrite $(p\land q) \implies q$ as

$\lnot(p \land q) \lor (p \land q)$ by using the identity $p\implies q \equiv \lnot p \lor q$
Am I on the right track?

Best Answer

Use De Morgan's law on $\neg(p\land q)$ near the end. This should give you a disjunction which should easily be seen as tautological by the law of excluded middle. Also, remember that $(p\land q)\implies q\equiv \neg(p\land q)\lor q$, not $\neg(p\land q)\lor(p\land q)$ as you wrote.