UNIT-3

Number System
• Any to decimal
Number • decimal to Any
System
Conversi • Octal and Hexadecimal into Binary
on
•B-G
•G-B
Code •Excess-3
Conversi
•BCD code
on

•1’s Complement
•2’s complement
Complime
nts •Binary Addition and Subtraction

•Logic gates
Logic gates •Boolean Algebra Rules
and
Boolean •Simplification of Boolean Algebra
Algebra

•SOP Form
SOP and •POS Form
POS

•K-map Rule
•Simplification using Kmap
Kmap
 Today’s
Highlights

Number System Conversion

Any to decimal
Binary to Decimal
Octal to Decimal
Hexadecimal to Decimal

Decimal to Any
Decimal to binary
Decimal to Octal
Decimal to Hexadecimal

Octal and Hexadecimal into Binary

Octal to Hexadecimal
Hexadecimal to octal
 Explanation Slide
MSB and LSB
IS (𝟐𝟖𝟗𝟏)8
is octal ???

A) True
B) False

5
MSB and LSB
IS (𝟐𝟖𝟗𝟏) 𝟏𝟔 is
Explanation Slide Hexadecimal?
??

A) True
B) False

6
Types of Number System: COMPARISON
Number Conversion: Decimal to Other Base
• 1. Decimal to Binary Conversion:
• Step 1: Continuously divide by 2
until quotient is either 0 or 1.
• Step 2: Note down the remainder
corresponding to each division.
• Step 3: The pattern of 1’s and 0’s at
the remainder column represented
from bottom to top represents the
equivalent binary number.
 QUICK QUIZ (POLL)
Q. 28 10 in binary is:
a) 110110
b) 11011
c) 11000
d) 11100

10
 Try Yourself
Q1. Convert the following into Binary equivalents?
a) 247 10
b) 27 10

11
 Number System: Base Conversion with Fractions
• [Link] to Binary Conversion:
𝐶𝑜𝑛𝑣𝑒𝑟𝑡(0.6875)10 to binary?
Step 1: Continuously multiply by 2 until
fractional part is 0. Or Multiply by 2 until you
observe that the fractional part is either
repeating or never ending.
Step 2: Note down the integer part
corresponding to each multiplication
Step 3: The pattern of 1’s and 0’s at the
integer column represented from top to
bottom represents the fractional part into an
equivalent binary number.
Ex2 :Convert decimal number 0.75 into binary form

Steps: 1. Multiply the fractional decimal number by 2.

2. Integral part of resultant decimal number will be first digit of fraction binary number.
[Link] step 1 using only fractional part of decimal number and then step 2.

▪ Reading the carries from top to bottom, the result is 0.11.

▪ Thus, the binary equivalent of (0.75)10 is (0.11)2
 Try Yourself
Q1. Convert the following into Binary equivalents?
a) 0.65 10 Attempt Poll:
𝟑𝟕. 𝟔𝟓𝟔𝟐𝟓 𝟏𝟎
---- Binary
a) 100101.10101
b) 101101.10111
c) 110101.11101

14
Explanation Slide

15
Ex 3: Convert (177)10 to octal equivalent

Answer = 261
Note: 0 6 2 the answer is read from bottom to top, the same as with the binary
case.
Ex4: Convert (0.1640625)10 to octal

Therefore, 0.164062510 = (0.124)8.

Ex 4: Convert decimal number 122810 into hex

122810 = 4CC16
 FRACTION
part
QUICK QUIZ (POLL)
POLL
Q. Convert the following to octal: 305 10
(0.6875)10…….( )8
a) 440 A.45
b) 441 B.54
c) 460 C.55
D5.5
d) 461

19
Ex 6: Convert (152.25)10 Hexadecimal
• Step 1: Divide the number 152 and its successive quotients with base 16 .

(152)10=(98)16
• Step 2: Now perform the multiplication of 0.25 and successive fraction with base 16.

(0.25)10=(4)16
• hexadecimal number of the decimal number 152.25 is 230.4.
 QUICK QUIZ (POLL)
Q. Convert the following to hexadecimal: 7825 10
FRACTION part :
a) 𝐵321 (0.760)10…….( )16
b) 1E91 A)DF120
c) 123A B)C28F5
C)CA8F5
d) E240 D)DA8F6

21
Integer part
Number System: Base Conversion
1. Binary to Decimal Conversion: MSB LSB

Step 1: Multiply with the powers of 2𝑛

where n=0,1,2,3,… starting from the LSB.
Step 2: Add all the decimal numbers
corresponding to the coefficients.
Step 3: The sum obtained would be the
equivalent decimal number representation
of the given binary number.

22
 2nd
example Number System: Base Conversion
Binary to Decimal Conversion:
𝐵𝑖𝑛𝑎𝑟𝑦: (101100101)2
Step 1: Multiply with the powers of 2𝑛
where n=0,1,2,3,… starting from the LSB.
Step 2: Add all the decimal numbers
corresponding to the coefficients.
Step 3: The sum obtained would be the
equivalent decimal number 𝑅𝑒𝑠𝑢𝑙𝑡: (357)10
representation of the given binary
number.

23
 QUICK QUIZ (POLL)
Q. Convert the following binary number to decimal: 01011 2
a) 11
b) 35
c) 15
d) 10

24
 Number System: Base Conversion with Fractions
1. Binary to Decimal Conversion:
𝐶𝑜𝑛𝑣𝑒𝑟𝑡(0.1011)2 to decimal?
Step 1: Multiply with the powers of 2−𝑛
where n=1,2,3,… starting from the MSB.
Step 2: Add all the decimal numbers
corresponding to the coefficients.
Step 3: The sum obtained would be the
equivalent decimal number
representation of the given binary
number.
Fraction part

25
 Number System: Base Conversion with Fractions
1. Binary to Decimal Conversion:
𝐶𝑜𝑛𝑣𝑒𝑟𝑡(0.11011)2 to decimal?
Step 1: Multiply with the powers of 2−𝑛
where n=1,2,3,… starting from the MSB.
Step 2: Add all the decimal numbers
corresponding to the coefficients.
Step 3: The sum obtained would be the
equivalent decimal number
representation of the given binary
number.

26
 Home
assignments
Try Yourself
Q1. Convert the following into Decimal equivalents? Share on lpu
live
a) 01101.10011 2
b) 1010111.001101 2

27
 QUICK QUIZ (POLL)

Q1. Convert the following into Decimal equivalents? (1011.10011)2

• A) (11.59735)10
• B) (10.59735)10
• C) (11.59375)10
• D) (10.59375)10
 Number System: Base Conversion
2. Octal to Decimal:
• The method is quite similar to the
transformation of any binary number
to decimal, the only difference is that
in this case the 2 will be replaced by 8
and everything else i.e. the methods
will remain same.
• We have to start multiplying the digits
of the number from LSB side with
increasing powers of 8 staring from 0
and finally summing up all the
products.

29
 QUICK QUIZ (POLL)
Q. Convert the following to decimal: 431.32 8
a) 280.00123
b) 281.40625
c) 421.40625
d) 431.4343

30
Convert (6432)8 into decimal (.32 )8------( )10
 Number System: Base Conversion
3. Hexadecimal to Decimal:
• The method is quite similar to the
transformation of any binary number to
decimal, the only difference is that in this
case the 2 will be replaced by 16 and
everything else i.e. the methods will
remain same.
• we have to start multiplying the digits of
the number from LSB side with increasing
powers of 16 staring from 0 and finally
summing up all the products.

32
 QUICK QUIZ (POLL)
Q. Convert the following to decimal: 3𝐹𝐵 16
a) 1210
b) 1019
c) 4821
d) 1101

33
 QUICK QUIZ (POLL)
Q. Convert the following to decimal: A9.8 16
a) 121.0
b) 101.9
c) 169.5
d) 110.1

34
Binary to Octal Conversion
Step1: To convert from binary to octal, start grouping the bits in groups of 3 from the right end
Step2: Write the equivalent octal for the 3-bit binary.
Step3: Add 0’s on the left to adjust the groups.
Octal to Binary Conversion
Binary to Hexadecimal Conversion
Step1: To convert from binary to octal, start grouping the bits in groups of 4 from the right end
Step2: Write the equivalent octal for the 3-bit binary.
Step3: Add 0’s on the left to adjust the groups.
Ex-1 Convert (110111110111.1100)2 to hexadecimal

The hexadecimal equivalent of (110111110111.1100)2 is (DF7.C)16.

EX-2: Convert (1110111001101.111011)2 to hexadecimal

The hexadecimal equivalent of the given binary number is ([Link])16.

Hexadecimal to Binary Conversion
Ex-1: The given hexadecimal number is 6FD16. Find out its binary
form.
• 616 = 01102
• F16 = 11112
• D16 = 11012

Ans: 6FD16 = 0110 1111 11012

Octal to Hexadecimal Conversion
• Step 1 − Convert each digit of the given octal number to its equivalent binary of 3-bits.
• Step 2 − Make groups of 4 bits each of the obtained binary number.

• Step 3 − Convert each 4-bit binary group to its equivalent hexadecimal.

• EX 1: Convert (742.35)8 to hexadecimal.

Hexadecimal equivalent of the given octal number is (1E2.74)16.

 POLL
Q1.(3CFB.2E)16---------(?)8
A) (36363.134)8
B) (36373.134)8
C) (37373.134)8

Q2. (574.32)8-------------(?)16
A) (17C.68)16 B) (17D.78)16 C) (17E.78)16

41
Practice Question
• Convert (25)10 in Binary
• What is equivalent value of (278)10 in Binary?
• Convert decimal number 0.125 into binary form
• Convert decimal number 65.16 into binary form
• Convert (82.523)10 to octal equivalent up to 3 decimal places.
• Convert 756210 to hex
• Convert (524.26)10 to hexadecimal.
• Convert hexadecimal number 8F4E9A16 to its binary form.
Disadvantages of
Number System How to Overcome
this problems ??

Complex Arithmetic Operations

Unstable StaHuman Readability

Issueste

Error-Prone Data Entry

Increased Hardware
Requirements

Inefficient Memory Usage

 Today’s
Highlights

Code Conversion
 Need for Code Conversion

Error Human- Optimization of Application-

Inter-System Simplified Need for Code
Detection and Readable Memory and Specific
Compatibility Circuit Design Conversion
Correction Output Processing Requirements
Code Conversion
• Decimal to BCD code
• [Link] the BCD numbering system, the given decimal number is segregated into chunks of four bits for
each decimal digit within the number.
• 2. Each decimal digit is converted into its direct binary form (usually represented in 4-bits).
Decimal Number BCD Excess 3 code

0 0000 0011

1 0001 0100

2 0010 0101

3 0011 0110

4 0100 0111

5 0101 1000

6 0110 1001

7 0111 1010

8 1000 1011

9 1001 1100
Ex-1: Convert (123)10 in BCD
• From the truth table above,
1 -> 0001
2 -> 0010
• 3 -> 0011
Thus, BCD becomes -> 0001 0010 0011

Ex-2: Convert (324)10 in BCD

• (324)10
Again from the truth table above,
3 -> 0011
2 -> 0010
4 -> 0100
thus, BCD becomes -> 0011 0010 0100
 QUICK QUIZ (POLL)

Q. What is the BCD representation of the decimal number 57?

1.A. 0101 0111

2.B. 0110 0111
3.C. 0101 0110
4.D. 1001 0110

5
 Decimal to Excess-3 Conversion
Ex-1

Ex-2 Decimal number 31

Home assignment
 QUICK QUIZ (POLL)
Q. What is the Excess-3 code for the decimal number
9?

A. 1010
B. 1100
C. 1001
D. 1110

7
 Home
assignments
Try Yourself
Share on lpu
Q1. What is the BCD (Binary-Coded Decimal) live
representation of the decimal number 75?

Q2. Which of the following is the Excess-3 code for

the decimal number 26?

8
Binary to Gray Code Conversion
Gray Code to Binary Conversion
 QUICK QUIZ (POLL)
•Q. What is the Gray code equivalent of the binary number
1011?

A. 1100
B. 1110
C. 1001
D. 0111

11
 QUICK QUIZ (POLL)
Q. What is the binary equivalent of the Gray code
1101?

A. 1000
B. 1011
C. 1111
D. 1100

12
 Home
assignments
Try Yourself
Share on lpu
Q1. Convert the decimal number 187 into BCD live
(Binary-Coded Decimal) code.

Q2. Convert the decimal number 56 into Excess-3

code.

Q3. Convert the decimal number 23 into Gray Code.

13
Why 1’s and 2’s
Complement
Needed??
 Today’s
Highlights

1’s Complement
2’s Complement

Binary Addition

Binary Subtraction
Why 1's and 2's Complement are Needed

Simplification of
Arithmetic Operations
Representation of
Negative Numbers
Elimination of Borrow
in Subtraction
Consistency in
Arithmetic Operations
Ease of
Implementation in
Hardware
1’s Complement
• It is a binary number system in which each bit of a binary number
is inverted (flipped), meaning 0 becomes 1 and 1 becomes 0.

• Ex: Binary number: (1010) 2

• 1's complement: ( 0101 ) 2

Q1. Represent 34 in 1’s complement form

Q2. Find 1's complement of (10110)2

 QUICK QUIZ (POLL)
Q. What is the 1's complement of the binary number 1011001?

A. 0100110
B. 1100110
C. 1010110
D. 0110100
2’s Complement
Represent 34 and 5 as 2’s Complement
 QUICK QUIZ (POLL)
Q. What is the 2's complement of the binary number 1100101?

A. 0011011
B. 1100110
C. 0011010
D. 0011011
 Binary Addition
Q. Add the binary number (1001 1000)2 and (00110110)2
Q. Add the numbers using binary addition (36)10 and (24)10.
Q. Add the number using binary addition (-28)10 and (-14)10.
QUICK QUIZ (POLL)
Q1. What is the result of adding 1011 and 1101 in binary?
A. 10100
B. 10010
C. 11000
D. 11110
QUICK QUIZ (POLL)
Q2. In binary addition, what is 1 + 1 + 1?

A. 10
B. 11
C. 01
D. 111
Binary Subtraction
Subtract (1010)2 from (1111)2 using 2’s complement method

• Step-1: 2’s complement of (1010)2 is (0110)2.

• Step-2: Add (0110)2 to (1111)2.
Subtract 3 from 2
QUICK QUIZ (POLL)
Q. What is the 2's complement of the binary number 01101?

A. 10010
B. 11010
C. 10101
D. 10011
QUICK QUIZ (POLL)
Q. Solve 1101 - 1010 using 2's complement. What is the final result?

A. 0011
B. 0110
C. 0101
D. 1111
QUICK QUIZ (POLL)
Q. Subtract 0110 from 1010 using 2's complement. What is the
result?

A. 0100
B. 1000
C. 1100
D. 0010
 Home
assignments
Try Yourself
Share on lpu
live
Q1. Find the 2's complement of the binary number
(101110) 2

Q2. Add the binary numbers (1101) 2

and (1011) 2 using 2's complement.

Q3. Subtract (0111) 2 from (1010) 2 ​using 2's

complement.

19
 Limitation 1. Ambiguity in Zero
OF 1’s and Representation
2’s
Complement 2. Complexity in
Arithmetic Operations
3. Inefficient for Some
Operations
[Link] Hardware
Complexity
5. Difficulties with
Negative Numbers
6. Limited Range of
Representations
 LOGIC GATE,
BOOLEAN ALGEBRA
 Today’s
Highlights

Logic Gates (Truth Table)

Rules of Boolean Algebra
Simplification of Functions
Need for Logic gates
Signal Processing

Decision Making

Data Storage

Arithmetic & Computation

Simplified Circuit Design

3
 Logic Gates

Basic Gates Arithmetic

Gates
Universal
Gates
AND
XOR
OR
NAND
XNOR
NOT
NOR
 LLogic Gate
IC 7408 IC 7432 IC 7404
NAND and NOR gates are called Universal gates called universal

IC 7400 IC 7402
IC 7486 IC 747266
Poll

A. AND
B. OR
C. NOT
D. XOR
Poll

A. AND
B. OR
C. NOT
D. XOR
Poll

A. AND
B. OR
C. XOR
D. XNOR
 QUICK QUIZ (POLL QUESTION)
The output of an AND gate with three inputs, A, B, and C, is HIGH when ________.

A. A = 1, B = 1, C = 0
B. A = 0, B = 0, C = 0
C. A = 1, B = 1, C = 1
D. A = 1, B = 0, C = 1

11
 Also known as
Rules of Boolean Algebra switching
algebra

[Link] Rule Name OR law AND law

1 Null element A+1=1 A.0=0
2 Identity law A+0=A A.1=A
3 Idempotent Law A+A=A A.A=A
4 Complement Law A+A’=1 [controlling pin] A.A’=0 [controlling pin]
5 Commutative law A+B=B+A [order does not A.B=B.A [order does not matter]
matter]
6 Associative law A+(B+C)=(A+B)+C A.(B.C)=(A.B).C
7 Distributive law A+(B.C)=(A+B).(A+C) A.(B+C)=(A.B)+(A.C)

8 Absorption law A+AB=A A.(A+B)=A

 Rules of Boolean Algebra
9 Double Inversion law A’’=A
10 Redundant Literal Rule A+A’B=A+B or A’+AB=A’+B or
(RLR) A’+AB’=A’+B’ or A +A’B’=A+B’
11 Consensus Theorem AB+A’C+BC=AB+A’C

De Morgan’s First Law Implementation using Logic De Morgan’s Second Law Implementation using Logic
Gates Gates

NAND =
Bubbled OR
gate NOR=bubbled
AND
 Need for De Morgan’s Law

Simplification of
Inversion of Gate Designing with
Boolean
Logic Gates Optimization Negative Logic
Expressions

Conversion Fault Tolerance Easier Circuit

Universality in
Between NAND and Design and
Digital Systems
and NOR Redundancy Implementation
De’ Morgan Laws:

15
 QUICK QUIZ (POLL QUESTION)

Which of the following Boolean theorem is incorrect?

A. A + A = A
B. A + 1 = 1
C. A + 0 = A
D. A + A’ = 0

16
DUAL of the function
Simplification
 Quick Poll
Simplify the expression
A) Z=X’Y
B) Z =X+Y’
C) Z=XY
D) Z=X+Y
Logic Gate Implement with NAND-NOR
 NAND and NOR as Universal Gates

Home assignment XNOR using

NAND and XOR using NOR send
on LPU live

21
Combination of Gates
A AB

AB + AB

B AB
A B

( A  B ) + BC

BC
22
 AB Combination of Gates

AB + C ( AB + C ). D

C ( AB + C ). D

Exercise

Y = AB + AC
Draw circuit for

23
 Simplification using Boolean Algebra

Practice Question:

1. Simplify the following Boolean expression:

𝐴𝐵 + 𝐴 + 𝐴𝐵

24
 Simplification using Boolean Algebra
Home Assignment

Practice Question: A) AB
B) A’B
C) AB+AC’
1. Simplify the following Boolean expression:
D) A’B+AC’

𝐴 𝐵 + 𝐶 𝐴𝐵 + 𝐴𝐶

25
Advantages of Boolean Algebra
[1]

To obtain simpler expression

[2]
To reduce the number of gates in the
circuit

[3]
To reduce the number of inputs in the
circuit

[4]

To reduce complexity

[5]

To reduce cost.
 QUICK QUIZ (POLL QUESTION)
Minimum number of two input NAND gates required to implement XOR function is:

A. 3
B. 4
C. 5
D. 6

27
 1. Lack of Representation for Negative
Limitation Values
OF Boolean 2. Limited to Binary States
3. Complexity in Simplification
Algebra and
4. Lack of Direct Representation for
Expressions Arithmetic Operations
5. Handling of Multiple Inputs and Outputs
6. No Support for Continuous Data

How to Overcome
Said problem
 Today’s
Highlights

SOP
POS
Boolean expression

Sum-of-Products (SOP)
• variables are operated by AND (product) are OR(sum) together

Product-of-sums (POS)
• variables are operated by OR (sum) are AND (product) together
Sum-of-Products (SOP) :

If the number of input variables are n, then the total number of

combinations in Boolean algebra is 2n.
• If the input variable (let A) value is :
• Zero (0) – A is LOW -It should be represented as A’ (Complement of
A)
• One (1) – A is HIGH -It should be represented as A
Min Term –Max Term
Construct SOP from a function X (SOP) = Σ m(1, 3, 6)
 QUICK QUIZ (POLL)
Q. Which of the following represents POLL
Which of the following correctly
the standard SOP (Sum of Products) describes the relationship between
form for the Boolean function SOP and POS for a Boolean
function?
F(A,B,C) where the truth table values A. SOP represents the OR of
for F are 1 at rows 1, 4, and 7? products, and POS represents the
AND of sums.
B. SOP represents the AND of sums,
and POS represents the OR of
A. A′B′C+AB′C’+ABC products.
C. Both SOP and POS represent the
B. A′B′C+ABC’+AB’C same type of expressions.
D. SOP uses only AND operations,
C. A′B′C′+ABC’+A’BC and POS uses only OR operations.

D. A′BC+AB′C’
6
 QUICK QUIZ (POLL)
Q. Which of the following represents POLL
The output of a Boolean function is 1 for
the SOP form for the Boolean the rows where A=0,B=0,C=1 and
expression derived from the min- A=1,B=1,C=0. What is the SOP form for
this Boolean function?
terms m1,m3,m5 for a 3-variable A. A’B’C+ABC’
function? B. A’BC+AB’C
C. AB’C+ABC’
A. A′B′C+A’BC+AB’C D. A’B’C+ABC

B. A′B′C+ABC’+A’BC
C. AB′C′+A’BC’
D. A′B’C+AB′C’

7
Conversion from Minimal SOP to Canonical SOP Form

Convert the following Boolean function into Canonical

Home assignment SOP form.
F = pq + qr + pr
 Product of Sums (POS) form
• POS is product of maxterms and is represented as:
If variable A is Low(0) - A
A is High(1) - A’
• Conversion from Minimal POS to Canonical form POS

• F = (A̅+B̅) (B+C)
• F = (A’+B’+CC’) (B+C+AA’)
• F = (A’+B’+C)(A’+B’+C’)(A+B+C)(A’+B+C)

Convert the following Boolean function into

Home assignment
Canonical POS form. f=(p+q)⋅(q+r)⋅(p+r)
 QUICK QUIZ (POLL) POLL

Q1. Which of the following is the POS (Product of Sums) form of the
Boolean expression A′B+AB′

A. (A+B)(A’+B’)
B. (A’+B)(A+B’)
C. (A+B)(A’+B)
D. (A’+B)(A+B)

12
 QUICK QUIZ (POLL)
[Link] the following truth table for a 3-variable Boolean function

Which of the following is the POS form for

the Boolean function?
 Home
assignments
Try Yourself
Share on lpu
live
Q1. Convert the following truth table into its
SOP (Sum of Products) form.

Q2. Convert the same truth table into its

POS (Product of Sums) form. 14
Why K-map
Needed??
 Today’s
Highlights

K-map
 Need for Karnaugh Map (K-map)
Simplifies Easy
Minimization of Eliminates
Boolean Identification of
Logic Circuits Human Errors
Expressions Prime Implicants

Avoids Applicable to Widely Used in

Visual
Redundant Both SOP and Digital Circuit
Representation
Terms POS Forms Design
 Karnaugh Map Method
▪ The map method presented here provides a simple,
straightforward rule based procedure for minimizing Boolean
functions(used to remove redundant operations in a Boolean
function).
▪ This method may be regarded as a pictorial form (two-
dimensional graphical representation ) of a truth table.
▪ The map method is also known as the Karnaugh map or K-map.
▪ It is named after Maurice Karnaugh, an American mathematician
and physicist, who developed K- Map at Harvard Computation
Laboratory
Karnaugh Map RULES
1. Construct K-map according to variables and place 1’s or 0’s in
the squares according to the truth table.
2. The number of 1’s or 0’s in a group must be a power of 2
3. Grouping is done horizontally, vertically but never diagonally.
4. The groups must be made as large as possible.(start from octet,
quard and then pair)
5. Groups can overlap and wrap around the sides of the K-map
 Karnaugh Map Method
▪ The map is made up of squares, with each square representing
one minterm of the function that is to be minimized.
▪ The simplified expressions produced by the map are always in one
of the two standard forms: sum of products or product of sums.
▪ This expression produces a circuit diagram with a minimum
number of gates and the minimum number of inputs to each gate.
 Follow Gray
Explanation code

2 variable ,3 variable,4 variable

K-map

▪The minterms are arranged, not in a binary sequence, but in a sequence similar to the Gray code.
▪The characteristic of this sequence is that only one bit changes in value from one adjacent column to the next.
4 variable K-map
 Prime Implicants
It is an implicant that (from • Redundant Prime
the point of view of the Implicants:RPI • Essential Prime
map) is not fully contained refer to the prime Implicants:
within any one other impli It implicants for Groups that
is an implicant that (from which every one of cover at least one
the point of view of the its minterms gets of the minterms
map) is not fully contained
covered by some that can’t get
important prime covered by
within any one other implicants another prime
implicant cant
 Poll Explanation
How many variable K-map required for given function?

A) 2 variable
B) 3 variable
C) 4 varaiable
D) none
Exercise
Simplify
 QUIZ (POLL)
An n variable K-map can have
Diagonal groups
____ no of minterms:
are not allowed
a) 𝑛2 Which of the following
combination of cells is
2
b) 𝑛 -1 NOT possible? a) True
b) False
c) 2𝑛
a) 4
𝑛
d) 2 -1 b) 8
c) 12
d) 16
Vertical K-map
X
 Quick Poll
After making group in form of pair,how many variables are
eliminate?
A) 3 variables
B) 2 variables
C) 1 variables
D) Not applicable
Example Two Variable Karnaugh Map
▪ There are four minterms for two variables; hence, the map consists of
four squares, one for each minterm. Which Octet,
Grouping Quard,
do you
think ?
Pair ?

How many
variable
eliminates
after pair ?
Q1. Solve 2 Variables K-Map for ∑(0, 2, 3)

Truth Table K-map

A B Y

0 0 1
1
0 1 0

1 0 1

1 1 1
1 1

Boolean Expression: Y = B + A
 Try Yourself
Q1. Reduce the function using K-map F(A,B) = Σ(0,2,3)?
Attempt Poll:
What does each cell in a
Karnaugh map represent?
A. A single minterm or
maxterm
B. A group of variables
C. A truth table output row
D. A simplified Boolean
expression

16
 Three Variable Karnaugh Map
Question: Simplify the Boolean function 𝒇(𝑨, 𝑩, 𝑪) = σ 𝟎, 𝟒, 𝟓 using K-
Map?
ഥ𝑪
𝑩 ഥ ഥ𝑪
𝑩 𝑩𝑪 ഥ
𝑩𝑪
ഥ
𝑨
𝑨
Question: Simplify the Boolean function 𝒇(𝑨, 𝑩, 𝑪) = σ 𝟎, 𝟐, 𝟒, 𝟓 using K-
Map?

ഥ𝑪ഥ ഥ𝑪 ഥ a) A’C’+AB’
𝑩 𝑩 𝑩𝑪 𝑩𝑪 b) AC’+AB
ഥ
𝑨 1 1 c) A’C’+AB

𝑨 1 1
Ques. Solve for F(A,B,C)= σ(𝟏, 𝟑, 𝟔, 𝟕) using K-map
A B C y

0 0 0 0

0 0 1 1

0 1 0 0

0 1 1 1

1 0 0 0

1 0 1 0

1 1 0 1

1 1 1 1

From red group we get product term— A’C

From green group we get product term— AB
Summing these product terms we get- Final expression (A’C+AB)
Question: Simplify the Boolean function 𝒇(𝑨, 𝑩, 𝑪) = σ 𝟏, 𝟐, 𝟒, 𝟕 using K-
Map?

ഥ𝑪
𝑩 ഥ ഥ𝑪
𝑩 𝑩𝑪 ഥ
𝑩𝑪
ഥ
𝑨
𝑨
Question: Simplify the Boolean function 𝒇(𝑨, 𝑩, 𝑪) = σ 𝟏, 𝟒, 𝟓, 𝟔, 𝟕 using
K-Map?

ഥ𝑪
𝑩 ഥ ഥ𝑪
𝑩 𝑩𝑪 ഥ
𝑩𝑪
ഥ
𝑨
𝑨
Exercise
Simplify
 Home
assignments
Try Yourself
Share on lpu
Q1. Reduce the function y(A,B,C) = Σ (0,1,3,6,7) live

Q2. Simplify the sop function F(A,B,C) = Σ (1,2,3,7)

23
Four Variable Karnaugh Map
Ques. Solve for F (A, B, C, D) = ∑(0, 2, 5, 7, 8, 10, 13, 15)

From the red group, the product term would be —BD

From the lilac group, the product term would be —B’D’
If we sum these product terms, then we will get this final expression (BD + B’D’)
Question: Simplify the Boolean function:
𝒇(𝒘, 𝒙, 𝒚, 𝒛) = σ 𝟎, 𝟏, 𝟐, 𝟒, 𝟓, 𝟔, 𝟖, 𝟗, 𝟏𝟐, 𝟏𝟑, 𝟏𝟒 into POS form?

ഥ𝒛ത
𝒚 ഥ𝒛
𝒚 𝒚𝒛 𝒚ത𝒛
ഥ𝒙
𝒘ഥ
ഥ
𝒘𝒙
𝒘𝒙
𝒘ഥ
𝒙
Question: Simplify the Boolean function:
𝒇(𝒘, 𝒙, 𝒚, 𝒛) = σ 𝟎, 𝟏, 𝟐, 𝟒, 𝟓, 𝟔, 𝟖, 𝟗, 𝟏𝟐, 𝟏𝟑, 𝟏𝟒 into POS form?

Prepared By: Pawandeep kaur

Question: Simplify the Boolean function:
𝒇(𝒘, 𝒙, 𝒚, 𝒛) = σ 𝟎, 𝟏, 𝟐, 𝟓, 𝟖, 𝟗, 𝟏𝟎 into: (1) SOP Form (2) POS form?

ഥ𝑫
𝑪 ഥ ഥ𝑫
𝑪 𝑪𝑫 ഥ
𝑪𝑫
ഥ𝑩
𝑨 ഥ
ഥ𝑩
𝑨
𝑨𝑩
ഥ
𝑨𝑩
Question: Simplify the Boolean function:
𝒇(𝒘, 𝒙, 𝒚, 𝒛) = σ 𝟎, 𝟏, 𝟐, 𝟓, 𝟖, 𝟗, 𝟏𝟎 into (1) SOP Form (2) POS form?

ഥ𝑫
𝑪 ഥ ഥ𝑫
𝑪 𝑪𝑫 ഥ
𝑪𝑫
ഥ𝑩
𝑨 ഥ
ഥ𝑩
𝑨
𝑨𝑩
ഥ
𝑨𝑩
 Don’t Care conditions
• In practice, in some applications the function is not specified for certain
combinations of the variables.
• As an example, the four-bit binary code for the decimal digits has six
combinations that are not used and consequently are considered to be
unspecified.
• In most applications, we simply don’t care what value is assumed by the
function for the unspecified minterms.
• For this reason, it is customary to call the unspecified minterms of a function
don’t-care conditions.
• These don’t-care conditions can be used on a map to provide further
simplification of the Boolean expression.
• Symbol of don’t care: X
Qsn: Implement the given function using K-Map:

ഥ𝑫
𝑪 ഥ ഥ𝑫
𝑪 𝑪𝑫 ഥ
𝑪𝑫
ഥ𝑩
𝑨 ഥ
ഥ𝑩
𝑨
𝑨𝑩
ഥ
𝑨𝑩
 NAND and NOR Implementation
• Digital circuits are frequently constructed with NAND or NOR gates
rather than with AND and OR gates. NAND and NOR gates are easier to
fabricate with electronic components and are the basic gates used in all
IC digital logic families.
• They are a universal gates because any logic circuit can be implemented
with them.
NAND Implementation
NOR Implementation
 NAND and NOR Implementation

Question: Implement the Boolean function 𝒇(𝑨, 𝑩, 𝑪) = σ 𝟏, 𝟐, 𝟑, 𝟒, 𝟓, 𝟕 using

(a) NAND gates only.
(b) NOR gates only
(c) SOP form.
(d) POS form.

ഥ𝑪
𝑩 ഥ ഥ𝑪
𝑩 𝑩𝑪 ഥ
𝑩𝑪
ഥ
𝑨
𝑨
Ex-3: Minimize the following function in SOP minimal form using K-Maps: f = m(1, 5, 6, 11, 12, 13, 14) + d(4) and
implement using Universal gate like NAND gate.

Therefore, SOP minimal is,

f = BC' + BD' + A'C'D + AB'CD
 Try Yourself
Q. F(A,B,C,D) = ∑( m0, m1, m2, m4, m5, m6, m8, m9,
m12, m13, m14 ) In a 4-variable K-map, which of
the following represents an
overlap in grouping?
A. Two separate groups of 2 cells
B. One group of 8 cells and one
group of 4 cells
C. Groups of 1 cell each
D. Overlapping groups are not
allowed

37
Ex-4: Minimize the following function in SOP minimal form using K-Maps: F(A, B, C, D) = m(1, 2, 6, 7, 8, 13,
14, 15) + d(0, 3, 5, 12) and implement using NAND gate

The SOP K-map for the given expression is: f = AC'D' + A'D + A'C + AB
Ex-5: Simplify the boolean function Y(A, B, C, D) = Π M (2, 3, 8, 9, 11, 13, 15) and implement using universal
NOR gate

The simplified output expression is Y = (A’+B+C) (A’+D’) (A+B+C’)

Simplify the boolean function Y(A, B, C, D) = Π M (2, 3, 8, 9, 11, 13, 15) and implement using universal NOR
gate
 Home
assignments
Try Yourself
Share on lpu
Q1. Simplify the following Boolean expression using live

the 4-variable K-map :

F⟮A,B,C,D⟯=∑m⟮2,3,6,7,8,10,13,15⟯ and Implement
the reduce expression using NAND gate

Q2. Reduce the following Boolean function using

4-variable K-map
f⟮A,B,C,D⟯=∑m⟮0,1,2,5,8,10,11,13,14,15⟯ +d(3,7)

41