get the proof of theorem using natural deduction

Question

I want to show, using natural deduction:

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

I get this:

but I don't know what should I assume. I tried to assume $\lnot(p \lor q)$, and then assume $p$ and $r$ particularly, but contradiction wasn't reached((( idk what is wrong.

Answer 1

Use $\lor$-E as in the other question you posted. Show that each of the conjuncts $p \land r$, $p \land s$ etc, implies the right hand side $(p\lor q)\land (r \lor s)$ and then you're done.

Lemma: the following derivation is valid (generalisation of $\lor$-E to $4$ conjuncts).

1. $(\phi_1 \lor \phi_2 \lor \phi_3 \lor \phi_3)$ ass.
2. We show $\phi_1 \to \psi$.
3. We show $\phi_2 \to \psi$.
4. We show $\phi_3 \to \psi$.
5. We show $\phi_4 \to \psi$.
6. $\psi$ follows.
7. $(\phi_1 \lor \phi_2 \lor \phi_3 \lor \phi_3) \to \psi$ by intro $\to$.

Try to show it by reducing to the usual $\lor$-E rule.

And that $p \land r \to (p\lor q)\land (r \lor s)$ holds, as an example:

1. $p \land r$. (ass)
2. $p$ from $\land$-E on 1.
3. $r$ from $\land$-E on 1.
4. $p \lor q$ from $\lor$-I on 2.
5. $r \lor s$ from $\lor$-I on 3.
6. $(p\lor q)\land (r \lor s)$ from 4,5.
7. $(p \land r) \to (p\lor q)\land (r \lor s)$ from intro $\to$, drop 1.

And so on for the other three terms.