How can I prove that (p→q)∧(p→r) ⇔ p→(q∧r)

Question

How can I prove that (p→q)∧(p→r) compound statements and compound statement p→(q∧r) are logically equivalent?

And can I use logical equivalences on this proof?

Answer 1

$$(p\implies q) \land (p\implies r)$$

is equivalent to

$$( q \lor \lnot p) \land ( r \lor \lnot p)$$

is equivalent to

$$(q \land r) \lor \lnot p$$

is equivalent to

$$p \implies (q\land r)$$

Answer 2

$(p→q)∧(p→r) $ is the same as

$(\overline{p} \vee q)\wedge (\overline{p} \vee r)$ which is the same as

$(\overline{p}\vee(\overline{p}\wedge r)\vee(q\wedge\overline{p})\vee(q\wedge r))$

From here, it is clear that if both $\overline{p}$ and $(q\wedge r)$ is false, the complete statement is false. If either is true, then the full statement is true. And so the full statement is the same as the statement $p→(q∧r)$ because $p→(q∧r)$ is the same as $\overline{p} \vee (q\wedge r)$.

Answer 3

The other answers showed how to use logical equivalences to prove the result. Here is a proof using natural deduction in a Fitch-style proof checker.

The inference rules are listed on the proof checker's page.

They are

• conjunction introduction ($\land$I),
• conjunction elimination ($\land$E),
• implication introduction or conditional proof ($\to$I),
• implication elimination or modus ponens ($\to$E) and
• biconditional introduction ($\leftrightarrow$I).

---

Kevin Klement's JavaScript/PHP Fitch-style natural deduction proof editor and checker http://proofs.openlogicproject.org/