Classical Gates

Logic gates are the fundamental building blocks of computation. They perform boolean operations on bits, taking one or more inputs and producing a single output.

They can be described in full by their truth tables, which is a table that just shows how inputs to the gate map to outputs.

By combining these simple gates, we can perform computations.

The circuit model of computation:

• Inputs: Bits flow in from the left
• Gates: Transform bits according to logical rules
• Outputs: Results flow out to the right
• Wires: Connect gates, carrying bit values
• Key principle: Any algorithm can be expressed as a circuit of gates!

The NOT gate (Inverter):

• Symbol: Triangle with a bubble
• Function: Flips the bit (0→1, 1→0)
• Truth table:

$$\begin{array}{|c|c|} \hline \text{Input} & \text{Output} \\ \hline 0 & 1 \\ 1 & 0 \\ \hline \end{array}$$

The AND gate:

• Symbol: D-shaped
• Function: Outputs 1 only if ALL inputs are 1
• Truth table:

$$\begin{array}{|c|c|c|} \hline A & B & A \land B \\ \hline 0 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \\ \hline \end{array}$$

...