Boolean Algebra

Boolean Algebra is a mathematical system used to analyze and design digital logic circuits. It was introduced by George Boole. Since digital circuits operate using two voltage levels, Boolean algebra is ideal for representing and simplifying digital logic. A Boolean function is an expression formed using Boolean variables and logical operators.

Boolean Algebra deals with variables that can take only two possible values:

  • 0 – FALSE / LOW
  • 1 – TRUE / HIGH

Boolean Variables and Constants

  • Boolean Variables: A, B, C, X, Y, etc.
  • Boolean Constants: 0 and 1

A Boolean function is an expression formed using Boolean variables and logical operators.

Basic Boolean Operations

AND Operation (·): The AND operation produces output 1 only when all inputs are 1.

ABA · B
000
010
100
111

OR Operation (+): The OR operation produces output 1 if any one of the inputs is 1.

ABA + B
000
011
101
111

NOT Operation (Complement): The NOT operation inverts the input value.

AA̅
01
10

Derived Boolean Operations

  • NAND: (A · B)̅
  • NOR: (A + B)̅
  • XOR: A ⊕ B (output is 1 when inputs are different)
  • XNOR: (A ⊕ B)̅

NAND and NOR gates are called Universal Gates because any Boolean function can be implemented using only NAND or only NOR gates.

Boolean Laws

  1. Identity Laws
  • A + 0 = A
  • A · 1 = A

2. Null Laws

  • A + 1 = 1
  • A · 0 = 0

3. Idempotent Laws

  • A + A = A
  • A · A = A

4. Inverse Laws

  • A + A̅ = 1
  • A · A̅ = 0

5. Commutative Laws

  • A + B = B + A
  • A · B = B · A

6. Associative Laws

  • A + (B + C) = (A + B) + C
  • A · (B · C) = (A · B) · C

7. Distributive Laws

  • A · (B + C) = A·B + A·C
  • A + (B · C) = (A + B)(A + C)

De Morgan’s Theorems

De Morgan’s theorems are used to simplify Boolean expressions and convert logic circuits.

  • (A + B)̅ = A̅ · B̅
  • (A · B)̅ = A̅ + B̅

Example:

Simplify (A + B + C)̅

Solution:

(A + B + C)̅ = A̅ · B̅ · C̅

Canonical Forms

  1. Sum of Products (SOP): An SOP expression consists of AND terms that are ORed together. Example: F = A̅B + AB̅
  2. Product of Sums (POS): A POS expression consists of OR terms that are ANDed together. Example: F = (A + B̅)(A̅ + B)

Minterms and Maxterms

  • Minterm: Output is 1 for a specific input combination
  • Maxterm: Output is 0 for a specific input combination

Notation:

  • Σm – Sum of minterms
  • ΠM – Product of maxterms

Simplification of Boolean Expressions

Algebraic Method

Example: Simplify A + A̅B

Solution:

A + A̅B

= (A + A̅)(A + B)

= 1 · (A + B)

= A + B

Karnaugh Map (K-Map) Method

Introduction

The Karnaugh Map (K-Map) is a graphical technique used to simplify Boolean expressions. It reduces complex Boolean functions into minimal Sum of Products (SOP) or Product of Sums (POS) forms, thereby minimizing the number of logic gates required in digital circuits.

K-Maps are practical for simplifying functions with up to 4 or 5 variables.

Purpose of K-Map Simplification

  • Reduces number of logic gates
  • Minimizes hardware cost
  • Improves speed and reliability
  • Eliminates redundant variables
  • Simplifies circuit implementation

Structure of K-Maps

Number of Cells

VariablesCells
24
38
416

Each cell represents a minterm (for SOP) or maxterm (for POS).

Variable K-Map Layout

Variables: A, B, C

        BC
        00   01   11   10
      -------------------
A = 0 | m0 | m1 | m3 | m2
A = 1 | m4 | m5 | m7 | m6

Gray code ordering (00, 01, 11, 10) ensures that only one variable changes between adjacent cells.

K-Map Simplification Rules

Grouping Rules

  1. Groups must contain 1, 2, 4, or 8 cells (powers of 2).
  2. Groups must include only 1s (for SOP) or only 0s (for POS).
  3. Groups should be as large as possible.
  4. Overlapping groups are allowed.
  5. Every 1 must be covered at least once.
  6. K-Map wraparound adjacency is allowed.

Steps for SOP Simplification

  1. Plot all minterms in the K-Map.
  2. Group adjacent 1s using largest possible groups.
  3. Identify common variables in each group.
  4. Write simplified Boolean expression.

Illustrative Problems

Problem 1: Simplify a 3-Variable Boolean Function

Given:

[F(A,B,C) = \sum m(1, 3, 5, 7)]

Step 1: Plot minterms

        BC
        00   01   11   10
      -------------------
A = 0 |  0 |  1 |  1 |  0
A = 1 |  0 |  1 |  1 |  0

Step 2: Grouping

  • One group of 4 adjacent 1s

Step 3: Identify constant variable

  • C = 1 remains constant

Simplified Expression:

[F = C]

Problem 2: Simplify Using K-Map

Given:

[
F(A,B,C) = \sum m(0, 2, 4, 6)
]

Step 1: Plot minterms

        BC
        00   01   11   10
      -------------------
A = 0 |  1 |  0 |  0 |  1
A = 1 |  1 |  0 |  0 |  1

Step 2: Grouping

  • One group of 4 cells (wraparound)

Step 3: Constant variable

  • C = 0

Simplified Expression:

[F = C’]

Problem 3: K-Map with Multiple Groups

Given:

[
F(A,B,C) = \sum m(1, 2, 3, 5)
]

Step 1: Plot minterms

        BC
        00   01   11   10
      -------------------
A = 0 |  0 |  1 |  1 |  1
A = 1 |  0 |  1 |  0 |  0

Step 2: Grouping

  • Group 1: (1, 3) → (A’C)
  • Group 2: (2, 3) → (A’B)
  • Group 3: (1, 5) → (B’C)

Simplified Expression:

[ F = A’C + A’B + B’C ]

Advantages of K-Map

  • Simple and visual method
  • Eliminates algebraic complexity
  • Provides minimal expression directly
  • Useful for combinational circuit design

Limitations

  • Not practical beyond 5 variables
  • Manual errors possible for large maps
  • Not suitable for automated optimization