Results 1 to 8 of 8

Math Help - Beginning Student in Propositional Logic: Problems Working Through Three Proofs

  1. #1
    Newbie
    Joined
    Feb 2008
    Posts
    10

    Beginning Student in Propositional Logic: Problems Working Through Three Proofs

    I'm new to propositional logic and I've been struggling to find justifications for these three proofs. Can anyone help?

    _____________________________

    1. A

    Therefore, B ⊃ (~ A ⊃ C)

    Prove valid using only the rule of inference and the rules of replacement (cannot use Conditional or Indirect Proofs)

    Here’s how I have it done right now:

    1. A
    2. A v (C v ~B) 1 Add
    3. (C v ~B) v A 2 Comm
    4. C v ( ~B v A) 3 Assoc
    5. ( ~B v A) v C 4. Comm
    6. (~B v ~ ~A) v C 5. DN
    7. ~ (B • ~A) v C 6. DeM
    8. (B • ~A) ⊃ C 7. Cont
    9. B ⊃ (~A ⊃ C) 8. Exp

    I ended up working backwards on this proof which explains why each justification derives from the preceding line. I don't see anything wrong with my justifications (though if there is please correct me), but I'm wondering if there is a more eloquent way to do this proof. Also, say I didn't want to work backwards. Obviously I would have to start with an Addition, but how would I go about choosing what to add to A?
    ______________________________

    1. A v B
    2. C ⊃ ~ A
    3. D ⊃ E
    4. ~ D ⊃ C
    5. E ⊃ ~ A

    Therefore, B

    Prove valid using any of the rules of deductive logic
    _____________________________________

    ~(~ T ⊃ ~ R) , ~ S v T , R ≡ S

    Using Natural Deduction demonstrate that the following set of statements are inconsistent.
    Last edited by coach2uf; October 29th 2010 at 09:28 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    What does



    stand for? Material implication?

    /

    What rules of replacement? Different textbook authors have different rules.

    /

    What "any" rules of deductive logic? Here's a rule of deductive logic:

    If a formula B is a tautological consequence of a finite set of formulas G, then from G we may infer B.

    So, since B is a tautological consequence of G = {AvB, C->~A, D->E, ~D->C, E->~A} we have that G proves B.

    If you wish to see some easy reasoning though:

    Since AvB, we only need to show ~A.
    E implies ~A, so we only need to show also ~E implies ~A.
    But D implies E, so ~E implies ~D, so, since ~D implies C, and C implies ~A, we have ~E implies ~A

    /

    What specific system of natural deduction?

    Anyway, here's some basic reasoning:

    Suppose ~(~T -> ~R).
    So ~T & R.
    Suppose R <-> S.
    So S.
    Suppose ~S v T
    So T, which provides a contradiction.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Feb 2008
    Posts
    10
    ⊃ is the material implication. I'll start using -> in its place to avoid confusion.

    Rules of Replacement are as follows:
    Double Negation
    DeMorgan's Theorem (two variations)
    Commutation (two variations)
    Association (two variations)
    Distribution (two variations)
    Contraposition
    Implication
    Exportation
    Tautology
    Equivalence

    Valid Argument Forms of Inference:
    Modus Ponens
    Modus Tollens
    Disjunctive Syllogism (two variations)
    Simplification
    Conjunction
    Hypothetical Syllogism
    Addition
    Constructive Dilemma
    About the specific system of Natural Deduction, I'm not sure. I typed exactly what it said on the sheet, though I assume it means use any of the ways of natural deduction emphasized in this section (the rules of replacement, valid argument forms of inference, and of conditional and implied proofs)
    Last edited by coach2uf; October 29th 2010 at 06:37 PM. Reason: Added Valid Argument Forms of Inference
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    For your own sake, you need to write out, for yourself, each rule specifically, and understand why each one is valid.

    And what is the difference in this system between conditional proof and implied proof? And does this system have any rules for indirect proof (sometimes called 'proof by contradiction'), and are there variations?

    What is the rule in this system for putting a premise on a line?

    DeMorgan's has two allowed variations?

    Equivalence has two allowed variations?

    And there is no rule of simplification for conjunctions?

    And there is no rule of addition for disjunctions? And no other rules for disjunctions?

    You need to be crystal clear about these things.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,966
    Thanks
    1785
    Awards
    1
    Quote Originally Posted by coach2uf View Post
    1. A
    Therefore, B ⊃ (~ A ⊃ C)
    Prove valid using only the rule of inference and the rules of replacement (cannot use Conditional or Indirect Proofs)

    Here’s how I have it done right now:

    1. A
    2. A v (C v ~B) 1 Add
    3. (C v ~B) v A 2 Comm
    4. C v ( ~B v A) 3 Assoc
    5. ( ~B v A) v C 4. Comm
    6. (~B v ~ ~A) v C 5. DN
    7. ~ (B • ~A) v C 6. DeM
    8. (B • ~A) ⊃ C 7. Cont
    9. B ⊃ (~A ⊃ C) 8. Exp

    I ended up working backwards on this proof which explains why each justification derives from the preceding line. I don't see anything wrong with my justifications (though if there is please correct me), but I'm wondering if there is a more eloquent way to do this proof. Also, say I didn't want to work backwards. Obviously I would have to start with an Addition, but how would I go about choosing what to add to A?
    ______________________________

    1. A v B
    2. C ⊃ ~ A
    3. D ⊃ E
    4. ~ D ⊃ C
    5. E ⊃ ~ A

    Therefore, B

    Prove valid using any of the rules of deductive logic
    _____________________________________

    ~(~ T ⊃ ~ R) , ~ S v T , R ≡ S

    Using Natural Deduction demonstrate that the following set of statements are inconsistent.
    This is Copi's notation he learned from Russel.
    You fine in below.
    1. A
    2. A v (C v ~B) 1 Add
    3. (C v ~B) v A 2 Comm
    4. C v ( ~B v A) 3 Assoc
    5. ( ~B v A) v C 4. Comm
    6. ~B v (A v C) 5. Assoc
    7, B ⊃ (~A ⊃ C) 6. Impl (twice)
    Last edited by Plato; October 30th 2010 at 08:13 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    ~(~ T ⊃ ~ R) , ~ S v T , R ≡ S

    Using Natural Deduction demonstrate that the following set of statements are inconsistent.
    You mean the preceding set of statements?

    The derivation depends on whether ~ is taken as a primitive connective or if ~A is a contraction for A -> _|_, where _|_ denotes contradiction. I'll assume the latter, but it should not be too hard to change the derivation to the former style.

    It is sufficient to show ~ S v T , R ≡ S |- ~ T ⊃ ~ R. So, assume ~T and R; one has to show _|_. Do reasoning by cases on ~ S v T. If T, then T and ~T give _|_. If ~S, then the assumption R together with R ≡ S give S, so again one has _|_.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by Plato View Post
    Copi's
    Oh, okay, then cancel my admonishment to the poster.

    But it would be helpful for posters to specify, such as saying "System found in Copi's 'Symbolic Logic' 4th edition" or whatever, so that it is clear exactly the rules and their exact formulation.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by emakarov View Post
    The derivation depends on whether ~ is taken as a primitive connective or if ~A is a contraction for A -> _|_, where _|_ denotes contradiction. I'll assume the latter
    In Copi, '~' is primitive.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Propositional Logic
    Posted in the Discrete Math Forum
    Replies: 12
    Last Post: June 1st 2011, 04:22 PM
  2. Book recommendation for beginning statement logic?
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 26th 2011, 03:18 AM
  3. Replies: 1
    Last Post: October 25th 2010, 03:37 AM
  4. Help with a few propositional logic proofs
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: February 10th 2009, 07:27 PM
  5. propositional logic
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: June 10th 2007, 10:50 AM

Search Tags


/mathhelpforum @mathhelpforum