The basic building blocks of a computer are called “logical gates” or just “gates”.
Gates are basic circuits that have at least one (and usually more) input and exactly one output. Input and output values are the logical values true and false. In computer architecture it is common to use 0 for false and 1for true. Gates have no memory. The value of the output depends only on the current value of the inputs. This fact makes it possible to use a truth table to fully describe the behavior of a gate.
We usually consider three basic kinds of gates, the AND-gate, the OR-gate, and the NOT-gate (or inverter).
An AND-gate has an arbitrary number of inputs.
The output value is 1 if and only if all of the inputs are 1.
Otherwise the output value is 0.
The name has been chosen because the output is 1 if and only if the first input and the second input is 1.
The truth table for an AND-gate with two inputs looks like this:
x y | z ------- 0 0 | 0 0 1 | 0 1 0 | 0 1 1 | 1
Like the AND-gate, the OR-gate can has two inputs.
The output value is 1 if and only of at least one of the input values are 1.
Otherwise the output is 0.
In other words, the output value is 0 only if all inputs are 0. The name has been chosen because the output is 1 if and only if the first input or the second input is 1.
The truth table for an OR-gate with two inputs looks like this:
x y | z ------- 0 0 | 0 0 1 | 1 1 0 | 1 1 1 | 1
An INVERTER has exactly one input and one output.
The value of the output is 1 if and only if the input is 0.
Otherwise, the output is 0.
In other words, the value of the output is the exact opposite of the value of the input.
The truth table for an INVERTER looks like this:
x | y ----- 0 | 1 1 | 0
Sometimes, it is practical to combine functions of the basic gates into more complex gates, for instance in order to save space in circuit diagrams. In this section, we show some such combined gates together with their truth tables.
The NAND-gate is an AND-gate with an inverter on the output.
The NAND-gate, like the AND-gate can takes two inputs.
The truth table for the NAND-gate is like the one for the AND-gate, except that all output values have been inverted:
x y | z ------- 0 0 | 1 0 1 | 1 1 0 | 1 1 1 | 0
The NOR-gate is an OR-gate with an inverter on the output.
The NOR-gate, like the OR-gate takes two inputs.
The truth table for the NOR-gate is like the one for the OR-gate, except that all output values have been inverted:
x y | z ------- 0 0 | 1 0 1 | 0 1 0 | 0 1 1 | 0
The EXCLUSIVE-OR-gate is similar to an OR-gate.
It takes two inputs.
Its output value is 1 if and only if exactly one input is 1 (and thus the other 0). Otherwise, the output is 0.
The truth table for an EXCLUSIVE-OR-gate with two inputs looks like this:
x y | z ------- 0 0 | 0 0 1 | 1 1 0 | 1 1 1 | 0
Summary
As it turns out, it is possible to build any kind of gate using only NAND-gates.
To see this, first observe that an INVERTER is just a NAND-gate with only one input.
Second, an AND-gate can be built as a NAND with an inverter on its output.
Last, an OR-gate can be built with a NAND-gate with an inverter on each input.
In some circuit technology, it is actually easier to build a NAND-gate than any of the other gates. In that case, the NAND-gate is considered the most primitive building block, and everything else is built from it.
Similarly, all gates can also be realized from only NOR-gates.
Again an inverter is just a NOR-gate with only one input.
An OR-gate is a NOR-gate with an inverter on its output, and an AND-gate is just a NOR-gate with an inverter on each input.