Logic Gates and Boolean Algebra

Modified: Mar. 14, 2026

Published: Mar. 2, 2026

Become Contributor Expert Support

Logic gates are the smallest building blocks of digital hardware. Every microcontroller, every processor, and every digital circuit is built from combinations of AND, OR, and NOT gates. When you write PORTB |= (1 << 5); in C, the compiler generates an instruction, and the CPU executes it using physical OR gates inside the chip. This lesson puts those gates on a breadboard so you can see them work. #LogicGates #BooleanAlgebra #DigitalCircuits

The Six Fundamental Gates

Every digital circuit, no matter how complex, is built from these six gate types. Each gate takes one or two binary inputs and produces one binary output.

  NOT (Inverter)     AND Gate          OR Gate
  A ──o── Y          A ──┐             A ──┐
                     B ──┤AND├── Y     B ──┤OR ├── Y
                         └───┘             └───┘

  NAND Gate          NOR Gate          XOR Gate
  A ──┐              A ──┐             A ──┐
  B ──┤AND├o── Y     B ──┤OR ├o── Y    B ──┤XOR├── Y
      └───┘              └───┘             └───┘
      (o = invert)

NOT Gate (Inverter)

The NOT gate has one input and one output. It inverts the input: 0 becomes 1, and 1 becomes 0.

Truth table:

Boolean expression: (also written as or )

C equivalent: y = ~a; (bitwise NOT)

IC: 74HC04 (hex inverter, six independent NOT gates in one package)

AND Gate

The AND gate outputs 1 only when both inputs are 1.

Truth table:

Boolean expression: (or simply )

C equivalent: y = a & b; (bitwise AND)

IC: 74HC08 (quad 2-input AND, four independent AND gates)

Embedded use: Masking bits. PINB & (1 << 5) tests whether bit 5 is high by ANDing with a mask that has only bit 5 set.

OR Gate

The OR gate outputs 1 when at least one input is 1.

Truth table:

Boolean expression:

C equivalent: y = a | b; (bitwise OR)

IC: 74HC32 (quad 2-input OR)

Embedded use: Setting bits. PORTB |= (1 << 5) sets bit 5 by ORing with a mask.

NAND Gate

The NAND gate is an AND followed by a NOT. It outputs 0 only when both inputs are 1.

Truth table:

Boolean expression:

IC: 74HC00 (quad 2-input NAND)

NAND is called a “universal gate” because you can build any other gate from NAND gates alone. This is why NAND flash memory uses NAND structures internally.

NOR Gate

The NOR gate is an OR followed by a NOT. It outputs 1 only when both inputs are 0.

Truth table:

Boolean expression:

NOR is also a universal gate. Like NAND, you can construct any logic function using only NOR gates.

XOR Gate (Exclusive OR)

The XOR gate outputs 1 when the inputs are different.

Truth table:

Boolean expression:

C equivalent: y = a ^ b; (bitwise XOR)

IC: 74HC86 (quad 2-input XOR)

Embedded use: Toggling bits. PORTB ^= (1 << 5) toggles bit 5 by XORing with a mask.

XOR is also the basis of parity checking, CRC calculations, and simple encryption.

74HC Series IC Pinouts

The 74HC family uses CMOS technology and operates at 2V to 6V, making it compatible with both 3.3V and 5V systems. All quad-gate ICs in this family share a similar 14-pin DIP package layout.

74HC08 (Quad AND) Pin Layout

        74HC08
     ┌────┐
 1A ─┤1  14├─ VCC
 1B ─┤2  13├─ 4B
 1Y ─┤3  12├─ 4A
 2A ─┤4  11├─ 4Y
 2B ─┤5  10├─ 3B
 2Y ─┤6   9├─ 3A
GND ─┤7   8├─ 3Y
     └────┘

• Pin 7 = GND (connect to 0V)
• Pin 14 = VCC (connect to 5V)
• Gate 1: inputs on pins 1, 2; output on pin 3
• Gate 2: inputs on pins 4, 5; output on pin 6
• Gate 3: inputs on pins 9, 10; output on pin 8
• Gate 4: inputs on pins 12, 13; output on pin 11

The 74HC00 (NAND), 74HC32 (OR), and 74HC86 (XOR) all use the same pinout. Only the gate function differs.

74HC04 (Hex Inverter) Pin Layout

        74HC04
     ┌────┐
 1A ─┤1  14├─ VCC
 1Y ─┤2  13├─ 6A
 2A ─┤3  12├─ 6Y
 2Y ─┤4  11├─ 5A
 3A ─┤5  10├─ 5Y
 3Y ─┤6   9├─ 4A
GND ─┤7   8├─ 4Y
     └────┘

Each inverter has one input and one output. There are six inverters in one package.

Practical: Build and Verify Truth Tables

Parts Needed

Wiring the AND Gate

1. Place the 74HC08 across the center groove of the breadboard, straddling the gap.

2. Connect power: pin 14 to the 5V rail, pin 7 to the GND rail.

3. Wire input A (pin 1) to a push button. Connect a 10K pull-down resistor from pin 1 to GND. The button connects pin 1 to 5V when pressed. When not pressed, the pull-down holds the input at 0.

4. Wire input B (pin 2) the same way with a second push button and pull-down resistor.

5. Wire the output (pin 3) to an LED through a 220 ohm resistor. Connect the LED anode to pin 3 (through the resistor) and the cathode to GND.

6. Test all four input combinations:

   • Both buttons released: LED off (0 AND 0 = 0)
   • Button A only: LED off (1 AND 0 = 0)
   • Button B only: LED off (0 AND 1 = 0)
   • Both buttons pressed: LED on (1 AND 1 = 1)

Wiring the OR Gate

Use the same circuit but replace the 74HC08 with the 74HC32. Now the LED lights when either or both buttons are pressed.

Wiring the NOT Gate

Use the 74HC04. Connect one push button (with pull-down) to pin 1 (input). Connect pin 2 (output) to an LED with a 220 ohm resistor. The LED will be on when the button is not pressed and off when it is pressed.

Boolean Algebra

Boolean algebra is the mathematics of logic. It lets you analyze, simplify, and design digital circuits using algebraic rules.

Basic Laws

De Morgan’s Theorems

These two theorems are among the most useful tools in digital design:

Theorem 1:

The complement of AND equals the OR of the complements. A NAND gate is equivalent to an OR gate with inverted inputs.

Theorem 2:

The complement of OR equals the AND of the complements. A NOR gate is equivalent to an AND gate with inverted inputs.

  De Morgan's Theorem 1 (NAND = bubbled OR)

  A ──┐                    A ──o──┐
  B ──┤AND├──o── Y    =    B ──o──┤OR ├── Y
      └───┘                       └───┘

  De Morgan's Theorem 2 (NOR = bubbled AND)

  A ──┐                    A ──o──┐
  B ──┤OR ├──o── Y    =    B ──o──┤AND├── Y
      └───┘                       └───┘

In C code, De Morgan’s theorems look like this:

// These two expressions are equivalent:
!(a && b)    ==    (!a || !b)

// These two expressions are equivalent:
!(a || b)    ==    (!a && !b)

// For bitwise operations:
~(a & b)     ==    (~a | ~b)
~(a | b)     ==    (~a & ~b)

Simplification Example

Simplify:

1. Factor out :
2. Apply the complement law ():
3. Apply the identity law:

The output depends only on , regardless of . If this were a circuit, you could remove the input entirely and save gates.

Another Example

Simplify:

1. Group the last two terms:
2. Simplify:
3. Apply the absorption law ():

The original expression with three terms reduces to a simple OR. In hardware, that means replacing multiple gates with a single OR gate.

Karnaugh Maps (K-maps)

For expressions with three or four variables, Karnaugh maps provide a visual method for simplification. A K-map arranges truth table entries in a grid where adjacent cells differ by only one variable.

Two-variable K-map for :

Group the two cells in the A=1 row (giving ) and the two cells in the B=1 column (giving ). The simplified expression is .

Three-variable K-map layout:

Notice the column order uses Gray code (only one variable changes between adjacent columns), so that adjacent cells always differ by exactly one variable. Group rectangular blocks of 1, 2, 4, or 8 adjacent cells to find the simplest expression.

Multi-Gate Combination Example

A practical circuit often chains several gate types. Here is a 2-bit equality comparator that outputs 1 when A1A0 equals B1B0:

  2-bit equality comparator (A == B)

  A0 ──┐                ┌───┐
  B0 ──┤XNOR├── E0 ──┐  │   │
       └────┘         ├──┤AND├── EQUAL
  A1 ──┐              │  │   │
  B1 ──┤XNOR├── E1 ──┘  └───┘
       └────┘

  EQUAL = 1 only when A1=B1 AND A0=B0

XNOR outputs 1 when its two inputs match. ANDing the per-bit results gives a full equality test. This pattern scales: an 8-bit comparator uses 8 XNOR gates feeding an 8-input AND tree.

NAND as a Universal Gate

Any logic function can be built using only NAND gates. This is practically important because manufacturing one type of gate is simpler and cheaper. Here is how to build each basic gate from NAND:

NOT from NAND: Connect both inputs of a NAND gate together.

This is a NOT gate.

AND from NAND: Use two NAND gates. The first performs NAND, the second inverts the result.

OR from NAND: Use three NAND gates. First invert both inputs (two NANDs with tied inputs), then NAND the results.

By De Morgan’s theorem:

  OR gate built from three NAND gates

  A ──┤NAND├──┐
      (A,A)   ├─┤NAND├── Y = A + B
  B ──┤NAND├──┘
      (B,B)

This is why the 74HC00 (quad NAND) is often called the most versatile IC in the 74HC family. With enough 74HC00s, you can build any digital circuit.

Practical: Build a NAND-Only OR Gate

1. Use a single 74HC00 (quad NAND) IC on your breadboard.

2. Gate 1 (inverter for A): Connect your first push button (with pull-down) to both pins 1 and 2. The output on pin 3 is .

3. Gate 2 (inverter for B): Connect your second push button (with pull-down) to both pins 4 and 5. The output on pin 6 is .

4. Gate 3 (NAND of inverted inputs): Connect pin 3 to pin 9, pin 6 to pin 10. The output on pin 8 is .

5. Connect pin 8 to an LED through a 220 ohm resistor.

6. Verify: The LED behaves exactly like an OR gate. It lights when either or both buttons are pressed.

You have just built an OR gate from NAND gates, demonstrating the universal property.

Gate Propagation Delay

Real gates do not switch instantaneously. The 74HC08 AND gate has a typical propagation delay of about 7 nanoseconds at 5V. This means the output takes 7 ns to respond after the input changes.

For a chain of gates, delays add up. If you cascade five gates, the total delay is approximately ns. At low frequencies this is negligible, but in high-speed circuits (and inside microcontrollers running at tens or hundreds of MHz), propagation delay determines the maximum clock speed.

The 74HCT series has TTL-compatible input thresholds and is used when interfacing with older TTL logic.

Exercises

Exercise 1: Truth Table Completion

Complete the truth table for (this is XOR):

Exercise 2: Boolean Simplification

Simplify:

Exercise 3: Apply De Morgan’s Theorem

Rewrite using only AND and NOT operations:

How This Connects to Embedded Programming

Summary

In the next lesson, you will combine these gates into larger functional blocks: multiplexers, decoders, and adders.