[Math] Prove the following Statement is a tautology

discrete mathematicsproof-writing

I need to prove the following statement is a tautology

[¬Q∧(P→Q)]→¬P

So far this is what i have but now i am stuck any advice on further finishing this problem would be helpful.

[¬Q∧(P→Q)]→¬P
[¬Q∧(¬P∨Q)]→¬P
[(¬Q∧¬P)∨(¬Q∧Q)]→¬P
¬[(¬Q∧¬P)∨(¬Q∧Q)]∨¬P
((Q∨P)∧(Q∨¬Q))∨¬P
[(Q∨P)∧T]∨¬P

And that's all i have so far. I can't figure out how to go from there. I can't use truth tables i must prove it using a series of logical equivalences.

Any help or ideas going on with this problem?

EDIT1:

I somewhat notice now can i do this?

[(Q∨P)∧T]∨¬P
(Q∨P)∧(¬P∨T)
Q∨T∨T
True!?!

Best Answer

i think what you did until here:

[(Q∨P)∧T]∨¬P

is correct. But then you can simply forget about the T; the formula above is logically equivalent to

(Q∨P)∨¬P

which is simply

Q∨P∨¬P

Q∨T

T.

Related Question