proving demorgan in a limited ND

yarden.katz_at_gmail.com
Date: 12/16/04 

Date: 16 Dec 2004 08:10:35 -0800

Hi, I'm having trouble proving DeMorgan using a natural deduction. I
want to prove it one way, namely that ~(p ^ q) |- ~p v ~q

I tried the following:

1. ~(p ^ q)
2. ~p A
3. ~(~p v ~q) A
4. ~p v ~q Iv 2
5. contradiction E~ 3, 4
6. ~p v ~q I~ 3, 5

This, however, only allows one to infer that ~p->(~p v ~q), which is
trivial and not what I'm trying to prove. If I do the same for ~q,
I'll just get another tautology: (~p v ~q)->(~p v ~q). The system I'm
working in does not have disjunctive syllogism which would probably
help in proving this. How can I prove this? I'm stuck on this one.
Any help is greatly appreciated..

Thanks.