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

Logic Q&A Game

  1. Sep 8, 2005 #1
    Since this forum seems a little slow, I propose a game. I'll post some sort of logic question (it can be symbolic or some sort of trivia about logic) and the next poster tries to answer. When s/he gets it correct, I'll verify that it was the answer I was looking for and then the poster gets to pose a question of his own. If using symbols please use Latex.

    Prove that this is a valid argument using reductio ad absurdum
    [tex]
    1. (A \supset (B \bullet C)) [/tex]
    [tex] 2. (B \supset (A \bullet C)) [/tex]
    [tex] Therefore, ((A \vee B) \supset C)
    [/tex]
     
  2. jcsd
  3. Sep 9, 2005 #2

    honestrosewater

    User Avatar
    Gold Member

    A little slow? :surprised
    I don't know what rules I can use (?), so if you want something, just ask. :smile: As much as I love it, [itex]\LaTeX[/itex] is taking forever, so: ~ = NOT; & = AND; v = OR; -> = IMPLIES.
    1) A -> (B & C) [premise]
    2) B -> (A & C) [premise]
    3) ~A v (B & C) [1]
    4) (~A v B) & (~A v C) [3]
    5) ~A v C [4]
    6) ~B v (A & C) [2]
    7) (~B v A) & (~B v C) [6]
    8) ~B v A [7]
    9)) (A v B) & ~C [assumption]
    10)) A v B [9]
    11)) ~C [9]
    12)) ~A [5, 11]
    13)) ~B [8, 12]
    14)) B [10, 12]
    15)) B & ~B [13, 14]
    16) ~((A v B) & ~C) [9, 15, reductio]
    17) ~(A v B) v ~~C [16]
    18) ~(A v B) v C [17]
    19) (A v B) -> C [18, QED]

    Wow, I must be getting rusty - that seems too long. The thing to notice is that A <-> B. Maybe I should have used that. Meh. I don't think I made any mistakes, at least. This isn't homework, is it? :wink:
     
    Last edited: Sep 9, 2005
  4. Sep 9, 2005 #3

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    Using Reductio ad Absurdum? Okay, but the straightforward proof is much faster. I'll give both proofs:

    Straightforward
    Code (Text):
    1  | (A > (B & C))                Premise
    2  | (B > (A & C))                Premise
       |----------------------------
    3  || (A v B)                     Assumption
       ||---------------------------
    4  ||| A                          Assumption
       |||--------------------------
    5  ||| (B & C)                    1, 4 Conditional Elimination
    6  ||| C                          5 Conjunction Elimination
       ||
    7  ||| B                          Assumption
       |||--------------------------
    8  ||| (A & C)                    2, 7 Conditional Elimination
    9  ||| C                          8 Conjunction Elimination
    10 || C                           3, 4-6, 7-9 Disjunction Elimination
    11 | ((A v B) > C)                3-10 Conditional Introduction
    A different way
    Code (Text):
    1  | (A > (B & C))                Premise
    2  | (B > (A & C))                Premise
       |----------------------------
    3  || ~C                          Assumption
       ||---------------------------
    4  || ~C v ~B                     3 Disjunction Introduction        
    5  || ~(B & C)                    4 DeMorgan's, Commutativity
    6  || ~A                          1, 5 Modus Tollens
    7  || ~C v ~A                     3 Disjunction Introduction
    8  || ~(A & C)                    7 DeMorgan's, Commutativity
    9  || ~B                          2, 8 Modus Tollens
    10 || (~A & ~B)                   6, 9 Conjunction Introduction
    11 || ~(A v B)                    10 DeMorgan's
    12 | (~C > ~(A v B))              3-11 Conditional Introduction
    13 | ((A v B) > C)                12 Transposition
    Reductio
    Code (Text):
    1  | (A > (B & C))                Premise
    2  | (B > (A & C))                Premise
       |----------------------------
    3  || ~((A v B) > C)              Assumption
       ||---------------------------
    4  || ((A v B) & ~C)              3 Implication, DeMorgan's, Double Negation
    5  || (~(A > C) v ~(B > C))       4 Dist, DeM, DN, Impl
    6  ||| A                          Assumption
       |||--------------------------
    7  ||| (B & C)                    1, 6 Conditional Elimination
    8  ||| C                          7 Conjunction Elimination
    9  || (A > C)                     6-8 Conditional Introduction
    10 ||| B                          Assumption
       |||--------------------------
    11 ||| (A & C)                    2, 10 Conditional Elimination
    12 ||| C                          11 Conjunction Elimination
    13 || (B > C)                     10-12 Conditional Introduction
    14 || ~((A > C) & (B > C))        5 DeMorgan's
    15 || ((A > C) & (B > C))         9, 13 Conjunction Introduction
    16 | ((A v B) > C)                3-15 Negation Elimination (Reductio)
     
    Last edited: Sep 9, 2005
  5. Sep 9, 2005 #4
    I'll have to give this one to AKG, although Honestrosewater's proof is correct. It was my impression that RAA proofs start by assuming the opposite of the conclusion. Honestrosewater's assumption is entailed by the negation of the conclusion by using only one inference rule, but since he didn't directly assume the negation his proof wasn't what I was looking for. A lot of logic books are different though and since he used a reductio rule his still could be correct. The little logic I know is self-taught. I'll post how I did it in a second as soon as I figure out how to use the code in AKG's post. (You're right, Latex is annoying for this).
     
  6. Sep 9, 2005 #5
    Code (Text):

    1| (A>(B&C))                 {Premise}

    2| (B>(A&C))                 {Premise}

    3|| ~((AvB)>C)              {Assumption}

    4||  (AvB)                     {from 3}

    5||  ~C                        {from 3}

    6||| A                          {Assumption}

    7||| (B&C)                    {From 6 and 1}

    8||| C                          {from 7}

    9|| ~A                         {from 6; 8 contradicts 5}

    10|| B                          {from 9 and 4}

    11|| (A&C)                    {from 10 and 2}

    12|| A                          {from 11}

    13| ((AvB)>C)                {from 3; 12 contradicts 9}

     
     
  7. Sep 9, 2005 #6

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    It's hard to find a good problem from an elementary course in logic, especially since I don't have any of the notes and never bought the book, but I found some practice problems I did, hopefully these will provide a sufficient challenge.

    1. Prove that:

    [tex]\{\mathbf{[}([X \wedge Z] \wedge Y) \vee (\neg X \supset \neg Y)\mathbf{]},\, \mathbf{[}X \supset Z\mathbf{]},\, \mathbf{[}Z \supset Y\mathbf{]}\} \vdash \mathbf{[}X \equiv Y\mathbf{]}[/tex]

    2. Show that the following is deductively inconsistent:

    [tex]\{\mathbf{[}(\exists x)(\exists y)Fxy\, \vee \, (\forall x)(\forall y)(\forall z)Hxxyz\mathbf{]},\, \mathbf{[}(\exists x)(\exists y)Fxy \supset \neg Haaab\mathbf{]},\, \mathbf{[}(Hbbba\, \vee \, \neg Haaab)\equiv (\forall x)\neg (Ax\, \vee \, \neg Ax)\mathbf{]}\}[/tex]

    3. Prove:

    [tex]\{(\forall x)[(Fx\, \wedge \, \neg Kx) \supset (\exists y)([Fy\, \wedge \, Hyx]\, \wedge \, \neg Ky)],\, \mathbf{[}(\forall x)([Fx\, \wedge \, (\forall y)([Fy\, \wedge \, Hyx] \supset Ky)]\supset Kx)\supset M\mathbf{]}\} \vdash M[/tex]

    I did what I could to ensure all the problems were legible, but ask for clarification if necessary.
     
  8. Sep 9, 2005 #7

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    Hints (in white, only highlight if needed):

    1. Actually, this one is easy, I don't know why I put it. I can't think of a hint that doesn't give it away, so only readi this hint if you really need it. Prove that X > Y using hypothetical syllogism, prove that Y > X using disjunction elimination and the first premise.

    2. Start by looking at the right half of the third sentence in the set.

    3. Basically, you're proving that {P, (Q > M)} entails M. This is easy if you can prove that P > Q. The P and Q we're dealing with are sort of ugly, but if you can concentrate on the important information you will be able to see that they are in fact equivalent.
     
  9. Sep 10, 2005 #8
    I'll take #1. Are you using relations in 2 and 3? I'll admit I never studied those on my own(taking a logic course next semester).

    Code (Text):

    1|    (((X&Z)&Y)v(~X>~Y))   [premise]
    2|    (X>Z)                         [premise]
    3|    (Z>Y)                         [premise]
    4||   X                               [assumption]
    5||   Z                               [modus ponens; 4 and 2]
    6||   Y                               [modus ponens; 5 and 3]
    7|    (X>Y)                         [conditional proof; 4 and 6]
    8||   ~(~X>~Y)                  [assumption]
    9||   ~X                            [forgot the name;8]
    10||  Y                              [forgot;8]
    11||  ((X&Z)&Y)                  [disjunctive syllogism;8 and 1]
    12||  (X&Z)                        [simplification; 11]
    13||  X                              [simplification; 12]
    14|   (~X>~Y)                    [reductio;8, 13 contradicts 9]
    15|   (Y>X)                         [transposition; 14]
    16|   ((X>Y)&(Y>X))            [conjunction; 15 and 7]
    17|   (X_=Y)                       [biconditional introduction; 16
     
    Can anyone remind of the rule I forgot? I looked it up but couldn't find it.
     
  10. Sep 10, 2005 #9

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    That proof looks fine. Line 10 looks unnecessary. For lines 9 and 10, I don't know of any "rule" that let's you do that. It's four rules in one that you've used, as far as I can tell:

    Implication - ~(~X > ~Y) <> ~(~~X v ~Y)
    DeMorgan's - ~(~~X v ~Y) <> ~~~X & ~~Y
    Double Negation - ~~~X & ~~Y <> ~X & ~~Y
    Simplification - ~X & ~~Y :> ~X

    I don't know what you mean by using "relations" in 2 and 3. It's predicate logic.
     
  11. Sep 10, 2005 #10
    I've only seen predicate logic that has one variable after a general term like Fx, Gy, etc. What does it mean to have several variables after a general term?
     
  12. Sep 10, 2005 #11

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    A 1-place predicate can be thought of as a sentence with one thing removed, so you could have a predicate M defined by:

    Mx = x met John in New York

    You could have a 2-place predicate N defined by:

    Nxy = x met y in New York

    A 3-place predicate P:

    Pxyz = x met y in z

    I don't know if the above explanation will help you though, because I can't imagine that you could know the rules of inference required to do the proof but not have learned about predicates of several terms.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Logic Q&A Game
  1. Logic/Proof/Puzzle games (Replies: 101)

  2. Logic game (Replies: 1)

  3. That game (Replies: 16)

Loading...