Logic and Gates

In Lesson 1, we did our first manipulation of data using transistors. We changed a 1 into a 0 and back again. Cool! Unfortunately, this alone will not let us do anything interesting. In order to take our next step toward the computer, we need to perform more complex transformations with multiple inputs.

I'm going to give a _very_ brief introduction to the field of boolean algebra here. Boolean algebra is the area of mathematics that deals with performing algebra on variables which may only hold 2 values: 0/false and 1/true. For the sake of brevity, and because I don't think it's necessary in order to understand what I'm trying to teach, I will not be getting into much detail about this right now. Ask me for more information or "use the google" if you're curious :).

Many of the same rules that apply to decimal algebra (commonly known as algebra with no qualifier) also apply in boolean algebra. For instance the distributive property of multiplication works in boolean algebra as the distributive property of AND.

The two most basic operations in boolean algebra are AND and OR. These are related to TIMES and PLUS in algebra. The definition of AND is "a AND b is true if and only if both a and b are true." The definition of OR is "a OR b is true if either a or b or both are true."

a AND b = c
-----------
0 AND 0 = 0
0 AND 1 = 0
1 AND 0 = 0
1 AND 1 = 1

a OR b = c
----------
0 OR 0 = 0
0 OR 1 = 1
1 OR 0 = 1
1 OR 1 = 1

To put this into terms that are more like those used in Lesson 1, let's look at how they translate to bits. Since bits hold values of 1 or 0, we'll use those values to represent true and false respectively and look at AND and OR. These tables are commonly called truth tables and are usually written in a shorter form.

AND
a . b = c 
--|---|-- 
0 | 0 | 0 
0 | 1 | 0 
1 | 0 | 0 
1 | 1 | 1 

OR
a + b = c
--|---|--
0 | 0 | 0
0 | 1 | 1
1 | 0 | 1
1 | 1 | 1

NOT
a' = c
---|--
0  | 1
1  | 0

The inverter from Lesson 1 is an operation in boolean algebra called NOT. Let's take a look at NOT as well as AND and OR in the standard truth table format. The symbols ".", "+" and "'" are standard symbols for representing AND OR and NOT respectively. As you might guess, the "+" and "." symbols were chosen because the operations they represent behave similarly to PLUS and TIMES.

I'd love to make a really smooth transition to building AND and OR from transistors at this point. Unfortunately, that is not in the cards. The simplest boolean operations to build from transistors (and therefor those most often used in building computers) are not AND and OR. Let's take a quick look at the ones more often used in modern electronics from the logic perspective and then move on to building them from transistors.

The two easiest boolean algebra operations to make with transistors are NAND and NOR. These are the equivalent of taking the result of AND and OR respectively and applying a NOT to it. I'm going to be a little bit like a teacher and suggest that you work out the truth tables for NAND and NOR for yourself. Of course I'm not a teacher, so the answers are at the bottom of this page.

NAND      __ Output
        _|   Source
   A__||
Gate  ||_
         | Drain
         |
        _| Source
   B__||
Gate  ||_
         |
         |  Drain
        --- Ground (0)
         -  

When boolean functions are built from electronic components like transistors, we call them gates, so what you see here is a NAND gate. Like we learned in Lesson 1, the circuit will default to 1 when neither transistor is active. Let's walk through this gate. When neither transistor is active, that means that A and B are 0 and the result is that the output remains in the default state of 1. If you built your truth tables, you'll see that this matches up. When A is 1 and B is 0, the top transistor is active, but the bottom transistor still blocks the connection, so the output is still 1. When B is 1 and A is 0, the connection is blocked by the top transistor and the output is 1 again. Finally, when both A and B are 1, both transistors are active and there is a connection between the output and the ground, resulting in an output value of 0.

NOR            __ Output
              |   
   Source ____|_____
        _|         _| Source
   A__||      B__||   
Gate  ||_  Gate  ||_
         |          | 
    Drain|__________| Drain
              |  
             --- Ground (0)
              -

Here in the NOR gate, we see what is called a parallel circuit, as opposed to the series circuit that we saw in the NAND gate. In this parallel arrangement, whenever either A or B or both are 1 (either or both of the transistors are active), the output has a connection to the ground and becomes 0. Only when neither A nor B are 1 will the output remain at its default value of 1. Look at that, I used the word nor to describe the NOR gate!

Thanks to the relative simplicity of boolean operations, any possible boolean algebraic equation can be represented using only the three gates we've already looked at (NOR, NAND and NOT). I'm sure that some very smart people have proven that, but I'm not going to try it myself.

That's it for this lesson. I hope that by this point, you are getting the inkling of how computers can perform math. We'll turn that inkling into solid knowledge by doing some addition and subtraction in the next lesson.

Here are the truth tables for NOR and NAND:

NAND
(a.b)'= c 
--|---|-- 
0 | 0 | 1 
0 | 1 | 1 
1 | 0 | 1 
1 | 1 | 0 

NOR
(a+b)'= c
--|---|--
0 | 0 | 1
0 | 1 | 0
1 | 0 | 0
1 | 1 | 0

This isn't much of an advanced anything, but just some extra knowledge. There are really only two other common logic functions that you may have heard of. The most popular is probably the XOR, exclusive or. XOR is defined as "A or B but not both" and is usually what we mean when we use the English word "or". XOR's cousin XNOR, exclusive nor, is not so friendly, it's defined as "both A and B or neither A nor B", it's the exact opposite of XOR.

---

Course Index

Introduction
Lesson 1: Bits and Transistors (plus CMOS)
Lesson 2: Logic and Gates

Planned:
Lesson 3: Adding and Subtracting
Lesson 4: Memory
Lesson 5: Sequences
Lesson 6: A Calculator

Ideas:
The internet, protocols
Website types and languages