Using the replacement laws to prove that ($a \to $b) $\vee$ ($a \to $c) = $a \to ($b $\vee$ c)

Question

I have been asked to prove that

($a \to $b) $\vee$ ($a \to $c) = $a \to ($b $\vee$ c).

I believe it is just the simple case of using the distributive law:

$a \wedge ($b $\vee$ c)= (a $\wedge c) \vee ($a $\wedge$ b).

But I am not sure.

Answer 1

I believe it is just the simple case of using the distributive law:

$a \wedge ($b $\vee$ c)= (a $\wedge c) \vee ($a $\wedge$ b).

But I am not sure.

You are right to not be sure.

First of all, there are distribution laws involving the conditional, but you have to be very careful. This is what is the case:

Distribution Laws for Conditionals

$a \rightarrow (b \land c) = (a \rightarrow b) \land (a \rightarrow c)$

$a \rightarrow (b \lor c) = (a \rightarrow b) \lor (a \rightarrow c)$

$(b \land c) \rightarrow a = (b \rightarrow a) \lor (c \rightarrow a)$

$(b \lor c) \rightarrow a = (b \rightarrow a) \land (c \rightarrow a)$

Note that for the last two, the $\land$ and the $\lor$ switch! ... So, it is easy to make mistakes with these. Therefore, it is typically safer to rewrite the conditionals as disjunctions.

That is, go from:

$(a \rightarrow b) \lor (a \rightarrow c)$

to:

$(\neg a \lor b) \lor (\neg a \lor c)$

Now, can we do Distribution on this? No, because all the operators are $\lor$'s.

OK, but what you can do, given that all operators are the same, is Association. Using Association, you can either move parentheses around or, if you are allowed to do so, drop parentheses altogether. Assuming we can indeed just drop parentheses, we thus get:

$\neg a \lor b \lor \neg a \lor c$

Now, at this point notice that you have two of the same terms $\neg a$. By Idempotnece (which says that $p \lor p = p$), you can drop one of them:

$\neg a \lor b \lor c$

OK, and now you can rewrite the disjunction back as a conditional:

$a \rightarrow (b \lor c)$

Answer 2

Left hand side is: $(a \rightarrow b) \vee (a \rightarrow c)=(\neg a \vee b)\vee(\neg a \vee c)=\neg a \vee b \vee c.$

also

Right hand side is :$a \rightarrow (b \vee c)= \neg a \vee (b \vee c)= \neg a \vee b\vee c$.

So they are equal.

Answer 3

Hint: you want to prove $(\neg a\lor b)\lor(\neg a\lor c)$ is equivalent by replacement to $\neg a\lor (b\lor c)$.

Answer 4

Yes, I believe you're correct. By expanding, using the distributive laws and simplifying you can prove this.

$$ \begin{align} &\quad (a \Rightarrow b) \lor (a \Rightarrow c) \\ &\Leftrightarrow (\neg a \lor b) \lor (\neg a \lor c) \\ &\Leftrightarrow (\neg a \lor b) \lor (\neg a \lor b \lor c) \\ &\Leftrightarrow (\neg a \lor b) \lor c \\ &\Leftrightarrow \neg a \lor (b\lor c) \\ &\Leftrightarrow a \Rightarrow (b\lor c) \end{align} $$