Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In my logic design exam today I was given this question:

Show that: $$ B \land ( B \lor C) = B $$

It's asking for a proof for this expression. Could someone please explain how such expression can be proven? I'm not that good at Boolean algebra but I believe that it's in the simplest form.

share|cite|improve this question
    
The question in the title and in the body are different – Dennis Gulko Dec 26 '12 at 9:41
    
@Dennis Gulko: Thank you, I fixed it. – user54251 Dec 26 '12 at 9:43
    
this is absorption law – Koushik Dec 26 '12 at 9:47
    
@doniyor that would obviously be wrong, for say $A$ were false but $B$ were true. – peoplepower Dec 26 '12 at 9:51
    
I think that propositional-logic would be a more appropriate tag than proof-theory. Just have a look at the tag-wiki for propositional-logic and proof-theory. – Martin Sleziak Dec 26 '12 at 9:55
up vote 2 down vote accepted

You could simply do it by a truth table. Or use the simple facts that $x\land y$ implies $x$ as well as $x$ implies $x\lor y$. Thus $B\land(\ldots)$ implies $B$ and $B$ implies $B\lor C$ and hence also implies $B\land (B\lor C)$, in summary $B\land(B\lor C)$ and $B$ are equivalent.

share|cite|improve this answer

A truth table will show it

B    C    B or C    B and (B or C)

T    T      T            T
T    F      T            T
F    T      T            F
F    F      F            F 
share|cite|improve this answer
    
I thought about it but, unfortunately, the teacher said that using truth table isn't acceptable. – user54251 Dec 26 '12 at 10:06

$a*(a+b)=a*a+a*b=a+a*b=a*1+a*b=a*(1+b)=a$

Conjunction $x∧y$ behaves on $0$ and $1$ exactly as multiplication does for ordinary algebra: if either $x$ or $y$ is $0$ then $x∧y$ is $0$, but if both are $1$ then $x∧y$ is $1$.

Disjunction $x∨y$ works almost like addition, with $0∨0 = 0$ and $1∨0 = 1$ and $0∨1 = 1$. However there is a difference: $1∨1$ is not $2$ but $1$.

share|cite|improve this answer
    
∧=* ∨=+ in the above calculation – Koushik Dec 26 '12 at 9:53

Distribute out expression, and you're left with B and B = B or B and C. so that should imply B.

$B \wedge (B \lor C) = (B\wedge B) \lor (B\wedge C )= B \lor (B\wedge C ) = B$

share|cite|improve this answer
    
Are you sure? The title and body say B∧(B∨C)=B. There is no A. – randomafk Dec 26 '12 at 9:49
    
Apologies, but I think you might want to. Just look at the URL... /proof-that-b-land-b-lor-c-b – randomafk Dec 26 '12 at 9:51

Your Answer

 
discard

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