Boolean Algebra and Minimization Technique

CONTENTS
o Boolean Algebra
o Daily Life Example
of Boolean Algebra
o Laws & Theorem of
Boolean Algebra
o Karnaugh-Map

1 Mukesh Jakkula
Boolean Algebra: It is used to analyze and simplify digital logic circuits. It works
only on two logic levels: 0 (Low) and 1 (High).

Daily Life Examples of Boolean Algebra :

1. Turning ON a Room Light .You have two switches to turn ON the same
light.
• Switch A = 1 (ON)
• Switch B = 1 (ON)
• Light turns ON if either switch is ON.
Solution : OR Gate

2. Door Lock + Fingerprint To unlock a digital locker:

• You enter the PIN (A)
• You give Fingerprint (B)
Both must be correct.
Solution : AND Gate

3. Car Seat-belt Alarm

If you don’t wear the seat-belt, alarm turns ON.
Solution : NOT Gate
4. TV Remote Power Button
Pressing the button changes the TV state:
• If OFF → ON
• If ON → OFF
Solution : XOR Gate

5. Washing Machine Safety. The machine runs only when:

• Door is closed (D = 1)
• Start button pressed (S = 1)
• Child-lock is not ON (C' = 1)
Solution : AND+NOT Gate (Run = D · S · C')

6. AC Temperature Setting Air conditioner turns ON cooling if:

• Room temperature > Set temperature

2 Mukesh Jakkula
This is digital form:
Cool = (Room > Set)
Solution : Comparator logic

7. Motion Sensor Light (OR + NOT)

Light turns ON if:
• Motion detected (M = 1)
• OR it is dark (D = 1)
Solution : OR + NOT Gate
If D = 1 means dark → M + D
If D = 0 means daylight → M + D' (if D means daylight)

8. Lift (Elevator) Door Control (AND Logic)

Door closes only if:
• No person is detected near the door
• Close button is pressed
Solution : AND Gate
Laws and Theorems of Boolean Algebra : It help simplify expressions and
reduce digital circuits.
1. Identity Laws
• A+0=A
• A·1=A

2. Null (Domination) Laws

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

3. Idempotent Laws
• A+A=A
• A·A=A

4. Complement Laws
• A + A' = 1
• A · A' = 0

3 Mukesh Jakkula
5. Commutative Laws
Order does not matter.
• A+B=B+A
• A·B=B·A

6. Associative Laws
Grouping does not matter.
• (A + B) + C = A + (B + C)
• (A · B) · C = A · (B · C)

7. Distributive Laws
AND distributes over OR and vice-versa.
• A(B + C) = AB + AC
• A + BC = (A + B)(A + C)

8. Absorption Laws
Absorbs redundant terms.
• A + AB = A
• A(A + B) = A

9. Involution Law
• (A')' = A

10. De Morgan’s Theorems

• (A + B)' = A'B'
• (A · B)' = A' + B'
✔ Converts OR to AND and AND to OR with negation.
Boolean functions can be represented using: Truth tables, Boolean
expressions, SOP/POS forms, minterms/maxterms, K-maps, and logic gate
diagrams.

Representation of boolean expression

• Boolean expressions can be represented in 2 forms

1. Sum of products [SOP].
2. Products of sum [POS].

4 Mukesh Jakkula
 • Eg: AB + AC → SOP.
(A+B).(A+C) → POS.

Canonical form of boolean expression

• In standard SOP and POS each term boolean expression must contain all the
literals that has been used in the boolean expression

• If the above condition is satisfied then only the expression is called as

canonical form of boolean expression

• Eg : AB+AC in this expression c is missing in 1st term and b is missing in

the
2nd term so this is not a canonical SOP

Canonical or standard form of SOP

AB +AC
• We need to add all the possible combinations of the missing variables in the
terms
• AB + AC
AB(C+C’) + AC(B+B”)
ABC + ABC” + ABC + AB”C
• The standard SOP expression is

→ ABC + ABC” + AB’C

→ each term in the standard SOP expression is called as a minterm

Canonical or standard form of POS

• (A+B).(A+C)
(A+B)+(C.C’).(A+C)+(B.B’)

• The standard POS form of expression is

→ (A+B+C).(A+B+C’).(A+B’+C)
→ each term in the standard POS expression is called as a maxterm

5 Mukesh Jakkula
Three variable Minterms and Maxtems

• Sum of minterms of entries that evaluates to ‘1’ sum of masters that

evaluates to ‘0’.

Conversion of SOP to POS and viceversa

• Start by converting given expression to SSOP form

• AB’ + A’C = AB’C + AB’C’ + A’BC + A’B’C
101 + 100 + 011 + 001
• By using the truth table map down the values of the minterms
→ (1,3,4,6).
• Now the remaining terms are the maxterms
→ (0,2,5,7).

Karnaugh Maps (K-MAP)

• Karnaugh maps (K-maps) graphically represent Boolean functions.

Each map cell matches a truth table row.

• Each cell also corresponds to a minterm or maxterm in the Boolean

expression.

• Grouped cells represent standard terms.

6 Mukesh Jakkula
 • K-maps systematically simplify Boolean expressions to the minimal SOP or
POS form.

What is K-Map

• K-Map resembles a truth table but uses an array of cells, each representing
a binary input value.

• Cells are arranged to simplify expressions by grouping adjacent cells.

• Applicable for expressions with 2 to 5 variables.

• Formula : 2^n = n is the number of variables.

• Example : 2^2 = 4 (2 variables)

2^3 = 8 (3 variables)
2^4 = 16 (4 variables)

Two-Variable K-map

• Ordering of variables is important for (x1, x2), x1 is the row, x2 is the

column.

• Cell 0 represents x1’ x2’;

• cell 1 represents x1 x2; etc.

• If a minterm is present in the function, then a 1 is placed in the

corresponding cell.

• Any two adjacent cells in the map differ by ONLY one variable, which
appears

• complemented in one cell and uncomplemented in the other.

• Example: m0=(x1’x2’) is adjacent to m1=(x1’x2) and m2=(x1x2’) but NOT

m3=(x1x2)

THREE-VARIABLE K-MAP

• There are 8 cells

7 Mukesh Jakkula
 • Example : Minimize the following equation using

• K-map. Y = A’B’C’+A’BC’+AB’C+ABC

• A’B’C’ = 000 = 0 A’BC’= 010 = 2

• AB’C = 101 = 5 ABC = 111 = 7

• Using this fill the k-map

• Grouping- here 2 groups of 2 1’s is possible

• for upper group A and C are constants B is varying.

• So the upper group term is (A’.C’).

• same goes for the lower group its term is (A.B).

The 4-variable k-map

• There are 16 cells

• • Example of 4 variable k-map

grouping
➔ SOP(2,4,5,7,8,9,10,12,13,15)

8 Mukesh Jakkula
K-map SOP minimization

• K-Map simplifier Boolean expressions to their minimal form

• Minimized SOP expressions have the fewest terms and variables

• Minimal SOP expressions use fewer logic gates than standard ones

Rules for KMAP grouping

Examples:

K-maps for Product-of-Sum Design

• Product-of-sums design uses the same principles, but applied to the zeros of
the function.

9 Mukesh Jakkula
Examples:

Designing with Don't-Care Values

• In some situations, we don't care about the value of a logic function. For
example, if we use wxyz to represent a number from 0 to 9, we need not
worry about the function value produced for wxyz = 10...15.
• For these situations, the function can be assigned an output in order to
make the resulting circuit as simple as possible
• Suppose we wish to implement the function f(wxyz)=Sum(3,5,6,7)and we
have the don't-care condition of d=Sum(10,11,12,13,14,15).

10 Mukesh Jakkula
The sum-of-products implementation:

The product-of-sums implementation:

Karnaugh Maps-Rules of Simplification

• The Karnaugh map uses the following rules for the simplification of
expressions by grouping together adjacent cells containing ones
• Groups may not include any cell containing a zero

11 Mukesh Jakkula
 • Groups must contain 1, 2, 4, 8, or in general 2n cells. That is if n = 1, a
group will contain two 1's since 21 = 2. If n = 2, a group will contain four 1's
since 22 = 4.

• Each group should be as large as possible.

12 Mukesh Jakkula
 • Each cell containing a one must be in at least one group.

• Groups may overlap.

• Groups may wrap around the table. The leftmost cell in a row may be
grouped with the rightmost cell and the top cell in a column may be
grouped with the bottom cell.

13 Mukesh Jakkula
 • There should be as few groups as possible, as long as this does not
contradict any of the previous rules.

• Karnaugh maps are used to simplify real-world logic requirements so that

they can be implemented using a minimum number of physical logic gates.

• A sum of product expression can always be implemented using AND gate

feeding into an OR gate, and a product of sum expression leads to OR gates
feeding an AND gate.

14 Mukesh Jakkula
K-MAP minimization for more than 5 variables

• For more than 5 variables, minimization using k-maps is very complex so we

adopt to other minimization techniques like

• Quine-McCluskey (Q-M) method is the primary manual technique used,

while computer programs and specialized algorithms are often employed in
practice.

• Espresso Algorithm: This is an industry-standard heuristic computer

program for logic minimization. It is highly efficient and can handle
functions with many variables far more effectively than manual methods.

• Modified Q-M Methods: Several modifications to the original Quine-

McCluskey method have been developed to improve its performance and
reduce the number of comparisons required, making it more efficient for
computer implementation.

15 Mukesh Jakkula