Logic Q&A Game: Prove Argument w/ Reductio Ad Absurdum

[Skomatth]

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
<br /> 1. (A \supset (B \bullet C))
2. (B \supset (A \bullet C))
Therefore, ((A \vee B) \supset C)<br />

 

[honestrosewater]

Since this forum seems a little slow

A little slow?

Prove that this is a valid argument using reductio ad absurdum
<br /> 1. (A \supset (B \bullet C))
2. (B \supset (A \bullet C))
Therefore, ((A \vee B) \supset C)<br />

I don't know what rules I can use (?), so if you want something, just ask. As much as I love it, \LaTeX 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?

 

[AKG]

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

Straightforward

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

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

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)

 

[Skomatth]

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).

 

[Skomatth]

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}

 

[AKG]

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:

\{\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{]}

2. Show that the following is deductively inconsistent:

\{\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{]}\}

3. Prove:

\{(\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

I did what I could to ensure all the problems were legible, but ask for clarification if necessary.

 

[AKG]

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.

 

[Skomatth]

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).

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.

 

[AKG]

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.

 

[Skomatth]

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?

 

[AKG]

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.