Take the tour ×

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 → q) and then apply the distribtive 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.

share|improve this question
add comment

1 Answer

up vote 5 down vote accepted

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}$$

share|improve this answer
Awesome @amWhy, thanks a lot! It was so simple, gah! I'll try even harder before asking next time. Thanks again! –  borg123 Oct 5 at 14:31
Your welcome! We've all encountered exercises that "look" more difficult than they really need to be. ;-) –  amWhy Oct 5 at 14:33
Thanks for the support, @Amzoti! –  amWhy Oct 5 at 18:22
@amWhy: Always! :-) –  Amzoti Oct 5 at 18:23
add comment

Your Answer


