How can you derive (P v ~P) in SD?

[wubie]

Hello,

I am doing some exercises in my symbolic logic text as review and I came across the following question:

Show that the following is a theorem in SD:

A v ~A

I am having no trouble in deriving other theorems in SD but this one eludes me.

Any help / hints would be appreciated.

Thankyou.

 

[Hurkyl]

I usually enjoy these types of problems!

Can you link me (or write down) the list of axioms you can use?

 

[wubie]

Yes. I don't mind doing these either.

As for a link I have none. 8(

But you can use the following:

Conjunction Elimination and Introduction
Disjunction Elimination and Introduction
Conditional Elimination and Introduction
Negation Elimination and Introduction
Biconditional Elimination and Introduction

and

Reiteration.

If you need further clarification please ask.

8)

 

[Hurkyl]

Yah, clarification is good. I need to see exactly what I'm allowed to use so I don't slip in details which aren't allowed.

Now, when you say you want to prove it's a theorem, I presume you want to deduce it from the rules of deduction? (As oppose to, say, proving that it evaluates to true for any truth assignment)

 

[wubie]

Well, by definition in my text, a sentence P of sentential logic is a theorem in sentential derivation if and only if P is derivable in sentential derivation from the empty set.

So by making certain assumptions, can you derive the sentence P using the rules of sentential derivation?

Here is the text that we are using in my philosophy class of symbolic logic just in case you are interested.

http://www.mhhe.com/wmg/bergmann/book/contents.mhtml

Rules of SD:


Reiteration

Given P then P.

Conjunction Introduction

Given P and P then P&Q.

Conjunction Elimination

Given P&Q then P. Or given P&Q then Q.

Disjunction Introduction

Given P then PvQ. Or given P then QvP.

Disjunction Elimintion

Given PvQ first assume P then arrive at R. Then assume Q and arrive at R. Then R by elimination of the disjunction.

Conditional Introduction

Assume P then arrive at Q. Then P implies Q.

Conditional Elimination

Given P implies Q, and given P, then Q.

Biconditional Introduction

Assume P then arrive at Q. Then assume Q and arrive at P. Therefore P iff Q.

Biconditional Elimination

Given P iff Q and given P then Q. Or given P iff Q and given Q then P.

Negation Introduction

Assume P. Then derive Q. Then derive ~Q. Therefore ~P.

Negation Elimination

Assume ~P. Then derive Q. Then dervie ~Q. Therefore P.


These are the rules of SD. I know its not too clear but that is the best I can do for now.

8| ...?

 

[Hurkyl]

Here is your hint: Assume ~(P v ~P)
Full proof below. Don't look! Try it yourself!











Whoops, there's another hint first.
Now, the full proof is below for real! Don't look.
Assume ~(P v ~P)
Assume P










Assume ~(P v ~P)
__Assume P
__Then P v ~P
__But ~(P v ~P)
Therefore ~P
__Assume ~P
__Then P v ~P
__But ~(P v ~P)
Therefore P
Therefore (P v ~P)

(Underlines are for formatting)

 

[wubie]

How did you get to

Therefore (P v ~P)?

I think I follow: It seems like you are doing two negation elimination claims with a negation introduction claim as well.

Is this what you are doing?

Assume ~(P v ~P)
__Assume P
__Then P v ~P (by line 2: disjunction introduction).
__But ~(P v ~P) (by line 1: repetition).
Therefore ~P (lines 2-4: negation introduction).
__Assume ~P
__Then P v ~P (by line 6: disjunction introduction).
__But ~(P v ~P) (by line 1: repetition).
Therefore P (by lines 6-8: negation elimination).
Therefore (P v ~P) (by lines 5,9: negation elimination).

I knew that I had to arrive at a contradiction somewhere to get the conclusion, but I never thought of deriving ~P and P through contradiction. In fact, even after you showed my your proof I had a bit of a time following what you were doing. But I think I got it now.

Thanks Hurkyl.