Boolean Algebra and Minimization

Overview

In this chapter, we shall establish the mathematical foundations upon which all digital systems are built. Boolean algebra provides a formal framework for the analysis and design of logic circuits, enabling us to describe the behavior of complex digital hardware through precise algebraic expressions. This system of logic, which operates on binary variables and logical operations, is the very language of computation. A rigorous understanding of its axioms, theorems, and manipulative techniques is therefore not merely an academic exercise, but a prerequisite for the competent design and comprehension of any digital device, from a simple logic gate to a sophisticated microprocessor.

The significance of this topic within the context of the GATE examination cannot be overstated. A substantial portion of questions in the Digital Logic section directly tests the principles of Boolean algebra and, more critically, the techniques for its simplification. The process of minimization is central to the discipline, as it directly translates to the reduction of circuit complexity, cost, and power consumption. Mastery of systematic minimization methods, such as Karnaugh Maps and the Quine-McCluskey algorithm, is essential for efficiently solving problems under examination conditions. These skills form the bedrock for subsequent chapters on combinational and sequential circuits, making this chapter a critical stepping stone in your preparation.

---

Chapter Contents

| # | Topic | What You'll Learn |
|---|-------|-------------------|
| 1 | Boolean Algebra | Axioms, theorems, and manipulation of logic. |

---

---

Learning Objectives

---

---

We now turn our attention to Boolean Algebra...
## Part 1: Boolean Algebra

Introduction

Boolean algebra is the mathematical foundation upon which the entire field of digital logic design is built. It provides a formal system for manipulating logical variables and expressions, which directly correspond to the behavior of digital circuits. For a GATE aspirant, a masterful command of Boolean algebra is not merely advantageous; it is essential for analyzing, simplifying, and designing the combinational and sequential circuits that constitute modern computing systems.

We will systematically explore the postulates that define this algebra, the key theorems that facilitate expression manipulation, and the standard forms used to represent logical functions. Our focus will be on the algebraic methods of simplification and the direct application of these principles to problems commonly encountered in the GATE examination. By understanding the underlying structure and rules, we can move beyond rote memorization to a more profound and flexible problem-solving capability.

---

---

Key Concepts

1. Boolean Postulates and Principal Theorems

The postulates of Boolean algebra give rise to a set of powerful theorems that are instrumental in the manipulation and simplification of Boolean expressions. The principle of duality is fundamental: for any valid Boolean equation, its dual, obtained by interchanging the $\cdot$ and $+$ operators and the identity elements $0$ and $1$, is also valid.

| Theorem Name | Statement | Dual Statement |
| :---------------- | :--------------------------------------- | :------------------------------------------- |
| Idempotence | $A + A = A$ | $A \cdot A = A$ |
| Annulment | $A + 1 = 1$ | $A \cdot 0 = 0$ |
| Absorption | $A + A \cdot B = A$ | $A \cdot (A + B) = A$ |
| Involution | $\overline{(\bar{A})} = A$ | |
| De Morgan's | $\overline{A + B} = \bar{A} \cdot \bar{B}$ | $\overline{A \cdot B} = \bar{A} + \bar{B}$ |

Two of the most frequently applied theorems in simplification are De Morgan's theorem and the Consensus theorem.

Worked Example:

Problem: Simplify the Boolean expression $F(X, Y, Z) = (X + Y)(\bar{X} + Z)$.

Solution:

Step 1: Apply the distributive law $a + (b \cdot c) = (a + b) \cdot (a + c)$, but in reverse. Here, we distribute terms from the first parenthesis into the second.

Step 2: Distribute $X$ and $Y$ into their respective terms.

Step 3: Apply the complement postulate, which states $A \cdot \bar{A} = 0$.

Step 4: Observe that the term $YZ$ is the consensus term of $XZ$ and $\bar{X}Y$. According to the Consensus Theorem ($AB + \bar{A}C + BC = AB + \bar{A}C$), we can eliminate the redundant consensus term.

Answer: The simplified expression is $XZ + \bar{X}Y$.

---

---

2. Boolean Functions and Canonical Forms

A Boolean function can be represented in several ways, most commonly via a truth table or an algebraic expression. For standardization and systematic manipulation, we use canonical forms.

For three variables $A, B, C$:

• The minterm for the combination $A=1, B=0, C=1$ (binary 101, decimal 5) is $A\bar{B}C$, denoted $m_5$.


• The maxterm for the same combination is $\bar{A}+B+\bar{C}$, denoted $M_5$.

A function can be uniquely expressed in one of two canonical forms:

Canonical Sum-of-Products (SOP): The function is expressed as a sum (OR) of the minterms for which the function's output is $1$. This is also known as the Sum-of-Minterms form, denoted by $\Sigma m()$.

Canonical Product-of-Sums (POS): The function is expressed as a product (AND) of the maxterms for which the function's output is $0$. This is also known as the Product-of-Maxterms form, denoted by $\Pi M()$.

Worked Example:

Problem: A 3-variable function $F(A,B,C)$ is $1$ when the number of $1$s in the input is odd. Express $F$ in both $\Sigma m$ and $\Pi M$ canonical forms.

Solution:

Step 1: Construct the truth table for the function. The function is $1$ for inputs 001, 010, 100, and 111.

| A | B | C | Decimal | F |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 2 | 1 |
| 0 | 1 | 1 | 3 | 0 |
| 1 | 0 | 0 | 4 | 1 |
| 1 | 0 | 1 | 5 | 0 |
| 1 | 1 | 0 | 6 | 0 |
| 1 | 1 | 1 | 7 | 1 |

Step 2: Identify the minterms for which $F=1$. These correspond to decimal indices 1, 2, 4, 7.

Step 3: Identify the maxterms for which $F=0$. These correspond to decimal indices 0, 3, 5, 6.

Answer: The canonical forms are $F = \Sigma m(1, 2, 4, 7)$ and $F = \Pi M(0, 3, 5, 6)$. This function is the 3-variable XOR function, $F = A \oplus B \oplus C$.

---

---

3. Operations on Functions in Canonical Form

When functions are expressed as lists of minterms, logical operations between them translate to set operations on their minterm lists.

Let $F_1 = \Sigma m(S_1)$ and $F_2 = \Sigma m(S_2)$, where $S_1$ and $S_2$ are sets of minterm indices.

• OR Operation ($F_1 + F_2$): The resulting function includes minterms present in either $F_1$ or $F_2$. This corresponds to the union of the minterm sets.

• AND Operation ($F_1 \cdot F_2$): The resulting function includes only the minterms present in both $F_1$ and $F_2$. This corresponds to the intersection of the minterm sets.

• XOR Operation ($F_1 \oplus F_2$): The resulting function includes minterms present in one function but not both. This corresponds to the symmetric difference of the minterm sets.

• Complement ($\bar{F_1}$): The complement of a function includes all minterms not present in the original function.

where $U$ is the set of all possible minterms for the given number of variables.

Worked Example:

Problem: Given two 4-variable functions $f_1 = \Sigma m(0, 2, 5, 7, 8, 10)$ and $f_2 = \Sigma m(2, 3, 7, 8, 11, 15)$, find the expression for $Y = f_1 \oplus f_2$.

Solution:

Step 1: Identify the sets of minterms for $f_1$ and $f_2$.

Step 2: Calculate the union of the two sets, $S_1 \cup S_2$.

Step 3: Calculate the intersection of the two sets, $S_1 \cap S_2$.

Step 4: Find the symmetric difference by taking the elements in the union but not in the intersection.

Answer: $\boxed{Y = \Sigma m(0, 3, 5, 10, 11, 15)}$

---

---

4. Deriving Expressions from Logic Circuits

To analyze a logic circuit, we systematically derive the Boolean expression for its output by writing expressions for the output of each gate, starting from the inputs and moving towards the final output.

Worked Example:

Problem: Determine the Boolean function $F$ implemented by the following circuit.

A

B

C

G1

G2

F

Solution:

Step 1: Write the expression for the output of the first-level gates, G1 and G2. Both are NAND gates.

Step 2: Write the expression for the final gate, which takes G1 and G2 as inputs. This is also a NAND gate.

Step 3: Substitute the expressions for G1 and G2 into the expression for F.

Step 4: Simplify the expression using De Morgan's theorem. First, break the outermost complement bar.

Step 5: Apply the involution theorem ($\overline{\bar{X}} = X$).

Step 6: Factor out the common variable B.

Answer: The Boolean function implemented by the circuit is $F = B(A+C)$.

---

---

Problem-Solving Strategies

---

Common Mistakes

---

Practice Questions

:::question type="MSQ" question="Which of the following Boolean equations is/are correct?" options=["$(A+C)(\bar{A}+B) = AB + \bar{A}C$","$A + \bar{A}B = A+B$","$\overline{A \oplus B \oplus C} = (A \odot B) \odot C$","$AB + BC + CA = (A+B)(B+C)(C+A)$"] answer="A,B,D" hint="Simplify the left-hand side of each equation using Boolean theorems like absorption, distribution, and De Morgan's law. Recognize standard functions like XOR and XNOR." solution="
A:

By consensus theorem, the $BC$ term is redundant.

This statement is correct.

B:

This statement is correct.

C: $\overline{A \oplus B \oplus C}$ is the complement of the 3-input XOR (odd function). The complement is an even function (output is 1 for an even number of 1s).
The expression $(A \odot B) \odot C$ is:

This corresponds to minterms $m_7, m_1, m_4, m_2$, which is $\Sigma m(1,2,4,7)$. This is the odd function, not the even one. So, this statement is incorrect.

D:

This is the majority function, and the identity is correct.
Answer: \boxed{A,B,D}
"
:::

:::question type="NAT" question="Consider three 4-variable functions: $f_1 = \Sigma m(1, 3, 4, 5, 9, 11, 12)$, $f_2 = \Sigma m(0, 3, 5, 7, 9, 13, 15)$, and $f_3 = \Pi M(1, 4, 5, 9, 11, 12)$. Calculate the number of minterms in the final function $F = (f_1 \cdot f_2) + \bar{f_3}$." answer="7" hint="First, perform the intersection of minterm sets for $f_1 \cdot f_2$. Then, convert $f_3$ from maxterm to minterm representation to find its complement, $\bar{f_3}$. Finally, perform the union of the two resulting minterm sets and count the number of unique minterms." solution="
Step 1: Find the minterms for $f_1 \cdot f_2$ by taking the intersection of their minterm sets.

Step 2: Find the minterms for $\bar{f_3}$. We are given $f_3$ in Product-of-Maxterms form. The maxterm indices are where the function is 0.

This means the minterm indices for $f_3$ are all other indices from 0 to 15.

The complement, $\bar{f_3}$, will have the minterms that $f_3$ does not have. These are exactly the indices listed in the $\Pi M$ form.

Step 3: Find the minterms for $F = (f_1 \cdot f_2) + \bar{f_3}$ by taking the union of the resulting sets.

Step 4: Count the number of elements in the final set $S_F$.
The set has 7 unique elements.
Answer: \boxed{7}
"
:::

:::question type="MCQ" question="The expression $F = A\bar{B}C + \bar{A}BC + AB\bar{C} + ABC$ represents which of the following functions?" options=["$A \oplus B \oplus C$","$AB+BC+CA$","$A+B+C$","$\overline{A+B+C}$"] answer="B" hint="Add redundant terms using the Idempotence law ($X+X=X$) to group and factor common terms. This is a common technique for simplifying the majority function." solution="
Step 1: Start with the given expression.

Step 2: Add the term $ABC$ two more times using the Idempotence law ($X+X=X$). This is a standard trick for simplifying the majority function.

Step 3: Rearrange and group terms.

Step 4: Factor out common terms from each group.

Step 5: Apply the complement law ($X+\bar{X}=1$).


Result: The expression simplifies to the majority function, $AB+BC+CA$.
Answer: \boxed{AB+BC+CA}
"
:::

---

Summary

---

What's Next?

---

Chapter Summary

---

Chapter Review Questions

:::question type="MCQ" question="For the 4-variable Boolean function given by $F(A,B,C,D) = \sum m(0, 2, 8, 10, 13, 15) + d(5, 7)$, where $d$ represents don't-care conditions, what is the number of Essential Prime Implicants (EPIs) in its minimal sum-of-products expression?" options=["1","2","3","4"] answer="B" hint="Draw a 4-variable K-map and identify the prime implicants. Then, determine which of them cover a minterm that no other prime implicant can cover." solution="
To find the Essential Prime Implicants (EPIs), we first plot the given function on a 4-variable Karnaugh map. The variables are ordered as A, B, C, D.

The minterms are: $m(0, 2, 8, 10, 13, 15)$
The don't-cares are: $d(5, 7)$

The K-map is as follows:

| CD\AB | 00 | 01 | 11 | 10 |
|-------|----|----|----|----|
| 00 | 1 | 0 | 0 | 1 |
| 01 | 0 | d | d | 0 |
| 11 | 0 | 1 | 1 | 0 |
| 10 | 1 | 0 | 0 | 1 |

Step 1: Identify all Prime Implicants (PIs).
We form the largest possible groups of 1s and d's.

A quad covering the four corners ($m_0, m_2, m_8, m_{10}$). This group corresponds to the term $B'D'$.

A quad covering the cells for $m_5, m_7, m_{13}, m_{15}$. This group corresponds to the term $BD$.

A pair covering cells $m_5$ and $m_7$. This corresponds to the term $A'BD$. This PI is redundant as its minterms are covered by the larger quad $BD$.

A pair covering cells $m_{13}$ and $m_{15}$. This corresponds to the term $ABD$. This PI is also redundant as it is covered by the quad $BD$.

The only PIs are the two quads:

• PI 1: $B'D'$ (covers $m_0, m_2, m_8, m_{10}$)


• PI 2: $BD$ (covers $m_5, m_7, m_{13}, m_{15}$)

Step 2: Identify the Essential Prime Implicants (EPIs).
An EPI is a PI that covers at least one minterm not covered by any other PI.

• Minterm $m_0$ is only covered by PI 1 ($B'D'$). Therefore, $B'D'$ is an EPI.


• Minterm $m_2$ is only covered by PI 1 ($B'D'$).


• Minterm $m_8$ is only covered by PI 1 ($B'D'$).


• Minterm $m_{10}$ is only covered by PI 1 ($B'D'$).


• Minterm $m_{13}$ is only covered by PI 2 ($BD$). Therefore, $BD$ is an EPI.


• Minterm $m_{15}$ is only covered by PI 2 ($BD$).

Both prime implicants, $B'D'$ and $BD$, are essential. The minimal expression is $F = B'D' + BD$.

Thus, there are 2 Essential Prime Implicants.
Answer: \boxed{2}
"
:::

:::question type="NAT" question="The Boolean expression $F(A,B,C) = (A+B+C)(A+B+C')(A+B'+C)(A'+B+C)$ is simplified to a minimal sum-of-products form. The number of literals in this minimal form is ___." answer="6" hint="Convert the Product-of-Sums expression to its canonical minterm list representation ($\sum m$) and then use a K-map or Boolean algebra to find the minimal SOP form." solution="
The given expression is in Product-of-Sums (POS) form.

Each term in the product corresponds to a maxterm where the function is 0.

• $(A+B+C) \implies M_0 \implies F=0$ for $A=0, B=0, C=0$.


• $(A+B+C') \implies M_1 \implies F=0$ for $A=0, B=0, C=1$.


• $(A+B'+C) \implies M_2 \implies F=0$ for $A=0, B=1, C=0$.


• $(A'+B+C) \implies M_4 \implies F=0$ for $A=1, B=0, C=0$.

So, the function can be represented as a product of maxterms:

This means the function is 1 for all other minterms. The minterms are:

We can now use a 3-variable K-map to find the minimal SOP expression.

| C\AB | 00 | 01 | 11 | 10 |
|------|----|----|----|----|
| 0 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 1 | 1 |

The 1s are at positions $m_3(011), m_5(101), m_6(110), m_7(111)$.

We form the following groups (prime implicants):

Pair for $m_3$ and $m_7$: $BC$.

Pair for $m_5$ and $m_7$: $AC$.

Pair for $m_6$ and $m_7$: $AB$.

All three prime implicants are essential. The minimal SOP expression is the sum of these three terms:

The number of literals is the total count of variables in the expression.
Literals = 2 (for AB) + 2 (for BC) + 2 (for AC) = 6.

Alternatively, using Boolean algebra:

Using the identity $(X+Y)(X+Y') = X$:
Let $X = A+B$. Then:

So, the expression becomes:

Now, distribute $(A+B)$:


Using $A+AB'=A$ and $BB'=0$:

Using $A+AC=A$ and $A+AB=A$:

Distribute again:


Using $AA'=0$, $BB=B$, $CC=C$:


Using the absorption law $X+X'Y = X+Y$ on $BC + A'BC$:

The number of literals is 6.
Answer: \boxed{6}
"
:::

:::question type="MCQ" question="Which of the following sets of logic gates is NOT functionally complete?" options=["{NOR}","{XOR, NAND}","A 2-to-1 Multiplexer","{AND, OR, XNOR}"] answer="D" hint="A set of gates is not functionally complete if it preserves a certain property that not all Boolean functions have. Consider properties like preserving the value 0 (T0), preserving the value 1 (T1), or monotonicity." solution="
A set of gates is functionally complete if it can be used to generate any Boolean function. This is equivalent to being able to generate a known complete set, such as {AND, OR, NOT}. Let's analyze each option based on Post's lattice criteria for functional completeness.

A. {NOR}: The NOR gate is a universal gate. It is well-known to be functionally complete on its own. For example, NOT A can be implemented as A NOR A.

B. {XOR, NAND}: This set contains the NAND gate, which is itself a universal gate. Since the set contains a functionally complete subset, the entire set is functionally complete.

C. A 2-to-1 Multiplexer (MUX): A 2-to-1 MUX is functionally complete. Let the MUX have inputs $I_0, I_1$ and select line $S$. The output is $Y = S'I_0 + SI_1$.

• To get NOT: Set $I_0=1, I_1=0$. Then $Y = S' \cdot 1 + S \cdot 0 = S'$.


• To get AND: Set $I_0=0, I_1=B$. Then $Y = S' \cdot 0 + S \cdot B = SB$. Let $S=A$. Then $Y=AB$.

Since we can generate NOT and AND, we can generate NAND, which is a complete set. Therefore, a 2-to-1 MUX is functionally complete.

D. {AND, OR, XNOR}: Let's check if this set preserves any of the special properties. A set is not complete if all its gates preserve a property. One such property is T1-preservation (preserving 1), which means that if all inputs to a gate are 1, the output is also 1.

• `AND(1, 1, ..., 1) = 1`. AND is T1-preserving.


• `OR(1, 1, ..., 1) = 1`. OR is T1-preserving.


• `XNOR(1, 1) = 1`. XNOR is T1-preserving.

Since all gates in the set {AND, OR, XNOR} are T1-preserving, any function constructed solely from these gates will also be T1-preserving. This means we cannot construct a function that is NOT T1-preserving, such as the NOT function (NOT(1) = 0) or the NAND function (NAND(1,1)=0). Therefore, this set is not functionally complete.
Answer: \boxed{D}
"
:::

---

What's Next?