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.

A	B	A · B
0	0	0
0	1	0
1	0	0
1	1	1

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

A	B	A + B
0	0	0
0	1	1
1	0	1
1	1	1

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

A	A̅
0	1
1	0

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

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

Sum of Products (SOP): An SOP expression consists of AND terms that are ORed together. Example: F = A̅B + AB̅
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

Variables	Cells
2	4
3	8
4	16

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

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

Steps for SOP Simplification

Plot all minterms in the K-Map.
Group adjacent 1s using largest possible groups.
Identify common variables in each group.
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)

Using Group 2 and Group 3 above we can cover all terms with output 1. Hence,

[ F = A’B + B’C ]

Yet another illustration

1. Requirement Statement

The first step is defining exactly what the circuit should do.

Example Requirement: Design a “Majority Vote” circuit for a three-person committee (A, B, and C). The output (Y) should be High (1) if at least two members vote “Yes,” and Low (0) otherwise.

2. The Truth Table

The truth table maps every possible input combination to the desired output. For three inputs, there are $2^3 = 8$ possible combinations.

A (Input)	B (Input)	C (Input)	Y (Output)
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

3. Sum of Products (SOP) Implementation

In SOP form, we look only at the rows where the output Y = 1. Each of these rows represents a minterm. We write the product (AND) of the variables for those rows and then sum (OR) them together.

From our table, the raw boolean expression is:

$Y = (\bar{A}BC) + (A\bar{B}C) + (AB\bar{C}) + (ABC)$

While this works, it is inefficient. Implementing this directly would require four 3-input AND gates and one 4-input OR gate.

4. Optimization using Karnaugh Map (K-Map)

A K-Map allows us to visually group adjacent “1s” to simplify the boolean expression. Adjacent cells in a K-Map differ by only one bit (Gray code).

Mapping the 1s:

We place a “1” in the cells corresponding to the minterms identified in the truth table:

Cell 011 ( $m_3$ )
Cell 101 ( $m_5$ )
Cell 110 ( $m_6$ )
Cell 111 ( $m_7$ )

Plot of minterms

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

Grouping (Looping):

We look for groups of 2, 4, or 8. In this map, we can form three groups of two:

Group 1 (Vertical): Covers $m_3$ and $m_7$ . Here, $B$ and $C$ remain constant (1), while $A$ changes. Result: BC
Group 2 (Horizontal): Covers $m_6$ and $m_7$ . Here, $A$ and $B$ remain constant (1), while $C$ changes. Result: AB
Group 3 : Covers $m_5$ and $m_7$ . Here, $A$ and $C$ remain constant (1), while $B$ changes. Result: AC

Optimized Expression:

$Y = AB + BC + AC$

5. Final Logic Circuit

The optimized expression is much cheaper to build. Instead of complex 3-input gates, we can now use:

Three 2-input AND gates.
One 3-input OR gate.

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

Karnaugh Map (K-Map) Method

Introduction

Purpose of K-Map Simplification

Structure of K-Maps

Number of Cells

Variable K-Map Layout

K-Map Simplification Rules

Grouping Rules

Steps for SOP Simplification

Illustrative Problems

Problem 1: Simplify a 3-Variable Boolean Function

Given:

Step 1: Plot minterms

Step 2: Grouping

Step 3: Identify constant variable

Simplified Expression:

Problem 2: Simplify Using K-Map

Given:

Step 1: Plot minterms

Step 2: Grouping

Step 3: Constant variable

Simplified Expression:

Problem 3: K-Map with Multiple Groups

Given:

Step 1: Plot minterms

Step 2: Grouping

Yet another illustration

1. Requirement Statement

2. The Truth Table

3. Sum of Products (SOP) Implementation

4. Optimization using Karnaugh Map (K-Map)

Mapping the 1s:

Plot of minterms

Grouping (Looping):

Optimized Expression:

5. Final Logic Circuit

Advantages of K-Map

Limitations

Share this: