There are only three **logic gates** from which all digital electronics can be built. They are AND, OR, and NOT. Each has one or two inputs (only NOT has only one input) and each has one output. All other logic is derived from these three concepts.

AND

____ Truth Table
A -------| `-. Input Out
| \_________ Out A B O
| / -----------
B -------|___,-' 0 0 0
0 1 0
1 0 0
1 1 1

The AND gate's output turns on when both inputs are turned on. Therefore, A *and* B must be 1 for the output to be 1.

You can simulate this with a number of relays whose switched sides are wired in series. (An AND gate can have any number of inputs - We are showing the simplest form here.) All of the relays must be switched on in order for current to flow. Hence, for each input on an AND gate, you need one transistor. You can actually construct some gates out of nothing but diodes as well, but I am taking a predominantly functional look at these gates here. In practice, they may be made out of diodes, diodes and resistors, or transistors.

OR

____ Truth Table
A -------\ `-._ Input Out
\ `._______ Out A B O
/ _,' -----------
B -------/___,-' 0 0 0
0 1 1
1 0 1
1 1 1

The OR gate turns on if any of its inputs are 1. Like the AND, it is a very simple device, made up of one transistor (or relay or what have you) per input. All of their switching sides are wired in parallel so that if any of them turn on, the output is turned on.

With both AND and OR gates, not only can the gates themselves have any number of inputs, but you can also cascade gates together and get exactly the same behavior out of them. If you run the output out of one two input and gate into the input of another you now have a three input and gate. For further proof, draw out the truth tables.

NOT

|\ Truth Table
| \ In(A) Out
A ------| >O----- Out -----------
| / 0 1
|/ 1 0

The NOT gate is also known as an inverter, because that is (simply enough) what it does; 1 becomes 0, 0 becomes 1. The not gate is extremely significant in spite of its limited function because it is used to create two *other* gates (or functions) when combined with the previously mentioned gates; NAND and NOR.

A CMOS inverter contains two transistors, one N type and one P type. The input goes to both of their inputs simultaneously. If the input voltage is 0 (or ground) then the P-type transistor connects VCC to the output. If the input voltage is 1 (or VCC) then the N-type transistor connects ground (or 0) to the output.

NAND AND NOR

____ Truth Table
A -------| `-. Input Out
| \/\_______ Out A B O
| /\/ -----------
B -------|___,-' 0 0 1
0 1 1
1 0 1
1 1 0
____ Truth Table
A -------\ `-._ Input Out
\ `./\_____ Out A B O
/ _,'\/ -----------
B -------/___,-' 0 0 1
0 1 0
1 0 0
1 1 0

One simply adds the inverter to the output of the AND or OR gate and reverses its logic; NAND is only true when both inputs are *not* 1. Similarly, a NOR gate will be true only when neither input is 1, rather than either.

XOR

____ Truth Table
A ------\\ `-._ Input Out
\\ `._______ Out A B O
// _,' -----------
B ------//___,-' 0 0 0
0 1 1
1 0 1
1 1 0

XOR (Exclusive OR) is the most complex of the "basic" gates, and one of the most interesting. It works like an OR function except that if *both* inputs are 1, it will return 0. This is useful for toggling bits (XOR with 1) or for rapidly clearing a series of bits (XOR the series with itself.)

XOR can be built with two inverters (NOT), an OR, *and* two ANDs.

|\ ____
A --+---| >O---| \
| |/ |AND|---+
| +--------|___/ | __
| | +----\ `-.
| | > OR>---- Out
| | +----/_,-'
| | |\ ____ |
B ----+-| >O---| \ |
| |/ |AND|---+
+----------|___/

You can also build it with four two-input NAND gates, which are of course themselves made up of an AND and a NOT:

_____
------+--------------| \
| |NAND|O--+
| _____ +--|____/ | _____
+--| \ | +--| \
|NAND|O--+ |NAND|O--- Out
+--|____/ | _____ +--|____/
| +--| \ |
| |NAND|O--+
------+--------------|____/

Again, draw out the (slightly lengthy) truth table if you are in doubt.

References:

- Webpage:
__Basic Logical Functions and Gates__. Ken Bigelow, 2002. (http://www.play-hookey.com/digital/basic_gates.html)
- Webpage:
__CMOS technology demonstration__. (http://tech-www.informatik.uni-hamburg.de/applets/cmos/cmosdemo.html)