# Proving ${\sim p}\mid{\sim q}$ implies ${\sim}(p \mathbin\& 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?

• Is $\mid$ the Sheffer stroke? Doesn't seem so. Do you mean $\lor$ instead of $\mid$? – Git Gud Oct 16 '13 at 12:35
• Yes, what I meant is ∨. – user2885820 Oct 16 '13 at 12:59

I'll have my first stab at an answer here (I've been won over from Stack overflow- first answer!).

I believe on math.stackexchange it's not tradition to completely give the game away if it's a homework question?

notation: noticed you're using single bar for vel, I'll use $\vee$ and "|" to distinguish Fitch hypothesis marks until I can work out math stackexchange formatting.

So, Hint: your last step will be $¬(p \wedge q)$, of course, and obviously your first

1 $(¬p \vee ¬q)$

Then we prove by two classical reductio. First, on the conclusion

2 | $p \wedge q$

Which gives us

3 | $p$

Then, remember the $\vee$-elim rules (you're working from (1) now): so we assume:

4 | | $¬p$

5 | | $\bot$(by 3)

Well, I'll leave you to fill in the details, but we can do the same for the q side of 2 and 1.

This means we can $\vee$ eliminate to

9) | $\bot$

Which gives us the discharge by reductio of (2)

10) $¬(p \wedge q)$

Hope this helps you fill in the minimal gaps.

If you wanted to cheat you could have a look at de morgan's laws as you're going one way here, or ask whether you can prove this in all logics.

Apologies for my first attempt at formatting, I'll try to edit as I go

• +1 Welcome! You're correct on the treatment of homework. You're not the first one having difficulty with natural deduction proofs: see this meta thread. – Lord_Farin Oct 16 '13 at 12:58
• Thank you for the hint. I have graduated a long time ago so it is definitely not a homework. I am just studying some logic and found myself stuck with that problem. – user2885820 Oct 16 '13 at 13:02
• Thanks Lord_Farin. What an agreeable and pleasant place! Good luck with the problem OP, I too graduated recently and miss it sorely! – Tom Oct 16 '13 at 13:26

I came up with the same derivation (see Tom's answer), but it's in a different format, so might be of some tiny use to the OP: 