# How to prove that $(A \lor B) \land (\lnot A \lor B) = B$

I know this is fairly basic, and I understand that it becomes \begin{align} (A \land \lnot A) \lor B \\ F \lor B \\ B \end{align}

However, I can't work out how to prove that it becomes that first line. It seems intuitive, but I cannot work out which laws let me simplify it like that.

This is from a previous homework, and the above equation is the correction I was given, and I can't remember exactly how it was produced.

-

The first line follows from distributivity: $$(X \wedge Y) \vee Z = (X \vee Z) \wedge (Y \vee Z)$$ Think what $X$, $Y$ and $Z$ are in this scenario.

-
Would $X=(A \lor B), Y=\lnot A, |=B$? Giving $((A \lor B) \lor B) \land (\lnot A \lor B) =$(A \land (\lnot A \lor B) = $(A \land \lnot A) \lor (A \land B)$ by distributivity of $\land$ – Callum M Apr 4 '13 at 15:52
No. $X=A$, $Y= \neg A$ and $Z=B$. – Clive Newstead Apr 4 '13 at 16:17
Ah, I see. Thankyou very much! – Callum M Apr 4 '13 at 16:31

As Clive pointed out, this comes from an application of the distributive law of "disjunction" $(\lor)$ over "conjunction" $(\land)$:

$$(\color{red}{\bf P}\color{blue}{\bf \lor R}) \color{red}{\bf \land} (\color{red}{\bf Q} \color{blue}{\bf \lor R})\iff (\color{red}{\bf P \land Q}) \color{blue}{\bf \lor R}$$

In your problem, you have: $$(\color{red}{\bf A} \color{blue}{\bf \lor B}) \color{red}{\bf \land} (\color{red}{\bf \lnot A} \color{blue}{\bf \lor B}) \iff (\color{red}{\bf A \land \lnot A}) \color{blue}{\bf \lor B}$$

You'll also want to become familiar with the other application of distributivity (which is not needed in your problem). It follows a similar pattern, with connectives interchanged, as follows:

$$(P\land R){\bf \lor }(Q\land R) \iff (P \lor Q) \land R$$

-
That's great, thanks! I was definitely confused about distributivity, this is really useful. – Callum M Apr 4 '13 at 16:30
Nice amy :-) nice to see u – Babak S. Apr 4 '13 at 16:38
Just note that each side of the distributive equivalence implies the other. So you can start from the left hand side to obtain the right hand side, and vice versa. – amWhy Apr 4 '13 at 21:30
@amWhy: Not only color coded, but using my fav red-white-blue! +1 – Amzoti May 20 '13 at 1:13