Conjunctive Normal Form to Disjunctive Normal Form

Question

My question is this... Convert: ((A->B)&(~A->C)) into ((A&B)|(~A&C)) using the natural deduction system

My working so far is:

(A->B) by simplification

(~A->C) by commutation and simplification

Then, using definition of implication on both of them, i get:

(~A|B)

(A|C)

Then, by the law of conjunction, i arrive at:

(~A|B)&(A|C)

I get stuck after this. By using a few distribution laws i managed to get it looking like this:

((A&~A)|(A&B)) | ((~A|B)&C)

where (A&~A) must be false but I also can't seem to find a rule to remove the (A&~A) part. Help please.

Also, The question also hints that a conditional proof will come in handy, but i just can't see where it should be applied because conditional proofs always end up with "assumption IMPLIES conclusion" but there is no "->" in the final answer.

Answer 1

With Natural Deduction :

1) $(A \to B) \land (\lnot A \to C)$ --- premise

2) $(A \to B)$ --- from 1 by $\land$-elimination (i.e. simplification)

3) $(\lnot A \to C)$ --- from 1 by $\land$-elimination (i.e. simplification)

4) $A \lor \lnot A$ --- Excluded Middle : is necessary for classical propositional calculus

5) $A$ --- assumed [a]

6) $B$ --- from 5) and 2) by $\to$-elimination

7) $A \land B$ --- from 5) and 6) by $\land$-introduction

8) $(A \land B) \lor (\lnot A \land C)$ --- from 7) by $\lor$-introduction

9) $\lnot A$ --- assumed [b]

10) $C$ from 9) and 3) by $\to$-elimination

11-12) $(A \land B) \lor (\lnot A \land C)$ --- from 9) and 10) by by $\land$-introduction followed by $\lor$-introduction, as above

13) $(A \land B) \lor (\lnot A \land C)$ --- from 4), 5) 9) and 12) by $\lor$-elimination, discharging [a] and [b]

14) $[(A \to B) \land (\lnot A \to C)] \to [(A \land B) \lor (\lnot A \land C)]$ --- from 1) and 13) by $\to$-introduction.

---

In the same way, we can derive the other implication :

15) $[(A \land B) \lor (\lnot A \land C)] \to [(A \to B) \land (\lnot A \to C)]$

concluding with :

$[(A \to B) \land (\lnot A \to C)] \leftrightarrow [(A \land B) \lor (\lnot A \land C)]$ --- from 14) and 15) by $\leftrightarrow$-introduction.