Proof of the distributive law in implication?

Question

I am doing a practice exam and in it is the following question:

Show without truth tables that the following logical equivalence holds:

$$(p → q) ∧ (p → r) ≡ p → (q ∧ r)$$

I attempted to substitute the left side's $(p \rightarrow q)$ and then apply the distributive laws, but what I got as a result was terribly long and messy.

I found a sample proof over here. However that is a proof using the tableau method of natural deduction and we still haven't covered that in class.

Is there a simpler proof?

Thank you.

amWhy · Accepted Answer · 2013-10-05T14:26:52.287

14

Use the equivalence $\quad a \rightarrow b \equiv \lnot a \lor b\tag{1}\;$

to transform the implications into disjunctions,

then use one of the distributive laws you know $(2)$:

$$\begin{align}(p → q) ∧ (p → r) &\equiv (\lnot p \lor q) \land (\lnot p \lor r)\tag{by (1)}\\ \\ & \equiv \lnot p \lor (q\land r)\tag{by (2)} \\ \\ & \equiv p \rightarrow (q \land r)\tag{by (1)}\end{align}$$

edited Oct 05 '13 at 14:26

answered Oct 05 '13 at 14:13

amWhy

209,954

Awesome @amWhy, thanks a lot! It was so simple, gah! I'll try even harder before asking next time. Thanks again! – borg123 Oct 05 '13 at 14:31
1

Your welcome! We've all encountered exercises that "look" more difficult than they really need to be. ;-) – amWhy Oct 05 '13 at 14:33
@amWhy: Always! :-) – Amzoti Oct 05 '13 at 18:23
This works the same with tautological consequence (or implication) right? – shinzou Feb 04 '15 at 13:46

Proof of the distributive law in implication?

1 Answers1

Linked