Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 6 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 '13 at 14:31
    
Your welcome! We've all encountered exercises that "look" more difficult than they really need to be. ;-) –  amWhy Oct 5 '13 at 14:33
    
Thanks for the support, @Amzoti! –  amWhy Oct 5 '13 at 18:22
    
@amWhy: Always! :-) –  Amzoti Oct 5 '13 at 18:23
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.