8
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ Your simplification and implication laws seem incompletely stated. $\endgroup$
    – Kevin
    May 30, 2015 at 7:44

1 Answer 1

7
$\begingroup$

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]
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$ May 30, 2015 at 9:37
  • 1
    $\begingroup$ @MauroALLEGRANZA As always, you are right :) $\endgroup$
    – Demosthene
    May 30, 2015 at 9:54
  • $\begingroup$ @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. $\endgroup$ May 30, 2015 at 11:20
  • $\begingroup$ @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. $\endgroup$
    – Demosthene
    May 30, 2015 at 11:29
  • $\begingroup$ @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 $\endgroup$ May 31, 2015 at 12:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .