Proof using Laws of Logic

Question

Using the laws of logic, prove:

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

My attempt to prove this:

p → (q ∧ r)

Implication Law: ¬p ∨ (q ∧ r)

Distribution Law: (¬p ∨ q) ∧ (¬q ∨ r)

I am unsure how to correctly apply the laws of logic (without the use of Truth Tables) so that:

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

Answer 1

You didn't apply the Distribution Law correctly.

You should go from:

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

to:

$$(\neg p \lor q) \land (\color{red}{\neg p} \lor r)$$

and from there you use Implication twice to get:

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

Answer 2

Note that

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

$$¬p ∨ (q ∧ r) ≡ $$

$$(¬p ∨ q) ∧ (¬p ∨ r) ≡$$

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

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

Answer 3

$\def\fitch#1#2{\begin{array}{|l}#1\\\hline#2\end{array}}$By natural deduction (classical and intuitive logic)

Take $p\to(q\wedge r)$ as a premise.   Assuming $p$ infers $q\wedge r$ which entails $q$, and so we conclude $p\to q$. Likewise we conclude $p\to r$.   Thus the premise entails $(p\to q)\wedge (p\to r)$.

Conversely take $(p\to q)\wedge (p\to r)$ as a premise.   This entails both $p\to q$ and $p\to r$.   Assuming $p$ thereby infers $q$ and $r$.   Thus the premise entails $p\to (q\wedge r)$.

Therefore proving the equivalence. $p\to (q\wedge r) \dashv\vdash (p\to q)\wedge(p\to r)$

${\fitch{p\to(q\wedge r)}{\fitch{p}{q\wedge r\\q}\\p\to q\\\fitch{p}{q\wedge r\\r}\\p\to r\\ (p\to q)\wedge (p\to r)}\\ \\[2ex] \fitch{(p\to q)\wedge (p\to r)}{p\to q\\p\to r\\\fitch{p}{q\\r\\q\wedge r}\\p\to (q\wedge r)}}$

Identifying which of the Rules of Inference were used is left to the student.