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 -

k-map

Example 2

For the expression - AB+ A’B’, develop a k-map.

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.

k-map Rule 1

Wrong grouping

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

k-map Rule 2

Wrong grouping

Rule 3 – Grouping is allowed horizontally, vertically but not allowed diagonally.

k-map Rule 3

Wrong diagonal grouping

k-map Rule 3

Proper vertical grouping

k-map Rule 3

Proper horizontal grouping

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

k-map Rule 4

Insufficient grouping

k-map Rule 4

Proper grouping

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

k-map Rule 5

Proper grouping

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

k-map Rule 6

Proper grouping

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

k-map Rule 7

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

K-map for F (A, B, C)

By following the rules, the cells of 1 are grouped.

k-map

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.

All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Discrete Mathematics Topics