Natural Deduction, Finish the Proof

68 Views Asked by At

$$(((p\land q)\lor r)\land ((p\land q)\lor s)) \to ((p\land q)\lor (r\land s))$$

I don't know how to finish this proof by natural deduction using tree. First I used $(\to I)$ I got $((p\land q)\lor(r\land s))$ then $(\lor I)$ I got $(r\land s) \land(I)$ I got $r$ and $s$ and I finished here and don't know how to continue.

I appreciate your help.

enter image description here

I tried it like that but I am not sure if it s right. enter image description here

2

There are 2 best solutions below

0
On

Your $\to \ I$ rule is not applied correctly.

Indeed, instead of starting with $r$ and $s$, you should start with the antecedent of the conditional you are trying to prove, i.e. start with:

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

and see if you can derive

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

from that.

0
On

No, $r$ and $s$ are not something you seek to derive using disjunction eliminations.

Rather they, along with $(p\vee q)$, are the assumptions which you discharge when you eliminate the disjunctions in $(p\wedge q)\vee r$ and $(p\wedge q)\vee s$ respectively, so that you may derive $(p\wedge q)\vee(r\wedge s)$.

Here's how you discharge assumptions of $p\vee q$ and $s$ to eliminate the disjunction in $(p\wedge q)\vee s$ (which naturally is derived from an assumption that you will eventually discharge to introduce the conditional in the conclusion).

$$\dfrac{\cdots~\dfrac{\dfrac{((p\wedge q)\vee r)\wedge((p\wedge q)\vee s))}{(p\wedge q)\vee s}{\tiny\wedge\mathsf E}~\dfrac{[p\wedge q]^3}{(p\wedge q)\vee(r\wedge s)}{\tiny\vee\mathsf I}~\dfrac{\dfrac{r\quad [s]^3}{r\wedge s}{\tiny\wedge\mathsf I}}{(p\wedge q)\vee(r\wedge s)}{\tiny\vee\mathsf I}}{(p\wedge q)\vee(r\wedge s)}{\tiny\vee\mathsf E^3}}{\vdots}$$

Of course, that leaves $r$ undischarged, but you should see how that will be handled.