0
$\begingroup$

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$

$\endgroup$
3
  • $\begingroup$ 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 :) $\endgroup$
    – Daniel W. Farlow
    Feb 1, 2015 at 20:55
  • $\begingroup$ 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. $\endgroup$
    – MarnixKlooster ReinstateMonica
    Feb 3, 2015 at 17:27
  • $\begingroup$ Thanks for the tip, getting a better understanding of this now. $\endgroup$
    – Brian Var
    Feb 3, 2015 at 18:35

2 Answers 2

Reset to default
2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – amWhy
    Feb 3, 2015 at 16:38
  • $\begingroup$ 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}$$ $\endgroup$
    – amWhy
    Feb 3, 2015 at 16:41
  • $\begingroup$ Don't delete it. It will be helpful to those who can benefit from "modeling" correct proofs. Just correct it ;-) $\endgroup$
    – amWhy
    Feb 3, 2015 at 16:42
2
$\begingroup$

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}$$

$\endgroup$
0

You must log in to answer this question.

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