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$
Best Answer
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$).