Logic

We're not talking about philosophical logic: modus ponens and the like. We're talking about boolean logic aka digital logic.

Boolean logic gets it's name from George Boole who formulated the subject in his 1847 book The Mathematical Analysis of Logic. Boole defined an algebra (not shockingly, called Boolean Algebra) for manipulating combinations of True and False values.  True and False (we'll use T and F as a shorthand)... sounds similar to 1 and 0, or on and off. It should be no surprise that boolean algebra is a foundation of digital circuit design.

Basic Operations

AND

Conjunction: the result is T if, and only if, all inputs are T; if any input is F, the result is F.

OR

Disjunction: the result is T if any (including all) inputs are T; the result is F if, and only if, all inputs are F.

NOT

Negation/Inversion: the result is T if the input is F, and F if the input is T.

Truth Tables

A very useful tool when working with boolean logic is the truth table. For simplicity and consistancy, we'll use A, B, C, and so on for inputs and Q for output. Truth tables list all possible combinations of inputs. At this point we limit our discussions to 2 inputs, though logical operations can have any number. For each combination the corresponding result is noted. As we explore more complex logic circuits we will find that there can be multiple outputs as well.

Here are tables for AND, OR, and NOT.

Combinations

These basic operations can be combined in any number of ways to build, literally, everything else in a computer.

One of the more common combinations is NAND, this is simply NOT AND. Likewise NOR is NOT OR.

Exclusive OR/NOR

One more pair of operations that is particularly useful (as we'll see in a later guide) is exclusive-or and it's negation: exclusive-nor.

The XOR is like an OR with the exception that Q is F if all the inputs are T, and T only if some inputs are T. You could describe this as Q being T when not all inputs are the same.

Of course, XNOR is the opposite: Q is T if, and only if, all inputs are the same.

We will see these gates later when we explore adders.

The Magical NAND

NAND is particularly interesting. Above, we discussed AND, OR, and NOT as fundamental operations. In fact NAND is THE fundamental operation, in that everything else can be made using just NAND: we say that NAND is functionally complete. NOR is also functionally complete but when we consider implementation circuits, NOR generally requires more transistors than NAND.

Look at the truth table for NAND. What happens if the inputs are the same? NAND acts like NOT. So you can make NOT from a NAND by connecting all its inputs together.

NAND is simply NOT AND, so what is NOT NAND? It's equivalent to NOT NOT AND. The NOTs cancel out and we are left with AND. So we can make an AND from 2 NANDs, using one to negate the output of the other.

What about OR, our other basic operation? The truth tables shows what A NAND B is.  What happens if we negate A and B (denoted by placing a bar over A and B)?  We have (NOT A) NAND (NOT B).  Let's write out the truth table for that.

That's interesting; it looks just like the truth table for A OR B.

This is a known phenomenon in boolean algebra: De Morgan's law. It was originally formulated by a Augustus De Morgan, a 19th century mathematician. It defines a relationship between AND and OR. Specifically if you negate an AND or OR expression, it is equivalent to using the other operation with the inputs negated:

NOT (A AND B) = (NOT A) OR (NOT B)

and

NOT (A OR B) = (NOT A) AND (NOT B)

How can we use this? Well, NOT (A AND B) is the same as A NAND B so

A NAND B = (NOT A) OR (NOT B)

if we now replace A with (NOT A) and B with (NOT B) we get

(NOT A) NAND (NOT B) = (NOT (NOT A)) OR (NOT (NOT B))

Knowing from above that pairs of NOTs cancel out, we are left with:

(NOT A) NAND (NOT B) = A OR B

BOOM!

NOT can be made with a NAND, so with 3 NANDs we can make OR. Specifically:

(A NAND A) NAND (B NAND B) = A OR B