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 **NOT**s 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 **NOT**s 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 **NAND**s we can make **OR**. Specifically:

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