# Homework Help: Natural deduction

1. Aug 31, 2014

### LauraSuh

Hello smart people!
I was having some troubles proving this derived rule using Natural deduction:

¬(∃y.Q(y) ∧ T(y))
------------------------
∀x.Q(x) → ¬ T(x)

I got stuck in the very first line, because of the "NOT". I can't do anything if I don't take it out of there...

I know that ¬(a ∧ b) = ¬a ∨ ¬b, but I don't know how to prove that as well....

If I could only get past this very first step I'd be able to finish it, but I've been trying for hours and I can't get around it.
1. The problem statement, all variables and given/known data

2. Relevant equations

3. The attempt at a solution

2. Aug 31, 2014

### Mogarrr

To prove DeMorgan's Law, you might want to write out a truth table.

3. Aug 31, 2014

### Mogarrr

It's also helpful to note that:

$p \implies q \equiv \neg p \vee q$

4. Sep 1, 2014

### andrewkirk

I would use the identity

$\exists x \phi\equiv \neg\forall x\neg\phi$ together with the theorem $\neg\neg\phi\leftrightarrow\phi$ and then de Morgan's Law.

If you need more help you will need to specify which Natural Deduction system you are using. There are many. To specify yours you need to list all the rules of inference and replacement rules you have available to you.