How to prove P → [(P → Q) → Q] tautology without using a truth table? I've been working through "P → [(P → Q) → Q]" for a while now, and I can't seem to be able to prove the truth without the use of a truth table.
 A: $\neg P \vee (\neg (\neg P \vee Q) \vee Q) \\ \Rightarrow \neg P \vee (( P \wedge \neg Q) \vee Q)\\ \Rightarrow \neg P \vee (( P \vee Q) \wedge (\neg Q \vee Q))\\\Rightarrow \neg P \vee  P \vee Q\\ \Rightarrow 1$
A: \begin{align}
P \Rightarrow ((P \Rightarrow Q) \Rightarrow Q)
&= P \Rightarrow ((\lnot P \lor Q) \Rightarrow Q) \\
&= P \Rightarrow (\lnot(\lnot P \lor Q) \lor Q) \\
&= P \Rightarrow (( P \land \lnot Q) \lor Q) \\
&= P \Rightarrow (\lnot Q \Rightarrow ( P \land \lnot Q) ) \\
\end{align}
Is that proof enough?
A: A key is to notice that
$$
A \Rightarrow B \equiv \neg A \lor B.
$$ One may then write
$$
\begin{align}
P \Rightarrow [(P\Rightarrow Q)\Rightarrow Q]&\equiv \neg P \lor [(P\Rightarrow Q)\Rightarrow Q]
\\&\equiv \neg P \lor [\neg(P\Rightarrow Q)\lor Q]
\\&\equiv \neg P \lor [\neg(\neg P \lor Q)\lor Q]
\\&\equiv \neg P \lor [(P \land \neg Q)\lor Q]
\\&\equiv \neg P \lor [(P \lor Q)\land (\neg Q \lor Q)]
\\&\equiv \neg P \lor [(P \lor Q)\land 1]
\\&\equiv \neg P \lor P \lor Q
\\&\equiv 1 \lor Q
\\&\equiv 1 .
\end{align}
$$
A: 
My technique always focuses on working towards using De Morgan's Law:
P ∧ Q ≡ ¬ (¬ P ∨ ¬ Q) De Morgan’s law 
P ∨ Q ≡ ¬ (¬ P ∧ ¬ Q) De Morgan’s law

Proof Idea:
Assuming the opposite, use implication with respect to the main conditional.  Follow this with the implication equivalence to derive a disjunction.  Use De Morgan's on the main disjunctive operator to derive a conjunction.  Separate atomic components.  Use implication on the newly formed main operator, apply De Morgan's and then use the remaining condition to derive Q using P, the contradiction is:
$Q \uparrow \lnot Q$
Contrapositive:
$\lnot [P → [(P → Q) → Q] ]$
Implication:
$ \lnot [ \lnot P \downarrow [ (P → Q) → Q ]$
De Morgan's:
$ P \uparrow \lnot [(P → Q) → Q]$
Separate Atomic Components:
$ \lnot [( P → Q) → Q] $
Implication:
$ \lnot [ \lnot (P → Q) \downarrow Q] $
De Morgan's:
$ \lnot \ \lnot (P → Q) \uparrow \lnot Q$
Separate Atomic Components:
Use $P$, $(P → Q)$, to derive $Q$.
The contradiction of  $Q \uparrow \lnot Q$ results, therefore we can discharge the assumption and assume the theorem is valid.
A: You can do a 'short' or 'indirect' truth-table:
Assume the statement is false, and see how the truth-values of other parts of the statement are forced as a result of that. If you ever get to a contradiction (e.g. some sentence is forced to be true and false at the same time), then you know that it is impossible for the original statement to be false, and hence it is a tautology. So:
$\begin{array}
\hline
  P & \rightarrow & [ & ( & P & \rightarrow & Q & ) & \rightarrow & Q & ] \\ 
  T_2 & F_1 & & & T_6 & T_4 & \color{red}T_7 & & F_3 & \color{red}F_5\\ 
(1) & A. &&& (2) & (3) & (4,6) & & (1) & (3)
\end{array}$
I used indices to indicate the order in which I put down the forced truth-values, and the indices in the parentheses indicate from which truth-values the truth-value is forced (e.g. $T_7$ was forced by $T_4$ and $T_6$.) The $A.$ is for the assumption that you start out with. Finally, the red colored truth values show the contradiction. So, the statement cannot be false. So, it is a tautology.
A: The natural deduction proof is straightforward:
$$\begin{array} {rll}
(1) & \quad P & \text{Premise} \\
(2) & \quad \quad P \Rightarrow Q & \text{Premise} \\
(3) & \quad \quad Q & \text{Modus Ponens of 1 and 2} \\
(4) & \quad (P \Rightarrow Q) \Rightarrow Q & \text{Deduction of 2 through 3} \\
(5) & P \Rightarrow (P \Rightarrow Q) \Rightarrow Q & \text{Deduction of 1 through 4} \\
\end{array}$$
