multiplying logical implications

Question

i'm trying to prove that ~p → (p → q) is a tautology without truth table. So what I did is distribute the ~p → over the (p → q) so what I did is ~p → p → ~p → q. But I found that by truth table it's not equivalent to ~p (p → q). So the question is: what is → x →? How can I prove ~p → (p → q) is a tautology without truth table? Thanks

Answer 1

The $\rightarrow$ does not distribute over another $\rightarrow$

Anyway, instead of using a truth-table, you can do something like this:

We need to show that $\neg p \rightarrow (p \rightarrow q)$

So, let's do a conditional proof: let's assume $\neg p$ and let's try to show $p \rightarrow q$. If we can show that, then we have shown that if $\neg p$, then $p \rightarrow q$, i.e. $\neg p \rightarrow (p \rightarrow q)$

OK, so we need to show another conditional: $p \rightarrow q$

So, let's do another conditional proof: assume $p$, and try to show $q$.

OK, so now we have two assumptions, $\neg p$ and $p$, and we're trying to show $q$. How can we do that? Well, there are several things we can do:

Proof by contradiction: assume $\neg q$, and show that that leads to a contyradiction. Well, we indeed have a contradiction: between $p$ and $\neg p$. So, $\neg q$ is not true, and hence (we're obviously doing classical logic here!) $q$ is true.

Another way of deriving $q$ from $p$ and $\neg p$:

Given that $p$ is true, the statement $p \lor q$ is also true. But given $\neg p$, that means $q$ (this inference is called Disjunctive Syllogism)