Proving tautology Trying to prove if this statement is a tautology:
$\neg (p\to q) \to p$
I can simplify the left hand side $\neg (p\to q)$ to $p\land \neg q$, but once I get there I'm stuck.
 A: Apply the equivalence of implication twice, then commute and associate so that you can apply identity rules.
$$\neg(p\to q)\to p \\= (p\to q) \vee p \\ = (\neg p \vee q)\vee p \\ \vdots$$
A: HINT (first 2 lines):


*

*Suppose $\neg[P\implies Q]$

*$\neg\neg[P\land \neg Q]$ (from 1)
A: From the simplification that was first done, the goal could be reached. 
(1) ~ ( P=> Q) => P
(2) ~ ~ (P&~Q) => P
(3)     (P&~Q) => P
But (3) has the same form as ( P & X ) => P ( with X = ~Q) which is a well-known tautology (corresponding to the rule of inference called  &-elimination). 
Since this is not really a proof, I propose the following one: 
(1) ~ ( P=> Q) => P
(2) ~ ( ~(P=>Q) & ~P)                        Using (X=>Y) equiv. to ~ (X&~Y)
(3) ~ ( (P& ~Q) & ~P) 
(4) ~ ( (P&~P) & ~Q)                     Using assoc. and commutativity of &                                   
(5) ~ (    F   & ~Q)                     Reason: (P&~P) is a logical falsehood. 
(6) ~  (       F    )                    Reason : (F&X) equiv. to F 
(7) T                                    Reason : negation of a Falsehood= Truth 
Since the original statement is the negation of an antilogy ( logical falsehood), it is equivalent to a tautology; and so it is itself a tautology. 
Reference: on the meaning of the symbols T and F, see Lipschutz, Schaum's Outline Of Set Theory, ch. 14. 
