# Proving equivalency using boolean algebra laws of logic

I have a question on my exam papers relating to proving equivalences using the laws of logic, but I'm not sure how to work it out as I don't have the solution paper.

Can someone explain to me the steps involved in proving the first question (iii)? Or perhaps point me in the direction of a good tutorial on the question?

(iii) $(A\lor B)\to C \equiv (A\to C)\land (B\to C)$

(iv) $(A\to B)\to C \equiv (\neg A\to C)\land (B\to C)$

(v) $A\land (A\to B)\to B\equiv T$

• amWhy referenced the equivalence $p\to q\equiv \neg p\lor q$ (which you may notice I used several times in my answer). I'd recommend committing this equivalence to memory. Most of the propositional logic questions I've seen on MSE are easily handled by knowing when to use this equivalence effectively. Just a friendly tip :) Feb 1, 2015 at 20:55
• I'm not going to add another answer, but I have two general tips: start at the most complex side, and treat each step as a simplification step, keeping your goal (the other side) in mind; and expand $\;p \to q\;$ to either $\;\lnot p \lor q\;$, $\;p \equiv p \land q\;$, or $\;p \lor q \equiv q\;$: that usually gives you more room for manipulation. Feb 3, 2015 at 17:27
• Thanks for the tip, getting a better understanding of this now. Feb 3, 2015 at 18:35

Here is how I would go about it:

(iii) \begin{align} (A\lor B)\to C &\equiv \neg(A\lor B)\lor C\tag{$p\to q \equiv \neg p \lor q$}\\ &\equiv (\neg A\land \neg B)\lor C\tag{DeMorgan}\\ &\equiv (\neg A\lor C)\land (\neg B\lor C)\tag{distributivity}\\ &\equiv (A\to C)\land (B\to C)\tag{$p\to q \equiv \neg p \lor q$} \end{align}

(iv) \begin{align} (A\to B)\to C &\equiv \neg(A\to B)\lor C\tag{$p\to q \equiv \neg p \lor q$}\\ &\equiv \neg(\neg A\lor B)\lor C\tag{$p\to q \equiv \neg p \lor q$}\\ &\equiv (A\land \neg B)\lor C\tag{DeMorgan}\\ &\equiv (A\lor C)\land (\neg B\lor C)\tag{distributivity}\\ &\equiv (\neg A\to C)\land (B\to C)\tag{$p\to q \equiv \neg p \lor q$} \end{align}

(v) \begin{align} A \land (A\to B) &\equiv A\land (\neg A\lor B)\tag{$p\to q \equiv \neg p \lor q$}\\ &\equiv (A\land \neg A)\lor (A\land B)\tag{distributivity}\\ &\Longleftrightarrow B\equiv T\tag{$\dagger$} \end{align} $(\dagger)$ The last equivalence is the only one that is actually somewhat tricky.

Hint: Consider the possible truth values of $A$ separately and see what must be true for all of the conjunctions to be true (you will see that $B$ must be true, hence $B\equiv T$).

• I understand your enthusiasm for math and for making math accessible to others (takes one to know one). I'll give you the benefit of the doubt (and give the OP that same benefit). I apologize if my comment was troubling. I will have deleted it by the time you read this comment. Feb 3, 2015 at 16:38
• Actually, your last exercise is in error: \begin{align} A\land (A\rightarrow B)&\equiv A\land (\lnot A \lor B) \\ &\equiv (A\land \lnot A) \lor (A\land B) \\ &\equiv A\land B\end{align} Feb 3, 2015 at 16:41
• Don't delete it. It will be helpful to those who can benefit from "modeling" correct proofs. Just correct it ;-) Feb 3, 2015 at 16:42

We'll look at $(iii)$.

First I will use the equivalence $(1)\;p \rightarrow q \equiv \lnot p \lor q$.

Then we apply one of DeMorgan's Laws $(2)$.

Then, we use distributivity of disjunction over conjunction $(3)$.

And for the last line $(4)$, two more applications of the equivalence to start with $(1)$.

\begin{align} (A\lor B) \rightarrow C & \equiv \lnot(A\lor B) \lor C \tag{1}\\ \\ & \equiv (\lnot A \land \lnot B) \lor C\tag{2}\\ \\ & \equiv (\lnot A \lor C) \land (\lnot B \lor C)\tag{3}\\ \\ &\equiv (A\rightarrow C) \land (B\rightarrow C)\tag{4}\end{align}