We'll also discuss the concept of gate deltay.

This is a diagram of a NOT gate. It is a triangle with a circle on the right. The circle indicates "negation".

The truth table defines the behavior of this gate.

x |
z |

0 | 1 |

1 | 0 |

where **x** is the input and **z** is the output.

The output of AND_{2} gate is 1 only if both inputs
are 1. Otherwise, the output is 0.

The truth table defines the behavior of this gate.

x_{1} |
x_{0} |
z |

0 | 0 | 0 |

0 | 1 | 0 |

1 | 0 | 0 |

1 | 1 | 1 |

The function implmented by **AND _{2}** gates has interesting
properties:

- The function is symmetric. Thus,
**x * y == y * x**. This can be verified by using truth tables. We use*****to represent AND_{2}. - The function is associative. Thus,
**(x * y) * z == x * (y * z)**. This can be verified by using truth tables.

That is, an AND gate with n-inputs is the AND of all the bits. This is not ambiguous because the AND function is associative (all parenthesization of this expression are equivalent).

The output of OR_{2} gate is 0 only if both inputs
are 0. Otherwise, the output is 1.

The truth table defines the behavior of this gate.

x_{1} |
x_{0} |
z |

0 | 0 | 0 |

0 | 1 | 1 |

1 | 0 | 1 |

1 | 1 | 1 |

The function implemented by **OR _{2}** gates has interesting
properties:

- The function is symmetric. Thus,
**x + y == y + x**. This can be verified by using truth tables. We use "+" to represent**OR**_{2} - The function is associative. Thus,
**(x + y) + z == x + (y + z)**. This can be verified by using truth tables.

That is, an AND gate with n-inputs is the AND of all the bits. This is not ambiguous because the AND function is associative (all parenthesization of this expression are equivalent).

NAND_{k} gates is define unusually. Since NAND_{2}
is *not* associative, the definition is based on AND_{2}.

In particular

Thus, NAND_{k} is the negation of AND_{k}.

The truth table defines the behavior of this gate. It's the
negation of **AND _{2}**.

x_{1} |
x_{0} |
z |

0 | 0 | 1 |

0 | 1 | 1 |

1 | 0 | 1 |

1 | 1 | 0 |

The function implemented by **NAND _{2}** gates has interesting
properties:

- The function is symmetric. Thus,
**x NAND y == y NAND x**. This can be verified by using truth tables. - The function is
*not*associative. This can be verified by using truth tables.

The output of NOR_{2} gate is the negation of
OR_{2}.

The truth table defines the behavior of this gate.

x_{1} |
x_{0} |
z |

0 | 0 | 1 |

0 | 1 | 0 |

1 | 0 | 0 |

1 | 1 | 0 |

The function implmented by **NOR _{2}** gates has interesting
properties:

- The function is symmetric. Thus,
**x NOR y == y NOR x**. This can be verified by using truth tables. - The function is
*not*associative. This can be verified by using truth tables.

The output of XOR_{2} gate is 1 only if the inputs
have opposite values. That is, when one input has value 0, and
the other has value 1.. Otherwise, the output is 0.

This is called *exclusive-or*. The definition of
OR_{2} is *inclusive-or*, where the output is
1 if either input is 1, or if both inputs are 1.

XOR_{2} can be defined using AND_{2}, OR_{2},
and NOT.

x XOR y == ( x AND (NOT y) ) OR ( (NOT x) AND y ) == x\y + y\x

Here's a diagram of the XOR_{2} gate.

If you look carefully at the drawing of the gate, there is a second arc behind the first one near the inputs. Since this second arc is hard to see, it's usually a good idea to write the word "XOR" inside the gate.

The truth table defines the behavior of this gate.

x_{1} |
x_{0} |
z |

0 | 0 | 0 |

0 | 1 | 1 |

1 | 0 | 1 |

1 | 1 | 0 |

The function implmented by **XOR _{2}** gates has interesting
properties:

- The function is symmetric. Thus,
**x (+) y == y (+) x**. This can be verified by using truth tables. (We use (+) to denote logical XOR--ideally, we'd draw it with a + sign inside a circle, but HTML doesn't seem to have a symbol for this). - The function is associative. Thus,
**[ x (+) y ] (+) z == x (+) [ y (+) z ]**. This can be verified by using truth tables.

That is, an XOR gate with n-inputs is the XOR of all the bits. This is not ambiguous because the XOR function is associative (all parenthesization of this expression are equivalent).

The output of XNOR_{2} gate is the negation of
XOR_{2} and has 1 when both inputs are the same.

If you look carefully at the drawing of the gate, there is a second arc behind the first one near the inputs. Since this second arc is hard to see, it's usually a good idea to write the word "XNOR" inside the gate.

The truth table defines the behavior of this gate.

x_{1} |
x_{0} |
z |

0 | 0 | 0 |

0 | 1 | 1 |

1 | 0 | 1 |

1 | 1 | 0 |

The function implmented by **XNOR _{2}** gates has interesting
properties:

- The function is symmetric. Thus,
**x XNOR y == y XNOR x**. This can be verified by using truth tables. - The function is associative. Thus,
**(x XNOR y) XNOR z == x XNOR (y XNOR z)**. This can be verified by using truth tables.

That is, an XNOR gate with n-inputs is the XNOR of all the bits. This is not ambiguous because the XNOR function is associative (all parenthesization of this expression are equivalent).

(Error-checkers! You may wish to verify this, and email me if this is incorrect!).

These circuits can implement any truth table.

- The output of a gate may only be attached to the input of another gate. (Think of this as a directed edge from output to input).
- There must be no cycles in the circuit. Treat the circuit like a directed graph with directed edges defined in the previous item.
- Although the output of a gate may be attached to more than one input, an input may not have two different outputs attached to it (this would create conflicting input signals).
- Each input of a gate must come from either the output of another gate or a source. A source is a source that generates either a 0 or 1.

This delay is due to the fact that information can travel at most, the speed of light, and in reality, the time it takes to do the computation is not infinitely quick.

This delay limits how fast the inputs can change and yet the output have meaningful values. It also allows certain kinds of circuits to be created that don't follow the rules from the previous section. In particular, flip flops (to be discussed later) can be generated from gates that use cycles.

While this is true, I subscript it because an **AND _{2}**
and an

Thus, I make the distinction by subscripting the number of inputs.

Real computers don't use these kinds of gates, because they take far too much space. With VLSI technology, you can cram millions of gates onto a wafer no bigger that your thumbnail.

The behavior of logic gates can be described by truth tables. However, because these gates are "physical", they have some properties not expressed in truth tables. In particular, gate delay describes the amount of time it takes for the output to change when the input changes. This time is not zero, thus, one must wait a short amount of time for the output to take effect.

We'll discuss how to build circuits from these gates in a later set of notes.