Skip to main content
⚡ Calmops
🤖 AI 🏗️ Architecture 🌐 Web 🗃️ Database ⚙️ DevOps 🌍 Network 💻 Programming 🧮 Algorithms 📐 Software Eng. ☁️ Cloud 🔒 Security 📈 Finance More →

Boolean Functions and Minimization

Created: December 20, 2025 7 min read

Introduction

Boolean function minimization is the process of finding the simplest equivalent Boolean expression. This is essential for:

  • Reducing circuit complexity
  • Minimizing hardware cost
  • Improving circuit performance
  • Reducing power consumption
  • Optimizing logic design

In this article, we’ll explore Boolean function minimization techniques.

Boolean Function Representation

Truth Table

A truth table lists all possible input combinations and corresponding outputs.

Example: f(A, B, C):

A | B | C | f
--|---|---|--
0 | 0 | 0 | 0
0 | 0 | 1 | 1
0 | 1 | 0 | 0
0 | 1 | 1 | 1
1 | 0 | 0 | 0
1 | 0 | 1 | 1
1 | 1 | 0 | 1
1 | 1 | 1 | 1

Canonical Forms

Sum of Products (SOP):

f(A, B, C) = A'·B'·C + A'·B·C + A·B'·C + A·B·C + A·B·C'
(from rows where f = 1)

Product of Sums (POS):

f(A, B, C) = (A + B + C') · (A + B' + C') · (A' + B + C')
(from rows where f = 0)

Karnaugh Maps (K-Maps)

Definition

A Karnaugh map is a visual method for minimizing Boolean functions.

Advantages:

  • Visual representation
  • Easy to identify patterns
  • Systematic minimization
  • Handles up to 6 variables

2-Variable K-Map

Layout:

     B'  B
A'  [0] [1]
A   [2] [3]

Example: f(A, B) = A’·B’ + A·B:

     B'  B
A'  [1] [0]
A   [0] [1]

3-Variable K-Map

Layout:

       B'C' B'C BC BC'
A'    [0]  [1] [3] [2]
A     [4]  [5] [7] [6]

Example: f(A, B, C) = A’·B’·C + A’·B·C + A·B·C + A·B·C’:

       B'C' B'C BC BC'
A'    [0]  [1] [1] [0]
A     [0]  [0] [1] [1]

4-Variable K-Map

Layout:

         C'D' C'D CD CD'
A'B'    [0]  [1] [3] [2]
A'B     [4]  [5] [7] [6]
AB      [12] [13][15][14]
AB'     [8]  [9] [11][10]

Minimization Process

Step 1: Create K-Map

Place 1’s in cells corresponding to minterms where f = 1.

Step 2: Group Adjacent 1’s

Group adjacent 1’s in rectangles of size 2ⁿ (1, 2, 4, 8, …).

Rules:

  • Groups must be rectangular
  • Groups must contain only 1’s
  • Groups can wrap around edges
  • Larger groups are better
  • All 1’s must be covered

Step 3: Extract Simplified Terms

For each group, identify variables that don’t change.

Step 4: Combine Terms

OR the simplified terms together.

Example: 3-Variable Minimization

Truth Table:

A | B | C | f
--|---|---|--
0 | 0 | 0 | 0
0 | 0 | 1 | 1
0 | 1 | 0 | 0
0 | 1 | 1 | 1
1 | 0 | 0 | 1
1 | 0 | 1 | 1
1 | 1 | 0 | 1
1 | 1 | 1 | 1

K-Map:

       B'C' B'C BC BC'
A'    [0]  [1] [1] [0]
A     [1]  [1] [1] [1]

Grouping:

Group 1: A'·B'·C + A'·B·C = A'·C (top two 1's in middle columns)
Group 2: A·B'·C' + A·B'·C = A·B' (bottom left two 1's)
Group 3: A·B·C' + A·B·C = A·B (bottom right two 1's)

Simplified Expression:

f(A, B, C) = A'·C + A·B' + A·B
           = A'·C + A·(B' + B)
           = A'·C + A

Algebraic Minimization

Method 1: Consensus Theorem

Theorem: A·B + A’·C + B·C = A·B + A’·C

Application:

f = A·B + A'·C + B·C
  = A·B + A'·C        (Remove consensus term B·C)

Method 2: Absorption

Law: A + A·B = A

Application:

f = A + A·B + A'·B
  = A + B·(A + A')
  = A + B·1
  = A + B

Method 3: De Morgan’s Laws

Laws: (A·B)’ = A’ + B’, (A + B)’ = A’·B'

Application:

f = (A·B + C)'
  = (A·B)'·C'
  = (A' + B')·C'
  = A'·C' + B'·C'

Don’t Care Conditions

Definition

Don’t care conditions are input combinations where the output is unspecified.

Notation: X or d

Example:

A | B | C | f
--|---|---|--
0 | 0 | 0 | 0
0 | 0 | 1 | 1
0 | 1 | 0 | X  (don't care)
0 | 1 | 1 | 1
1 | 0 | 0 | 1
1 | 0 | 1 | X  (don't care)
1 | 1 | 0 | 1
1 | 1 | 1 | 1

Using Don’t Cares

Treat don’t cares as 1’s when they help create larger groups.

K-Map with Don’t Cares:

       B'C' B'C BC BC'
A'    [0]  [1] [1] [X]
A     [1]  [X] [1] [1]

Grouping:

Group 1: A'·B'·C + A'·B·C + A'·B·C' = A'·C + A'·B (using don't care)
Group 2: A·B'·C' + A·B'·C + A·B·C' + A·B·C = A (covers all A=1)

Simplified:

f = A + A'·C + A'·B = A + A'·(B + C)

Quine-McCluskey Method

Algorithm

Step 1: List all minterms in binary

Step 2: Group by number of 1’s

Step 3: Compare adjacent groups, combine if differ by one bit

Step 4: Repeat until no more combinations possible

Step 5: Select minimal set of prime implicants

Example

Minterms: 0, 1, 2, 5, 6, 7

Binary:

0: 000
1: 001
2: 010
5: 101
6: 110
7: 111

Grouping by 1’s:

Group 0: 000
Group 1: 001, 010
Group 2: 101, 110
Group 3: 111

Combining:

000, 001 → 00-
000, 010 → 0-0
001, 101 → -01
010, 110 → -10
101, 111 → 1-1
110, 111 → 11-

Prime Implicants:

00- (A'·B')
0-0 (A'·C')
-01 (B·C')
-10 (B·C')
1-1 (A·C)
11- (A·B)

Glossary

  • Boolean function: Function mapping Boolean inputs to outputs
  • Minimization: Finding simplest equivalent expression
  • Karnaugh map: Visual minimization method
  • Minterm: Product term with all variables
  • Maxterm: Sum term with all variables
  • Prime implicant: Minimal group of minterms
  • Essential prime implicant: Prime implicant covering unique minterm
  • Don’t care: Unspecified output condition
  • Quine-McCluskey: Tabular minimization method
  • Consensus: Redundant term in Boolean expression

Practice Problems

Problem 1: K-Map Minimization

Minimize f(A, B, C) = A’·B’·C + A’·B·C + A·B·C using K-map.

Solution:

K-Map:
       B'C' B'C BC BC'
A'    [0]  [1] [1] [0]
A     [0]  [0] [1] [0]

Groups:
- A'·B'·C + A'·B·C = A'·C
- A·B·C (single 1)

f = A'·C + A·B·C

Problem 2: Algebraic Minimization

Minimize f = A·B + A·B’ + A’·B.

Solution:

f = A·B + A·B' + A'·B
  = A·(B + B') + A'·B    (Distributive)
  = A·1 + A'·B           (Complement)
  = A + A'·B             (Identity)
  = (A + A')·(A + B)     (Distributive)
  = 1·(A + B)            (Complement)
  = A + B                (Identity)

Problem 3: Don’t Care Conditions

Minimize f(A, B, C) with minterms 1, 3, 5, 7 and don’t cares 0, 2.

Solution:

K-Map:
       B'C' B'C BC BC'
A'    [X]  [1] [1] [X]
A     [0]  [1] [1] [0]

Using don't cares:
Group 1: A'·B'·C + A'·B·C + X + X = A'·C + A'·B' (using don't care)
Group 2: A·B'·C + A·B·C = A·C

f = A'·C + A·C + ... = C (simplified)

Problem 4: Quine-McCluskey

Find prime implicants for minterms 0, 1, 2, 3.

Solution:

Minterms: 0(000), 1(001), 2(010), 3(011)

Grouping:
Group 0: 000
Group 1: 001, 010
Group 2: 011

Combining:
000, 001 → 00-
000, 010 → 0-0
001, 011 → 0-1
010, 011 → 01-

Prime implicants: 00-, 0-0, 0-1, 01-

Online Platforms

Interactive Tools

  • “Digital Design” by Morris Mano - Comprehensive coverage
  • “Boolean Algebra and Its Applications” by Givone - Mathematical approach
  • “Introduction to Digital Logic” by Wakerly - Practical approach
  • “Switching and Finite Automata Theory” by Kohavi - Theoretical approach
  • “Digital Systems” by Tocci, Widmer, Moss - Practical applications

Academic Journals

Software Tools

  • Logisim - Logic circuit simulator
  • Quartus - FPGA design
  • Verilog - Hardware description language
  • VHDL - Hardware description language
  • Graphviz - Graph visualization

Conclusion

Boolean function minimization is essential for efficient logic design:

  • K-Maps: Visual minimization method
  • Algebraic methods: Systematic simplification
  • Don’t cares: Optimize with unspecified outputs
  • Quine-McCluskey: Tabular minimization
  • Applications: Circuit optimization and design

Understanding minimization techniques is crucial for digital design and logic optimization.

In the next article, we’ll explore logic gates and circuits, which implement Boolean functions.

Next Article: Logic Gates and Circuits

Previous Article: Boolean Algebra: Operations and Laws

Comments