Using limited natural deduction rules to prove de morgan's law

Question

I am trying to prove something reversely, but always get stuck when it comes to $\neg r\wedge \neg q\vdash \neg (r\vee q)$.

How can I prove it using the following rules?

Here's where I get stucked.

Answer 1

I'm not particularly fond of this list of rules, because $ \neg $-introduction is missing. Normally I say, eliminate what you have and introduce what you want, but how can you do that when you want $ \neg $ and there is no introduction rule for that!?

So first, here is the introduction rule for $ \neg $:

If $ \Sigma , A \vdash B $ and $ \Sigma , A \vdash \neg B $ are theorems, then so is $ \Sigma \vdash \neg A $.

(It looks a lot like the elimination rule! But whereas that rule (3) is fundamentally about eliminating the $ \neg $ on $ \neg B $, this rule is fundamentally about introducing the $ \neg $ on $ \neg A $.)

Now, you can't use this in your assignment (assuming that you're doing an assignment), because it's not on your list. But the reason that they can leave it off the list is because it can be proved from the rules on the list!

First, we must prove the double-negation theorem $ \neg \neg A \vdash A $. First, notice that $ \neg \neg A \vdash \neg \neg A $ by reflexivity (1) and so $ \neg A , \neg \neg A \vdash \neg \neg A $ by addition (2). Similarly, $ \neg A \vdash \neg A $ by reflexivity, and so $ \neg A , \neg \neg A \vdash \neg A $ by addition. Now (3) applies (with $ \neg \neg A $ for $ \Sigma $ and $ \neg A $ for $ B $) and conclude that $ \neg \neg A \vdash A $.

Now we can prove the $\neg$-introduction rule. So suppose that $ \Sigma , A \vdash B $ and $ \Sigma , A \vdash \neg B $. Then by $ \to $-introduction (5), $ \Sigma \vdash A \to B $ and $ \Sigma \vdash A \to \neg B $. By addition, also $ \Sigma , \neg \neg A \vdash A \to B $ and $ \Sigma , \neg \neg A \vdash A \to \neg B $. But also, by applying addition to the double-negation rule proved in the last paragraph, $ \Sigma , \neg \neg A \vdash A $. So by $ \to $-elimination (6), $ \Sigma , \neg \neg A \vdash B $ and $ \Sigma , \neg \neg A \vdash \neg B $. Then by $ \neg $-elimination, $ \Sigma \vdash \neg A $.

Now you can use $ \neg $-introduction even though it wasn't on your list!