Can someone explain consensus theorem for boolean algebra

36.1k Views Asked by At

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?

3

There are 3 best solutions below

0
On BEST ANSWER

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.

0
On

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$

12
On

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.