# Simplification of Boolean Functions - Discrete Mathematics

## How Boolean Functions are simplified by using Algebraic Functions?

Boolean identities are used for minimizing the Boolean expression and transforming into a equivalent expression.

Consider the following problems -

### Problem 1

By using the Boolean identities, how the following Boolean expression is minimized.

F(A,B,C)=A′B+BC′+BC+AB′C′

### Solution

Given,F(A,B,C)=A′B+BC′+BC+AB′C

Or,F(A,B,C)=A′B+(BC′+BC′)+BC+AB′C′

[By idempotent law, BC’ = BC’ + BC’]

Or,F(A,B,C)=A′B+(BC′+BC)+(BC′+AB′C′)

Or,F(A,B,C)=A′B+B(C′+C)+C′(B+AB′)

[By distributive laws]

Or,F(A,B,C)=A′B+B.1+C′(B+A)

[ (C' + C) = 1 and absorption law (B + AB')= (B + A)]

Or,F(A,B,C)=A′B+B+C′(B+A)

[ B.1 = B ]

Or,F(A,B,C)=B(A′+1)+C′(B+A)

Or,F(A,B,C)=B.1+C′(B+A)

[ (A' + 1) = 1 ]

Or,F(A,B,C)=B+C′(B+A)

[ As, B.1 = B ]

Or,F(A,B,C)=B+BC′+AC′

Or,F(A,B,C)=B(1+C′)+AC′

Or,F(A,B,C)=B.1+AC′

[As, (1 + C') = 1]

Or,F(A,B,C)=B+AC′

[As, B.1 = B]

So,F(A,B,C)=B+AC′ is the minimized form.

### Problem 2

By using the Boolean identities, how the following Boolean expression is minimized.

F(A,B,C)=(A+B)(B+C)

### Solution

Given, F(A,B,C)=(A+B)(A+C)

Or, F(A,B,C)=A.A+A.C+B.A+B.C [Applying distributive Rule]

Or, F(A,B,C)=A+A.C+B.A+B.C [Applying Idempotent Law]

Or, F(A,B,C)=A(1+C)+B.A+B.C [Applying distributive Law]

Or, F(A,B,C)=A+B.A+B.C [Applying dominance Law]

Or, F(A,B,C)=(A+1).A+B.C [Applying distributive Law]

Or, F(A,B,C)=1.A+B.C [Applying dominance Law]

Or, F(A,B,C)=A+B.C [Applying dominance Law]

Hence, F(A,B,C)=A+BC is the minimized form.

## What are Karnaugh Maps?

The Boolean algebra expressions are simplified by using a truth table. This truth table is represented by Karnaugh Map (K–map). At different positions 0 and 1 are used by k-map. Boolean expressions are grouped and the variables which are considered as unwanted are eliminated.

### Example 1

For instance, the following truth table is considered -

 A B A operation B 0 0 w 0 1 x 1 0 y 1 1 z

For the table, k-map is developed - ### Example 2

For the expression - AB+ A’B’, develop a k-map. ## How Boolean expressions are simplified Using K-map?

Boolean expressions are simplified using k-map by following some of the rules such as -

Rule 1 – It is not possible to group the cell with a zero. Wrong grouping

Rule 2 – 2n cells should be must for a group (n starting from 1). Wrong grouping

Rule 3 – Grouping is allowed horizontally, vertically but not allowed diagonally. Wrong diagonal grouping Proper vertical grouping Proper horizontal grouping

Rule 4 – As long and large as possible the group should be formed. Insufficient grouping Proper grouping

Rule 5 – If it is not possible to group 1 with other cell, it is considered as a group. Proper grouping

Rule 6 – The overlapping of the groups is allowed by should be as minimum as possible. Proper grouping

Rule 7 – The leftmost and the rightmost cells can be grouped. Similarly the topmost and bottommost cells can be grouped together. Proper grouping

### Problem

Use k-map and minimize the following Boolean expression -

F(A,B,C)=A′BC+A′BC′+AB′C′+AB′C

### Solution

All the terms are put into the k-map as follows - K-map for F (A, B, C)

By following the rules, the cells of 1 are grouped. K-map for F (A, B, C)

Two groups are formed - A′B and AB′.

Therefore, F(A,B,C)=A′B+AB′=A⊕B, which is the minimized form.

Discrete Mathematics Topics