# Math Help - Could use some help with a Natural Deduction proof

1. ## Could use some help with a Natural Deduction proof

I've been working on a proof for my symbolic logic class, but I cannot seem to solve it. Even after hours and hours of work I am pretty stuck. Anyone want to take a crack at it? It's probably easy for experts. Our class has been working with Hurley's 18 rules

I'm not sure what convention everyone is used to around here, so i'll post a key.

> = If then,
* = Conjuction,
~ = Negation
v= Or
C: will precede the conclusion/goal of the proof

Okay, here is the proof:

C: I
1. (I>E)>C
2. C > ~C

I can't seem to solve it.

There are a few obvious lines (and about a hundred others) I've found are useful right off the bat.

3. ~C v ~C 2, Material Implication
4. ~C 3, Tautology

Can anyone help me solve this? I've tried a million things. It's truly my "white whale" of our logic problem set.

2. 1. (I>E)>C
2. C > ~C
From the intuitive standpoint, C is a contradiction because, supposing otherwise, truth cannot imply falsehood. Therefore, (I -> E) -> C is equivalent to ~ (I -> E), and this in turn implies I.

More formally, Natural Deduction, is, in fact, natural, so here is an explanation in the natural language .

The proof can be broken into two parts. The first proves ~ (I -> E), and the second deduces I from that.

For the first part, assume I -> E. Then you get C with 1. Also, you get ~ C with 2. Obtaining C as before once more, you get a contradiction from C and ~ C. Therefore, the assumption I -> E was false and we have ~ (I -> E).

The second part is just a bit trickier because it uses the law of double negation. Assume ~ I and (separately) I. This, of course, gives a contradiction. Since everything follows from contradiction by ex falso quodlibet, we deduce E. Closing the assumption I, we get I -> E. (We still have ~ I open.) But, in the first step we deduced ~ (I -> E), so we get a contradiction again. Now, closing the the assumption ~ I we get ~~ I, from which by Double Negation we get I.

3. Originally Posted by Cermak
I've been working on a proof for my symbolic logic class, but I cannot seem to solve it. Even after hours and hours of work I am pretty stuck. Anyone want to take a crack at it? It's probably easy for experts. Our class has been working with Hurley's 18 rules

I'm not sure what convention everyone is used to around here, so i'll post a key.

> = If then,
* = Conjuction,
~ = Negation
v= Or
C: will precede the conclusion/goal of the proof

Okay, here is the proof:

C: I
1. (I>E)>C
2. C > ~C

I can't seem to solve it.

There are a few obvious lines (and about a hundred others) I've found are useful right off the bat.

3. ~C v ~C 2, Material Implication
4. ~C 3, Tautology

Can anyone help me solve this? I've tried a million things. It's truly my "white whale" of our logic problem set.
If I'm not mistaken, ten of those 18 rules are rules of replacement. And, DM, DN and Impl are among those ten.
With those three in hand, you can work the subformulas to your advantage.
Add to those three the three rules HS, MT and Simp (that are among the other eight rules -- the rules of inference),
and you have everything you need to write out a derivation that'll take no more than six lines (modulo the premisses).