- #1

Skomatth

- 100

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

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter Skomatth
- Start date

- #1

Skomatth

- 100

- 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,136

- 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,566

- 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

Skomatth

- 100

- 0

- #5

Skomatth

- 100

- 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,566

- 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,566

- 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

Skomatth

- 100

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

Can anyone remind of the rule I forgot? I looked it up but couldn't find it.

- #9

AKG

Science Advisor

Homework Helper

- 2,566

- 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

Skomatth

- 100

- 0

- #11

AKG

Science Advisor

Homework Helper

- 2,566

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

Share:

- Replies
- 43

- Views
- 3K

- Replies
- 13

- Views
- 441

- Replies
- 6

- Views
- 358

- Last Post

- Replies
- 1

- Views
- 588

- Last Post

- Replies
- 11

- Views
- 1K

- Last Post

- Replies
- 2

- Views
- 791

- Replies
- 16

- Views
- 724

- Replies
- 1

- Views
- 178

- Replies
- 3

- Views
- 499

- Replies
- 9

- Views
- 909