Boolean Algebra could be considered part of the hardware section, as well as the software section. I will cover the basics of Boolean algebra first, and then briefly describe the early silicon implementation.
Boolean Algebra is a logic system based on two state logic (on/off or 0/1). An item could only be in one of the two states. This is from where the term digital was created. First, we will have a few tables to show the basic States of Boolean Algebra (or Logic)
| States | |
|---|---|
| On | 1 |
| Off | 0 |
| AND | ||
|---|---|---|
| Input A | Input B | Results |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
| OR | ||
|---|---|---|
| Input A | Input B | Results |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
| XOR (Exclusive OR) | ||
|---|---|---|
| Input A | Input B | Results |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
| NOT | |
|---|---|
| Input A | Results |
| 0 | 1 |
| 1 | 0 |
| NAND (NOT AND) | |||
|---|---|---|---|
| Input A | Input B | AND Results | NAND Results |
| 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 |
| NOR (NOT OR) | |||
|---|---|---|---|
| Input A | Input B | OR Results | NOR Results |
| 0 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 |
When put into silicon, each of this logic units was considered a gate. The first Large Scale Integration was putting four gates on a single chip. The main problem was they could fit more NAND and NOR gates on a chip than they could AND and OR gates. Electrical Engineers had to take this “fact” into consideration when designing boards.In the past, the logic was represented by a cap for AND and a cup for OR. Since then, maybe for convenience of typing, the cap has been changed to a multiplication symbol (since anything times zero is zero) and an addition symbol.
| Symbols | ||
|---|---|---|
| Function | Old Symbol | New Symbol |
| AND | ∩ | * |
| OR | ᴜ | + |
| NOT | – (bar over negations) | ~ |
Because of the ease of typing, all examples will use the new notation. Now, if all equations were simply having two inputs, the problems would be easy to solve. There are some basic rules which help solve problems. One site that can help with solving Boolean Algebra problems is on electronics-course.com. There are some basic Theorems for solving Boolean Algebra problems. These are taken from the previously mentioned website:
| Basic Theorems of Boolean Algebra | ||
|---|---|---|
| Law | Input | Output |
| Idempotent | A * A A + A |
A A |
| Associative | (A * B) * C (A + B) + C |
A * (B * C) A + (B + C) |
| Commutative | A * B A + B |
B * A B + A |
| Distributive | A * (B + C) A + (B * C) |
A * B + A * C (A + B) * (A + C) |
| Identity | A * 0 A * 1 A + 0 A + 1 |
0 A 0 1 |
| Complement | A * ~A A + ~A |
0 1 |
| Involution | ~(~A) | A |
| DeMorgan’s | ~(A * B) ~(A + B) |
~A + ~B ~A * ~B |
All of the Laws, except perhaps DeMorgan’s Law are obvious. However, creating a Truth Table for each of these corollaries might be helpful.
| Truth Table: ~(A * B) =? ~A + ~B | |||||||
|---|---|---|---|---|---|---|---|
| A | ~A | B | ~B | A*B | ~(A*B) | ~A+~B | Match? |
| 0 | 1 | 0 | 1 | 0 | 1 | 1 | Yes |
| 0 | 1 | 1 | 0 | 0 | 1 | 1 | Yes |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 | Yes |
| 1 | 0 | 1 | 0 | 1 | 0 | 0 | Yes |
| Truth Table: ~(A + B) =? ~A * ~B | |||||||
|---|---|---|---|---|---|---|---|
| A | ~A | B | ~B | A+B | ~(A+B) | ~A*~B | Match? |
| 0 | 1 | 0 | 1 | 0 | 1 | 1 | Yes |
| 0 | 1 | 1 | 0 | 1 | 0 | 0 | Yes |
| 1 | 0 | 0 | 1 | 1 | 0 | 0 | Yes |
| 1 | 0 | 1 | 0 | 1 | 0 | 0 | Yes |
Thus we have shown that DeMorgan’s Laws are true. Now try a couple of simplifications.
A'B'C' + AB'C' +A'B'D (change it to a form that matches the notation above) ~A*~B*~C + A*~B*~C + ~A*~B*D (extract out ~B*~C out of the first 2 terms) ~B*~C*(A+~A) + ~A*~B*D (Distributive Law) ~B*~C*1 + ~A*~B*D (Complement Law) ~B*(~C + ~A*D) (Distributive Law)
I do not see a way to reduce it further. Mot for a bit harder one>
A*B*C + A*B*~C + A*C*D + A*~C*D + A*C*~D + A*~(C + D) A*B*C + A*B*~C + A*C*D + A*~C*D + A*C*~D + A*~C*~D [DeMorgan's Law] A*B*C + A*B*~C + D*(A*C + A*~C) + ~D*(A*C + A*~C) [Distribution] A*B*C + A*B*~C + (D + ~D)*(A*C + A*~C) [Distribution] B*(A*C + A*~C) + 1*(A*C + A*~C) [Distribution and Complement] (B + 1)*(A*C + A*~C) [Distribution] 1*(A*C + A*~C) [Complement] A*C + A*~C [Simplification] A*(C+~C) [Distribution] A*1 [Complement] A [Simplification]
Now, the purpose of these reductions is to simplify circuits and limit the number of gates needed to create the desired circuit. I was looking for a way to draw a circuit to match the Boolean expressions on this page. One tool that does look promising is Scheme-It.