---
title: Logic Gates and Boolean Algebra
url: https://doc.liz6.com/en/hardware/05-digital-circuits/01-logic-gates-and-boolean-algebra
locale: en
area: hardware
tags:
- hardware
- digital-circuits
date: 2026-06-30
modified: 2026-07-16
description: Logic Gates and Boolean Algebra Boolean Algebra Basics Three Basic Operations Truth Tables Basic Theorems --- Basic Logic Gates Symbols and Expressions Universa…
---

# Logic Gates and Boolean Algebra

## Boolean Algebra Basics

### Three Basic Operations

```
AND:  Y = A · B    "1 only if both are 1"
OR:   Y = A + B    "1 if any is 1"
NOT:  Y = Ā        "Invert"
```

### Truth Tables

```
AND          OR           NOT
A B | Y     A B | Y      A | Y
0 0 | 0     0 0 | 0      0 | 1
0 1 | 0     0 1 | 1      1 | 0
1 0 | 0     1 0 | 1
1 1 | 1     1 1 | 1
```

### Basic Theorems

```
Associative Law:  (A·B)·C = A·(B·C)
                  (A+B)+C = A+(B+C)
Commutative Law:  A·B = B·A
                  A+B = B+A
Distributive Law: A·(B+C) = A·B + A·C

De Morgan's Theorem (Extremely Important!):
  ───
  A·B = Ā + B̄     "NAND = OR of NOTs"
  ───
  A+B = Ā · B̄     "NOR = AND of NOTs"

Reduction:
  A + Ā = 1
  A · Ā = 0
  A + 1 = 1
  A · 0 = 0
  A + A = A
  A · A = A
  =    (Double Negation)
  A = A
```

---

## Basic Logic Gates

### Symbols and Expressions

```
AND:     A ──┬──
              │  )── Y    Y = A·B
         B ──┴──

OR:      A ──┬──
              │  )── Y    Y = A+B
         B ──┴──

NOT:     A ──▷── Y        Y = Ā

NAND:    A ──┬──
              │  )─○ Y    Y = A·B̄  (AND + NOT)
         B ──┴──

NOR:     A ──┬──
              │  )─○ Y    Y = A+B̄  (OR + NOT)
         B ──┴──

XOR:     A ──┬──
              │  )── Y    Y = A⊕B = ĀB + AB̄
         B ──┴──            ("1 if different")

XNOR:    A ──┬──
              │  )─○ Y    Y = A⊕B̄  ("1 if same")
         B ──┴──
```

### Universality of NAND / NOR
```
NAND can implement any logic function!
  NOT:  A NAND A = Ā
  AND:  (A NAND B) NAND (A NAND B) = A·B
  OR:   (A NAND A) NAND (B NAND B) = A+B

NOR can similarly construct everything
This is why NAND Flash and NOR Flash are named as such
```

---

## Combinational Logic Simplification

### Karnaugh Map (K-Map)
```
2 Variables:
    B
  A 0  1
  0 0  1
  1 1  0   ← Fill in output values

3 Variables: AB/C arrangement
  Group adjacent 1s (in groups of 2ⁿ) → Write minterms → Obtain simplest expression

Goal: Implement a given truth table using the minimum number of gates
```

### Race Conditions and Hazards
```
Different delays in multiple signal paths → Output produces brief erroneous pulses (glitches)

Example: A and Ā should arrive at the AND gate simultaneously, but Ā has a delay due to the inverter
     → For a brief moment A=1, Ā=1 (hasn't switched to 0 yet) → AND outputs erroneous 1

Solution: Add redundant terms or add a capacitor filter at the output
```

---

## Logic Levels

### TTL vs CMOS

```
       TTL (5V)         CMOS (5V)       CMOS (3.3V)
VIH:   > 2.0V           > 3.5V          > 2.0V
VIL:   < 0.8V           < 1.5V          < 0.8V
VOH:   > 2.4V           > 4.4V          > 2.9V
VOL:   < 0.4V           < 0.1V          < 0.4V

Noise Margin = min(VOH-VIH, VIL-VOL)
CMOS noise margin is significantly better than TTL
```

### Input Types
```
Floating Input — Never do this! Floating CMOS input = Indeterminate state + High power consumption
Unused input pins: Connect to Vcc or GND (via resistor)
```

---

## Practical Logic Gates

### CMOS Inverter
```
       Vdd
        │
    ┌───┤ PMOS (Top transistor)
    │   │
A ──┤   ├── Y
    │   │
    └───┤ NMOS (Bottom transistor)
        │
       GND

A=1 → NMOS ON, PMOS OFF → Y=0
A=0 → NMOS OFF, PMOS ON → Y=1

CMOS's greatest advantage: Static power consumption is nearly zero!
(Power is only consumed during switching transitions)
```

### 74 Series Quick Reference
```
74HC00:  Quad 2-input NAND
74HC02:  Quad 2-input NOR
74HC04:  Hex NOT (Inverter)
74HC08:  Quad 2-input AND
74HC32:  Quad 2-input OR
74HC86:  Quad 2-input XOR
74HC14:  Hex Schmitt Trigger NOT
74HC595: 8-bit Shift Register (Super common!)
74HC165: 8-bit Parallel-to-Serial
```

---
*Keywords: Boolean Algebra, AND, OR, NOT, NAND, NOR, XOR, De Morgan, Karnaugh Map, CMOS, TTL*