CS 101 › Lesson 4 of 8

Logic Gates & Boolean Algebra

Lesson 4 · OKSTEM College · Associate of Science in Computer Science

Logic Gates & Boolean Algebra

All computation reduces to switching circuits. A logic gate is a circuit with one or more binary inputs and a binary output, implementing a Boolean function.

Basic Gates — click any gate to expand

🔵 AND gate  A · B Output: 1 only if ALL inputs = 1 ▼

Rule: The output is HIGH (1) only when every input is HIGH. Think of it as a logical "both".

Analogy: A door opens only if you have the right key AND the right badge. Either one alone does nothing.

A
B
Out
0
0
0
0
1
0
1
0
0
1
1
1
Used in: conditional logic, masking bits
Example: if (a == 1 AND b == 1)
🟢 OR gate  A + B Output: 1 if ANY input = 1 ▼

Rule: The output is HIGH if at least one input is HIGH. The only case it outputs 0 is when all inputs are 0.

Analogy: A light turns on if switch A OR switch B is flipped — either one (or both) work.

A
B
Out
0
0
0
0
1
1
1
0
1
1
1
1
Used in: flag merging, error detection
Example: if (error_A OR error_B) → alert
🔴 NOT gate  ¬A Single input — inverts it ▼

Rule: The NOT gate (also called an inverter) has exactly one input. It flips 0 → 1 and 1 → 0.

Why it matters: Without NOT you can't build complements, which means you can't subtract, compare, or implement conditional jumps. It's the "negation" of all logic.

A
Out (¬A)
0
1
1
0
Used in: inverters, complement circuits, D flip-flops
⭐ NAND gate  ¬(A · B) Universal gate — builds everything ▼

Rule: NAND = AND followed by NOT. Output is 0 only when all inputs are 1; otherwise output is 1.

Why it's universal: You can build any other gate (NOT, AND, OR, XOR…) using only NAND gates. This makes it the most important gate in chip manufacturing — factories can optimize one gate type and use it everywhere.

  • NOT A = NAND(A, A)
  • AND(A,B) = NAND(NAND(A,B), NAND(A,B))
  • OR(A,B) = NAND(NAND(A,A), NAND(B,B))
A
B
Out
0
0
1
0
1
1
1
0
1
1
1
0
Used in: SRAM cells, flip-flops, entire CPUs
🟠 NOR gate  ¬(A + B) Also universal ▼

Rule: NOR = OR followed by NOT. Output is 1 only when all inputs are 0.

Also universal: Like NAND, NOR can build any other gate. Early microprocessors (e.g., the Apollo Guidance Computer) were built entirely from NOR gates because NOR was cheap to manufacture in the 1960s.

A
B
Out
0
0
1
0
1
0
1
0
0
1
1
0
Fun fact: Apollo Guidance Computer used only NOR gates
💜 XOR gate  A ⊕ B Exclusive OR — inputs must differ ▼

Rule: XOR (Exclusive OR) outputs 1 when inputs are different. If both are the same (both 0 or both 1), the output is 0.

Why it's essential: XOR is the core of addition and encryption. In binary addition, A XOR B gives the sum bit (the carry is A AND B). In cryptography, XOR-ing plaintext with a key produces ciphertext — and XOR-ing again with the same key recovers the original.

A
B
Out
0
0
0
0
1
1
1
0
1
1
1
0
Used in: half adder (sum bit), checksums, AES encryption
Property: A ⊕ A = 0  ·  A ⊕ 0 = A

Boolean Algebra Laws

// Identity A · 1 = A A + 0 = A // Null A · 0 = 0 A + 1 = 1 // Idempotent A · A = A A + A = A // Complement A · ¬A = 0 A + ¬A = 1 // DeMorgan's ¬(A·B) = ¬A+¬B ¬(A+B) = ¬A·¬B

Half Adder

A half adder adds two 1-bit numbers. Sum = A XOR B. Carry = A AND B. Chain two half adders to make a full adder, chain 8 full adders to make an 8-bit ALU.

Lab — Interactive Logic Gate Simulator

Knowledge Check

Which gate outputs 1 only when ALL inputs are 1?

NAND is called a 'universal gate' because

DeMorgan's Law states that ¬(A·B) equals

A half adder computes Sum = A XOR B and Carry =

XOR outputs 1 when

← PreviousNext →