Natural deduction proof for : p → ( c ∨ b) , b → s ⊢ ( p ∧ ¬s)→ c

Question

I am trying to prove the following statement but I am getting stuck at the 6th line and I'm unsure how to continue.

p → ( c ∨ b) , b → s ⊢ ( p ∧ ¬s)→ c

1. p → ( c ∨ b) (premise)
2. b → s (premise)
3. p ∧ ¬s (Assumption)
4. p (∧e 3)
5. ¬s (∧e 3)
6. c ∨ b (→e 1,4)

From here I'm unsure how to continue, ∨elimination would involve assuming c and b, which would give c and complete the implication (or so I think), but this doesn't seem right as the 2nd premise would then be necessary.

Answer 1

Everything will depend on the particular set of rules for natural deduction that are available to you. But assuming a pretty standard set of rules, just proceeding doing the only obvious thing at each step you will, as you say, get as far as ...

$1.\quad p → ( c ∨ b)\quad\quad\quad (premiss)\\ 2.\quad b → s \quad\quad\quad\quad\quad(premiss)\\ 3.\quad | \quad p ∧ ¬s \quad\quad\quad\quad(Assumption \text{ for later conditional proof})\\ 4. \quad | \quad p \quad\quad\quad\quad\quad\quad (∧e 3)\\ 5.\quad | \quad ¬s \quad\quad\quad\quad\quad\ \ (∧e 3)\\ 6. \quad | \quad c ∨ b \quad\quad\quad\quad\ \ (→e 1,4)$

Here I'm indenting a column to indicate (Fitch-style) that we are now operating in the scope of a temporary assumption. The only option now (in a standard system) is to use disjunction elimination. So that means that the rest of the derivation must look like this (initially indenting another column to show that we are operating within the scope of a new assumption):

$7.\quad\ | \quad | \quad c\quad\quad\quad\quad\ (Assumption \text{ begin first subproof of two needed for later or-elimination})\\ 8.\quad \ | \quad | \quad c\quad\quad\quad\quad\ \text{(If your system needs the repetition!)}\\\\ \ \ \quad \ | \quad | \quad --\quad\quad\quad\text{(End first subproof for or-elim, start the second)}\\ 9.\quad \ | \quad | \quad b \quad\quad\quad\quad\ (Assumption)\\ 10.\quad | \quad | \quad \vdots\\ n.\ \quad | \quad | \quad c \quad\quad\quad\quad\text{(End of second subproof for or-elim)}\\ n+1.\ |\quad c \quad\quad\quad\quad\quad (∨e, 6, 7-8, 9-n)\\ n+2.\ (p∧¬s) \to c\quad\quad (\to i, 3 - n+1)$

So that completes the proof, so long as you can fill in between steps 9 and $n$!

But that's easy. From 2 and 9 (what else?!) you get $s$, contradicting 5. So 9 leads to contradiction and hence anything, including $c$. But how your natural deduction system handles that will depend on its details.

Answer 2

Suppose the first premise alone suffices. Then if CpAcb is true, so is CKpNsc. Suppose that CpAcb is true and CKpNsc is false. Then KpNs = 1, c = 0. Thus, p = 1, Ns = 1, and thus s = 0. In which case if b = 1, then CpAcb = 1 and CKpNsc = 0. Consequently, the first premise can hold as true while the conclusion can ends up as false. Consequently, it is not the case that if CpAcb is true, so is CKpNsc. Therefore, the first premise alone does not suffice.

In other words the second premise does end up as necessary in the sense you seemed to have used. Peter Smith's answer may well help you otherwise, and if not, then please post the rules of inference of your system (though you need not include conditional introduction as a rule of inference as all natural deduction systems so far as I know have such a rule of inference).