Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer
    
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
2  
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$$

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.