- #1

- 99

- 0

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]

- Thread starter Skomatth
- Start date

- #1

- 99

- 0

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

honestrosewater

Gold Member

- 2,105

- 5

ASkomatth said:Since this forum seems a little slow

I don't know what rules I can use (?), so if you want something, just ask. As much as I love it, [itex]\LaTeX[/itex] is taking forever, so: ~ = NOT; & = AND; v = OR; -> = IMPLIES.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]

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?

Last edited:

- #3

AKG

Science Advisor

Homework Helper

- 2,565

- 4

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

__Straightforward__
__A different way__
__Reductio__

Code:

```
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
```

Code:

```
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
```

Code:

```
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:

- #4

- 99

- 0

- #5

- 99

- 0

Code:

```
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}
```

- #6

AKG

Science Advisor

Homework Helper

- 2,565

- 4

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.

- #7

AKG

Science Advisor

Homework Helper

- 2,565

- 4

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 {

- #8

- 99

- 0

Code:

```
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
```

- #9

AKG

Science Advisor

Homework Helper

- 2,565

- 4

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.

- #10

- 99

- 0

- #11

AKG

Science Advisor

Homework Helper

- 2,565

- 4

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.