TITLE: Simple Fitch proof of De Morgan law
QUESTION [2 upvotes]: 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 :(

REPLY [4 votes]: 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}
$$
{"set_name": "stack_exchange", "score": 2, "question_id": 3399434}