# Simplifying propositional logic

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?

• Your simplification and implication laws seem incompletely stated. May 30, 2015 at 7:44

## 1 Answer

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]
• To be precise, you have to use $\lor$-introduction twice, in order to derive $(A∧B)∨(¬A∧C)$ under the [a] assumption : $A$ and under the [b] assumption : $\lnot A$. Then, you can conclude with $(A∧B)∨(¬A∧C)$ by $\lor$-elimination with 4, discharging both assumptions. May 30, 2015 at 9:37
• @MauroALLEGRANZA As always, you are right :) May 30, 2015 at 9:54
• @Demosthene thanks for detailed answer! Unfortunately, the system I'm using (its an online marking system) does not accept answers from assumptions which was why I was wondering if there was another way to eliminate the letters I asked. May 30, 2015 at 11:20
• @KadanaKanz If you want to reduce the conjunction of your two propositions $1$ and $2$ (in your question) to the final result, then the second paragraph of my answer is the way to go. May 30, 2015 at 11:29
• @Demosthene sorry for the late reply. I've been looking into your method (in the yellow) but I'm confused at what number 4 is and how you get it using the natural deduction laws May 31, 2015 at 12:38