1. Not finding help here? Sign up for a free 30min 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!

Sentential logic derivations?

  1. Nov 19, 2009 #1
    how do i prove the following is a theorem in SD
    [(A -> B)->A]->A
    ... i started off by assuming [(A -> B)->A] then assume ~A to try to derive A in the end... but now i'm stuck :(

    and also:

    Suppose we dropped from SD the rule for vE, and adopted in its place the rule of Disjunctive Syllogism (DS), thus giving a modified system SD. Show that
    you can derive the SD rule for vE in SD.

    I have no idea how to even approach the second question.. any help would be greatly appreciated.. thanks! :D
     
  2. jcsd
  3. Nov 19, 2009 #2

    sylas

    User Avatar
    Science Advisor

    I am pretty sure this should be in the homework section, and have requested it to be moved. But in any case, it would be a good idea to use the homework template to show your work so far. The template requests you to provide the following sections:

    1. The problem statement, all variables and given/known data

    2. Relevant equations

    3. The attempt at a solution

    You should also describe your terms. I am pretty sure you must be using the text book The Logic Book by Bergmann, Moor and Nelson, or something like it. Sentential logic is often also called propositional logic. There are a number of different equivalent proof systems for SL, or PL. Your reference to SD is probably the "Derivation System" described in chapter 5. This proof system has rules for "introduction" and "exit" of the various connectives. Is that correct?

    "Disjunctive syllogism" (DS) is an additional rule that you can add to the system SD, which still proves all the same theorems, but lets you do so faster and more easily. The second question asks if you can derive the rule for "or Exist" (vE) by using SD+DS-vE.

    If I have understood the context of your question, and if you can show a bit more about what you have done so far, we may be able to help.

    Cheers -- sylas
     
  4. Nov 21, 2009 #3
    I get the feeling that I am in this person's class. If so here is the question:

    Suppose we dropped from SD the rule for vE (Disjunction Elimination), and adopted in its place the rule of Disjunctive Syllogism, thus giving a modified systemd of SD*. Show that you can derive the SD rule for vE in SD*.

    All terms come from the Bergmann Logic Book. All the basic Derivation rules can be used except vE (duh). Furthermore, Modus Tollens, Hypothetical Syllogism and Disjunctive Syllogism can be used as well as what the book describes as Rules of Replacement. The rules of Replacement concern how certain things such as P -> Q can be replaced by ~P v Q. Essentially, they are all the logical equivalences that exist in SD.

    There is nothing more to the question but I'm not going to add a solution because I feel obliged not to give away answers to people I'm actually in a class with. I'm sure you guys can do it and save me my conscience.
     
  5. Nov 21, 2009 #4
    Since he already made an attempt to find the solution to the first question I'm going to help out and post my answer for you guys to help me out and him at the same time.

    Question: Show that [(A -> B) -> A] -> A is a theorem of SD.

    Relevant Equations: All rules of SD found in the Logic Book. This includes all the ones in the above post BUT vE is not excluded.

    The Attempt at a Solution:

    1. [(A -> B) -> A] Assume
    2. ~A Assume
    3. ~(A->B) Modus Tollens from 1,2
    4. ~(~AvB) Implication from 3
    5. ~~A & ~B De Morgan from 4
    6. ~~A & Elimination from 5
    7. A Double Negation from 6
    8. ~A Reiteration from 2
    9. A ~ Elimination from 2-8
    10. [(A -> B) -> A] -> A -> Introduction from 1, 9

    Since this began with an empty set the final result must be a theorem of SD.
     
  6. Nov 21, 2009 #5
    Since he already made an attempt to find the solution to the first question I'm going to help out and post my answer for you guys to help me out and him at the same time.

    Question: Show that [(A -> B) -> A] -> A is a theorem of SD.

    Relevant Equations: All rules of SD found in the Logic Book. This includes all the ones in the above post BUT vE is not excluded.

    The Attempt at a Solution:

    1. [(A -> B) -> A] Assume
    2. ~A Assume
    3. ~(A->B) Modus Tollens from 1,2
    4. ~(~AvB) Implication from 3
    5. ~~A & ~B De Morgan from 4
    6. ~~A & Elimination from 5
    7. A Double Negation from 6
    8. ~A Reiteration from 2
    9. A ~ Elimination from 2-8
    10. [(A -> B) -> A] -> A -> Introduction from 1, 9

    Since this began with an empty set the final result must be a theorem of SD.
     
  7. Nov 22, 2009 #6
    Knark's solution makes use of SD+ concepts (e.g. Modus Tollens.)

    Since the answer asks for the use of SD, are we to assume that such a concepts of SD+ may be cited, without requiring the appropriate subderivation?
     
  8. Nov 22, 2009 #7
    Well every thing that can be done using SD+ can also be done using SD, it would simply take a little more time. But I believe you are right and that it should be done in only SD so I will rework it. Thanks for catching that.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook