Logic Gates

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

— Merlin, The Coder

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	${A\cdot {\overline {S}}}\lor {B\cdot S}$		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

	Coming Soon
	Add section describing special properties of NAND and NOR gates Add exercises constructing other gates as such