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. Feb 9, 2010 #1
    1. The problem statement, all variables and given/known data
    I am new at logic and i'm stuck on a problem set:
    a)[tex] (~C \vee (A \cap B)) \vdash ((~C \vee A)\cap (~C \vee B))[/tex]
    b)[tex] \vdash ((A\cap B) \leftrightarrow (B^A))[/tex]
    c)[tex] \vdash (((A \rightarrow B) \rightarrow C) \rightarrow (A \rightarrow (B \rightarrow C)))[/tex]
    d)[tex] ((A \rightarrow B) \rightarrow C), ~C \vdash ~A[/tex]
    e)[tex] \vdash (~~~A \vee ~~~~A)[/tex]
    f)[tex] \vdash ((A \rightarrow B) \vee (B \rightarrow A))[/tex]
    g)[tex] \vdash ((A\cap C) \rightarrow B)[/tex]
    h)[tex] (A \vee B) \vdash ~~(A \vee B)[/tex]
    i)[tex] (A \leftrightarrow B), ~B, (A \vee B) \vdash (C \rightarrow A)[/tex]
    j)[tex] ~(~A\cap ~B) \vdash (A \vee B)[/tex]

    2. Relevant equations
    Introduction and elimination riles in SL

    3. The attempt at a solution
    I am new at this but I've done some and stuck on others. Please see attached picture since I don't know how to type derivations with latex.

    Last edited by a moderator: Apr 24, 2017
  2. jcsd
  3. Feb 9, 2010 #2


    Staff: Mentor

    These are 10 separate problems, right?

    Most of the people here on this forum at pretty sharp at logic, but probably more along the lines of mathematical logic, which uses some different symbols.

    What does this symbol--[itex]\vdash[/itex]--mean? Implies?

    Also, your ~ symbols are not rendering. Here's problem a with what I think you mean.
    [tex] (\neg C \vee (A \wedge B)) \vdash ((\neg C \vee A) \wedge (\neg C \vee B))[/tex]

    And what does BA mean?
  4. Feb 9, 2010 #3
    The symbol [itex]\vdash[/itex] means deducibility (the expression on the right may be deduced from the one at the left, by application of the rules), but some of the formulas don't make sense, and I can't open your links either: I just get an error message.

    Just one more question, by "SL" you mean sequents, not natural deduction? (They are different.)
  5. Feb 9, 2010 #4
    Sorry the latex is not picking up my "ands" the attached pictures should be more clear.
  6. Feb 10, 2010 #5
    ok, everything is fixed. v stands for or
  7. Apr 16, 2010 #6
    Hey..Im new to this as well and have a few problems to solve. Any chance you guys could help?

    1) AvB, 2) ~A, derive B
    1) H(I&J), derive HI
    1) AB, 2) ~(~B&~C)E, derive AE
    1) ~A, 2) ~AZ, 3) QZ, 4) (Q&~A)M, derive M

    The  represents a conditonal
  8. Apr 16, 2010 #7
    Ah... I asked the question half a semester ago and now I got it all figured out.
  9. Apr 16, 2010 #8
    First let me ask you do u know the format of natural deduction? Do you know the rules of natural deduction?
  10. Apr 16, 2010 #9
    For the 1st one, will u understand if i write:

    1 1.(AvB) A
    2 2.~A A
    1,2 3.B 1,2 vE q.e.d.

    And the 2nd:

    1 1.(H->(I&J)) A
    2 2.H A
    1,2 3.(I&J) 1,2 ->E
    1,2 4.I 3 &E
    1 5.(H->I) 2,4 ->I q.e.d.

    Do u understand what I'm doing and the SL rules that i'm using?
  11. Apr 16, 2010 #10


    Staff: Mentor

    It is considered "hijacking a thread" and therefore bad manners to tack a different question onto an existing thread. There's a button labelled New Thread that you can use to start (surprise, surprise!) a new thread.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook