Logic gates

Everything starts with 0 and 1

A computer handles only two values: 0 and 1, physically realized by a low or high voltage. A logic gate is a small circuit that takes one or two bits as input and produces one bit as output according to a fixed rule. By combining these elementary building blocks, absolutely everything else is built, from the calculator to the processor.

The basic gates

• The AND gate outputs 1 only if both its inputs are 1.
• The OR gate outputs 1 as soon as at least one input is 1.
• The NOT gate inverts its single input: 0 becomes 1, 1 becomes 0.
• The exclusive OR (XOR) gate outputs 1 if the two inputs are different.

Truth tables

A truth table lists the output for every possible combination of inputs.

 A B | AND OR  XOR        A | NOT
-----+-------------      ---+----
 0 0 |  0   0   0          0 |  1
 0 1 |  0   1   1          1 |  0
 1 0 |  0   1   1
 1 1 |  1   1   0

(AND: 1 only if both are 1)
(XOR: 1 only if the inputs differ)

A universal set of building blocks

A remarkable result: the NOT-AND (NAND) gate alone is enough to rebuild all the other gates. It is said to be universal. This is handy in electronics, because an entire circuit can be made with a single type of component.

Classic pitfall

Don't confuse OR and exclusive OR: the ordinary (inclusive) OR outputs 1 even when both inputs are 1, whereas XOR outputs 0 in that case. This difference is crucial for addition, where XOR computes the sum digit and AND computes the carry.