2

Using only the ten primitive inference rules how do you derive:

$$ \lnot (A \land B) $$

from

$$(\lnot A \lor \lnot B)$$

The basic rules are 5 (one for each connective) In and Out or Add and Eliminate. The primitive rules are supposed to be a complete set so it is possible. Just difficult.

Joshua Taylor
  • 2,481
  • 16
  • 35
mbr_at_ml
  • 121

1 Answers1

5

The proof almost writes itself.

Given you can't apply any elimination rule to the premiss $\neg A \lor \neg B$ to extract info, you obviously need to suppose $A \land B$ and aim for a contradiction (what else?). Next, extract both conjuncts from this supposition (what else?). So your task at this point is reduced to showing that

$\neg A \lor \neg B$, $A$ and $B$ entail some contradiction.

Now intuitively

$\neg A \lor \neg B$ and $A$ entail $\neg B$.

And that gives us the desired contradiction as we have both $B$ and $\neg B$. So it just remains to derive the second displayed result.

You use $\lor$-elimination to argue by cases (what else is there to try, given you have a disjunction to work with?). Assume $\neg A$ then you have contradiction and hence anything so $\neg B$. Assume $\neg B$ then trivially $\neg B$. So either way $\neg B$. And you are done.

Exercise: fill in the details.

Peter Smith
  • 54,743
  • Yes. I assume (A&B) and if I use what we are calling the disjunctive argument I proved it in 7 lines by a contradiction 0f B and -B based the the provisional assumption. . But I can't use that. However I had already proved DA in 14 lines so we end up with a 17 line proof which I believe is the shortest possible. I will post it when I get it all cleaned up. – mbr_at_ml May 02 '13 at 00:21