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:
 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.
 The law of noncontradiction: which says A is not nonA; 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 nonstudent.
 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.
 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?
Theorem 1. 
A + 0 = A 
A • 1 = A 
Identities 
Theorem 2. 
A + 1 = 1 
A • 0 = 0 
Null elements 
Theorem 3. 
A + A = A 
A • A = A 
Sameness/Idempotency 
Theorem 4. 
A + A’ = 1 
A • A’ = 0 
Complements 
Theorem 5. 
( A’ )’ = A 

Involution 
Theorem 6. 
A + B = B + A 
A • B = B • A 
Commutative 
Theorem 7. 
A + (B + C) = (A + B) + C 
A • (B • C) = (A • B) • C 
Associative 
Theorem 8. 
A • (B + C) = A • B + A • C 
A + B • C = (A + B) • (A + C) 
Distributive 
Theorem 9. 
(A + B)’ = A’ • B’ 
(A • B)’ = A’ + B’ 
DeMorgan’s theorem 
Theorem 10. 
A + A’ • B = A + B 
A • (A’ + B) = A • B 
DeMorgan’s theorem 
Theorem 11. 
A + A • B = A 
A • (A + B) = A 
Absorption/Covering 
Theorem 12. 
A • B + A • B’ = A 
(A + B) • (A + B’) = A 
Combining 
Theorem 13. 
A • B + A’ • C + B • C = A • B + A’ • C 
(A+B) • (A’+C) • (B+C) = (A+B) • (A’+C) 
Consensus 
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!