Results 1 to 6 of 6

Math Help - Logic: Given ((p^段)v(殆^q)) |- (p v q)

  1. #1
    Junior Member
    Joined
    Jul 2011
    Posts
    26

    Logic: Given ((p^段)v(殆^q)) |- (p v q)

    Hi,

    I am trying to answer the following exam question:
    Let \theta be ((p\wedge\neg q)\vee(\neg p\wedge q)).
    Show that \theta\vdash(p\vee q) but that neither \theta\vdash p nor \theta\vdash q

    (Note: this question is using Propositional logic)

    My current attempt is this:
    1. Given ((p\wedge\neg q)\vee(\neg p\wedge q))
    2. Assume \neg (p \vee q)
    3. Assume p
    4. Using "OR introduction" (p \vee q)
    5. Contradiction in lines 2 and 4
    6. Derive \neg p using Reductio Ad Absurdum
    7. Assume q
    8. Using "OR introduction" (p \vee q)
    9. Contradiction in lines 2 and 8
    10. Derive \neg q using Reductio Ad Absurdum
    11. Using "AND introduction" (\neg p \wedge \neg q)

    I'm not sure where to go from here.

    Can anyone help?

    Thanks
    Last edited by dwally89; April 11th 2012 at 05:59 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    773

    Re: Logic: Given ((p^段)v(殆^q)) |- (p v q)

    It's simpler to have a direct proof rather than a proof by contradiction. You need to apply disjunction elimination (reasoning by cases) to (p\wedge\neg q)\vee(\neg p\wedge q). If p\wedge\neg q holds, then p and so p\lor q. The other case is similar.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jul 2011
    Posts
    26

    Re: Logic: Given ((p^段)v(殆^q)) |- (p v q)

    I'm not sure if we're allowed to reason by cases in the exam.
    The rules that we're allowed to use are:
    1. (Given Statements Rule) Any \sigma \in \Sigma may be deduced from \Sigma in one step
    2. (Top Rule) The statement \top may be deduced from any \Sigma in one step
    3. ( \wedge-Introduction) If \sigma and \tau have been derived from \Sigma then (\sigma \wedge \tau) may be deduced from \Sigma in one further step
    4. ( \vee-Introduction) If \tau has been deduced from \Sigma then either (\sigma \vee \tau), (\tau \vee \sigma) may be deduced from \Sigma in one further step
    5. ( \wedge-Elimination) If (\sigma \wedge \tau) has been deduced from \Sigma the either \sigma or \tau may be deduced from \Sigma in one further step
    6. ( \vee-Elimination) If (\sigma \vee \tau) and \neg \sigma have been deduced from \Sigma then \tau may be deduced from \Sigma in one further step
    7. ( \neg-Elimination) If \neg \neg \sigma has been deduced from \Sigma then \sigma may be deduced from \Sigma in one further step
    8. (Contradiction Rule) If \sigma and \neg \sigma have been deduced from \Sigma then \bot may be deduced from \Sigma in one further step
    9. (Reductio Ad Absurdum Rule) If \bot has been deduced from \Sigma \union {\sigma } then \neg \sigma may be deduced from \Sigma in one further step

    Using these rules, could you possibly suggest how to approach the proof?

    Thanks
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    773

    Re: Logic: Given ((p^段)v(殆^q)) |- (p v q)

    What you have listed as disjunction elimination is in fact disjunctive syllogism, or modus tollendo ponens. A more standard disjunction elimination rule has the form



    (taken from the book "Proofs and Types" by Girard, Lafont, Taylor, p. 72). This rule can be simulated in your system as follows.



    Numbers in parentheses indicate where corresponding assumptions have been closed. Now you can proceed using reasoning by cases.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Jul 2011
    Posts
    26

    Re: Logic: Given ((p^段)v(殆^q)) |- (p v q)

    Quote Originally Posted by emakarov View Post
    What you have listed as disjunction elimination is in fact disjunctive syllogism, or modus tollendo ponens. A more standard disjunction elimination rule has the form



    (taken from the book "Proofs and Types" by Girard, Lafont, Taylor, p. 72). This rule can be simulated in your system as follows.



    Numbers in parentheses indicate where corresponding assumptions have been closed. Now you can proceed using reasoning by cases.
    I'm not too sure I understand what you said, but I think I may have derived a proof as follows:

    1. Given ((p \wedge \neg q) \vee ( \neg p \wedge q))
    2. Assume \neg (p \vee q)
    3. Assume p
    4. \vee-Introduction (p \vee q)
    5. \bot from lines 2 and 4
    6. \neg p by RAA
    7. Assume (p \wedge \neg q)
    8. p by \wedge-Elimination
    9. \bot from lines 6 and 8
    10. \neg (p \wedge \neg q) by RAA
    11. (\neg p \wedge q) by \vee-Elimination on lines 1 and 10
    12. q by \wedge-Elimination
    13. (p \vee q) by \vee-Introduction
    14. \bot from lines 2 and 13
    15. (p \vee q) by RAA

    How does this seem to you?

    Thanks
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    773

    Re: Logic: Given ((p^段)v(殆^q)) |- (p v q)

    Quote Originally Posted by dwally89 View Post
    How does this seem to you?
    Not bad. Strictly speaking, you need to first derive \neg\neg(p\lor q) using RAA in step 15 and then derive p\lor q using \neg-Elimination.

    Quote Originally Posted by dwally89 View Post
    I'm not too sure I understand what you said
    I think that tree representations of derivations are much simpler to understand than Fitch-style text that you are using. One writes premises above the line and the conclusion below the line. For example, \wedge-Introduction looks like

    \frac{\sigma\qquad\tau}{\sigma\land\tau}

    I used vertical dots \vdots to hide some subderivations in post #4.

    Your derivation can be simplified a little. In steps 2-9 you derive \bot from \neg(p\lor q) and p\land\neg q (left picture):



    You can move the subderivation \frac{p\land\neg q}{p} as the arrow shows to get a shorter derivation on the right. If the result is substituted into your complete derivation, then you get exactly the picture from post #4 where A = p\land\neg q, B = \neg p\land q and C = p\lor q.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Can someone check my logic (sentential logic)
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: July 13th 2010, 03:30 AM
  2. logic
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 2nd 2009, 09:24 AM
  3. logic
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 2nd 2008, 11:53 PM
  4. Logic
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: September 27th 2008, 01:52 PM
  5. Logic
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: September 12th 2007, 05:05 PM

Search Tags


/mathhelpforum @mathhelpforum