Simplifying propositional logic

Question

Hi I asked a question a few hours ago which has been solved but I got stuck on another exercise so I thought I'd reach out for some help.

I have the premise: $((A \to B) \land (\lnot A \to C))$

With the desired result at : $((A \land B) \lor (\lnot A \land C))$

Without adding more premises / assuming anything, I have gotten the following using some simplification and implication laws.

$1. (B \lor (\lnot A \land C))$

$2. (C \lor (A \land B))$

What are the methods to eliminate B and C so that I can use conjunction to add the remaining expressions together?

Answer 1

You can think about it in this way: $(A\to B)\land(\neg A\to C)$ is a rule you're given, which tells you what happens when you know the truth value of $A$. If $A$ is true, then you must have $B$; if $A$ is false, you must have $C$. And since $A\lor\neg A$ is a tautology (always true), then either you have $A$ and $B$ or you have $\neg A$ and $C$, which we can write as $(A\land B)\lor(\neg\land C)$.

More formally: \begin{align}(A\to B)\land(\neg A\to C)&\equiv (\neg A\lor B)\land(A\lor C)\\&\equiv(\neg A\land A)\lor(\neg A\land C)\lor(B\land A)\lor(B\land C)\\&\equiv(\neg A\land C)\lor(B\land A)\lor(B\land C)\\&\equiv(\neg A\land C)\lor(B\land A)\end{align}

Some details on the above derivation:

• The first line is simply expressing $\to$ in terms of $\left\{\lor,\neg\right\}$.
• Next, we distribute the parentheses over the conjunction (you could actually break it into two steps, one distributing over the disjunction, the second over the conjunction, but I think it is clear enough that way).
• In the third line we remove the $(A\land\neg A)$ term, which is clearly a contradiction, so that it doesn't influence the truth value of the whole proposition.
• And the final step, as I explained in the first paragraph, is to notice that if we have $\neg A$, $C$ follows, and we have $A$, $B$ follows. Thus $(B\land C)$ doesn't contribute to the truth value of the whole proposition, since whenever it is true, one of $(\neg A\land C)$ or $(B\land A)$ is already true.

Finally, a deduction:

1. $\vdash (A\to B)\land(\neg A\to C)$ --- Hypothesis
2. $\vdash A\to B$ --- Simplification, 1
3. $\vdash \neg A\to C$ --- Simplification, 1
4. $\vdash A\lor\neg A$ --- Axiom 1 (tautology)
5. $\vdash A$ --- Assumption [a]
6. $\vdash B$ --- Modus Ponens, 2-5
7. $\vdash A\land B$ --- Adjunction, 5-6
8. $\vdash (A\land B)\lor(\neg A\land C)$ --- $\lor$-introduction, 7
9. $\vdash\neg A$ --- Assumption [b]
10. $\vdash C$ --- Modus Ponens, 3-8
11. $\vdash \neg A\land C$ --- Adjunction, 8-9
12. $\vdash (\neg A\land C)\lor(A\land B)$ --- $\lor$-introduction, 11
13. $\vdash (A\land B)\lor(\neg A\land C)$ --- $\lor$-elimination, 4, discharging [a] and [b]