Answer to Question #90135 in Discrete Mathematics for Rahim Ansari

Question

Show that the following argument form is valid.

p --> q
q --> r

∴ p --> r

Answer 1

We have to prove (p-->q) and (q-->r) implies (p-->r)

$$((p\to q)\land(q\to r))\to(p\to r)\equiv$$

$$using(a\to b)\equiv(\neg a\lor b)$$

$$\equiv\neg((p\to q)\land(q\to r))\lor(p\to r)\equiv$$

$$using \ \neg(a\land b)\equiv(\neg a\lor \neg b)$$

$$(\neg(p\to q)\lor\neg(q\to r))\lor(p\to r)\equiv$$

$$using(a\to b)\equiv(\neg a\lor b)$$

$$\neg(\neg p\lor q)\lor\neg(\neg q\lor r)\lor(\neg p\lor r)\equiv$$

$$using \neg(a\lor b)\equiv(\neg a\land \neg b)$$

$$(\neg\neg p\land \neg q)\lor(\neg\neg q\land\neg r)\lor(\neg p\lor r)\equiv$$

$$using \neg\neg a\equiv a$$

$$( p\land \neg q)\lor( q\land\neg r)\lor\neg p\lor r\equiv$$

$$using \ commutative \ law$$

$$( p\land \neg q)\lor\neg p\lor( q\land\neg r)\lor r\equiv$$

$$using\ associative\ law\$$

$$(( p\land \neg q)\lor\neg p)\lor(( q\land\neg r)\lor r)\equiv$$

$$using\ distributive\ law$$

$$(( p\lor\neg p)\land (\neg q\lor\neg p))\lor(( q\lor r)\land(\neg r\lor r))\equiv$$

$$using\ a\lor \neg a \equiv T$$

$$(T\land (\neg q\lor\neg p))\lor(( q\lor r)\land T)\equiv$$

$$using \ T\land a\equiv a$$

$$(\neg q\lor \neg p)\lor(q\lor r)\equiv$$

$$using\ associative\ law$$

$$(\neg q\lor q)\lor(\neg p\lor r)\equiv$$

$$using\ a\lor \neg a \equiv T$$

$$T\lor(\neg p\lor r)\equiv$$

$$using\ T\lor a\equiv T$$

$$T$$

Q.E.D.