How to prove this using natural deduction?

Question

could I get some help on how to solve this problem? I have been doing this course where we were asked to solve this problem and I'm stuck on how to even get started. ¬((A ∨ B)→(A ∨ C)) ⊢ (A ∨ B) ∧ ¬(B→C)

I have been given ¬((A ∨ B)→(A ∨ C)) as the assumption introduction and the rules that I can use are -

Conjunction introduction, Conjunction elimination

Disjunction introduction, disjunction elimination

Implication introduction, implication elimination

Falsum introduction, falsum elimination

Negation introduction, negation elimination

Any help would be highly appreciated. Thank you.

Answer 1

Hint

You have to assume $\lnot B$ and, using LEM: $A \lor \lnot A$, derive a contradiction with Disjunction Elimination.

In this way, we have $B$ by Double Negation.

Having $B$, we have $(A \lor B)$ and, assuming $(B \to C)$ we get a new contradiction, from which $\lnot (B \to C)$.

Answer 2

¬((A ∨ B)→(A ∨ C)) ⊢ (A ∨ B) ∧ ¬(B→C)

Prove the conjuncts by (1) reduction to absurdity and (2) indirect proof.

• Reduction to Absurdity: Assume $\neg(A\vee B)$ then derive a contradiction of the premise through a conditional proof using negation elimination and explosion (aka falsum elimination).

• Indirect Proof: Assume $B\to C$ then derive a contradiction of the premise through disjunction elimination.

$$\def\fitch#1#2{\quad\begin{array}{|l}#1\\\hline#2\end{array}}\fitch{\neg((A\vee B)\to(A\vee C))}{\fitch{\neg(A\vee B)}{\fitch{}{~}\\~\\\bot}\\A\vee B\\\fitch{B\to C}{\fitch{}{\fitch{}{~}\\\fitch{}{~}\\~}\\~\\\bot}\\\neg(B\to C)\\(A\vee B)\wedge\neg(B\to C)}$$