# Thread: classical logic - proofs via natural deduction

1. ## classical logic - proofs via natural deduction

Hi,

I've recently started working through an introduction to logic work book and I am having a lot of trouble generating proofs using natural deduction. I understand the rules, but have difficulty figuring out when to apply them and how to properly discharge assumptions.

Here are a couple of problems that are spinning my head at the moment:

1. I would like to prove the following theorem:

(p => r) => ((q => p) => (q => r))

It seems to me that this proof will rely heavily on the conditional proof (CP) rule. Beyond that, I'm not sure how to proceed. Should I start by assuming the antecedent of the entire string (p => r), or do I need to attack the bracketed section first?

2. I would like to translate the following argument and then prove that it is valid.

Mice are not welcome if and only if mice and rats are not welcome. If Tanya is a reliable witness, then rats are welcome. If it's not true that if Tanya is not a reliable witness mice are welcome, then mice are welcome. Therefore, mice are welcome.

This is what I've tried so far as a translation:

(p) Mice are not welcome
(q) Rats are not welcome
(r) Tanya is a reliable witness

1) p <=> (p ^ r)
2) r => !q
3) !(!r => !p) => !p
C) !p

I'm very uncertain of my reading of premise 3. I'm not 100% confident on my translations of the other premises either. However, even taking this into account, I'm not really sure how to proceed with the proof. I would start by assuming the premises:

1 1 p <=> (p ^ r) A
2 2 r => !q A
3 3 !(!r => !p) => !p A

But once the real work begins, I'm drawing a blank. I understand from my reading that I should target the conclusion and try and use valid rules to reach it. As the conclusion is !p, it seems that proving the antecedent of premise 3 is probably the best way to get there. I'm really unsure though.

If someone was willing to help me not only solve the problems, but understand the process taken to do so, it would be hugely appreciated. I'm determined to figure it out, but if I go it alone I fear I'll still be sitting here tearing my hair out two weeks from now!

2. Originally Posted by sanktum
Hi,

I've recently started working through an introduction to logic work book and I am having a lot of trouble generating proofs using natural deduction. I understand the rules, but have difficulty figuring out when to apply them and how to properly discharge assumptions.

Here are a couple of problems that are spinning my head at the moment:

1. I would like to prove the following theorem:

(p => r) => ((q => p) => (q => r))

It seems to me that this proof will rely heavily on the conditional proof (CP) rule. Beyond that, I'm not sure how to proceed. Should I start by assuming the antecedent of the entire string (p => r), or do I need to attack the bracketed section first?

2. I would like to translate the following argument and then prove that it is valid.

Mice are not welcome if and only if mice and rats are not welcome. If Tanya is a reliable witness, then rats are welcome. If it's not true that if Tanya is not a reliable witness mice are welcome, then mice are welcome. Therefore, mice are welcome.

This is what I've tried so far as a translation:

(p) Mice are not welcome
(q) Rats are not welcome
(r) Tanya is a reliable witness

1) p <=> (p ^ r)
2) r => !q
3) !(!r => !p) => !p
C) !p

I'm very uncertain of my reading of premise 3. I'm not 100% confident on my translations of the other premises either. However, even taking this into account, I'm not really sure how to proceed with the proof. I would start by assuming the premises:

1 1 p <=> (p ^ r) A
2 2 r => !q A
3 3 !(!r => !p) => !p A

But once the real work begins, I'm drawing a blank. I understand from my reading that I should target the conclusion and try and use valid rules to reach it. As the conclusion is !p, it seems that proving the antecedent of premise 3 is probably the best way to get there. I'm really unsure though.

If someone was willing to help me not only solve the problems, but understand the process taken to do so, it would be hugely appreciated. I'm determined to figure it out, but if I go it alone I fear I'll still be sitting here tearing my hair out two weeks from now!

(Would you tell me first what book you are working through?) Natural deduction is the kind that does not make use of axioms. Only make asuumptions and use figures (schemes ?). In first exercise we start with three consecutive assumtions $\displaystyle p\to r$, $\displaystyle q\to p$, $\displaystyle q$. Then by using some "schemes" we get $\displaystyle r$. Then by using other we get the whole formula.
You don't say Suppose $\displaystyle p\to r$ is true. You just say suppose $\displaystyle p\to r$ and use schemes. if you cannot then make next assumption and so on.