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.

In boolean algebra, below is the consensus theorem

$$X⋅Y + X'⋅Z + Y⋅Z = X⋅Y + X'⋅Z$$ $$(X+Y)⋅(X'+Z)⋅(Y+Z) = (X+Y)⋅(X'+Z)$$

I don't really understand it? Can I simplify it to

$$X'⋅Z + Y⋅Z = X' \cdot Z$$

I don't suppose so. Anyways, why can $Y \cdot Z$ be removed?

share|improve this question
    
I think you should think about the distribution rule of boolean algebra. It is the counterpart of distribution rule of set operation. –  newbie Aug 30 '11 at 14:23

3 Answers 3

up vote 5 down vote accepted

The proof that grep has given is fine, as is the one in Wikipedia, but they don’t give much insight into why such a result should be true. To get some feel for that, look at the most familiar kind of Boolean algebra: the Boolean algebra of subsets of some given set $S$, with $\cap$ for $\cdot$, $\cup$ for $+$, and $'$ interpreted as the relative complement in $S$ (i.e., $X' = S \setminus X$). In this algebra the theorem says that $$(X\cap Y) \cup (X' \cap Z) \cup (Y \cap Z) = (X\cap Y) \cup (X' \cap Z),$$ which amounts to saying that $$Y \cap Z \subseteq (X\cap Y) \cup (X' \cap Z).$$ This isn’t hard to prove, but doing so won’t necessarily give you any better feel for what’s going on. For that I suggest looking at the corresponding Venn diagram, with circles representing $X$, $Y$, and $Z$. Shade the region representing $(X\cap Y) \cup (X' \cap Z)$. Now look at the region representing $Y \cap Z$: it’s already shaded, because it’s a subset of $(X\cap Y) \cup (X' \cap Z)$. Throwing it in with $(X\cap Y) \cup (X' \cap Z)$ to make $(X\cap Y) \cup (X' \cap Z) \cup (Y \cap Z)$ adds nothing.

share|improve this answer

Boolean Algebra has a very powerful metatheorem that says that if any 2-element "{0, 1}" Boolean Algebra has a theorem, then it holds for all Boolean Algebras. So, if you just want an argument that should come as convincing, you just need to check that all substitution instances of "0" and "1" in those equations. Here's a compact argument:

Suppose x=0. Then for the first equation we have 0.y+0'.z+y.z=0+1.z+y.z=z+y.z on the left-hand side, and 0.y+0'.z=0+1.z=z. Well, z+y.z=z by absorption and commutation. Now suppose x=1. Then on the left hand side we have 1.y+1'.z+y.z=y+0.z+y.z=y+y.z. On the right-hand side we have 1.y+1'.z=y+0.z=y. So, the two sides equal each other by absorption. So, the first equation holds. In other words, it qualifies as a theorem. The second equation follows by the De Morgan duality metatheorem. So, by the metatheorem which says that if any 2-element Boolean Algebra has a theorem, the consensus theorem holds for all Boolean Algebras. If anything doesn't come as clear here, please don't hesitate to ask.

Why is this true? Well, one could argue that Boolean Algebra originally got skillfully set-up as an algebraic system to behave like classical propositional logic, and in classical propositional logic where "=" gets taken as logical equivalence, each equality in your question corresponds to a theorem. However, I suspect such an answer many people would find that explanation contentious at best. Sometimes things in mathematics just hold true, because they do hold true... or many different explanations can get put forth to explain why something holds true.

Your can't simplify it to x'.z+y.z=x'.z That is not an theorem in Boolean Algebra. Suppose x=1, y=0, z=1. Then, we have 0'.1+0.1=1.1+0=1 for the expression on the left-hand side, and 1'.1=0.1=0 on the right hand side.

share|improve this answer
    
You should be careful here when you state that if a theorem holds for the {0,1} Boolean algebra, then it holds for all Boolean algebras. This is only true for theorems stated in the form of an identity. (For all a,b,c,... some combinations of Boolean operators of a,b,c,... are equal.) Obviously the theorem "the Boolean algebra contains exactly 2 elements" holds in {0,1} but not in an arbitrary Boolean algebra :) –  Ted Aug 31 '11 at 4:24
    
@Ted You might have a point, but unfortunately your example didn't work here. This "the Boolean algebra contains exactly 2 elements" does not hold in a 2-element Boolean algebra. It consists of a true metaproposition (which you may call a metatheorem) about the 2-element Boolean Algebra. The distinction here may take a while to appreciate. –  Doug Spoonwood Aug 31 '11 at 23:31
    
No, it's not a metatheorem. It's a first-order theorem in the language of the Boolean algebra, just like identities are. "The boolean algebra contains exactly 2 elements" can be re-stated as: "There exists x,y in B such that x != y, and for all x,y,z in B, either x=y or y=z or x=z." Identities are stated in the same way: "For all x,y in B, x+xy=x." These are both statements in the object language, not the metalanguage. To distinguish these two cases, you need to restrict the form of the statement. –  Ted Sep 1 '11 at 4:36
    
@Ted I don't see how one needs to restrict the form to distinguish those two cases. The object language of Boolean Algebra consists of the axioms, and those statements that follow from the axioms. I simply do not see how anything about the 2-element Boolean Algebra follows from the axioms, so unless you have a proof here, statements about the 2-element Boolean Algebra end up in the metatheory of Boolean Algebra. –  Doug Spoonwood Sep 2 '11 at 0:37
1  
Can you give a precise statement of your claim "If every 2-element Boolean algebra has a theorem, then it holds for all Boolean algebras" ? Usually, I would interpret this statement to mean: "If a statement in the first order language of Boolean algebras holds in the Boolean algebra {0,1}, then it holds for all Boolean algebras." Since the sentence "the boolean algebra consists of 2 elements" can be expressed in this language, your claim is false unless you restrict the kinds of statements you are considering. –  Ted Sep 2 '11 at 3:44

Something like the following:

$X \cdot Y + X' \cdot Z + Y \cdot Z $ = $X \cdot Y + X' \cdot Z + (X + X') \cdot Y \cdot Z $ = $X \cdot Y + X \cdot Y \cdot Z + X' \cdot Z + X' \cdot Y \cdot Z$ = $X \cdot (Y + Y \cdot Z) + X' \cdot (Z + Y \cdot Z)$ = $X \cdot Y + X' \cdot Z$

share|improve this answer

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.