Digital Logic & Circuit Design

Boolean Algebra and Logic Gates

Prepared by:
Nilesh Patidar and Shiraz Husain
Logic Gates

Boolean Algebra and Logic Gates 2

Laws

Boolean Algebra and Logic Gates 4

Proving theorems
§ Example 1: Prove the uniting theorem-- X•Y+X•Y'=X
Distributive =X•Y+X•Y'=X•(Y+Y’)
Complementary = X•(1)
Identity =X

§ Example 2: Prove the absorption theorem-- X+X•Y=X

Identity X+X•Y=(X•1)+(X•Y)
Distributive = X•(1+Y)
Null = X•(1)
Identity =X

Boolean Algebra and Logic Gates 5

Proving theorems

§ Example 3: Prove the consensus theorem

(XY)+(YZ)+(X'Z)= XY+X’Z
Solution:
Ø Complementarity XY+YZ+X'Z = XY+(X+X')YZ + X’Z
Ø Distributive = XY+XYZ+X'YZ+X’Z
Ø Use absorption {AB+A=A}
= XY+X'YZ+X'Z
Ø Rearrange terms = XY+X'ZY+X’Z
Ø Use absorption {AB+A=A}
= XY+X'Z

Boolean Algebra and Logic Gates 6

Example: Simplification

Z = A'BC + AB'C' + AB'C + ABC' + ABC

= A'BC + AB'(C’ + C) + AB(C' + C) distributive
= A'BC + AB’ + AB complementary
= A'BC + A(B' + B) distributive
= A'BC+ A complementary
= BC + A absorption

Boolean Algebra and Logic Gates 7

Simplification of Boolean Equation
§ Reduce the Expression- + (!" + + "# $)

Boolean Algebra and Logic Gates 8

Simplification of Boolean Equation
§ Simplify the Expression- ( + ")( + & ")( + $)

Boolean Algebra and Logic Gates 9

Simplification of Boolean Equation
§ Simplify the Expression- ( + ")( + & ")( + $)

Boolean Algebra and Logic Gates 10

Simplification of Boolean Equation
§ Simplify the Expression- F= A’B(C’D’ + C’D) + AB (C’D’ +C’D) + AB’C’D

Boolean Algebra and Logic Gates 11

Logic Diagram
§ Implement the following function using logic gates-
= !" + !# + "$

Boolean Algebra and Logic Gates 12

Logic Diagram
§ Implement the following function using logic gates-
§ F = (P’Q’ + PQ)R + (P’Q+PQ’)R’

Boolean Algebra and Logic Gates 13

Logic Diagram
§ Minimize the following Boolean Function & also draw the
simplified logic diagram
Y = (AB+C)(AB+D)

Boolean Algebra and Logic Gates 14

Logic Diagram
§ Minimize the following Boolean Function & also draw the
simplified logic diagram

Boolean Algebra and Logic Gates 15

Logic Diagram
Obtain the Boolean expression

Boolean Algebra and Logic Gates 16

Logic Diagram
§ Simplify the given logic diagram.

Boolean Algebra and Logic Gates 17

Duality
§ It states that in a two valued Boolean algebra, the dual of an
algebraic expression can be obtained simply by interchanging
OR and AND operators and by replacing 1’s by 0’s and 0’s by
1’s.

§ Find the dual of the following Boolean expressions:

i. A+AB = A
ii. A + A’B = A + B
iii. A + A’ = 1
iv. (A+B)(A+C) = A+BC

Boolean Algebra and Logic Gates 18

Universal Gate: NAND Gate

Boolean Algebra and Logic Gates 19

Bubble Pushing Method- NAND Gate

§ Step 1: Implement the given Boolean expression in AOI form.

§ Step 2: Add a bubble at output of each AND gate and input of
each OR gate.
§ Step 3: Connect a NOT gate on each wire where a bubble is
added in Step 2.
§ Step 4: Cancel out 2 NOT gates that are connected in series.
§ Step 5: Replace NOT gate with NAND gate equivalent.
§ Step 6: Replace bubbled OR with NAND gate.

Boolean Algebra and Logic Gates 20

Implementation using NAND Gate
§ Implement the following function using NAND gates only
Y = AB’ + BC

Boolean Algebra and Logic Gates 21

Implementation using NAND Gate
§ Implement the following function using NAND gates only
F= AB ( C+D) + E

Boolean Algebra and Logic Gates 22

Universal Gate: NOR gate

Boolean Algebra and Logic Gates 23

Bubble Pushing Method- NOR Gate

§ Step 1: Implement the given Boolean expression in AOI form.

§ Step 2: Add a bubble at input of each AND gate and output of
each OR gate.
§ Step 3: Connect a NOT gate on each wire where a bubble is
added in Step 2.
§ Step 4: Cancel out 2 NOT gates that are connected in series.
§ Step 5: Replace NOT gate with NOR gate equivalent.
§ Step 6: Replace bubbled AND with NOR gate.

Boolean Algebra and Logic Gates 24

Implementation using NOR Gate
§ Implement the following function using NOR gates only
F = A(B’+C) + (BC)

Boolean Algebra and Logic Gates 25

Implementation using NOR Gate
§ Implement the following function using NOR gates only
F = (A’+B+C)(A+B)D

Boolean Algebra and Logic Gates 26

Implementation using NOR Gate
§ Implement the following function using NOR gates only
F= (C+BD’).(B’CA+CD)

Boolean Algebra and Logic Gates 27

Standard Form (SOP & POS)

§ Standard SOP form

Ø Y = ABC + AB’C’ + A’BC
Ø Each product term consists of all the literals in the
complemented or uncomplemented form

§ Standard POS form

Ø Y = (A+B+C’)(A+B’+C)(A’+B’+C’)
Ø Each sum term consists of all the literals in the complemented
or uncomplemented form

Boolean Algebra and Logic Gates 28

Canonical Form (SOP & POS)

§ SOP Form Y = m(0,3,4,5)

§ POS Form Y = "M(1,2,5,6)

Boolean Algebra and Logic Gates 29

Canonical Form (SOP & POS)
§ Convert the following expressions into their standard SOP
form.
Ø Y = AB + AC + BC

Boolean Algebra and Logic Gates 30

Examples
§ Convert the following expressions into their standard SOP
form.
Ø Y = AB + AC + BC

Boolean Algebra and Logic Gates 31

Examples
§ Convert the following expressions into their standard POS
form.
Ø Y = (A+B)(B’+C)

Boolean Algebra and Logic Gates 32

Examples
§ Convert the following expressions into their standard SOP
form.
Ø Y = A + BC + ABC

Boolean Algebra and Logic Gates 33

SOP to POS Conversion

Boolean Algebra and Logic Gates 34

Karnaugh Maps (K-Maps)

§Simplification of logic expression using Boolean

algebra is awkward because:
Ø it lacks specific rules to predict the most suitable next step
in the simplification process
Ø it is difficult to determine whether the simplest form has
been achieved.
§ K-MAPS
Ø A visual way to simplify logic expressions
Ø It gives the most simplified form of the expression

Boolean Algebra and Logic Gates 35

Rules to obtain the most simplified expression

§ A Karnaugh map is a graphical method used to obtained the

most simplified form of an expression in a standard form (Sum-
of-Products or Product-of-Sums).
§ The simplest form of an expression is the one that has the
minimum number of terms with the least number of literals
(variables) in each term.
§ By simplifying an expression to the one that uses the minimum
number of terms, we ensure that the function will be
implemented with the minimum number of gates.
§ By simplifying an expression to the one that uses the least
number of literals for each terms, we ensure that the function
will be implemented with gates that have the minimum
number of inputs.

Boolean Algebra and Logic Gates 36

K-maps

Boolean Algebra and Logic Gates 37

2 Variable K-map

Boolean Algebra and Logic Gates 38

3 Variable K-map

Boolean Algebra and Logic Gates 39

4 Variable K-map

Boolean Algebra and Logic Gates 40

Three-Variable K-Maps Examples
f = å (0,4) = B C f = å (4,5) = A B f = å (0,1,4,5) = B f = å (0,1,2,3) = A

BC BC BC BC
A 00 01 11 10 A 00 01 11 10 A 00 01 11 10 A 00 01 11 10
0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 1
1 1 0 0 0 1 1 1 0 0 1 1 1 0 0 1 0 0 0 0

f = å (0,4) = A C f = å (4,6) = A C f = å (0,2) = A C f = å (0,2,4,6) = C

BC BC BC BC
A 00 01 11 10 A 00 01 11 10 A 00 01 11 10 A 00 01 11 10
0 0 1 1 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 1
1 0 0 0 0 1 1 0 0 1 1 0 0 0 0 1 1 0 0 1

Boolean Algebra and Logic Gates 41

 Three-Variable K-Map Examples

§ Minimize the expression

Ø Y = AB’C + A’B’C + A’BC + AB’C’ + A’B’C

Boolean Algebra and Logic Gates 42

Four-Variable K-Maps
CD CD CD CD
00 01 11 10 00 01 11 10 00 01 11 10 00 01 11 10
AB AB AB AB
00 1 0 0 0 00 0 0 0 0 00 0 0 0 0 00 0 0 0 0
01 0 0 0 0 01 0 1 0 0 01 0 0 0 0 01 1 0 0 1
11 0 0 0 0 11 0 1 0 0 11 0 1 1 0 11 0 0 0 0
10 1 0 0 0 10 0 0 0 0 10 0 0 0 0 10 0 0 0 0

f = å (0,8) = B · C · D f = å (5,13) = B · C · D f = å (13,15) = A · B · D f = å (4,6) = A · B · D

CD CD CD CD
AB 00 01 11 10 AB 00 01 11 10 AB 00 01 11 10 AB 00 01 11 10
00 0 0 1 1 00 0 0 0 0 00 0 0 1 1 00 1 0 0 1

01 0 0 1 1 01 1 0 0 1 01 0 0 0 0 01 0 0 0 0
11 0 0 0 0 11 1 0 0 1 11 0 0 0 0 11 0 0 0 0
10 0 0 0 0 10 0 0 0 0 10 0 0 1 1 10 1 0 0 1

f = å (2,3,6,7) = A · C f = å (4,6,12,14) = B · D f = å (2,3,10,11) = B · C f = å (0,2,8,10) = B · D

Boolean Algebra and Logic Gates 43

Four-Variable K-Maps
CD CD CD CD
AB 00 01 11 10 AB 00 01 11 10 AB 00 01 11 10 AB 00 01 11 10
00 0 0 0 0 00 0 0 1 0 00 1 0 1 0 00 0 1 0 1
01 1 1 1 1 01 0 0 1 0 01 0 1 0 1 01 1 0 1 0
11 0 0 0 0 11 0 0 1 0 11 1 0 1 0 11 0 1 0 1
10 0 0 0 0 10 0 0 1 0 10 0 1 0 1 10 1 0 1 0

f = å (0, 3,5, 6, 9,10,12,15) f = å (1, 2, 4, 7,8,11,13,14)

f = å (4,5, 6, 7) = A · B f = å (3,7,11,15) = C · D
f = A Ä BÄCÄ D f = A Å BÅ CÅ D

CD CD CD CD
AB 00 01 11 10 AB 00 01 11 10 AB 00 01 11 10 AB 00 01 11 10
00 0 1 1 0 00 1 0 0 1 00 0 0 0 0 00 1 1 1 1
01 0 1 1 0 01 1 0 0 1 01 1 1 1 1 01 0 0 0 0
11 0 1 1 0 11 1 0 0 1 11 1 1 1 1 11 0 0 0 0
10 0 1 1 0 10 1 0 0 1 10 0 0 0 0 10 1 1 1 1

f = å (1, 3,5, 7,9,11,13,15) f = å (0,2,4,6,8,10,12,14) f = å (4,5,6,7,12,13,14,15) f = å (0,1,2,3,8,9,10,11)

f=D f =D f =B f=B

Boolean Algebra and Logic Gates 44

Special Case
§ Find the Boolean expression.

Boolean Algebra and Logic Gates 45

Four-Variable K-Maps Examples
CD CD CD
AB 00 01 11 10 AB 00 01 11 10 AB 00 01 11 10
00 1 1 1 00 1 1 1 00
01 1 1 1 01 1 01 1 1 1
11 1 1 1 11 11 1 1 1

10 1 1 10 1 1 1 10 1

CD CD CD
AB 00 01 11 10 AB 00 01 11 10 AB 00 01 11 10
00 1 1 00 00
01 1 1 1 1 01 01
11 1 1 1 11 11
10 1 10 10

Boolean Algebra and Logic Gates 46

Four-Variable K-Maps don’t care

§ Y = m (1,4,8,12,13,15) + d(3,14)

Boolean Algebra and Logic Gates 47

Four-Variable K-Maps don’t care

§ Y = m (1,3,7,11,15) + d(0,2,5)

Boolean Algebra and Logic Gates 48

Four-Variable K-Maps don’t care

§ Y = m (1,3,7,10,11,15) + d(0,2,5,8,14)

Boolean Algebra and Logic Gates 49

K-maps
§ Obtain the expression in POS form
§ F = "M(2,3,7)

Boolean Algebra and Logic Gates 50

K-maps
§ Obtain the expression in POS form
§ F = "M(0,2,3,5,7)

Boolean Algebra and Logic Gates 51

Five Variable K-Map

Boolean Algebra and Logic Gates 52

Five Variable K-Map

§ F(A,B,C,D,E) = m(0,2,4,6,9,11,13,15,17,21,25,27,29,31)

Boolean Algebra and Logic Gates 53

Five Variable K-Map

§ F(A,B,C,D,E) = m(0,1,7,9,11,13,15,16,17,23,25,27)

Boolean Algebra and Logic Gates 54

Five Variable K-Map

§ F(A,B,C,D,E) =
m(0,1,3,4,6,8,9,11,13,14,16,19,20,21,22,24,25)+ d(5,7,12,15,17,23)

Boolean Algebra and Logic Gates 55

Six variable K-map

Boolean Algebra and Logic Gates 56

Quine-McCluskey Tabular Method
§ Quine-McCluskey tabular method is a method based on
the concept of prime implicants. We know that prime
implicant is a product or sum term, which can’t be further
reduced by combining with any other product or sum
terms of the given Boolean function.

§ This tabular method is useful to get the prime implicants

by repeatedly using the following Boolean identity.

§ xy + xy’ = xy+y′ = x.1 = x

Boolean Algebra and Logic Gates 57

Quine-McCluskey Tabular Method
§ Step 1 − Arrange the given min terms in an ascending order and make the
groups based on the number of ones present in their binary representations. So,
there will be at most ‘n+1’ groups if there are ‘n’ Boolean variables in a
Boolean function or ‘n’ bits in the binary equivalent of min terms.
§ Step 2 − Compare the min terms present in successive groups. If there is a
change in only one-bit position, then take the pair of those two min terms. Place
this symbol ‘_’ in the differed bit position and keep the remaining bits as it is.
§ Step 3 − Repeat step2 with newly formed terms till we get all prime implicants.
§ Step 4 − Formulate the prime implicant table. It consists of set of rows and
columns. Prime implicants can be placed in row wise and min terms can be
placed in column wise. Place ‘1’ in the cells corresponding to the min terms that
are covered in each prime implicant.
§ Step 5 − Find the essential prime implicants by observing each column. If the
min term is covered only by one prime implicant, then it is essential prime
implicant. Those essential prime implicants will be part of the simplified
Boolean function.
§ Step 6 − Reduce the prime implicant table by removing the row of each
essential prime implicant and the columns corresponding to the min terms that
are covered in that essential prime implicant. Repeat step 5 for Reduced prime
implicant table. Stop this process when all min terms of given Boolean function
are over.

Boolean Algebra and Logic Gates 58

Quine Mc’clusky Method
§ Simplify- f(a,b,c,d)= m(0,1,2,5,6,7,8,9,10,14)

Boolean Algebra and Logic Gates 59

Quine Mc’clusky Method
§ f = a’c’d + a’bd + a’bc + b’c’""""""+ b’d’""""""+ cd’
(1, 5) (5, 7) (6, 7) (0, 1, 8, 9) (0, 2, 8, 10) (2, 6, 10,14)
§ Prime Implicant Table-
Minterms Given Minterms
PI corresponds
to PI 0 1 2 5 6 7 8 9 10 14

a’c’d 1, 5

a’bd 5, 7

a’bc 6, 7

b’c’ 0, 1, 8, 9

b’d’ 0, 2, 8, 10

cd’ 2, 6, 10,14

Boolean Algebra and Logic Gates 60

Quine Mc’clusky Method
§ Prime Implicant Table-
Minterms Given!Minterms
PI corresponds!
to!PI 0 1 2 5 6 7 8 9 10 14

a’c’d 1, 5 X X

a’bd 5, 7 X X

a’bc 6, 7 X X

b’c’ 0, 1, 8, 9 X X X X

b’d’ 0, 2, 8, 10 X X X X

cd’ 2, 6, 10,14 X X X X

f = a’bd + b’c’ + cd’

Boolean Algebra and Logic Gates 61
Quine Mc’clusky Method
§ Find the minimal SOP expression for the given Boolean
function- f(a,b,c,d)= m(1,3,4,5,9,10,11) + d(6,8)
Column-I Column-II Column-III
Group Binary Minterm Binary Minterm Binary
Minterms
(abcd) Pairs (abcd) Pairs (abcd)
1 0001 1-3 00-1 * 1-3-9-11 -0-1
Group 0 4 0100 1-5 0-01 1-9-3-11 -0-1
8 1000 1-9 -001 * 8-9-10-11 10--
3 0011 4-5 010- 8-10-9-11 10--
5 0101 4-6 01-0
Group 1 6 0110 8-9 100- *
9 1001 8-10 10-0 *
10 1010 3-11 -011 *
Group 2 11 1011 9-11 10-1 *
10-11 101- *
Boolean Algebra and Logic Gates 62
Quine Mc’clusky Method
§ f = a’c’d + a’bc’"+"a’bd’ + b’d + ab’
(1,5) (4,5) (4,6) (1,3,9,11) (8,9,10,11)
§ Prime Implicant Table-
Prime Minterms Given Minterms
Implicants corresponds to
(PI) PI 1 3 4 5 9 10 11

a’c’d 1, 5

a’bc’ 4, 5

a’bd’ 4, 6

b’d 1, 3, 9, 11

ab’ 8, 9, 10, 11

Boolean Algebra and Logic Gates 63

Quine Mc’clusky Method
§ Prime Implicant Table-
Minterms Given Minterms
PI corresponds to
PI 1 3 4 5 9 10 11

a’c’d 1, 5 X X

a’bc’ 4, 5 X X

a’bd’ 4, 6 X

b’d 1, 3, 9, 11 X X X X

ab’ 8, 9, 10, 11 X X X

f = ab’+ b’d + a’bc’

Essential
Prime Implicants

Boolean Algebra and Logic Gates 64

Thank You
Any Questions

Boolean Algebra and Logic Gates 65