Unit-1

Digital Logic Circuits & Boolean Laws

Contents
• Introduction
• Digital logic
• Types of Gates
• AND Gate
• OR Gate
• NOT Gate
• NAND Gate
• NOR Gate
• Exclusive OR Gate(X-OR)
• X-NOR Gate
• Universal Gates
• NAND gate implementation
• NOR gate implementation
• Boolean Laws
SHIVANJALI KESHARWANI
 Introduction
◉ The basic digital electronic circuit that has one or more inputs and single
output is known as Logic gate.
◉ Digital electronic circuits operate with voltages of two logic levels namely
Logic Low and Logic High.
◉ The range of voltages corresponding to Logic Low is represented with ‘0’.
◉ Similarly, the range of voltages corresponding to Logic High is represented
with ‘1’.
 Digital Logic
◉ Digital Logic Gates can be made from discrete components such
as Resistors, Transistors and Diodes to form RTL (resistor-transistor logic)
or DTL (diode-transistor logic) circuits.
◉ Depending in the input value, the logic gate will be either output value of
‘1’ for on and ‘0’ for off.
◉ we can implement these Boolean functions by using basic gates. The
basic gates are AND, OR & NOT gates.
◉ A truth table is a mathematical table used in logic—specifically in
connection with Boolean algebra, Boolean functions, and propositional
calculus
Types of Gates
There are 6 gates
1. AND Gate
2. OR Gate
3. NOT Gate
4. NAND Gate
5. NOR Gate
6. Exclusive OR Gate(X-OR)
7. X-NOR Gate
 AND Gate
◉ The AND gate produces the AND logic function: that is, the output is
1 if input A and input B are both equal to 1; otherwise, the output is
0.
◉ An AND gate is a digital circuit that has two or more inputs and
produces an output, which is the logical AND of all those inputs. It is
optional to represent the Logical AND with the symbol ‘.’.
A B Y = A.B
0 0 0
0 1 0
1 0 0
1 1 1
 OR Gate
◉ An OR gate is a digital circuit that has two or more inputs and
produces an output, which is the logical OR of all those inputs.
◉ This logical OR is represented with the symbol ‘+’.
◉ Here A, B are the inputs and Y is the output of two input OR gate. If
both inputs are ‘0’, then only the output, Y is ‘0’. For remaining
combinations of inputs, the output, Y is ‘1’.
A B Y=A+B
0 0 0
0 1 1
1 0 1
1 1 1
 NOT Gate
◉ A NOT gate is a digital circuit that has single input and single output. The output of NOT gate
is the logical inversion of input.
◉ Hence, the NOT gate is also called as inverter.
◉ Here A and Y are the input and output of NOT gate respectively. If the input, A is ‘0’, then the
output, Y is ‘1’.
◉ Similarly, if the input, A is ‘1’, then the output, Y is ‘0’.

A Y = A’
0 1
1 0
 NAND Gate
◉ The NAND function is the complement of the AND function
◉ The designation NAND is derived from the abbreviation of NOT-AND

A B Y = (A.B)’
0 0 1
0 1 1
1 0 1
Key-rule -> “If both inputs are 1 ,the output is 0 ,rest is 1 ”
1 1 0
 NOR gate
◉ NOR gate is a digital circuit that has two or more inputs and produces an output,
which is the inversion of logical OR of all those inputs.
◉ Here A, B are the inputs and Y is the output. If both inputs are ‘0’, then the output, Y
is ‘1’.
◉ If at least one of the input is ‘1’, then the output, Y is ‘0’. This is just opposite to that
of two input OR gate operation.
A B Y = (A+B)’
0 0 1
0 1 0
1 0 0
1 1 0
 Exclusive OR Gate
◉ The exclusive-OR gate has a graphic symbol similar to the OR gate
except for the additional curved line on the input side.
 Exclusive NOR Gate

◉ The exclusive-NOR is the complement of the exclusive-OR, as indicated by

the small circle in the graphic symbol.
◉ The output of this gate is 1 only if both inputs are equal to 1 or both
inputs are equal to 0.

x=(A’B+AB’)’
 Universal Gates
◉ A universal gate is a gate which can implement any Boolean function
without need to use any other gate type.
◉ The NAND and NOR gates are universal gates.
◉ In fact, an AND gate is typically implemented as a NAND gate followed
by an inverter not the other way around!!
◉ Likewise, an OR gate is typically implemented as a NOR gate followed
by an inverter not the other way around!!
1. NAND Gate is a Universal Gate
◉ To prove that any Boolean function can be implemented using only
NAND gates, we will show that the AND, OR, and NOT operations can
be performed using only these gates.
◉ Implementing an Inverter Using only NAND Gate
◉ Implementing AND Using only NAND Gates
◉ Implementing OR Using only NAND Gates
 i) NAND as NOT
◉ A NOT gate is made by joining the inputs of a NAND gate together.
◉ Since a NAND gate is equivalent to an AND gate followed by a NOT
gate, joining the inputs of a NAND gate leaves only the NOT gate.

FOR SAME INPUTS,INVERTS THE VALUE

“If both inputs are 0,the output is 1,

if both inputs are 1 ,output is 0” (A.A)’=A’
ii) NAND Gate as AND Gate
The AND gate can be implemented by using two NAND gates in the below
fashion:
iii) NAND Gate as OR Gate
◉ If the truth table for a NAND gate is examined, it can be seen that if any
of the inputs are 0, then the output will be 1.
◉ To be an OR gate, however,
the output must be 1 if any input is 1.
◉ Therefore, if the inputs are inverted,
any high input will trigger a high output.
Steps to construct OR gate using NAND gate using
Boolean law
Given NAND gate Boolean expression ; C=(A.B)’,we need to derive OR
gate Boolean expression ; C= (A+B)
Step 1: Start with C=A+B
=> C= ((A+B)’)’ { Since, (A’)’=A}
=> C= (A’.B’)’ { De-Morgan’s law ; (A+B)’=A’.B’}
This is similar to NAND expression and can be achieved using NAND
gates

Hence , if we design the logical expression C= (A’.B’)’ ,it will be equivalent to

C=(A+B)
Steps to construct OR gate using NAND gate
using Boolean law
A A’ B B’ A’.B’ (A’.B’)’
0 1 0 1 1 0
Step 2: Designing the expression C= (A’.B’)’ : 1 0 1 0 0 1
1 0 0 1 0 1
A’
0 1 1 0 0 1
C= (A’.B’)’ Or C= ((A+B)’)’
B’ Which is similar to
A B Y=A+B
B Or C = (A+B)
0 0 0

0 1 1
Lets check it with a truth table
1 0 1

1 1 1
iv) NAND as NOR Gate
◉ A NOR gate is an OR gate with an inverted output. Output is high when
neither input A nor input B is high.
◉ Hence, this is easily constructed by
adding a NAND inverter to the
previously discussed circuit of OR
gate using NAND gate
v) NAND as XOR Gate
◉ Given NAND gate Boolean expression ; C=(A.B)’,we need to derive OR
gate Boolean expression ; C= A+B
To get :

x=(A’B+AB’)

Step 1: We have to implement A’B+AB’ .Lets draw this using simple logic gates
construction :
A’
B A’B+AB’

A
B’
 vi ) NAND as XOR Gate
◉ Step 2: Use bubbles to invert the values on the basis of following
concept
◉ (If A is input,we get A only as output )
A’

A’ (A’)’=A A’+B’ OR

B’ (A.B)’
B (De-morgan’s
◉ Similarly in the previous diagram law)
A’
B A’B+AB’

A
Both are NAND gates B’’
This is also NAND
gate…?
vi) NAND as XOR Gate
◉ Step 3 : Now convert A’ & B’ inputs to NAND inverter gates
Hence, This construction uses five gates instead
of four.

[ (A NAND A ) NAND B ] NAND [(B NAND B) NAND A]

vii) NAND Gate as X-NOR gate
◉ NAND gate is an inverted-input OR gate.
◉ Here, just add a NAND inverter ,rest the circuit remains the same

[ (A NAND A ) NAND B ] NAND [(B NAND B) NAND A]’

2. NOR as a universal gate

◉ NOR gate also can be utilised to generate other gates.

Hence ,it is also called as Universal gate.

A B Y = (A+B)’
0 0 1
0 1 0
1 0 0
1 1 0
i)NOR Gate as an Inverter Gate
X + X = X (Before Bubble)

X Z=X

(X+X)' = X‘ Idempotent

SHIVANJALI KESHARWANI
ii)NOR Gate as an OR Gate
X+Y
X
Z= X+Y= X+Y
Y

NOR Gate “Inverter”

SHIVANJALI KESHARWANI
iii)NOR Gate as an AND Gate
X

X Y
Z=X+Y=XY=XY
Y

“Inverters” NOR Gate

SHIVANJALI KESHARWANI
NOR Gate Equivalent of AOI Gates
AND OR INVERTER

SHIVANJALI KESHARWANI
iv)NAND Gate using NOR Gate
Add NOR inverter to the previous AND gate constructed from NOR gate

SHIVANJALI KESHARWANI
 v) X-OR Gate using NOR Gate
C = A’B + AB’ from C= (A+B)’
We need to get
Let us take C =A’B+AB’

We can write it as C= A’B+AB’ + AA’+BB’ (Since , AA’ =0)

 C= B’(A+B) + A’ (A+B)
C = (A+B).(A’+B’)
C= [ [(A+B).(A’+B’)]’]’ (Since (A’)’=A)
C= [ (A+B)’ + (A’+B’)’ ]’ (De morgan’s law ; (A.B)’ = A’+B’ )

In the above expression , the terms (A+B)’ and (A’+B’)’ are NOR forms which are
again connected by a NOR.
Hence the above expression gives us the idea for connecting the NOR gates and
getting XOR gate
SHIVANJALI KESHARWANI
v) X-OR Gate using NOR Gate

(A+B)’
((A+B)’ + (A’+B’)’ )’
OR
A’B+AB’

(A’+B’)’

SHIVANJALI KESHARWANI
vi) X-NOR Gate using NOR Gate

(A’B+AB’)’

SHIVANJALI KESHARWANI
 Summary of universal gates
Gate NAND gate NOR Gate
NOT Join the inputs A and B Join the inputs A and B

AND Connect a NAND with NAND inverter Use De-morgan’s law -> Two NOR inverter
connected with a NOR
OR Use De-morgan’s law -> Two NAND inverters connected Connect NOR with NOR inverter
with a NAND

NOR Connect the above OR with a NAND inverter -

NAND - Connect AND circuit with a NOR inverter
X-OR 5-NAND gates, (start with logical expression for X-OR 5-NOR Gates ( one NOR with A,B inputs
gate and consequently add bubbles and connect the ,other with A’,B’ inputs connected with
NAND inverters ) another NOR gate )
X-NOR Connect the above with a NAND inverterSHIVANJALI KESHARWANI Connect the above with a NOR inverter
 Boolean Algebra
◉ Boolean Algebra is used to analyse and simplify the digital (logic) circuits.
◉ It uses only the binary numbers i.e. 0 and 1. It is also called as Binary
Algebra or logical Algebra.
◉ Boolean algebra was invented by George Boole in 1854.
◉ There is no negative and fractional numbers
◉ Boolean algebra uses Boolean Variables and Boolean operators.
◉ There are 3 Basic operators AND,OR,NOT.
◉ A Boolean Expression is combination of Boolean Variables and Boolean
Operators.
◉ A Boolean Function has one or more input variables and Produces the result
based on the input.
Truth Table:
◉ Boolean function can be uniquely and completely described by truth table.
◉ A truth table lists all possible values of input combinations of the function and
produces the output for all combinations.
Rule in Boolean Algebra:
◉ Variable used can have only two values. Binary 1 for HIGH and Binary 0 for LOW.
◉ Complement of a variable is represented by an over bar (-) or ‘ . Thus, complement of
variable B is represented as . Thus if B = 0 then B’ = 1 and B = 1 then B’= 0.
◉ OR ing of the variables is represented by a plus (+) sign between them. For example OR
ing of A, B, C is represented as A + B + C.
◉ Logical AND ing of the two or more variable is represented by writing a dot between
them such as A.B.C. Sometime the dot may be omitted like ABC.
 Boolean Laws
◉ There are six types of Boolean Laws.
1. Commutative law
2. Associative law
3. Distributive law
4. AND law
5. OR Law
6. INVERSION law
7. IDEMPOTENCE law
8. Absorption law
◉ Commutative law:
Any binary operation which satisfies the following expression is
referred to as commutative operation.

Commutative law states that changing the sequence of the variables

does not have any effect on the output of a logic circuit.
◉ Associative law:
This law states that the order in which the logic operations are
performed is irrelevant as their effect is the same.
◉ Distributive law:
Distributive law states the following condition.

◉ AND law:
These laws use the AND operation. Therefore they are called as AND laws.

◉ OR law :
These laws use the OR operation. Therefore they are called as OR laws.
◉ INVERSION law:
This law uses the NOT operation. The inversion law states that double inversion of a
variable results in the original variable itself.

◉ Idempotence Laws :
i)A · A = A ii) A + A = A
◉ Absorption Laws :
i) A + A · B = A ii)A(A + B) = A
Duality Principle:
◉ According to the duality principle, if we have theorems of Boolean Algebra
for any one type of operation then the operation can be converted into
another type of operation.
◉ In other words AND can be converted to OR and OR can be converted into
AND
◉ We can interchange '0 with 1', '1 with 0', '(+) sign with (.) sign' and '(.) sign
with (+) sign' to perform dual operation.
◉ For Eg.
 De Morgan's Theorem
◉ This theorem explains that the complements of the products of all the
terms are equal to the sums of the complements of each and every term
◉ Likewise, the complements of the sums of all the terms are equal to the
products of the complements of each and every term.
◉ There are 2 theorems in DeMorgan’s
1. Theorem 1:

2. Theorem 2:
◉ Theorem 1: This theorem explains that the complements of the products
of all the terms are equal to the sums of the complements of each and
every term

◉ The LHS (left-hand side) of this theorem represents the NAND gate that has inputs A and B. On the
other hand, the RHS (right-hand side) of this theorem represents the OR gate that has inverted
inputs.
◉ The OR gate here is known as a Bubbled OR.
◉ Theorem 2: The complements of the sums of all the terms are equal to the
products of the complements of each and every term.

◉ The left-hand side of this theorem represents the NOR gate that has inputs
A and B. On the other hand, the right-hand side represents the AND gate
that has inverted inputs.
◉ The AND gate here is known as a Bubbled AND.
Digital Circuit
◉ Digital computers contain circuits that implement Boolean
functions.
◉ The simpler that we can make a Boolean function ,the
smaller the circuit that will result .
◉ Simpler circuits are cheaper to build ,consume less power
and run faster that complex circuits
◉ With this in mind, we always want to reduce our Boolean
functions to their simplest form
◉ The Boolean identities help us to do this
Example
Simplify the Boolean function :
1. A.B + A.B’
2. A+A’.B
3. (A+B).(A+B’)+(B.B’)
4. A.(B+C)+A’.(B+C)
5. A+B.A’+C.C’
 Question 4: Simplify A . (B + C) + A’ . (B + C)
Question 1: Simplify A . B + A . B’.
Solution:
Solution:
A . (B + C) + A’ . (B + C) = (A + A’) . (B + C)
A . B + A . B’ = A . (B + B’)
= 1 . (B + C)
= A . (1)
=B+C
=A

Question 2: Simplify A + A’ . B. Question 5: Simplify A + B . A’ + C . C’

Solution: Solution:
A + A’ . B = (A + A’) . (A + B) A + B . A’ + C . C’ = A + 0 + 0
= (1) . (A + B) =A
=A+B

Question 3: Simplify (A + B) . (A + B’) + (B . B’).

Solution:
(A + B) . (A + B’) + (B . B’) = (A + B) . (A + B’) + (0)
= A + (B . B’)
= A + (0)
=A
1. Simplify A + A . B.
2. Simplify (A . B) + (A . B’) + (B . B’).
3. Simplify A + B + A’ . B.
4. Simplify (A . B) + (A . B’) + (A’ . B).
5. Simplify A + B + A . B.
6. Simplify (A + B) . (A’ + B’).
7. Simplify A . (B + C) + A’ . (B + C).
8. Simplify A + B . A’ + C . C’.
9. Simplify A . B’ + A’ . B + B . C.
10. Simplify A . (B + B’).
 Standard Form of Boolean Expressions
◉ All Boolean expressions regardless of their forms can be converted in to
2 standard forms
1. SOP Sum of product
2. POS Product of Sum
Here ,

◉ Sum means OR operation ,for eg: A+B,A’+B,A+B’,A’+B’

Sum results in value 1 ,if any of the values of the variables is 1 and it results in value 0 ,if any of the values of the
variables is 0

◉ Product means AND operation, for eg : A.B,A’.B,A.B’,A’.B’

Product results in value 0 ,if any of the values of the variables is 0 and it results in value 1 ,if both the values of the
variables are 1 .
1. Sum of Products
◉ The SOP or Sum of Products form is a form of expressing a logical or Boolean expression.
In SOP, different product terms of input variables are logically ORed together. Therefore, in the
case of SOP form, we first logically AND the input variables, and then all these product terms
are summed together with the help of logical OR operation.
Standard Sum of Products
◉ These Boolean product terms are called as Max Terms or Standard Sum Terms.
◉ The Standard Sum of Products (SSOP) form is a form of expressing a logical expression in
which the logical expression is represented as the sum of a number of product terms where
each product term will contain all the variables of the logical expression either in
complemented or un-complemented form.
For example,

This is a logical expression in three variables, but it is expressed in SOP form. We can convert this
expression into SSOP form using Boolean algebra as follows.
Standard Sum of Products

This is the Standard Sum of Products form of the given logical expression. We can notice that in
the SSOP form, each product term contains all the variables of the logic function either in
complemented or un-complemented form
2. Product of Sums
These Boolean product terms are called as Min Terms or Standard Product Terms.
The POS or Product of Sum form is another form used to represent a logical
expression. In POS form, different sum terms of input variables are logically ANDed
together. Hence, if we want to express a logical expression in POS form, for that we first
logically OR all the input variables and then these sum terms are ANDed using AND
operation.
 Standard Product of Sums
◉ The Standard Products of Sum (SPOS) form is a form of expressing a logical expression
in which the logical expression is represented as the product of a number of sum terms where
each sum term will contain all the variables of the logical expression either in complemented
or un-complemented form.

For example,
◉ This is a logical expression in three variables, but it is expressed in POS form. We can
convert this expression into SPOS form using Boolean algebra as follows

This is the Standard Product of Sum form of the given logical expression. We can notice that in the SPOS form, each sum
term contains all the variables of the logic function either in complemented or un-complemented form
 Min Term
◉ Min term means the term that is true for a minimum number of combination of inputs. That is
true for only one combination of inputs.
◉ Since AND gate also gives True only when all of its inputs are true so we can say min terms are
AND of input combinations like in the table given below.
◉ Canonical SOP Form: This is the standard form of Sum of Product.
◉ Canonical SOP expression is represented by summation sign ∑ and min
terms in the braces for which For this function the canonical SOP
expression is
● F = ∑( m1, m2, m3, m5 )
● Which means that the function is true for the min terms {1, 2, 3, 5} the
output is true.
● By expanding the summation we get.
● F = m1 + m 2 + m 3 + m 5
● Now putting min terms in the expression
● F = A̅B̅C + A̅BC̅ + A̅BC + AB̅C
● Canonical form contains all inputs either complemented or non-
complemented in its product terms.
◉ Non-Canonical SOP Form: As the name suggests, this form is the non-
standardized form of SOP expressions. The product terms are not the
min terms but they are simplified.
◉ Minimal SOP Form: Minimal SOP form can be made using Boolean
algebraic theorems but it is very easily made using Karnaugh map (K-
map).
Minimal SOP form is preferred because it uses the minimum number of
gates and input lines. it is commercially beneficial because of its compact
size, fast speed, and low fabrication cost.
 Product of Sums
◉ When two or more sum terms are multiplied the resultant expression if
product of sums.
◉ Canonical form of Boolean Expression
◉ A Min term is product of N distinct literals where each literal occurs
exactly once
◉ A Max term is sum of N distinct literals where each literal occurs exactly
once
◉ A Boolean function can be expressed as sum of min terms(SOP)
◉ A Boolean function can be expressed as product of max terms(POS)
 K-map
K-Map or Karnaugh Map is a graphical method of simplifying
Boolean expression.
A K-Map composed of an arrangement of adjacent squares or cells,
where each cell represent a particular combination of variables in sum
or product form.

SHIVANJALI KESHARWANI
Karnaugh Map

SHIVANJALI KESHARWANI
 K-map
Steps to Solve Expression using K-map
1.Select the K-map according to the number of variables. For 2-variable- kmap of 4 square
grid,3-variables –kmap of 8 square grid and 4-variables ,k-map of 16 square grid

2.Identify minterms or maxterms as given in the problem.

3.For SOP put 1’s in blocks of K-map respective to the minterms (0’s elsewhere).

4.For POS put 0’s in blocks of K-map respective to the max terms (1’s elsewhere).

5.Make rectangular groups containing total terms in power of two like 2,4,8 ..(except 1) and
try to cover as many elements as you can in one group.

6.From the groups made in step 5 find the product terms and sum them up for SOP form.

SHIVANJALI KESHARWANI
K-map –Rules to simplify the Boolean
expression
• Adjacent 1’s represent minterms (or 0s -> maxterms) that differ by
only one variables are grouped in form of i) Pairs ii) quads iii) octets
• The preference of grouping is as follows : Octet>Quads>Pairs
• These groups can be adjacent or from four corners of the k-map ,but
they should be in straight lines horizontal or vertical.
• After grouping ,find the common variables and eliminate the others
• Rolling of k-map is also considered for grouping if four corners are
Available.

SHIVANJALI KESHARWANI
 ▪The 3-variable karnaugh map is an array of eight cells.
▪In this case A, B and C are used for the variables although
K-map of 3 variables other letters could be used.
▪Binary values of A is along the left side and the value of B and
C is across the top

Grouping the terms

Grouping we get A’C + AB as the minimum SOP expression

SHIVANJALI KESHARWANI
 3-Variable K-map

AB\C 0 1
A\BC 00 01 11 10

00 0 1 0 0 1 3 2

1 4 5 7 6
01 2 3

11 6 7

10 4 5

SHIVANJALI KESHARWANI
Three-Variable K-Maps
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

SHIVANJALI KESHARWANI
K-map of 4- variables

SHIVANJALI KESHARWANI
 The 4-variable Karnaugh Map
◼ The 4-variable karnaugh map is an array of sixteen cells

◼ Binary values of A and B are along the left side and the
values of C and D are across the top.

◼ The value of a given cell is the binary value of A and B at the

left in the same row combined with the binary values of C and
D at the top of the same column.

SHIVANJALI KESHARWANI
4-Variable K-map

AB\CD 00 01 11 10

00 0 1 3 2

01 4 5 7 6

11 12 13 15 14

10 8 9 11 10

SHIVANJALI KESHARWANI
Determining the Minimum SOP Expression from the Map

CD
00 01 11 10 B + A C + AC D
AB
00 1 1 AC
01 1 1 1 1 B
11 1 1 1 1
AC D
10 1

SHIVANJALI KESHARWANI
Mapping Directly from a Truth Table
I/P O/P
A B C X C
0 1
0 0 0 1 AB
0 0 1 0
00 1
0 1 0 0
0 1 1 0 01
1 0 0 1
1 0 1 0 11 1
1
1 1 0 1
10 1
1 1 1 1
SHIVANJALI KESHARWANI
Don’t care condition
• Sometimes, in a Boolean expression for certain input combinations,
the value of the output is not specified either due to invalid input
combinations or due to the precise value of output is of no importance.
• These input combinations for which the values of the Boolean function
are not specified are called don’t care combinations.
• Don’t care combinations are also referred to as optional
combinations.
• In K-map, don’t care combinations are represented by "X" or "d" or
"ϕ".

SHIVANJALI KESHARWANI
Don’t care condition
• For example, in 8421 binary code, the binary combination 1010, 1011,
1100, 1101, 1110, and 1111 are the invalid terms and their corresponding
outputs are don’t care combinations.
• Similarly, in Excess-3 code, the combinations 0000, 0001, 0010, 1101,
1110, and 1111 do not occur, hence these are called don’t care combinations.
• When we deal with SOP (Sum of Products) K-map, each don’t care term is
treated as a 1, if it helps in reduction of the expression, otherwise it is
considered as a 0 and left alone.
• On the other hand, when we are using POS (Product of Sums) K-map, each
don’t care term is considered as a 0, if it is helpful in reduction of the
expression, otherwise it is treated as a 1 and left alone.

SHIVANJALI KESHARWANI
 Don’t care condition
Example
Minimize the following 4-variable Boolean expression in SOP form using K-map.
f⟮A,B,C,D⟯=∑m⟮0,1,4,5,6,10,11,13⟯+d⟮2,3⟯
The reduction of the expression is done as per the following
steps −
•The minterms m0, m1, m4 and m5 form a 4-square. Make
it and read it as ⟮A¯C¯⟯⟮A¯C¯⟯.
•The minterms m10 and m11 form a 4-sqaure with two don’t
care terms m2 and m3. Make it and read it as B¯CB¯C.
•The minterms m0, m4, m6 and the don’t care term
m2 together form a 4-square. Make it and read it
as A¯D¯A¯D¯.
•The minterms m5 and m13 form a 2-square. Make it and
read it as BC¯DBC¯D.
•Finally, write all the product terms in SOP form.
Therefore, the minimal Boolean expression is,
f⟮A,B,C,D⟯=A¯C¯+B¯C+A¯D¯+BC¯D

SHIVANJALI KESHARWANI