Use the rules of natural deduction to prove the therem of Disjunctive Syllogism: ((P or Q) & ~ P) => Q

Step

Rule Applied

1

H1: (P or Q) & ~P

Start of first level hypothesis.

2

P or Q

Disjunction elimination from step 1.

3

~P

Disjunction elimination from step 2.

4

H.2: P

Start of second level hypothesis.

5

H3: ~Q

Start of third level hypothesis. We are seeking a contradiction.

6

P & ~P

Conjunction introduction from steps 3, 4

7

contradiction

8

-H3: ~~Q

Reductio ad absurdum. End of third level hypothesis from step 5.

9

Q

Negation elimination from step 8. i.e. ~(~Q) <=> Q

10

-H2: P => Q

Conditional Proof. End of second level hypothesis from step 4.

11

H2: Q

Start of new second level hypothesis.

12

H2: Q => Q

Conditional Proof. End of second level hypothesis from step 11.

13

P => Q

Repeat from step 10.

14

Q => Q

Repeat from step 12.

15

P or Q

Repeat from step 2.

16

Q

Disjunction elimination from steps 13, 14, 15.

i.e. [(A or B) & (A => C) & (B => C)] => C

17

-H1: ((P or Q) & ~P) => Q

Conditional Proof from steps 1, 2 to 17. End of first level hypothesis.

((P

or

Q)

&

~

P)

=>

Q

1

1

1

0

0

1

1

1

0

1

1

1

1

0

1

1

1

1

0

0

0

1

1

0

0

0

0

0

1

0

1

0