Consensus Theorem

 ____ ____ ____ ____ _________ ____ ____ ____ ____
||y |||i |||t |||s |||       |||s |||i |||t |||e ||
||__|||__|||__|||__|||_______|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/_______\|/__\|/__\|/__\|/__\|

When I learned about boolean algebra the one thing that didn't seem clear to me was the consensus theorem.

x y + \overline{x} z + y z = x y + \overline{x} z

Once I learned about this I was confused why this would work. It seems like such a random property. To get a better sense of what it is saying I tried to prove it myself. The first idea I had to prove it is to make a truth table for all the parts. Looking at the truth table below you should be able to see that the $y z$ term is redundant.

$x$	$y$	$z$	$x y$	$\overline{x} z$	$y z$
0	0	0	0	0	0
0	0	1	0	1	0
0	1	0	0	0	0
0	1	1	0	1	1
1	0	0	0	0	0
1	0	1	0	0	0
1	1	0	1	0	0
1	1	1	1	0	1

This proves that the theorem is true, but it didn't help me understand why it is true. The next thing I did was prove it by manipulating the boolean algebra. This strategy was probably this worst way to do this as it was the most work and revealed nothing to me about why it is true. There might have been a better process to take that is more enlightening, but I did not find it. Despite this I will put the proof at the bottom of this page.

Ultimately the thing that gave me the best understanding of why the theorem works is by understanding what it is saying. The most important term to focus on is the $y z$ term. As it is a boolean value there are two values it could be, and if we prove that for both of these values it is redundant than we have proved the term is redundant in all cases.

First let's consider when it is false. We can substitute the value false into the equation to get

x y + \overline{x} z + F

Doing an or operation between a value and false will give the value unchanged. That means that the $y z$ term has no effect when if is false.

When $y z$ is true it is a bit harder to show that it has no effect, but still easy enough. Doing an or operation between a value and true will always be true, so we need to show that $x y + \overline{x} z$ is always true when $y z$ is true. When the result of an and operation is true it means that both values where true, so in this case $y$ is true, as well as $z$ . Knowing that they are both true the next step is substituting both of them into the equation.

x T + \overline{x} T

Doing an and operation between a value and true will not change the original value. This means that the equations is equal to $x + \overline{x}$ . An or operation between a value and its opposite will always be true which shows that $x y + \overline{x} z$ is always true. That was the final thing needed to show that the consensus theorem is true.

Here is the proof using only boolean algebra. I will start with the expression $x y + \overline{x} z$ and manipulate it until the $y z$ term is added.

x y + \overline{x} z

De Morgan's law (on each part)

\overline{x} + \overline{y} + x + \overline{z}

De Morgan's law (on the whole expression)

\frac{}{(\overline{x} + \overline{y}) (x + \overline{z})}

Distribute

\frac{}{\overline{x} x + \overline{x} \overline{z} + \overline{y} x + \overline{y} \overline{z}}

The $\overline{x} x$ part will always be false.

\frac{}{\overline{x} \overline{z} + \overline{y} x + \overline{y} \overline{z}}

De Morgan's law (on the whole expression)

(\overline{x} \overline{z}) (\overline{y} x) (\overline{y} \overline{z})

De Morgan's law (on each part)

(x + z) (y + \overline{x}) (y + z)

Distribute the first two parts

(x y + x \overline{x} + z y + z \overline{x}) (y + z)

Ignore $\overline{x} x$

(x y + z y + z \overline{x}) (y + z)

Distribute the rest

x y y + z y y + z \overline{x} y + x y z + z z y + z z \overline{x}

Simplify and reorder terms

x y + \overline{x} z + y z + y z + x y z + \overline{x y z}

Factor out $y z$

x y + \overline{x} z + y z (1 + 1 + x + \overline{x})

$(1 + 1 + x + \overline{x})$ will always be true

x y + \overline{x} z + y z