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.
Best Answer
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}$$