Boolean Algebra and Karnaugh Map (K-Map) Simplification

Why Do We Simplify Boolean Expressions?

Every extra logic gate inside a computer uses up silicon chip space, drains battery, generates heat, and slows down processing speed.

• Boolean Algebra and K-Maps help us reduce complicated equations to their simplest possible form.
• A smaller equation means fewer physical gates and a faster, cheaper computer circuit!

💡 Real-Life Indian Student Analogy:
Imagine packing your college bag.
Instead of carrying 5 separate heavy books for one subject, you carry one combined all-in-one notebook!
That is what Boolean minimization does for computer chips: same result, but much lighter and faster.

1. Fundamental Laws of Boolean Algebra

2. De Morgan’s Theorems

De Morgan’s rules are the most popular simplification tools in university exams.
Easy memory trick: “Break the line, change the sign!”

First Theorem:

The complement of an AND is the OR of individual complements:
(A • B)' = A' + B'
(A NAND gate acts like an OR gate with inverted inputs).

Second Theorem:

The complement of an OR is the AND of individual complements:
(A + B)' = A' • B'
(A NOR gate acts like an AND gate with inverted inputs).

3. Canonical Forms: SOP and POS

1. Sum of Products (SOP):

   • Built using Minterms (m).
   • Each minterm is a product (AND) of variables.
   • Example: F(A, B, C) = Σ m(1, 3, 5, 7)
   • Written out: F = A'B'C + A'BC + AB'C + ABC

2. Product of Sums (POS):

   • Built using Maxterms (M).
   • Each maxterm is a sum (OR) of variables.
   • Example: F(A, B, C) = Π M(0, 2, 4, 6)

4. Karnaugh Map (K-Map) Simplification

A K-Map is a graphical grid used to simplify logic functions without solving long algebraic formulas.

• Adjacent squares differ by only one single bit.
• This is why coordinates follow Gray code order: 00, 01, 11, 10.

Golden Rules for K-Map Grouping:

1. Groups must always be in powers of 2: 1, 2, 4, 8, or 16 cells.
2. Group only 1s for SOP expressions (or 0s for POS).
3. Groups can be horizontal or vertical—never diagonal.
4. Always make groups as big as possible (an octet is better than two quads).
5. Wrap-Around Property: The top row touches the bottom row, and the left column touches the right column!
6. Don’t-Care Conditions (d or X): You can treat X as a 1 if it helps make a larger group; otherwise, simply leave it as 0.

Solved Example: 3-Variable K-Map

Simplify the Boolean function:
F(A, B, C) = Σ m(1, 3, 5, 7)

K-Map Grid:

           BC
   A \    00   01   11   10
      +----+----+----+----+
   0  |  0 |  1 |  1 |  0 |  (m0, m1, m3, m2)
      +----+----+----+----+
   1  |  0 |  1 |  1 |  0 |  (m4, m5, m7, m6)
      +----+----+----+----+

Step-by-Step Grouping:

• Notice cells m₁, m₃, m₅, m₇ form a single Quad (group of 4) across columns 01 and 11.
• Check row: A changes from 0 to 1 → A is eliminated.
• Check columns: B changes from 0 to 1 → B is eliminated.
• C remains 1 in both columns.
• Minimal SOP Answer: F = C
  (A complex circuit with four 3-input AND gates and an OR gate simplifies to just a single bare wire C!)

💡 DAVV Exam Preparation Tips

5-Mark Question: “State and prove De Morgan’s laws using a truth table.”

• State both laws clearly: (A • B)' = A' + B' and (A + B)' = A' • B'.
• Draw a 4-row truth table with columns: A, B, A', B', A • B, (A • B)', and A' + B'.
• Show that column (A • B)' matches column A' + B' values: [1, 1, 1, 0].

10-Mark Question: “Simplify the 4-variable Boolean function F(A, B, C, D) = Σ m(0, 1, 2, 4, 5, 6, 8, 9, 12, 13, 14) using a Karnaugh map.”

• Draw a 4 × 4 grid with Gray code coordinates: 00, 01, 11, 10.
• Fill 1s in the given minterm positions.
• Use corner wrap-around and combine adjacent 1s into quads and octets.
• Write the final reduced SOP expression and draw the final logic circuit diagram.