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:
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:
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
One further step that we take is to let TRUE = 1 and FALSE = 0, which allows us to further rewrite your four choices as
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.
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
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.
For the NOT operator we use the apostrophe (). Hence, we rewrite your two choices as
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.)
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 +.
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.
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.
We will simplify the right side of the equation to make it look like the left side.