Simplification of Boolean Functions

Definition

Simplification of Boolean functions is the process of transforming a Boolean expression into an equivalent expression with minimum possible literals, terms, or logic gates, while preserving the same input-output behavior for all input combinations.

For example, the Boolean function

$$F = A\bar{B} + AB$$

can be simplified as:

$$F = A(\bar{B} + B) = A(1) = A$$

So the simplified form is just:

$$F = A$$

This means the original expression and the simplified expression produce the same output, but the simplified one is much easier to implement.

---

Main Content

1. Boolean Variables, Literals, and Logic Expressions

Boolean variables

• represent binary quantities, typically written as $A$, $B$, $C$, etc., and each can be either 0 or 1.

Literals

• are variables in either direct or complemented form, such as $A$, $\bar{A}$, $B$, or $\bar{B}$. Boolean expressions are built from these literals using logical operators like AND, OR, and NOT.

Boolean functions are commonly represented in several standard forms:

Sum of Products (SOP)

• OR of AND terms, such as $F = \bar{A}B + AB\bar{C}$

Product of Sums (POS)

• AND of OR terms, such as $F = (A + B)(\bar{A} + C)$

Canonical forms

• Expressions where every term includes all variables either in direct or complemented form

Understanding these representations is important because simplification often starts from a canonical or expanded form.

Example:

$$F(A,B) = A\bar{B} + AB$$

Here, both terms contain $A$, and $B$ appears in complemented and uncomplemented forms. This expression can be simplified by factoring out $A$.

---

2. Boolean Algebra Laws and Theorems

• Boolean simplification relies heavily on Boolean algebra laws, which are identities used to reduce expressions without changing their meaning.
• These laws form the mathematical foundation for simplification methods and help eliminate redundancy.

Important Boolean laws include:

Identity law

$$A + 0 = A,\quad A \cdot 1 = A$$

Null law

$$A + 1 = 1,\quad A \cdot 0 = 0$$

Idempotent law

$$A + A = A,\quad A \cdot A = A$$

Complement law

$$A + \bar{A} = 1,\quad A\bar{A} = 0$$

Distributive law

$$A(B + C) = AB + AC$$

Absorption law

$$A + AB = A,\quad A(A + B) = A$$

De Morgan’s laws

$$\overline{A + B} = \bar{A}\bar{B},\quad \overline{AB} = \bar{A} + \bar{B}$$

These laws are used repeatedly in algebraic simplification.

Example:

$$F = A + AB$$

Using absorption:

$$F = A$$

This works because if $A=1$, the function is already 1; if $A=0$, then both terms become 0.

---

3. Methods of Simplification

• Boolean functions can be simplified using several methods depending on the size and complexity of the expression.
• The most common methods are algebraic simplification, Karnaugh maps, and computer-based minimization.

Algebraic Method

This method uses Boolean laws and theorems directly to reduce expressions.

Example:

$$F = AB + A\bar{B}$$

Factor out $A$:

$$F = A(B + \bar{B})$$

Since $B + \bar{B} = 1$,

$$F = A$$

This method is useful for small expressions and manual simplification.

Karnaugh Map (K-map) Method

A K-map is a visual tool used to simplify Boolean functions by grouping adjacent 1s in a map arranged according to Gray code order.

For a 2-variable function:

      B
     0   1
A  +---------
0  | 0 | 1 |
1  | 1 | 1 |

If the 1s are grouped properly, the expression can be reduced by eliminating variables that change within the group.

Example: If the minterms are $m_2, m_3$, the function may simplify to $A$.

Computer-Aided Minimization

For large logic systems, software tools and algorithms such as the Quine-McCluskey method or heuristic logic minimizers are used to find optimal or near-optimal simplified forms.

This is especially important in VLSI and large digital systems where manual simplification becomes impractical.

---

Working / Process

1. Write the Boolean function clearly

• Identify the variables and whether the function is in SOP, POS, or canonical form.
• If the function is given in a truth table or minterm/maxterm form, convert it first into an algebraic expression.

2. Apply simplification rules or map-based grouping

• Use Boolean algebra laws to combine terms, remove duplicates, eliminate complements, and apply absorption or consensus rules.
• If using a K-map, place 1s in the correct cells and group adjacent cells in powers of 2: 1, 2, 4, 8, etc.

3. Verify the simplified expression

• Compare the truth table of the original and simplified expressions.
• Ensure both forms produce identical outputs for all input combinations.
• The simplified form should use fewer gates, fewer literals, or less hardware while preserving exact behavior.

Example using algebra:

Given:

$$F = \bar{A}B + AB + A\bar{B}$$

Simplify:

$$F = B(\bar{A} + A) + A\bar{B}$$

$$F = B + A\bar{B}$$

Now use absorption:

$$F = A + B$$

So the simplified function is:

$$F = A + B$$

---

Advantages / Applications

Reduces hardware cost

• Fewer gates and fewer components are needed to implement the circuit.

Improves speed and efficiency

• Simpler logic often means shorter propagation delay and faster operation.

Makes circuits easier to design and test

• Simplified expressions are easier to understand, analyze, troubleshoot, and verify.

Applications of Boolean simplification include:

• Design of combinational logic circuits
• Microprocessors and control logic
• Digital adders and subtractors
• Multiplexers, encoders, and decoders
• Programmable logic devices and VLSI design

For example, in a digital controller, reducing a Boolean expression from three levels of logic to one or two levels can significantly improve performance and reduce power consumption.

---

Summary

• Boolean function simplification means reducing a logic expression without changing its output.
• It is done using Boolean laws, algebraic manipulation, K-maps, or software tools.
• Simplification helps create faster, cheaper, and more reliable digital circuits.
• Important terms to remember: Boolean function, literal, minterm, maxterm, SOP, POS, K-map, absorption law, De Morgan’s laws