# Natural Deduction Proof of $p∧(q∨r) \vdash (p \land q) \lor (p \land r)$

Trying to go from $$[p∧(q∨r)]$$ to prove $$(p∧q) ∨ (p∧r)$$

Wanted to know if I am heading in the right direction with my deductions or where I am getting messed up.

$$\begin{array}{|l}(p\wedge (q\vee r) \quad \text{premise}\\\hline p \quad\wedge\text{elim 1}\\q\vee r \quad \wedge\text{elim 1}\\\hline q \quad \text{assumption} \\p\wedge q\quad \wedge \text{intro 2,4} \\(p\wedge q)\vee (p\wedge r) \quad \vee\text{intro 5}\\\hline r \quad \text{assumption}\\p\wedge r \quad\wedge\text{intro 2,7}\\(p\wedge q)\vee (p\wedge r)\quad \vee\text{intro 8}\\\hline (p\wedge q)\vee (p \wedge r) \quad \vee \text{elim 3,4-6,7-9}\end{array}$$

• Welcome to Mathematics Stack Exchange. Note that this is the distributive property Sep 18, 2019 at 21:05
• Why do you state assumption $q\land r$ when the premise has $q\lor r$? Sep 18, 2019 at 21:11

You assumed $$q \land r$$ ... twice ... but you never discharged any of these assumptions.

So, what you managed to show is that $$p \land (q \lor r)$$ together with $$q \land r$$ implies $$(p \land q) \lor (p \land r)$$

However, you needed to show that $$p \land (q \lor r)$$ by itself implies $$(p \land q) \lor (p \land r)$$

So no, this is not a good proof.

In fact, I see little value in assuming $$q \land r$$ ... how would you discharge that?

So, your proof isn't even going in the right direction.

Instead, use $$\land$$ Elim to get $$q \lor r$$ ... and now do two suproofs: one with $$q$$, and one with $$r$$ ... and eventually use $$\lor$$ elim to discharge those assumptions

• $\begin{array}{|l}(p\wedge (q\vee r) \quad premise\\\hline q\vee r \quad \vee elim 1\\ p \quad \vee elim 1\\\hline q \quad assumption \\ \vdots \\ r \quad \\\hline r \quad assumption \\ \vdots \\ q \quad \\\hline q \quad \vee elim 3-5,6-8\\ r \quad \vee elim 3-5,6-8\\ p \wedge q \quad \wedge intro \\ p \wedge r \quad \wedge intro \\(p\wedge q)\vee (p \wedge r) \quad \vee intro 7,8\end{array}$ So then it would look something like this? How would I get r and q alone? Sep 18, 2019 at 22:05
• @AndrewRyan As you realize yourself ... this is not going to work. Instead, notice that your ultimate goal is $(p \land q) \lor (p \land r)$ ... so try and get to that at the end of each subproof. Sep 18, 2019 at 22:12

$$\def\fitch#1#2{\quad\begin{array}{|l}#1\\\hline#2\end{array}}$$ I think your proof would be something like this:

$$\fitch {~~1.~P\land(Q\lor R)} { ~~2.~P\hspace{25ex}{\land}~\textsf{E}~1\\ ~~3.~Q\lor R\hspace{20.6ex}{\land}~\textsf{E}~1\\ \fitch {~~4.~Q} {~~5.~P\land Q\hspace{17.2ex}{\land}~\textsf{I}~2,4\\ ~~6.~(P\land R)\lor(P\land Q)\hspace{5ex}{\lor}~\textsf{I}~5}\\ \fitch {~~7.~R} {~~8.~P\land R\hspace{17.5ex}{\land}~\textsf{I}~2,7\\ ~~9.~(P\land R)\lor(P\land Q)\hspace{5.2ex}{\lor}~\textsf{I}~8}\\ ~~10.~(P\land R)\lor(P\land Q)\hspace{7.2ex}{\lor}~\textsf{E}~3,4-6,7-9}\\$$

Wanted to know if I am heading in the right direction with my deductions or where I am getting messed up.

Nope. You are completely off course.

Okay now, you do have some idea of what rules were needed, but have gotten muddled on the assumptions which are needed to apply them.

You shall only need to raise assumptions to pepare for a rule of discharge (eg: conditional introduction, negation introduction, or disjunction elimination). So always begin building a proof by deciding what rules you shall likely need, and in which order, and let that inform you what assumption will be required for any subproofs.

You have a conjunction of disjunctions as your only premise. That suggests that their elimination rules will be involved somewhere in the proof.

Start there: conjunction elimination lets you infer $$p$$ and the disjunction $$q\vee r$$.

Now, disjunction elimination is the "Proof by Cases" structure , where two subproofs each aim to derive the same conclusion from each of the assumptions .

So, those assumptions will clearly be $$q$$ for the first subproof and $$r$$ for the second. Note: not wedged together as you did, but one for each seperate case.

Well, that conclusion is a disjunction of conjunctions. That suggests that their introduction rules will be involved in each case.

That is all. So just put it together.