Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Symbolic Logic: Theorem In SD

  1. Mar 10, 2004 #1

    I am doing some exercises in my symbolic logic text as review and I came across the following question:

    I am having no trouble in deriving other theorems in SD but this one eludes me.

    Any help / hints would be appreciated.

  2. jcsd
  3. Mar 11, 2004 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I usually enjoy these types of problems!

    Can you link me (or write down) the list of axioms you can use?
  4. Mar 11, 2004 #3
    Yes. I don't mind doing these either.

    As for a link I have none. 8(

    But you can use the following:

    Conjunction Elimination and Introduction
    Disjunction Elimination and Introduction
    Conditional Elimination and Introduction
    Negation Elimination and Introduction
    Biconditional Elimination and Introduction



    If you need further clarification please ask.

  5. Mar 11, 2004 #4


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Yah, clarification is good. I need to see exactly what I'm allowed to use so I don't slip in details which aren't allowed.

    Now, when you say you want to prove it's a theorem, I presume you want to deduce it from the rules of deduction? (As oppose to, say, proving that it evaluates to true for any truth assignment)
  6. Mar 11, 2004 #5
    Well, by definition in my text, a sentence P of sentential logic is a theorem in sentential derivation if and only if P is derivable in sentential derivation from the empty set.

    So by making certain assumptions, can you derive the sentence P using the rules of sentential derivation?

    Here is the text that we are using in my philosophy class of symbolic logic just in case you are interested.

    http://www.mhhe.com/wmg/bergmann/book/contents.mhtml [Broken]

    Rules of SD:


    Given P then P.

    Conjunction Introduction

    Given P and P then P&Q.

    Conjunction Elimination

    Given P&Q then P. Or given P&Q then Q.

    Disjunction Introduction

    Given P then PvQ. Or given P then QvP.

    Disjunction Elimintion

    Given PvQ first assume P then arrive at R. Then assume Q and arrive at R. Then R by elimination of the disjunction.

    Conditional Introduction

    Assume P then arrive at Q. Then P implies Q.

    Conditional Elimination

    Given P implies Q, and given P, then Q.

    Biconditional Introduction

    Assume P then arrive at Q. Then assume Q and arrive at P. Therefore P iff Q.

    Biconditional Elimination

    Given P iff Q and given P then Q. Or given P iff Q and given Q then P.

    Negation Introduction

    Assume P. Then derive Q. Then derive ~Q. Therefore ~P.

    Negation Elimination

    Assume ~P. Then derive Q. Then dervie ~Q. Therefore P.

    These are the rules of SD. I know its not too clear but that is the best I can do for now.

    8| ...?
    Last edited by a moderator: May 1, 2017
  7. Mar 11, 2004 #6


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Here is your hint: Assume ~(P v ~P)
    Full proof below. Don't look! Try it yourself! :smile:

    Whoops, there's another hint first.
    Now, the full proof is below for real! Don't look. :smile:
    Assume ~(P v ~P)
    Assume P

    Assume ~(P v ~P)
    __Assume P
    __Then P v ~P
    __But ~(P v ~P)
    Therefore ~P
    __Assume ~P
    __Then P v ~P
    __But ~(P v ~P)
    Therefore P
    Therefore (P v ~P)

    (Underlines are for formatting)
    Last edited: Mar 11, 2004
  8. Mar 11, 2004 #7
    How did you get to

    Therefore (P v ~P)?

    I think I follow: It seems like you are doing two negation elimination claims with a negation introduction claim as well.

    Is this what you are doing?

    Assume ~(P v ~P)
    __Assume P
    __Then P v ~P (by line 2: disjunction introduction).
    __But ~(P v ~P) (by line 1: repetition).
    Therefore ~P (lines 2-4: negation introduction).
    __Assume ~P
    __Then P v ~P (by line 6: disjunction introduction).
    __But ~(P v ~P) (by line 1: repetition).
    Therefore P (by lines 6-8: negation elimination).
    Therefore (P v ~P) (by lines 5,9: negation elimination).

    I knew that I had to arrive at a contradiction somewhere to get the conclusion, but I never thought of deriving ~P and P through contradiction. In fact, even after you showed my your proof I had a bit of a time following what you were doing. But I think I got it now.

    Thanks Hurkyl.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook