1.6, 9c) done as an example:

We want to apply modus ponens to show that, given

\underbrace{(r\rightarrow p)\land(p\rightarrow q)}_{A},
we can obtain
\underbrace{r\rightarrow q}_B.

Modus ponens demands that we show A\rightarrow B to be true. Since we're not at liberty to assume truth values of p, q, and r, A\rightarrow B needs to be a tautology, i.e. true for any values of p, q, r.

Let's show that:

A\rightarrow B\equiv (r\rightarrow p)\land(p\rightarrow q)\rightarrow (r\rightarrow q)
\equiv (\neg r\lor p)\land(\neg p\lor q)\rightarrow (\neg r\lor q)
\equiv \neg((\neg r\lor p)\land(\neg p\lor q))\lor (\neg r\lor q)
\equiv \neg (\neg r\lor p)\lor \neg(\neg p\lor q)\lor (\neg r\lor q)
\equiv (r\land \neg p)\lor (p\land \neg q)\lor \neg r\lor q
Reorder:
\equiv \neg r\lor (r\land \neg p)\lor q \lor (p\land \neg q)
Distribute:
\equiv (( \neg r\lor r) \land (\neg r\lor \neg p))\lor ((q \lor p) \land (q \lor \neg q))
\equiv (t \land (\neg r\lor \neg p))\lor ((q \lor p) \land t)
\equiv \neg r\lor \neg p \lor q \lor p
Reorder:
\equiv \neg r\lor (\neg p \lor p) \lor q
\equiv \neg r\lor t \lor q
\equiv t

(Note that the equivalences needed on 9b are much more gentle. There might also be a quicker way of showing this.)

We thus have A, A\rightarrow B, and thus by modus ponens, we conclude B.

Teaching/DiscreteMathSpring2011/HomeworkSet03/9c (last edited 2011-02-23 01:38:27 by AndreasKloeckner)