1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Natural deduction

  1. Aug 31, 2014 #1
    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.
    Please help!!!
    1. The problem statement, all variables and given/known data

    2. Relevant equations

    3. The attempt at a solution
  2. jcsd
  3. Aug 31, 2014 #2
    To prove DeMorgan's Law, you might want to write out a truth table.
  4. Aug 31, 2014 #3
    It's also helpful to note that:

    [itex] p \implies q \equiv \neg p \vee q [/itex]
  5. Sep 1, 2014 #4


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted