Logic Gates

Overview

From Algebra to Hardware

Logic gates are physical devices that implement Boolean operations. They are the building blocks of all digital hardware - processors, memory, and displays. Each gate takes binary inputs and produces a binary output according to a specific Boolean function.

Definition

Basic Gates

AND gate: output = x · y (1 only if both inputs are 1) OR gate: output = x + y (1 if at least one input is 1) NOT gate (inverter): output = x̄ (flips the input)

These three gates can implement ANY Boolean function.

Definition

Derived Gates

NAND gate: output = (x · y)̄ - NOT of AND. Output is 0 only when both inputs are 1. NOR gate: output = (x + y)̄ - NOT of OR. Output is 1 only when both inputs are 0. XOR gate: output = x ⊕ y - output is 1 when inputs differ. XNOR gate: output = (x ⊕ y)̄ - output is 1 when inputs are equal.

Note

Universal Gates

NAND and NOR are each called universal gates because any Boolean function can be built using only NAND gates (or only NOR gates).

NOT using NAND: x̄ = (x · x)̄ = NAND(x, x) AND using NAND: x · y = ((x · y)̄)̄ = NAND(NAND(x,y), NAND(x,y)) OR using NAND: x + y = (x̄ · ȳ)̄ = NAND(NAND(x,x), NAND(y,y))

Example

XOR Truth Table

x | y | x ⊕ y ---|---|------ 0 | 0 | 0 0 | 1 | 1 1 | 0 | 1 1 | 1 | 0

XOR can be expressed as: x ⊕ y = x · ȳ + x̄ · y In words: exactly one input is 1.

Example

Half Adder Circuit

A half adder adds two single bits x and y, producing a sum bit S and a carry bit C.

S = x ⊕ y (XOR) C = x · y (AND)

x | y | S | C ---|---|---|--- 0 | 0 | 0 | 0 0 | 1 | 1 | 0 1 | 0 | 1 | 0 1 | 1 | 0 | 1

This is the simplest arithmetic circuit and the basis for all computer addition.