BOOLEAN ALGEBRA
by Isai Damier

The logic we apply in studying digital systems is based on a definition of truth made popular by Greek philosopher Aristotle (384 BC–322 BC). To Aristotle, truth had two possible values: true or false: nothing is ever both true and false at the same time; nothing ever contradicts itself; and everything is what it is. In fact, Aristotle’s system of truth devised four laws:

1. The law of identity: which states that A is A; in other words, A = A.
• If it’s raining outside, then it’s raining outside.
• If you are in college, then you are in college.
• If you are happy, then you are happy.
2. The law of non-contradiction: which says A is not non-A; in other words, A = not (not A).
• A happy person is not unhappy.
• An indoor pool is not outdoors.
• If you are a student you are not a non-student.
3. The law of excluded middle: which says that either A is true or not A is true.
• Either you are beautiful or you are not beautiful.
• Either the sky is blue or it is not blue.
• Either your friend is pregnant or she is not pregnant.
4. The law of inference: which says that you can arrive at one fact from other facts.
• If you are in college, and everyone in college is a student, then you are a student.
• If proteins are chains of amino acids, and amino acids are coded from genes, then proteins are coded from genes.
• If you drive drunk, and everyone who drives drunk breaks the law, then you break the law.

About 2000 years after Aristotle’s work, an English mathematician named George Boole (1815–1864) turned Aristotle's logic into an algebra. 90 years later, a Master’s student at MIT, Claude Shannon (1916–2001), proved that Boole’s algebra can be applied to electrical systems. This brief history is part of the reason you are studying digital systems with logic algebra today.

---

---

Let's start our exploration of Boolean algebra with three scenarios. And through these three scenarios, we will demonstrate ten basic facts concerning Boolean algebra.

For our first scenario, imagine that my friend Francois wants to eat a fruit and asks you to bring him an apple OR a banana. In that case you have four choices:

Apple	Banana	Francois's whish is granted	COMMENT
False	False	False	You brought him neither
False	True	True	You brought him a banana
True	False	True	You brought him an apple
True	True	True	You brought him both

Table 1

In Boolean algebra, we use the plus sign (+) to mean OR. Hence, since Francois's request was Apple OR Banana, we can rewrite it as Apple + Banana. We can also rewrite your four choises as

False	+	False	=	False
False	+	True	=	True
True	+	False	=	True
True	+	True	=	True

One further step that we take is to let TRUE = 1 and FALSE = 0, which allows us to further rewrite your four choices as

Axiom 1.	0	+	0	=	0
Axiom 2.	0	+	1	=	1
Axiom 3.	1	+	0	=	1
Axiom 4.	1	+	1	=	1

Notice that in Boolean algebra 1 + 1 = 1. This is because 1 stands for TRUE and TRUE + TRUE = TRUE. What this also means is that Boolean numbers and binary numbers aren’t the same. In binary arithmetic 1 + 1 = 10. Binary numerals is just a translation of the decimal system; Boolean algebra is about logic. Anyway, let’s continue to our second scenario.

Now let’s apply the same Francois situation to another operator: AND. This time Francois wants to make smoothie and asks you to bring him an apple AND a banana. You still have four choices and each one of them will affect Francois’s wish.

Apple	Banana	Francois's whish is granted	COMMENT
False	False	False	You brought him neither
False	True	False	You brought him a banana
True	False	False	You brought him an apple
True	True	True	You brought him both

Table 2

Because Francois specified that he needed an apple AND a banana, you will only satisfy his command by bringing both.

For the AND operator, we use the symbol • in Boolean algebra. Hence, we can rewrite your four choices as

Axiom 5.	0	•	0	=	0
Axiom 6.	0	•	1	=	0
Axiom 7.	1	•	0	=	0
Axiom 8.	1	•	1	=	1

If you think of the AND operator as the multiplication operator in normal algebra, then you are right on the money. They are not the same, but they work the same way.

Now let’s proceed to our third and final scenario. Imagine this time that Francois is allergic to apple and tells you that no matter what you do, do NOT bring apple into the house. In this final case you only have two choices — which of course will affect Francois.

Apple	Francois’s wish is granted
False	True
True	False

Table 3

For the NOT operator we use the apostrophe (’). Hence, we rewrite your two choices as

Axiom 9.		0’	=	1		in Boolean algebra 0 is the opposite of 1.
Axiom 10.		1’	=	0		in Boolean algebra 1 is the opposite of 0.

The ten choices you just made regarding the different situations of Francois are known as the basic facts (or axiom if you want to be fancy) of Boolean algebra. Most textbooks write these facts as complementary pairs to show so–called duality. For mere mortals like you and me, this “complementary to show duality” business simply means that in Boolean algebra if a statement is true then its opposite is also true. Your professor may not like that I am telling you that complementary means opposite, but trust me — that’s all you need to know. Below are the five opposite pairs. (I call them complements just to stay on the good side of your professor. But feel free to call them opposites.)

AND (•)		complement		OR(+)
A		complement		A’
1		complement		0
A = 1		complement		A’ = 0
A = 0		complement		A’ = 1

To show you how this complement stuff works, I have rearranged the ten axioms in pair of opposites. Notice that I get the opposite of an expression by swapping 0 and 1, and by swapping • and +.

1 + 1 = 1		complement		0 • 0 = 0
1 + 0 = 1		complement		0 • 1 = 0
0 + 1 = 1		complement		1 • 0 = 0
0 + 0 = 0		complement		1 • 1 = 1
0’		complement		1
1’		complement		0

As you will find out soon, the duality of the complements (i.e., the fact that the opposite of a true statement is also true) makes it easy to simplify expressions in Boolean algebra. But before I show you, here is a list of convenient truths (textbooks call them theorems) that we get from manipulating the basic facts (axioms) above. Don’t try to memorize the list. If you can’t see why something in the list is true, just replace the letters with 0s and 1s and they will make sense; for example, A + 0 = A is true because if you replace A with 1 you get 1 + 0 = 1 and if you replace A with 0 you get 0 + 0 = 0. You see how easy it is?

I know that was a long list, but it’s a good idea to at least read through it once. Nobody memorizes this thing. As you simplify more and more Boolean expressions, they will come to you. It’s as I said: we derive all of them from the axioms. Now, let me show you an example where we use the theorems to simplify an expression.

Given F = A’ • B + A • B’ + A • B, simplify F.
Solution:

F	=	A’ • B + A • (B’ + B)		we factor out the A using the distributive law (theorem 8)
	=	A’ • B + A • (1)		from theorem 4 we know that B’ + B = 1 (complements)
	=	A’ • B + A		from theorem 1 we know that A • 1 = A (identity)
	=	A + B		finally, from theorem 10 we know that A + A’ • B = A + B

Therefore F = A + B!
Here are a few more examples. You can do them first and then check your work against mine for reinforcement.

Show that A + B • C = (A + B) • (A + C) is true.
Solution:
We will simplify the right side of the equation to make it look like the left side.

A + B • C		=		(A + B) • (A + C)
		=		A • A + A • C + B • A + B • C		After expanding (think FOIL from algebra class)
		=		A + A • C + B • A + B • C		From theorem 3 we know that A • A = A (Idempotency)
		=		A • (1 + C + B) + B • C		After factoring out the A (just like in normal algebra)
		=		A • (1) + B • C		From theorem 2 we know that 1 plus anything is 1
		=		A + B • C		From theorem 1 we know that A • 1 = A (Identity)

Voila!