Simplification of Boolean Functions

Unit 3: Simplification of Boolean Functions (5 Hrs.)

1. Introduction to Boolean Function Simplification

Objective: Simplify Boolean expressions to reduce the number of logic gates and inputs, leading to cost-effective and efficient digital circuits.

Methods:

• Algebraic Simplification (using Boolean algebra laws).
• Karnaugh Maps (K-maps).
• Quine-McCluskey Method (for more complex functions).

2. Karnaugh Maps (K-maps)

Definition: A graphical method for simplifying Boolean expressions.

Advantages:

• Easy to use for up to 4 variables.
• Provides a visual representation of minterms and maxterms.

Steps:

1. Represent the Boolean function in a truth table.
2. Plot the minterms or maxterms on the K-map.
3. Group adjacent 1s (for SOP) or 0s (for POS).
4. Derive the simplified expression from the groups.

3. Two and Three Variable K-maps

Two-Variable K-map

Grid: 2 rows × 2 columns.

Variables: A and B.

B\A	0	1
0	m0	m1
1	m2	m3

Grouping: Adjacent cells (horizontally or vertically).

Three-Variable K-map

Grid: 2 rows × 4 columns.

Variables: A, B, and C.

C\AB	00	01	11	10
0	m0	m1	m3	m2
1	m4	m5	m7	m6

Grouping: Adjacent cells (horizontally, vertically, or wrapping around edges).

4. Four-Variable K-maps

Grid: 4 rows × 4 columns.

Variables: A, B, C, and D.

CD\AB	00	01	11	10
00	m0	m1	m3	m2
01	m4	m5	m7	m6
11	m12	m13	m15	m14
10	m8	m9	m11	m10

Grouping: Adjacent cells (horizontally, vertically, or wrapping around edges). Groups can be of size 1, 2, 4, 8, or 16.

5. Product of Sum (POS) Simplification

Definition: Simplifying Boolean functions expressed as a product of maxterms.

Steps:

1. Plot 0s on the K-map for the given maxterms.
2. Group adjacent 0s.
3. Derive the simplified POS expression.

Example:

Given: F(A,B,C) = Π(0, 2, 4, 6)

Simplified POS: F = (A + C)

6. NAND and NOR Implementation

Universal Gates: NAND and NOR gates can implement any Boolean function.

NAND Implementation

Steps:

1. Simplify the Boolean function using SOP.
2. Implement the SOP using AND and OR gates.
3. Replace AND and OR gates with NAND gates.

Example: F = AB + CD → Implement using NAND gates.

NOR Implementation

Steps:

1. Simplify the Boolean function using POS.
2. Implement the POS using OR and AND gates.
3. Replace OR and AND gates with NOR gates.

Example: F = (A + B)(C + D) → Implement using NOR gates.

7. Don’t Care Conditions

Definition: Input combinations for which the output is unspecified (can be 0 or 1).

Symbol: Represented as 'X' in K-maps.

Use: Can be included in groups to simplify the function further.

Example:

Given: F(A,B,C) = Σ(1, 3, 5) + d(0, 2)

Use 'X' to form larger groups for simplification.

8. Determinant and Selection of Prime Implicants

Prime Implicant: A group of minterms that cannot be combined further.

Essential Prime Implicant: A prime implicant that covers at least one minterm not covered by any other prime implicant.

Steps:

1. Identify all prime implicants on the K-map.
2. Select essential prime implicants.
3. Use the minimum number of prime implicants to cover all minterms.

Example:

Given: F(A,B,C) = Σ(0, 1, 2, 5, 6, 7)

Identify prime implicants and select essential ones.

Diagrams and Images

Two-Variable K-map

B\A	0	1
0	0	1
1	2	3

Three-Variable K-map

C\AB	00	01	11	10
0	0	1	3	2
1	4	5	7	6

Four-Variable K-map

CD\AB	00	01	11	10
00	0	1	3	2
01	4	5	7	6
11	12	13	15	14
10	8	9	11	10

NAND and NOR Gate Symbols

NAND: AND gate followed by a bubble (inversion).

NOR: OR gate followed by a bubble (inversion).

Summary

• K-maps provide a visual and systematic way to simplify Boolean functions.
• Two, three, and four-variable K-maps are commonly used.
• POS simplification involves grouping 0s, while SOP involves grouping 1s.
• NAND and NOR gates are universal and can implement any Boolean function.
• Don’t care conditions help in further simplification.
• Prime implicants are crucial for selecting the minimal expression.