Boolean Algebra

Boolean Algebra starts with very simple axioms from which more theorems are derived. The axioms define the behaviour of the three basic operations and are equivalent to the truth tables seen before.

Axioms

In the following, \(x\) can represent a 0, a 1, or even a more complicated expression (e.g. \(x = AB\)).

AND

\[\begin{split}\begin{align} 0x &= 0 \\ 1x &= x \end{align}\end{split}\]

OR

\[\begin{split}\begin{align} x + 0 &= x \\ x + 1 &= 1 \end{align}\end{split}\]

NOT

\[\begin{split}\begin{align} \bar{0} &= 1 \\ \bar{1} &= 0 \end{align}\end{split}\]

These axioms lead trivially to some very useful single variable theorems.

Single Variable Theorems

AND

\[\begin{split}\begin{align} xx &= x \\ x\bar{x} &= 0 \end{align}\end{split}\]

OR

\[\begin{split}\begin{align} x + x &= x \\ x + \bar{x} &= 1 \end{align}\end{split}\]

NOT

\[\bar{\bar{x}} = x \]

Multi-variable Axioms

Boolean Algebra is defined as having the same commutative, associative, and distributive properties as regular algebra.

Commutative

\[\begin{split}\begin{align} xy &= yx \\ x + y &= y + x \end{align}\end{split}\]

Associative

\[\begin{split}\begin{align} x(yz) &= (xy)z \\ (x + y) + z &= x + (y + z) \end{align}\end{split}\]

Distributive

\[x(y + z) = xy + xz\]

Multi-variable Theorems

These axioms lead to several useful theorems that help simplify algebraic expressions.

1. Absorption: \(\Large x + xy = x\)

Proof

Start with the left-hand side (LHS) of the equation

\[\begin{split}\begin{align} LHS &= x + xy \\ &= x(1 + y) \\ &= x\cdot{1} \\ &= x \\ &= RHS\ \blacksquare \end{align}\end{split}\]

2. Redundant Literal: \(\Large x + \bar{x}y = x + y\)

Proof

Start with the right-hand side (RHS) of the equation. Go through some expansion and then employ the above Absorption theorem as the last step.

\[\begin{split}\begin{align} RHS &= x + y \\ &= 1(x + y) \\ &= (x + \bar{x})(x + y) \\ &= xx + \bar{x}x + xy + \bar{x}y \\ &= x + 0 + xy + \bar{x}y \\ &= x + xy + \bar{x}y \\ &= x + \bar{x}y \\ &= LHS\ \blacksquare \end{align}\end{split}\]

3. DeMorgan’s Theorem I: \(\Large \overline{x + y} = \bar{x}\bar{y}\)

Danger

Take note of how far each negation line stretches. You can’t split them up.

\(\Large \overline{xy} \neq \bar{x}\bar{y}\)

Also, if you don’t see the big negation lines try zooming in. This is a bug in Mathjax and certain browsers and is out of my control.

Proof

First let’s think about the term \(\Large \overline{x + y}\). This means the negation of \(x + y\). From the single variable theorems, we know a term and its negation behave the following ways:

\[\begin{split}q\bar{q} = 0 \\ q + \bar{q} = 1\end{split}\]

Suppose we have two terms \(q\) and \(p\), and we have no knowledge of either term (they could be any combination of 0 or 1). If we can show that either of the above relations are always true (e.g. \(qp = 0\)), then we know \(q\) and \(p\) must be inverses of eachother.

For DeMorgan’s Theorem I, we want to show \(\bar{x}\bar{y}\) is the inverse of \(x + y\). Let’s first try using the OR relation to prove they are infact inverses. If, and only if, they are inverses will \(\bar{x}\bar{y} + (x + y) = 1\). This is shown below making use of the redundant literal theorem.

\[\begin{split}\begin{align} LHS &= \bar{x}\bar{y} + (x + y) \\ &= x + \bar{x}\bar{y} + y \\ &= x + \bar{y} + y \\ &= x + 1\\ &= 1 \\ &= RHS\ \blacksquare \end{align}\end{split}\]

Now, to be clear, the ORing of two does not necessarily always equal one only if the the two terms are inverses. If either of the terms were always a 1, then it doesn’t matter what the other term is; the ORing will always yield 1.

But, our proof above is completely agnostic to the values of \(x\) and \(y\). Therefore the terms \(x + y\) and \(\bar{x}\bar{y}\) could represent any Boolean value. Thus the only way their ORing could always equal 1 is if they are in fact inverses. \(\bar{x}\bar{y}\) is therefore the inverse of \(x + y\), or put another way:

\[ \Large \overline{x + y} = \bar{x}\bar{y} \]

---

Bonus Proof:

Using the same logic and the AND operation. We want to show that \((x + y)(\bar{x}\bar{y}) = 0\)

\[\begin{split}\begin{align} LHS &= (x + y)(\bar{x}\bar{y}) \\ &= x\bar{x}\bar{y} + y\bar{x}\bar{y} \\ &= 0y + 0\bar{x} \\ &= 0 + 0\\ &= 0 \\ &= RHS\ \blacksquare \end{align}\end{split}\]

Again, we have made no restrictions on the values \(x\) and \(y\) can have. The only way the ANDing can always be zero is if the two terms are inverses of eachother.

---

Bonus Bonus Proof:

All the theorems can also be proven using truth tables, but this mathod becomes cumbersome for anything more than two variables. You should get used to using the algebraic approach.

\(\Large x\)	\(\Large y\)	\(\Large x + y\)	\(\Large\overline{x + y}\)	\(\Large\overline{x}\)	\(\Large\overline{y}\)	\(\Large \bar{x}\bar{y}\)
0	0	0	1	1	1	1
0	1	1	0	1	0	0
1	0	1	0	0	1	0
1	1	1	0	0	0	0

When two columns are the same, it means those expressions must be equal.

4. DeMorgan’s Theorem II: \(\Large \overline{xy} = \bar{x} + \bar{y}\)

Proof

This proof is left up to the reader.

Examples

Concept Check:

Use Boolean algebra to simplify the following expressions.

1. \(\Large (\bar{A} + B)(A + B)\)

---

2. \(\Large \overline{(\bar{A} + C)(B + \bar{D})}\)

Solution

\[\begin{split}\begin{align} (\bar{A} + B)(A + B) &= \bar{A}A + \bar{A}B + AB + BB \\ &= 0 + \bar{A}B + AB + B \\ &= B(\bar{A} + A + 1) \\ &= B(1 + 1) \\ &= B \end{align}\end{split}\]

---

\[\begin{split}\begin{align} \Large \overline{(\bar{A} + C)(B + \bar{D})} &= \Large \overline{\bar{A} + C} + \overline{B + \bar{D}} \\ &= \Large \bar{\bar{A}}\bar{C} + \bar{B}\bar{\bar{D}} \\ &= \Large A\bar{C} + \bar{B}D \end{align}\end{split}\]

Note: If you are not seeing negation bars when you think you should, try zooming in. This is a known bug in MathJax and some browsers that will hopefully be fixed soon, but is out of my control.