Prove the theorem by using natural deduction in propositional logic. Is it right to use De Morgan laws?

Question

I am attempting to prove $$[(p\vee q)\wedge(r\vee s)]\to[(p\wedge r)\vee(p\wedge s)\vee(q\wedge r)\vee(q\wedge s)]$$ by natural deduction. Above you can see the work I have made progressing on this proof. Can I use the De Morgan Laws to get a contradiction?

Answer 1

Even if you do have DeMorgan laws, you probably don't "have" that you can distribute the negation across four disjunctions.

If I were doing it, I would choose a strategy more like this. (This is only part of the proof, but it gives you a sense of how you would need to proceed.)

Answer 2

You need to use $\lor$-elimination, which is in my book:

1. $p \lor q$
2. $p \to s$.
3. $q \to s$.
4. $s$ (from elimination and 1,2,3)

So I'd start the following way, there are no real choices what to do anyway:

1. $(p\lor q) \land (r \lor s)$ ass. to get the right hand side (and the full statement, I'll write RHS for the disjunction with the 4 terms from now on) and the full statement.
2. $p \lor q$ from $\land$-elim. from 1.
3. $r \lor s$ from $\land$-elim. from 1.
4. $p$ ass. for $\to$ to use in $\lor$-elim.
5. $r$ ass.
6. $p \land r$ from $\land$-I; and 4,5.
7. RHS in three steps using $\lor$-I and 6.
8. $r \to \text{RHS}$ drop ass. 5, from $\to$-intro.
9. $p \to (r \to \text{RHS})$ from $\to$-I drop ass 4.
10. $q$ ass. for $\to$ to use in $\lor$-E.
11. $r$ ass. 12 $q \land r$ $\land$-I; 10,11
12. RHS again from 3 times $\lor$-I.
13. $r \to \text{RHS}$ drop 11, $\to$-I.
14. $q \to (r \to \text{RHS})$ from $\to$-I drop ass 10.
15. $r \to \text{RHS}$ from $\lor$-E on 2,9,14.

Now do $s \to \text{RHS}$ in a similar way and apply $\lor$-E on 3,16 and that. We get RHS directly.

Note that this proof just checks the 4 cases on the disjunctions 2 and 3, essentially.