Simple Fitch proof of De Morgan law

Question

Can someone tell me how to prove $\neg( \wedge )$ given the premise $\neg \vee \neg $ using Fitch system?

I was trying to do something like Proving De Morgan's Law with Natural Deduction but my teacher said that this is too complicated and I shouldn't use proof by contradiction.

I should use Or Elimination at the highest level and there should be about 20 steps. Do you have any ideas or hints? I've been struggling on this for a long time :(

Answer 1

I'm not an expert, but I would like to try my hand on this problem. Here's my version

$$ \begin{array}{l|llll:l} 1. & \neg p \vee \neg q & & & & \text{Premise} \\\hline 2. & & p \wedge q & & & \text{Assumption} \\\hline 3. & & p & & & \text{And Elimination: 2} \\ 4. & & q & & & \text{And Elimination: 2} \\ 5. & (p \wedge q) \rightarrow q & & & & \text{Implication Introduction: 2, 4}\\ 6. & & p \wedge q & & & \text{Assumption} \\\hline 7. & & & \neg q & & \text{Assumption} \\\hline 8. & & \neg q \rightarrow \neg q & & & \text{Implication Introduction: 7, 7} \\ 9. & & & \neg p & & \text{Assumption} \\ \hline 10. & & & & q & \text{Assumption} \\\hline 11. & & & & p \wedge q & \text{Reiteration: 6} \\ 12. & & & & p & \text{And Elimination: 11} \\ 13. & & & q \rightarrow p & & \text{Implication Introduction: 10, 12}\\ 14. & & & & q & \text{Assumption} \\\hline 15. & & & & \neg p & \text{Reiteration: 9} \\ 16. & & & q \rightarrow \neg p & & \text{Implication Introduction: 14, 15} \\ 17. & & & \neg q & & \text{Negation Introduction: 13, 16} \\ 18. & & \neg p \rightarrow \neg q & & & \text{Implication Introduction: 9, 17} \\ 19. & & \neg p \vee \neg q & & & \text{Reiteration: 1} \\ 20. & & \neg q & & & \text{Or Elimination: 19, 18, 8} \\ 21. & (p \wedge q) \rightarrow \neg q & & & & \text{Implication Introduction: 6, 20}\\ 22. & \neg(p \wedge q) & & & & \text{Negation Introduction: 5, 21} \\ \end{array} $$

Answer 2

I don't see any way to avoid Proof by Contradiction in order to prove this in Fitch.

And sure, you can start with $\lor$ Elimination: one subproof for $\neg p$, and another for $\neg q$. However, since in both cases you are trying to get to $\neg (p \land q)$, you'll want Proof by Contradiction inside each of those subproofs: Assume $p \land q$, and get a contradiction. The good news is that each of these can be completed pretty fast (I'll leave the missing steps to you):

Maybe your teacher meant: don't do a Proof by Contradiction at the top level ... and the above approach avoids doing exactly that ... but my question is: why not do a Proof by Contradiction at the top level?! That should work just as well and just as efficiently: Assume $p \land q$ on the outset, and then do the two subproofs for the $\lor$ Elim on $\neg p \lor \neg q$ inside of that ... but the rest is exactly the same. In fact, this proof ends up being two lines shorter: