4
$\begingroup$

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?

  • 0
    I think you should think about the distribution rule of boolean algebra. It is the counterpart of distribution rule of set operation.2011-08-30

4 Answers 4

9

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.

4

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

2

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.

  • 0
    @Ted "Object language" doesn't just refer to the set of all sentences in the language. A formal proof, with at least two wffs, consists of a *sequence* of wffs, which simply does not belong to the set of sentences in the language. Formal proofs do belong to the object language (though their proof analysis does not).2011-09-04
1

If Y and Z are both true, making the third term (YZ) true, and if X is also true, then the first term (XY) is also true making the third term redundant; if X is false, then the second term (X'Z) is also true, making the third term redundant. Since X must be either true or false, if the third term (YZ) is true, either the first or the second term must also be true, so the third term is always redundant.

  • 0
    This is a very old question and has a well-accepted answer. You have not contributed anything new. Please refrain from opening up old questions unless you have something new to contribute2017-03-12