Logic Gates

Within these castle walls be forged Mavens of Computer Science ...

— Merlin, The Coder

The 7400 chip contains four logical NAND gates.

Introduction

A logic gate is an idealized or physical device implementing a Boolean function; that is, it performs a logical operation on one or more binary inputs and produces one or more binary outputs.

Symbols

The table below provides the symbols that are used to represent common gates.

Formal Name	Abbreviated Name	Symbol	Gate	Truth Table
Buffer				Inputs Outputs $A$ $Q=A$ 0 0 1 1
Conjunction	AND	$A\land B$		Inputs Outputs $A$ $B$ $Q=A\land B$ 0 0 0 0 1 0 1 0 0 1 1 1
Disjunction	OR	$A\lor B$		Inputs Outputs $A$ $B$ $Q=A\lor B$ 0 0 0 0 1 1 1 0 1 1 1 1
Exclusive OR	XOR	$A\oplus B$		Inputs Outputs $A$ $B$ $Q=A\oplus B$ 0 0 0 0 1 1 1 0 1 1 1 0
Inverter	NOT	$\neg A$		Inputs Outputs $A$ $Q={\overline {A}}$ 0 1 1 0
Negated Conjunction	NAND	${\overline {A\land B}}$		Inputs Outputs $A$ $B$ $Q={\overline {A\land B}}$ 0 0 1 0 1 1 1 0 1 1 1 0
Negated Disjunction	NOR	${\overline {A\lor B}}$		Inputs Outputs $A$ $B$ $Q={\overline {A\lor B}}$ 0 0 1 0 1 0 1 0 0 1 1 0
Negated Exclusive OR	NOT XOR	${\overline {A\oplus B}}$		Inputs Outputs $A$ $B$ $Q={\overline {A\oplus B}}$ 0 0 1 0 1 0 1 0 0 1 1 1

Additionally, a multiplexer is a device which selects from $n$ digital inputs and forwards the signal to a single output line. Given $n$ inputs, there are $log_{2}n$ selector pins. Conversely, a demultiplexer forwards the signal from a single line to one of multiple outputs.

Formal Name	Abbreviated Name	Symbol	Gate	Truth Table
Multiplexer	MUX	${A\cdot {\overline {S}}}\lor {B\cdot S}$		Inputs Outputs $S$ $A$ $B$ $Q={A\cdot {\overline {S}}}\lor {B\cdot S}$ 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 0 1 1 1 1
Demultiplexer	DEMUX			Inputs Outputs $S$ $A$ $Q={{\overline {S}}\cdot A}$ $R={S\cdot A}$ 0 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1

The Special Role of NAND and NOR Gates

Both NAND and NOR gates exhibit a property known as functional completeness. Any Boolean function can be implemented using one or more of either of these gates. This is a very powerful principal because it enables us, using only one type of logic gate, to implement systems of arbitrary complexity.

References

• NAND Gate (Wikipedia)
• Schocken, Simon and Nisan, Noam. The Elements of Computing Systems. MIT Press, 2005.