I have been trying to understand how to use natural deduction rules to solve problems in logic. I understand the different rules. However, I find it the most difficult to determine what can be set as assumptions, in order to solve the problems. For instance, I have understood the simple problems, such as the following: Where it is clear what ought to be the assumption and how to work from there.
However, when it comes to other problems, I get really confused as to what I am allowed to state as assumptions and what not to state as assumptions. Following is an example:
Is there a simple rule for proving formulas through natural deduction, with regards to problem solving techniques? For instance, when given problems such as:
How can I know which assumptions to make, etc.?
Any help is highly appreciated!
Added
I'm still a bit confused as to what I can set as the assumption(s).
The below example confuses me. In line (I), both the first conjunction [(P->Q)&(R->Q)] of the expression, as well as the second conjunction, [P & R], which is actually the conclusion of the left-most implication, is also set as an assumption.
As @Henning Makholm explained, I expected to end this proof with two stacked →Is.
The problem is how to know what expressions to use as assumptions? I keep seeing worked examples, all of them which make sense. However, when I am to solve problems myself, I get confused with the assumptions that can be made. Any advice on this particular matter?
For instance, I thought one could not assume an expression that is also the conclusion of an implication (P & R), as an assumption? Or is this just the case of the right-most conclusion, in this case Q?
Evidently, the choice of assumptions confuses me!.
Best Answer
Usually natural deduction proofs are easiest to construct from the bottom up. Whenever you need to prove something of the form $\varphi\to\psi$, your options are either to produce it using ${\to}E$ on $\sigma\to\varphi\to\psi$ and $\sigma$, or to produce it using ${\to}I$ on $\psi$. The first of these options requires some cleverness in choosing a formula $\sigma$; the second is more or less mechanical.
Whenever you use ${\to}I$ to conclude $\varphi\to\psi$, you get to state $\varphi$ as an assumption in the proof of $\psi$. And these are the only assumtions you ever get to make, at least in most orthodox formulations of Natural Deduction.
So if you're writing a proof from the top down, you have better not make any assumptions that you don't plan to "discharge" using ${\to}I$ further down in the tree.
In your second example is looks like you have the ${\lor}I$ rule wrong. It ought to be just $$ \frac{P}{P\lor R} {\lor}I $$ with no $R$ premise. And that's good because you cannot assume $R$ in this place -- there is no instance of ${\to}I$ in the tree that concludes something of the form $R\to\cdots$.
In the last example, you;re trying to conclude $((P\to Q)\land (R\to Q)) \to (P \land R) \to Q$. Here the natural approach will be to end the proof with two stacked ${\to}I$s to produce the two arrows. Then your task is to conclude $Q$, while being allowed to assume $(P\to Q)\land (R\to Q)$ and $P\land R$. That's easy enough; would have been slightly more interesting of one of the $\land$s (but not both) had been $\lor$.