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!

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

    andrewkirk

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Natural deduction
  1. Logic Deduction (Replies: 1)

  2. Natural Deduction (Replies: 9)

Loading...