Let P and Q be any propositions, show that $(P \wedge Q) \Rightarrow (P \Rightarrow Q) \equiv [P \wedge (P \Rightarrow Q)] \Rightarrow Q.$ For phone users,
$(P \wedge Q) \Rightarrow (P \Rightarrow Q) \equiv [P \wedge (P \Rightarrow Q)] \Rightarrow Q$
Can you prove it for me? My friend asked me last night (GMT+7) and I still cannot solve it. Can you please help me?
 A: They are both tautologies, and this can be observed with a truth table. The following is a proof via natural deduction:

$(p \wedge q) \rightarrow (p \rightarrow q)$
$\Leftrightarrow \neg (p \wedge q) \vee (\neg p \vee q)$ implication
$\Leftrightarrow \neg p \vee \neg q \vee \neg p \vee q$ DeMorgan's Rule
$\Leftrightarrow \neg p \vee \neg p \vee \neg q \vee q$ commutivity
$\Leftrightarrow \neg p \vee \neg q \vee q$ idempotence
$\Leftrightarrow \neg p \vee T$ negation law
$\Leftrightarrow T$ domination law

$[p \wedge (p \rightarrow q)] \rightarrow q$
$\Leftrightarrow \neg [p \wedge (\neg p \vee q)] \vee q$ implication
$\Leftrightarrow [\neg p \vee \neg(\neg p \vee q)] \vee q$ DeMorgan's Rule
$\Leftrightarrow [\neg p \vee (\neg \neg p \wedge \neg q)] \vee q$ DeMorgan's Rule
$\Leftrightarrow [\neg p \vee (p \wedge \neg q)] \vee q$ Double negation
$\Leftrightarrow [(\neg p \vee p) \wedge (\neg p \vee \neg q)] \vee q$ distribution
$\Leftrightarrow [T \wedge (\neg p \vee \neg q)] \vee q$ negation law
$\Leftrightarrow (\neg p \vee \neg q) \vee q$ identity law
$\Leftrightarrow \neg p \vee (\neg q \vee q)$ associativity
$\Leftrightarrow \neg p \vee T$ negation law
$\Leftrightarrow T$ domination law
