Proving ${\sim}(p \mathbin\& q)$ implies ${\sim p}\mid{\sim q}$ using Fitch I am struggling with proving something in Fitch. How can I prove from the premise ~(p & q), that ~p | ~q . Any ideas on how I should proceed; I have no idea...?
 A: Here are two different Fitch-style proofs. In the one immediately below I've used the propositional tautology (P v ~P) and proved the desired conclusion by cases. In the second one, I've used the definition of '$\rightarrow$' and proved it directly (i.e., by conditional introduction).
$\fbox{Proof by Cases}$

$\fbox{Direct Proof }$

A: I use Polish notation.  Instead of writing $\land$, $\lor$, $\lnot$, and ->, I write K, A, N, and C respectively.  Connectives also appear before lower case letters instead of in the middle of them.  Thus, for (p->q) I write Cpq.  So, we want to show that
NKpq $\vdash$ ANpNq.  
The rules I use probably vary a little from Fitch, but not so much that you can't figure out how to write a proof in Fitch after reading this one.  The basic plan of this proof goes to assume the negation of the desired conclusion.  Then, we'll show that Kpq will hold, by showing that p and q will hold.  We'll show that p and q hold respectively by showing that if we assume Np and Nq respectively, then we'll get a contradiction.  Then since we have p and q, we'll infer Kpq, and since we have NKpq upfront, this gives us a contradiction.  Since NANpNq was the last hypothesis in effect, this means we can eventually infer ANpNq.
The rules I'll use can get written as follows.
C-in: {$\alpha$, ..., $\beta$} $\vdash$ C$\alpha$$\beta$, where $\alpha$ and $\beta$ have the same scope.
A-in left: $\alpha$ $\vdash$ A$\alpha$$\beta$.
A-in right: $\alpha$ $\vdash$ A$\beta$$\alpha$.
K-in: {$\alpha$, $\beta$} $\vdash$ K$\alpha$$\beta$.
N-out: CN$\alpha$K$\beta$N$\beta$ $\vdash$ $\alpha$.
 1 assumption         NKpq
 2 hypothesis      !  NANpNq
 3 hypothesis      !@ Np
 4 3 A-in left     !@ ANpNq
 5 2, 4 K-in       !@ KANpNqNANpNq
 6 2-5 C-in        !  C Np KANpNqNANpNq
 7 6 N-out         !  p
 8 hypothesis      !# Nq
 9 8 A-in right    !# ANpNq
 10 9, 2 K-in      !@ KANpNqNANpNq
 11 8-10 C-in      !  C Nq KANpNqNANpNq
 12 11 N-out       !  q
 13 7, 12 K-in     !  Kpq
 14 1, 13 K-in     !  KKpqNKpq
 15 2-14 C-in         C NANpNq KKpqNKpq
 16 15 N-out          ANpNq.

