Help with natural deduction (Propositional logic)

Question

I'm trying to get to $(\neg A \to C)$ from the following formula: $$(A \wedge B) \vee (\neg A \wedge C)$$

I have attempted the following: $$((A \wedge B) \vee \neg A) \wedge ((A \wedge B) \vee C ) \text{ distribution}$$ $$((A \wedge B) \vee C) \wedge ((A \wedge B) \vee \neg A) \text{ commutation}$$ $$(A \wedge B) \vee C \text{ simplification}$$ $$(C \vee (A \wedge B) \text{ commutation}$$ $$(C \vee A) \wedge (C \vee B) \text{ distribution}$$ $$(C \vee A) \text{ simplification}$$

I'm stuck from this point, I have no idea how to change the $A$ into a $\neg A$ and would love some help solving this.

Answer 1

First note that when using the natural deduction method, we do not primarily operate with algebraic rules such as association, commutation, distribution or simplification. Instead, we set for each one of the logical connectives a pair of introduction and elimination rules. Algebraic properties such as associativity, commutativity and so on of a connective, if exist, can be deduced from those rules, and they are known as derivate rules.

---

Now the statement you want to prove is the following:

Proposition:

$$(A∧B)∨(¬A∧C) \vdash (¬A→C)$$

Proof:

I provide below a formal proof in the terms I described above:

1. $(A∧B)∨(¬A∧C)$, premise

2. $\neg A$, assumption

   3. $(\neg A \land C)$, assumption
   4. $C$, 3, $\land$-elimination

3. $(\neg A \land C) \rightarrow C$, 3-4, $\rightarrow$-introduction

6. $(A∧B)$, assumption
7. $A$, 6, $\land$-elimination
8. $\bot$, 2,6, $\land$-introduction //$A\land \neg A$
9. $C$, 3, ex falsum

10. $(A \land B) \rightarrow C$, 6-9, $\rightarrow$-introduction
11. $C$, 1,3,10, $\lor$-elimination

12. $(¬A→C)$, 2-11, $\rightarrow$-introduction

Answer 2

Short answer: use disjunction elimination on $(C \lor A)$.

Longer answer: Assume $¬A$. Since you have $(C \lor A)$, that means if you assume $A$, that you'll get a contradiction. So, you can get $(A → C)$. Get $(C → C)$. Then use disjunction elimination to get to $C$. Then discharge the hypothesis $¬A$ into the conditional ($¬A$ → C) and you have the result.