Some Questions on proving Forward direction of statements of the form $A$ IFF $(B\wedge C)$

Question

When proving $(\rightarrow)$ direction for something like of the form $$A\quad IFF\quad (B\wedge C)$$ (where $\wedge$ means and), Does showing $A\implies B$ and $A\implies C$ always work, or is there some difference between showing $B$ and $C$ are individually implied by $A$ versus them being jointly implied by A.

Also, for showing that they must be jointly implied by $A$, is proof by cases and contradiction a valid technique? (i.e. Assume $A, B$ and $\neg C$ and show contradiction, and also $A,B$ and $\neg C$)

• My confusion with this approach is that it shows that if two of them are true, the third must be as well, but it does not show that just $A$ is enough for the other two?

Lastly, is there any advice, general guidelines for such proofs?

Answer 1

I focus on the $A\Rightarrow (B\wedge C)$ because that is what really interests you.

Notice that in the propositional calculus, $A\to B\Leftrightarrow\neg A \vee B$ (cf. material implication (rule of inference)). Therefore, $$A\to (B\wedge C)\Leftrightarrow\neg A \vee (B\wedge C) \Leftrightarrow (\neg A \vee B)\wedge (\neg A \vee C) \Leftrightarrow (A\to B)\wedge (A\to C)$$ due to distributivity. So this is an explanation why it is fine to do what you're uncertain about. Another way and a generic method to do this would be to write out the complete truth table with its $2^3=8$ rows for the two expressions you are comparing.

To prove that they are jointly implied by $A$, again $$A \to (B\wedge C) \Leftrightarrow (\neg A \vee B)\wedge (\neg A \vee C)\tag{1}$$ from above, but your suggested proof by cases by contradiction, $(A \land B \land \lnot C)$ is false and $(A \land C \land \lnot B)$ is false is only $$\lnot (A \land B \land \lnot C) \land \lnot(A \land C \land \lnot B)\\ \Leftrightarrow (\lnot A \lor \lnot B \lor C) \land (\lnot A \lor \lnot C \lor B)\\ \Leftrightarrow(\neg (A \wedge B) \vee C) \wedge (\neg (A \wedge C)\vee B)\\ \Leftrightarrow((A \wedge B)\to C) \wedge ((A \wedge C)\to B).$$

What we want to get above in $(1)$ is true in fewer cases than the last calculation for the suggested proof by contradiction. Basically, we AND together shorter expressions of ORs. Specifically, $(1)$ is not true if $(A \land \lnot B \land \neg C)$ holds, but in the second line of the last calculation, $\neg B \land \neg C$ would make $\neg B \lor C$ and $\neg C\lor B$ certain, and $(\lnot A \lor \lnot B \lor C)$ and $(\lnot A \lor \lnot C \lor B)$, too. With this, we found a row in the truth table where $(1)$ is false and the value of the expression in the last calculation is true. Your proof by cases didn't rule this out when it should have. (We could have transformed the compared expressions from conjunctive normal form to disjunctive normal form and argued for that.)

My general advice: I find these calculations confusing and hard to get right. I hazard a guess that there will be personal differences among us based on perhaps the development of our short-term memory. You develop intuition over the months and years by practising these arguments a lot, and then you can always confirm your intuition by propositional calculus.

Answer 2

By definition, in classical boolean algebra implication $A\to B$ is equivalent to the statement $\neg A \vee B$. Thus \begin{align} (A\to B)\wedge (A\to C) \equiv (\neg A\vee B)\wedge(\neg A\vee C) \equiv \neg A \vee (B\wedge C) \equiv A\to(B\wedge C), \end{align} where second equivalence is exact form of distributivity law.