5/24/2024

Combinational Logic Circuits

Switching Circuit or Digital Circuit

The circuit, which is used to produce output as a combination of its inputs
such that the truth table conditions are satisfied, is called switching circuit
or logic circuit or digital circuit. Basically, switching circuits or logic circuits
or digital circuits are divided into two broad categories:
1. Combinational Logic Circuits, and
Combinational Logic Circuits 2. Sequential Logic Circuits.
Combinational Logic Circuits
Circuits in which the outputs at any instant of time is dependent upon its
inputs present at that instant of time are called combinational logic circuits.
This means that the outputs of combinational logic circuits are function of
present values of inputs only. Thus, there is no memory in these circuits.
Let X be the set of all input variables {x0, x1,….,xn), and Y be the set of all
output variables {y0, y1…...,yn}. The combinational logic function, F, operates
on the input variable set, X to produce the output variable set, Y. The output
is related to the input as
𝒀 = 𝑭(𝑿) ⋯ ⋯ ⋯ ⋯ (𝟒. 𝟏)

Combinational Logic Circuits Combinational Logic Circuits

Combinational logic circuits can be modeled as illustrated in Fig. 4.1. The

Problem Truth Table Switching
x0 . Combinational . y0 Statement Construction Equations Written
Inputs . Logic Functions . Outputs
xn . (F) . yn

Fig. 4.1 Combinational logic model

Logic Circuit Logic Diagram Equation(s)
Built Drawn Simplified
relationship between the input and the output variables can be expressed
in logic equations, logic diagrams, or truth table.
Proper statement of a problem is the most important part of any digital
Fig. 4.2 General logic design sequence
design task. Once correctly and clearly stated or defined, any problem
can be converted to the necessary logic for implementation. Figure 4.2
Example 4.1 Establish a combinational logic truth table so that an output is
illustrates the sequence of design tasks in a general way. Notice that the
generated indicating when a majority inputs is true.
first task is to define the problem to be solved. Nothing can occur until
that is correctly accomplished. Solution: Determine input and output variables and assign names.

1
 5/24/2024

Combinational Logic Circuits Combinational Logic Circuits

Example 4.2 A NASA system consists of three computers, two of which

I1 I2 I3 I4 O1
Solution: The combinational logic circuit has are on-line (connected to the system) at any given time. The system uses
four inputs and a single output. Let I1, I2, I3, and 0 0 0 0 0 three computers to ensure safety in spacecraft operation through
I4 represent the input variables, and O1 be the 0 0 0 1 0 redundancy. If one computer experiences a problem it is taken off-line and
output variable. 0 0 1 0 0
another computer is brought on-line. Self-checking diagnostics determine
0 0 1 1 0
A majority occurs any time three or more of the each computer’s operating status and generate an output in the event
0 1 0 0 0
input variables are true. failure. When one computer fails it must be switched off-line. No more
0 1 0 1 0
than two computers are to be on-line at any given time. Design the control
For four input variables, the input combinations 0 1 1 0 0
0 1 1 1 1
logic to connect or disconnect the computers. In the event that two
will be 24 = 16. Table 4.1 shows the truth table of
1 0 0 0 0 computers are unavailable, generate a warning and allow the third
this example.
1 0 0 1 0 computer to come on-line. If all three computers are unavailable, generate
1 0 1 0 0 a second warning signal that invokes emergency procedures.
1 0 1 1 1 Solution: Determine input and output variables and assign names.
1 1 0 0 0
1 1 0 1 1 Let variables represent the operation status of three computers:
1 1 1 0 1 C1 is computer 1, C2 is computer 2, and C3 is computer 3. When Cx = 1, for
1 1 1 1 1 example, then that computer is failed. Let O1, O2, and O3 be the computer
disconnect control signal outputs. If Ox = 1, for example, then that comput-
Table 4.1 Truth table for example 4.1 er is connected. Let W1 and W2 be the two warning output signals. If Wx =
1, then the warning signal is activated.

Combinational Logic Circuits Combinational Logic Circuits

Now we have to construct a truth table that generates the proper output In summary, the process of converting a verbal problem statement into a
responses based on input variables. Because of three input variables, the truth table involves the following steps:
input combinations will be 23 = 8. Each connect/disconnect control signal  Determine the input variables and output variables that are involved.
is generated based on the values of the computer operation status signals  Assign mnemonic or letter or number symbols to each variable.
and the requirement for two computers to be available.  Determine the size of the truth table; how many input combinations exist:
For instance, if C1 = C2 = C3 = 0, then all C1 C2 C3 O1 O2 O3 W1 W2 𝟐𝒙 = 𝒚
three computers are operational; which Where x = number of input variables and y = number of combinations.
0 0 0 0 1 1 0 0  Construct a truth table containing all of the input variable combinations.
two are brought on-line is the designer’s
choice. In this example, computers 2 and 0 0 1 1 1 0 0 0  By careful reading of the problem statement determine the combinations
3 are connected. 0 1 0 1 0 1 0 0 of input variables that cause a given output to be true.
The 2nd case, when C1 = C2 = 0 and C3 = 1, 0 1 1 1 0 0 1 0 Sequential Logic Circuits
computer 3 has failed, so computers 1
1 0 0 0 1 1 0 0 Circuits in which the outputs at any instant of time is dependent upon its
and 2 are switched on-line. The truth
1 0 1 0 1 0 1 0 inputs present at that instant of time as well as on the past history of the
table 4.2 illustrates all of the output
system are called sequential logic circuits. This means that the outputs of
values for each input combination. 1 1 0 0 0 1 1 0 the sequential logic circuits are function of present as well as past value of
A separate equation must be written for 1 1 1 0 0 0 0 1 inputs. Therefore, these circuits are needed elements to store past
each output variable. information i.e. past value of inputs. These elements are known as memory.
Table 4.2 Truth table for example 4.1

2
 5/24/2024

Combinational Logic Circuits Combinational Logic Circuits

Disjunctive Normal Form or Sum of Product Form

Deriving Switching Function Expression or Logic Expression or Boolean
Expression A switching function which is written as either a single product term or as a
sum of product terms (conjunction) is said to be in disjunctive normal form.
A mathematical model of a logic system also known as switching function
The following expression (4.2) shows a switching function in disjunctive
expression or logic expression or Boolean expression is developed from
normal form. It is also known as sum of product (S of P) form.
the truth table or logic diagram. Likewise a truth table or logic diagram can
be constructed from the switching function expression or logic expression 𝒇 𝒙𝟏 , 𝒙𝟐 , 𝒙𝟑 = 𝒙𝟑 + 𝒙𝟐 𝒙𝟏 + 𝒙𝟏 𝒙𝟐 𝒙𝟑 ⋯ ⋯ ⋯ ⋯ ⋯ (𝟒. 𝟐)
or Boolean expression. Before continuing, some definitions are necessary: Conjunctive Normal Form or Product of Sum Form
Literal: A literal is defined as a Boolean variable/switching variable or its A switching function which is written as either a single sum term or as a
complement . For instance, If 𝒙𝟏 is a Boolean variable, then both 𝒙𝟏 and 𝒙𝟏 product of sum terms (disjunction) is said to be in conjunctive normal form.
would be literals. The following expression (4.3) shows a switching function in conjunctive
normal form. It is also known as product of sum (P of S) form.
Product Term: A product term (conjunction) is defined as either a literal or a
logical product of literals. For instance, if 𝒙𝟏 , 𝒙𝟐 , and 𝒙𝟑 are Boolean 𝒇 𝒙𝟏 , 𝒙𝟐 , 𝒙𝟑 = 𝒙𝟑 𝒙𝟏 + 𝒙𝟐 𝒙𝟏 +𝒙𝟐 +𝒙𝟑 ⋯ ⋯ ⋯ ⋯ ⋯ (𝟒. 𝟑)
variables, then a representative product term could be 𝒙𝟏 , 𝒙𝟏 𝒙𝟐 , or 𝒙𝟏 𝒙𝟐 𝒙𝟑 .
Canonical Forms
Sum Term: A sum term (disjunction) is defined as either a literal or a logical Canonical is a word used to describe a condition of a switching equation. In
sum of literals. For instance, if 𝒙𝟏 , 𝒙𝟐 , and 𝒙𝟑 are Boolean variables, then a normal use the word means “conforming to a general rule”. The “ rule”, for
representative sum term could be 𝒙𝟏 , 𝒙𝟏 + 𝒙𝟐 , or 𝒙𝟏 + 𝒙𝟐 + 𝒙𝟑 . switching logic, is that each term used in switching equation must contain

Combinational Logic Circuits Combinational Logic Circuits

Canonical Forms
m-notation
all of the available input variables either in complemented or uncomplemen-
ted form. The switching equations expressed in canonical form are not In the case of a minterm, a symbol 0 is assigned to complemented variable
simplified. Two formats generally exist for expressing switching equations and 1 is assigned to uncomplemented variable to obtain a binary represe-
or functions in a canonical form: ntation of that minterm. The corresponding decimal number, 𝒅 is found
and the minterm is denoted by the symbol 𝒎𝒅 . For example, the minterm
(a) Disjunctive Canonical Form or Minterm Canonical Form or Canonical 𝒙 𝒚𝒛 has binary number 011 and its corresponding decimal number is 3.
Sum of Minterm form or Standard Sum of Product Form. Thus this minterm is denoted by 𝒎𝟑 . This type of notation for the minterm
(b) Conjunctive Canonical Form or Maxterm Canonical Form or Canonical is known as m-notation. Using m-notation, the following Boolean function
Product of Maxterm Form or Standard Product of Sum Form. or switching function can be written as
Now we need to define minterm and maxterm before discussing these two
𝒇 𝒙, 𝒚, 𝒛 = 𝒙𝒚 𝒛 + 𝒙 𝒚 𝒛 + 𝒙𝒚𝒛
formats:
= 𝒎𝟓 + 𝒎𝟏 + 𝒎𝟕
Minterm or Standard Product Term
= ∑ 𝒎 𝟏, 𝟓, 𝟕 .
A minterm is a special case of product (AND) term. A minterm is a product
term consisting of all the available input variables either in complemented Therefore, the switching function becomes through m-notation
or uncomplemented form. For a switching function of 𝒏 input variables, 𝒇 𝒙, 𝒚, 𝒛 = ∑ 𝒎 𝟏, 𝟓, 𝟕 .
there are 𝟐𝒏 distinct minterms. For example, the minterms for a three varia-
ble switching function 𝒙, 𝒚, and 𝒛 are: 𝒙 𝒚 𝒛 , 𝒙 𝒚 𝒛, 𝒙 𝒚𝒛 , 𝒙 𝒚𝒛, 𝒙𝒚 𝒛 , 𝒙𝒚 𝒛,
𝒙𝒚𝒛 , and 𝒙𝒚𝒛.

3
 5/24/2024

Combinational Logic Circuits Combinational Logic Circuits

Maxterm or Standard Sum Term

𝒇 𝒙𝟏 , 𝒙𝟐 , 𝒙𝟑 = 𝒙𝟏 + 𝒙𝟐 +𝒙𝟑 𝒙𝟏 +𝒙𝟐 +𝒙𝟑 𝒙𝟏 + 𝒙𝟐 + 𝒙𝟑
A maxterm is a special case of sum (OR) term. A maxterm is a sum term
consisting of all the available input variables either in complemented or =𝑀 𝑀 𝑀
uncomplemented form. There are 𝟐𝒏 possible maxterms for a switching = ∏ 𝑀 2, 3, 7 .
function of 𝒏 variables. For example, the maxterms for a three variable
switching function 𝒙, 𝒚, and 𝒛 are: 𝒙 + 𝒚 + 𝒛 , 𝒙 + 𝒚 +𝒛 , 𝒙 +𝒚 +𝒛 , (a) Disjunctive Canonical Form or Minterm Canonical Form or Canonical Sum
𝒙 + 𝒚 + 𝒛 , 𝒙 + 𝒚 + 𝒛 , 𝒙 + 𝒚 +𝒛 , 𝒙 +𝒚 + 𝒛 , and 𝒙 +𝒚 +𝒛 . of Product Form or Standard Sum of Product Form

M-notation A switching function expressed in sum of product (S of P) form with each

product term containing every variable, either complemented or uncomplem-
In the case of a maxterm, a symbol 1 is used to designate a complemented ented, is known as disjunctive canonical function or minterm canonical
variable and a symbol 0 is used to designate a uncomplemented variable function or canonical sum of product function or standard sum of product
for obtaining a binary representation of that maxterm. The corresponding function. Such product terms are also known as minterms or standard
decimal number, 𝒅 is found and the maxterm is denoted by the symbol 𝑴𝒅 . product terms. The following expression (4.4) shows a switching function in
For example, the maxterm (𝒙 +𝒚 + 𝒛 ) has binary number 101 and its disjunctive canonical form or minterm canonical form or canonical sum of
corresponding decimal number is 5. Thus this maxterm is denoted by 𝑴𝟓 . product form or standard sum of product form.
This type of notation for the maxterm is known as M-notation. Using M-
notation, the following Boolean function or switching function can be 𝒇 𝒙𝟏 , 𝒙𝟐 , 𝒙𝟑 = 𝒙𝟏 𝒙𝟐 𝒙𝟑 + 𝒙𝟏 𝒙𝟐 𝒙𝟑 + 𝒙𝟏 𝒙𝟐 𝒙𝟑 ⋯ ⋯ ⋯ ⋯ (𝟒. 𝟒)
written as

Combinational Logic Circuits Combinational Logic Circuits

(b) Conjunctive Canonical Form or Maxterm Canonical Form or Canonical  Identify the missing variable(s) in each product (AND) term.
Product of Sum Form or Standard product of Sum Form
 Product (AND) the term(s) formed by ORing (logical adding) the missing
A switching function expressed in product of sum (P of S) form with each variable(s) and its complement with the original product (AND) term.
sum term containing every variable, either complemented or uncomple-
mented, is known as conjunctive canonical function or maxterm canonical Explanation: Let consider a three variable switching function/expression
function or canonical product of sum function or standard product of sum with variables 𝒙, 𝒚, and 𝒛. Now if there is a term 𝒙𝒚, where 𝒛 variable is
function. Such sum term is also known as maxterm or standard sum term. missing, then we form the term 𝒛 + 𝒛 and product (AND) it with the
The following expression (4.5) shows a switching function in conjunctive original term 𝒙𝒚. Therefore we get, 𝒙𝒚 𝒛 + 𝒛 . As we know, 𝒛 + 𝒛 = 𝟏, the
canonical form or maxterm canonical form or canonical product of sum original product (AND) term value is not changed.
form or standard product of sum form.  Expand the term by application of distributive property,
𝒇 𝒙𝟏 , 𝒙𝟐 , 𝒙𝟑 = 𝒙𝟏 + 𝒙𝟐 +𝒙𝟑 𝒙𝟏 +𝒙𝟐 +𝒙𝟑 𝒙𝟏 + 𝒙𝟐 + 𝒙𝟑 ⋯ ⋯ ⋯ (𝟒. 𝟓) 𝒙𝒚𝒛 + 𝒙𝒚𝒛 .

Conversion of Disjunctive Normal Function into Disjunctive Canonical Conversion of Conjunctive Normal Function into Conjunctive Canonical
Function or Minterm Canonical Function or Standard Sum of Product. Function or Maxterm Canonical Function or Standard Product of Sum
To convert sum of product (S of P) form or disjunctive normal form of a To convert product of sum (P of S) form or conjunctive normal form of a
switching function into standard sum of product form or disjunctive switching function into standard product of sum form or conjunctive
canonical form or minterm canonical form of the switching function using canonical form or maxterm canonical form of the switching function
Boolean algebra, we do the following: using Boolean algebra, we do the following:

4
 5/24/2024

Combinational Logic Circuits Combinational Logic Circuits

 Identify the missing variable(s) in each sum (OR) term. Deriving Disjunctive Canonical Expression or Minterm Canonical Expression
or Standard Sum of Product Term from Truth Table directly.
 Sum (OR) the term(s) formed by ANDing (logical multiplying) the
missing variable(s) and its complement with the original sum (OR) term.  Select the minterms or standard product terms corresponding to the
rows in the truth table where the output functions are 1.
Explanation: Let consider a three variable switching function/expression  In the case of minterm, use complemented input variable for the value
with variables 𝒙, 𝒚, and 𝒛. Now if there is a term 𝒙 + 𝒚 , where 𝒛 variable is
of 0 and uncomplemented input variable for the value of 1.
missing, then we form the term 𝒛𝒛 and sum (OR) it with the original term
𝒙 + 𝒚 . Therefore we get, 𝒙 + 𝒚 + 𝐳𝒛 As we know, 𝐳𝒛 = 𝟎, the original  Sum (OR) the all such minterms or standard product terms to obtain
sum (OR) term value is not changed. disjunctive canonical expression or Minterm canonical expression or
standard sum of product form of the switching expression.
 Expand the term by application of distributive property,
Deriving Conjunctive Canonical Expression or Maxterm Canonical Expression
𝒙+𝒚+𝒛 𝒙+𝒚+𝒛 . or Standard Product of Sum Term from Truth Table directly
 Select the maxterms or standard sum terms corresponding to the
Example 4.3 Find the standard product of sum for the following function:
rows in the truth table where the output functions are 0.
𝒇 = 𝒙𝟏 𝒙𝟐 𝒙𝟑 + 𝒙𝟏 𝒙𝟑 𝒙𝟒 + 𝒙𝟏 𝒙𝟐 𝒙𝟒  In the case of maxterm, use complemented input variable for the
value of 1 and uncomplemented input variable for the value of 0.
Example 4.4 Find the standard sum of product for the following function:
 Product (AND) the all such maxterms or standard sum terms to obtain
𝒇 = 𝒙𝟏 + 𝒙𝟑 + 𝒙𝟐 𝒙𝟒 conjunctive canonical expression or Maxterm canonical expression
or standard product of sum form of the switching expression.

Combinational Logic Circuits Combinational Logic Circuits

From the truth table 4.3, we can write the Table 4.3
switching equation in terms of minterms Shannon’s Theorem
𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒇 𝒙𝟏 , 𝒙𝟐 , 𝒙𝟑
or standard sum of product terms using Every Boolean function 𝒇 𝒙𝟏 , 𝒙𝟐 , 𝒙𝟑 , ⋯ ⋯ , 𝒙𝒋 , ⋯ ⋯ , 𝒙𝒏 of 𝒏 variables can be
the above steps and hence its m-notation 0 0 0 0
expressed in any one of the following forms:
as given below: 0 0 1 1
𝒇 𝒙𝟏 , 𝒙𝟐 , 𝒙𝟑 = 𝒙𝟏 𝒙𝟐 𝒙𝟑 + 𝒙𝟏 𝒙𝟐 𝒙𝟑 + 𝒙𝟏 𝒙𝟐 𝒙𝟑 + (a) 𝒇 𝒙𝟏 , 𝒙𝟐 , 𝒙𝟑 , ⋯ ⋯ , 𝒙𝒋 , ⋯ ⋯ , 𝒙𝒏 = 𝒙𝒋 𝒇 𝒙𝟏 , 𝒙𝟐 , 𝒙𝟑 , ⋯ ⋯ , 𝟏, ⋯ ⋯ , 𝒙𝒏 +
0 1 0 1
𝒙𝒋 𝒇 𝒙𝟏 , 𝒙𝟐 , 𝒙𝟑 , ⋯ ⋯ , 𝟎, ⋯ ⋯ , 𝒙𝒏 ……
𝒙𝟏 𝒙𝟐 𝒙𝟑 + 𝒙𝟏 𝒙𝟐 𝒙𝟑 0 1 1 0 ……..(4.6)
In m-notation, it becomes 1 0 0 1 (b) 𝒇 𝒙𝟏 , 𝒙𝟐 , 𝒙𝟑 , ⋯ ⋯ , 𝒙𝒋 , ⋯ ⋯ , 𝒙𝒏 = 𝒙𝒋 + 𝒇 𝒙𝟏 , 𝒙𝟐 , 𝒙𝟑 , ⋯ ⋯ , 𝟏, ⋯ ⋯ , 𝒙𝒏
𝒇 𝒙𝟏 , 𝒙𝟐 , 𝒙𝟑 = ∑ 𝒎 𝟏, 𝟐, 𝟒, 𝟔, 𝟕 . 1 0 1 0 𝒙𝒋 + 𝒇 𝒙𝟏 , 𝒙𝟐 , 𝒙𝟑 , ⋯ ⋯ , 𝟎, ⋯ ⋯ , 𝒙𝒏 …
Similarly, we can write the switching equation 1 1 0 1 ....….(4.7)
in terms of maxterms or standard product of
1 1 1 1 for 𝒋 = 𝟏, 𝟐, 𝟑, ⋯ ⋯ , 𝒏
sum terms using the above steps and hence
its M-notation as given below: Where 1 and 0 in eqns. (4.6) and (4.7) are in the jth position, i.e. replacing 𝒙𝒋
𝒇 𝒙𝟏 , 𝒙𝟐 , 𝒙𝟑 = 𝒙𝟏 + 𝒙𝟐 + 𝒙𝟑 𝒙𝟏 + 𝒙𝟐 + 𝒙𝟑 𝒙𝟏 + 𝒙𝟐 + 𝒙𝟑 in the switching function
𝒇 𝒙𝟏 , 𝒙𝟐 , 𝒙𝟑 , ⋯ ⋯ , 𝒙𝒋 , ⋯ ⋯ , 𝒙𝒏
In M-notation, it becomes
𝒇 𝒙𝟏 , 𝒙𝟐 , 𝒙𝟑 = ∏ 𝑴 𝟎, 𝟑, 𝟓 .

5
 5/24/2024

Combinational Logic Circuits Combinational Logic Circuits

Proof: = 𝒙𝟏 𝒙𝟐 𝒇 𝟏, 𝟏, ⋯ , 𝒙𝒏 + 𝒙𝟐 𝒇 𝟏, 𝟎, ⋯ , 𝒙𝒏

By perfect induction − +𝒙𝟏 𝒙𝟐 𝒇 𝟎, 𝟏, ⋯ , 𝒙𝒏 + 𝒙𝟐 𝒇 𝟎, 𝟎, ⋯ , 𝒙𝒏

⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯
Let 𝒙𝒋 be equal to 1, then 𝒙𝒋 equals to zero and eqn. (4.6) becomes an identity, = 𝒙𝟏 𝒙𝟐 ⋯ 𝒙𝒏 𝒇 𝟏, 𝟏, ⋯ , 𝟏 + 𝒙𝟏 𝒙𝟐 ⋯ 𝒙𝒏 𝒇 𝟏, 𝟏, ⋯ , 𝟎 + ⋯ ⋯
that is,
+𝒙𝟏 𝒙𝟐 ⋯ 𝒙𝒏 𝒇 𝟎, 𝟎, ⋯ , 𝟏 + 𝒙𝟏 𝒙𝟐 ⋯ 𝒙𝒏 𝒇 𝟎, 𝟎, ⋯ , 𝟎 ⋯ ⋯ ⋯ (𝟒. 𝟖)
𝒇 𝒙𝟏 , 𝒙𝟐 ⋯ , 𝟏 ⋯ , 𝒙𝒏 = 𝟏 𝒇 𝒙𝟏 , 𝒙𝟐 ⋯ , 𝟏 ⋯ , 𝒙𝒏
Similarly, substituting 𝒙𝒋 = 𝟎 and 𝒙𝒋 = 𝟏 also reduces eqn. (4.6) to an identity, Expanding the function similarly using eqn. (4.7) gives
and this proves the part (a) of the theorem. 𝒇 𝒙𝟏 , 𝒙𝟐 , ⋯ , 𝒙𝒏 = 𝒙𝟏 + 𝒙𝟐 + ⋯ + 𝒙𝒏 + 𝒇 𝟏, 𝟏, ⋯ , 𝟏 𝒙𝟏 + 𝒙𝟐 + ⋯ + 𝒙𝒏 + 𝒇 𝟏, 𝟏, ⋯ , 𝟎

Part (b) of the theorem follows by the principle of duality. ⋯ 𝒙𝟏 + 𝒙𝟐 + ⋯ + 𝒙𝒏 + 𝒇 𝟎, 𝟎, ⋯ , 𝟏 𝒙𝟏 + 𝒙𝟐 + ⋯ + 𝒙𝒏 + 𝒇 𝟎, 𝟎, ⋯ , 𝟎

⋯ ⋯ ⋯ (𝟒. 𝟗)
Either of the Shannon’s theorem can be used to obtain a complete expansion
of Boolean function or switching function. If eqn. (4.6) is used to expand the In eqns. (4.8) and (4.9) the functions 𝒇 𝟏, 𝟏, ⋯ , 𝟏 , 𝒇 𝟏, 𝟏, ⋯ , 𝟎 etc. are functions
function then first expand the function with respect to 𝒙𝟏 . After that, each of of constant and corresponds to the various rows of truth table for the Boolean
the resulting functions is expanded with respect to 𝒙𝟐 . This is repeated until function or switching function. They can take up either of the value 0 or 1.
each function becomes a constant. This is illustrated below: These two expansions of Boolean functions are disjunctive canonical expan-
sion or standard product of sum expansion and conjunctive canonical expan-
𝒇 𝒙𝟏 , 𝒙𝟐 , ⋯ , 𝒙𝒏 = 𝒙𝟏 𝒇 𝟏, 𝒙𝟐 , ⋯ , 𝒙𝒏 + 𝒙𝟏 𝒇 𝟎, 𝒙𝟐 , ⋯ , 𝒙𝒏 sion or standard sum of product expansion respectively.

Combinational Logic Circuits Combinational Logic Circuits

Example 4.5 Find the standard sum (disjunctive canonical) and standard Minimization
(conjunctive canonical) forms for the switching function given by the truth
The design is not unique and it is possible to get many circuits performing
table 4.4.
the same functions. Now it is the task of the designer to select an optimum
Solution: Using the expansion given by eqn. (4.8), circuit configuration.
we get As is usual in any engineering design, the number of components used in
Table 4.4
𝒇 𝒙𝟏 , 𝒙𝟐 , 𝒙𝟑 = 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒇 𝟏, 𝟏, 𝟏 + 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒇 𝟏, 𝟏, 𝟎 + resulting optimum circuit configuration should be minimum to ensure
𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒇 𝟏, 𝟎, 𝟏 + 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒇 𝟏, 𝟎, 𝟎 + 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒇 𝒙𝟏 , 𝒙𝟐 , 𝒙𝟑 minimum cost, minimum space requirement, maximum speed of operation,
easy availability of components, low power requirements, ease of intercon-
𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒇 𝟎, 𝟏, 𝟏 + 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒇 𝟎, 𝟏, 𝟎 + 0 0 0 0 necting the components, easy to design, etc. There can be two different
𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒇 𝟎, 𝟎, 𝟏 + 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒇 𝟎, 𝟏, 𝟎 + 0 0 1 1 approaches to the design of combinational logic circuits:
= 𝒙𝟏 𝒙𝟐 𝒙𝟑 + 𝒙𝟏 𝒙𝟐 𝒙𝟑 + 𝒙𝟏 𝒙𝟐 𝒙𝟑 + 𝒙𝟏 𝒙𝟐 𝒙𝟑 + 𝒙𝟏 𝒙𝟐 𝒙𝟑 0 1 0 1  One of these is the traditional method, wherein the given Boolean
Similarly, using the expansion given by eqn. (4.9), 0 1 1 0 expression or the logic expression or the truth table is simplified or
we get minimized by using standard methods and the simplified or minimized
1 0 0 1
expression is realized using the gates.
𝒇 𝒙𝟏 , 𝒙𝟐 , 𝒙𝟑 = 𝒙𝟏 + 𝒙𝟐 + 𝒙𝟑 + 𝒇 𝟏, 𝟏, ⋯ , 𝟏 ⋯⋯ 1 0 1 0
 The other method normally does not require any simplification or
⋯ 𝒙𝟏 + 𝒙𝟐 + 𝒙𝟑 + 𝒇 𝟎, 𝟎, 𝟎 1 1 0 1 minimization of the logic expression or the truth table, instead the
= 𝒙𝟏 + 𝒙𝟐 + 𝒙𝟑 𝒙𝟏 + 𝒙𝟐 + 𝒙𝟑 𝒙𝟏 + 𝒙𝟐 + 𝒙𝟑 1 1 1 1 complex logic functions available in medium scale integrated (MSI)
circuits can be directly used. Computer-aided design (CAD) tools are

6
 5/24/2024

Combinational Logic Circuits Combinational Logic Circuits

used for the design using programmable logic devices ( PLDs) and field- Map Method
programmable gate arrays (FPGAs).
simplifying switching functions or expressions. The Karnaugh map or Veitch
The following standard methods can be used to simplify or minimize the diagram is a matrix of squares. Each square represents a minterm or
Boolean functions: maxterm from a switching/Boolean expressions and arranges in such
fashion so as to provide adjacent places for minterms or maxterms that
1. Boolean algebraic method differ in only one variable which is primed in one term and unprimed in the
2. Map method (known as Karnaugh map technique) other. As a result, the following Boolean identity can easily be applied to
3. Quine-McCluskey or tabular method simplify the Boolean/switching expression.
4. Variable entered mapping (VEM) technique
𝒙. 𝒇 + 𝒙 . 𝒇 = 𝒇. 𝒙 + 𝒙′ = 𝒇
The Boolean algebraic method have already been discussed for the
simplification of Boolean functions/expressions but it is not convenient That is, if the two terms (either minterms or maxterms) which are identical
if the expressions are long and many variables are involved. The other except for only one variable which is in the true form in the one term but in
methods which are much better than Boolean algebraic method will be the complemented form in the other, then both the terms when combined
discussed here one by one. can be replaced by their common factor.
If a given switching/Boolean expression contains a minterm, then a 1 is
Map Method entered into the square that represents that minterm. A maxterm is
The map method, first proposed by E. W. Veitch and slightly modified represented by a 0. The two terms which are same except in one variable
by M. Karnaugh, is also known as the “Veitch diagram/representation” appear as adjacent 1’s (for minterms) or 0’s (for maxterms) in the Karnaugh
or the “Karnaugh map”. It is a very useful tool in representing and map (K-map).

Combinational Logic Circuits Combinational Logic Circuits

Karnaugh map or Veitch diagram may also be regarded as the pictorial repre- 𝑨𝑩
sentation of the truth table for the switching/Boolean function and a 1 or 0 is 𝑪𝑫 00 01 11 10
written inside the square/cell depending upon whether the function is having 0 4 12 8
the value 1 or 0 for that particular minterm and vice versa for maxterm. 00

Figure 4.3 shows the K-maps for two, three and four variables. For a Boolean 1 5 13 9
01
or switching function of 𝒏 variables, the K-map is made of 𝟐𝒏 squares/cells.
Each square/cell corresponds to one of the combinations of 𝒏 variables 3 7 15 11
11
switching or Boolean function, since there are 𝟐𝒏 combinations of 𝒏
variables. In K-map, each square/cell is designated by a decimal number 2 6 14 10
which is written on the right hand upper corner of the cell/square. The 10
decimal number corresponds to the minterm/maxterm number of the term. (c)
𝑨 𝑨𝑩 Fig. 4.3 Karnaugh maps (a) Two variables (b) Three variables (c) Four
0 1 𝑪 00 01 11 10 variables
𝑩
0 2 0 2 6 4
0 0
Gray code is used for the identification of square/cells in the K-map because
1 3 1 3 7 5 it ensures that only one variable changes between each pair of adjacent cells
1 1
or squares.
(a) (b)

7
 5/24/2024

Combinational Logic Circuits Combinational Logic Circuits

Figure 4.4 shows the minterm/maxterm corresponding to each cell and the 𝑨𝑩
minterm/maxterm is written inside the cell for clear understanding. 𝑪 00 01 11 10
0 2 6 4
𝑨 𝑨 0 𝑨+𝑩+𝑪 𝑨+𝑩 +𝑪 𝑨 +𝑩 +𝑪 𝑨 +𝑩+𝑪
𝑩 0 1 𝑩 0 1
0 2 0 2 1 3 7 5
1 𝑨 + 𝑩 + 𝑪′ 𝑨 + 𝑩 + 𝑪′ 𝑨 + 𝑩 + 𝑪′ 𝑨 + 𝑩 + 𝑪′
0 𝑨𝑩 𝑨𝑩 0 𝑨+𝑩 𝑨 +𝑩

1 3 1 3 𝑨𝑩
1 𝑨𝑩 𝑨𝑩 1 𝑨 + 𝑩′ 𝑨 + 𝑩′ 𝑪𝑫 00 01 11 10
0 4 12 8
00 𝑨𝑩𝑪𝑫 𝑨 𝑩𝑪 𝑫 𝑨𝑩𝑪 𝑫 𝑨𝑩 𝑪 𝑫
𝑨𝑩 1 5 13 9
00 01 11 10 01 𝑨 𝑩 𝑪 𝑫 𝑨 𝑩𝑪 𝑫 𝑨𝑩𝑪 𝑫 𝑨𝑩 𝑪 𝑫
𝑪
0 2 6 4
0 3 7 15 11
𝑨𝑩𝑪 𝑨 𝑩𝑪 𝑨𝑩𝑪 𝑨𝑩 𝑪 11 𝑨 𝑩 𝑪𝑫 𝑨 𝑩𝑪𝑫 𝑨𝑩𝑪𝑫 𝑨𝑩 𝑪𝑫
1 3 7 5 2 6 14 10
1 𝑨𝑩C 𝑨 𝑩𝑪 𝑨𝑩𝑪 𝑨𝑩 𝑪 10 𝑨 𝑩 𝑪𝑫 𝑨 𝑩𝑪𝑫 𝑨𝑩𝑪𝑫 𝑨𝑩 𝑪𝑫

Combinational Logic Circuits Combinational Logic Circuits

𝑨𝑩 K-maps for five variables

𝑪𝑫 00 01 11 10
0 4 12 8
00 𝑨+𝑩+𝑪+𝑫 𝑨+𝑩 +𝑪+𝑫 𝑨 +𝑩 +𝑪+𝑫 𝑨 +𝑩+𝑪+𝑫 𝑨=𝟎 𝑨=𝟏
𝑩𝑪
1 5 13 9 𝑫𝑬 00 01 11 10 00 01 11 10
01 𝑨 + 𝑩 + 𝑪 + 𝑫′ 𝑨 +𝑩 +𝑪 + 𝑫′ 𝑨 +𝑩 +𝑪 + 𝑫′ 𝑨 + 𝑩 + 𝑪 + 𝑫′ 0 4 12 8 16 20 28 24
00
3 7 15 11 1 5 13 9 17 21 29 25
11 01
𝑨 + 𝑩 + 𝑪 + 𝑫′ 𝑨 + 𝑩 + 𝑪 + 𝑫′ 𝑨 + 𝑩 + 𝑪 + 𝑫′ 𝑨 + 𝑩 + 𝑪 + 𝑫′
11 3 7 15 11 19 23 31 27
2 6 14 10
10 𝑨 + 𝑩 +𝑪 +𝑫 𝑨 + 𝑩 + 𝑪 + 𝑫 𝑨 +𝑩 +𝑪 + 𝑫 𝑨 + 𝑩 +𝑪 + 𝑫 2 6 14 10 20 22 30 26
10

Fig. 4.4 Minterm/Maxterm corresponding to each cell of K-maps or

8
 5/24/2024

Combinational Logic Circuits Combinational Logic Circuits

In this case, 𝑨 = 𝟎 for first gray codes of 2-bit binary combinations 3-bit Gray Codes i.e. Gray codes of 3-bit binary
and 𝑨 = 𝟏 for next gray codes of 2-bit binary combinations as combinations are used here.
immediate before slide. Here combinations of BC stands for 2-bit
𝑨𝑩𝑪
binary combinations.
𝑫𝑬 000 001 011 010 110 111 101 100
𝑨𝑩𝑪 0 12 8 24 20 16
4 28
00
𝑫𝑬 000 001 011 010 100 101 111 110
0 4 12 8 16 20 28 24 1 5 13 9 25 29 21 17
00 01

1 5 13 9 17 21 29 25 11 3 7 15 11 27 31 23 19
01
3 7 15 11 19 23 31 27 10 2 6 14 10 26 30 22 18
11

10 2 6 14 10 20 22 30 26
All representations of K-maps for five variables ensures that only one
variable changes between each pair of adjacent cells or squares.
or

Combinational Logic Circuits Combinational Logic Circuits

K-maps for Six variables

𝑨𝑩𝑪
𝑩𝑪 𝑨=𝟎 𝑨=𝟏
𝑫𝑬𝑭 000 001 011 010 100 101 111 110
𝑬𝑭 00 01 11 10 00 01 11 10
0 8 24 16 32 40 56 48
0 8 24 16 32 40 56 48 000
00
1 9 25 17 33 41 57 49
1 9 25 17 33 41 57 49 001
01
𝑫=𝟎

3 11 27 19 35 43 59 51
3 11 27 19 35 43 59 51 011
11
2 10 26 18 34 42 58 50
2 10 26 18 34 42 58 50 010
10
4 12 28 20 36 44 60 52
4 12 28 20 36 44 60 52 100
00
5 13 29 21 37 45 61 53
5 13 29 21 37 45 61 53 101
01
𝑫=𝟏

7 15 31 23 39 47 63 55
7 15 31 23 39 47 63 55 111
11
6 14 30 22 38 45 62 54
6 14 30 22 38 45 62 54 110
10

9
 5/24/2024

Combinational Logic Circuits Combinational Logic Circuits

3-bit Gray codes Representation of Truth Table on K-Map

𝑨𝑩𝑪 Let us consider a truth table of a 3-variable logic function given in Table 4.5.
𝑫𝑬𝑭 The output 𝒇 is logic 1 corresponding to the rows 1, 2, 4, and 7 i.e., the input
000 001 011 010 110 111 101 100
combinations of 001 (𝑨′𝑩′𝑪), 010 (𝑨′𝑩𝑪′), 100 (𝑨𝑩′𝑪′) and 111 (𝑨𝑩𝑪). Thus,
0 8 24 16 48 56 40 32 the equation in terms of canonical SOP cab be written as follows:
000
𝒇 = 𝑨 𝑩 𝑪 + 𝑨 𝑩𝑪 + 𝑨𝑩 𝑪 + 𝑨𝑩𝑪 ⋯ ⋯ Row Inputs Output
1 9 25 17 49 57 41 33
001 ⋯ (𝟒. 𝟏𝟎) Number 𝑨 𝑩 𝑪 𝒇
3 11 27 19 51 59 43 35 Equation (4.10) represents the compl- 0 0 0 0 0
011
3-bit Gray codes

ete truth table in canonical SOP form. 1 0 0 1 1

2 10 26 18 50 58 42 34 Similarly, we note that the output 𝒇 is
010 logic 0 corresponding to the rows 0, 3, 2 0 1 0 1
4 12 28 20 54 62 46 38 5, and 6 and the output 𝒇 can be repre- 3 0 1 1 0
110 sented in terms of canonical POS form 4 1 0 0 1
5 13 29 21 55 63 47 39 as given below:
111 5 1 0 1 0
𝒇 = (𝑨 + 𝑩 + 𝑪)(𝑨 + 𝑩 + 𝑪 )
7 15 31 23 53 61 45 37 (𝑨 + 𝑩 + 𝑪 )(𝑨 + 𝑩 + 𝑪) ⋯ (𝟒. 𝟏𝟏) 6 1 1 0 0
101
7 1 1 1 1
6 14 30 22 52 60 44 36
100
Table 4.5 Truth table of a 3-variable function

Combinational Logic Circuits Combinational Logic Circuits

Representation of Truth Table on K-Map Looping

Equation (4.11) also represents the complete truth table in canonical POS
form. Now, we will use the 3-variable K-map and enter the value of the output As we know, K-map for a given Boolean/switching function expressed in
variable, 𝒇 (1 or 0) in each cell/square corresponding to its decimal number minterm representation can be drawn by writing 1’s in the squares/cells
or minterm or maxterm identification. Figure 4.5 gives the complete K-map corresponding to the minterms of the function. In the rest of the squares
of the truth table given in Table 4.5. or cells 0’s are placed. Similarly, K-map for a given Boolean/switching
function expressed in maxterm representation can be drawn by writing 0’s
𝑨𝑩 in the squares/cells corresponding to the maxterms of the function and 1’s
00 01 11 10 are placed in rest of the squares/cells.
𝑪
0 2 6 4 The Boolean/switching expression for output can be simplified by properly
0 𝟎 𝟏 𝟎 𝟏
combining those adjacent squares/cells in the K-map that contain 1’s
Fig. 4.5 K-map for
corresponding to the minterms of the Boolean/switching expression and
1 3 7 5 Table 4.5
0’s corresponding to the maxterms of the Boolean/switching expression.
1 𝟏 𝟎 𝟏 𝟎
The process for combining these 1’s or 0’s is called looping.
Adjacent 1’s or 0’s in squares/cells of the K-map makes loops containing
The procedure used above is general and is used to represent a truth table 1, 2, 4, 8. Squares or, in general, 𝟐𝒋 squares, where 𝒋 gives the number of
on the K-map. On the other hand, if a K-map is given we can make the truth variables missing from the resulting product term or sum term.
table corresponding to this by following the reverse process.

10
 5/24/2024

Combinational Logic Circuits Combinational Logic Circuits

Looping Groups of Two (Pairs) Thus,

A K-map may contain a group of two 1s for minterms or 0s for maxterms that 𝒀 = 𝑨 𝑩′
are adjacent to each other. This group is called a pair. An example of three To summarize:
variables K-map that contains an adjacent pair of 1s is shown in Figure 4.5.
Looping a pair of adjacent 1s in a K-map eliminates the one variable that
𝑨𝑩 appears in complemented and uncomplemented form.
00 01 11 10
𝑪
0 2 6 4 Looping Groups of Four (Quads)
0 𝟏 𝟎 𝟎 𝟎
In a K-map, a group of four 1s for minterms or 0s for maxterms that are
1 3 7 5 adjacent to each other is called a quad. An example of four variables K-map
1 𝟏 𝟎 𝟎 𝟎 that contains an adjacent quad of 1s is shown in Figure 4.6.
When a quad is looped, the resultant term will contain only the variables
Fig. 4.5 Example of looping pair of adjacent 1s. that do not change form for all the squares in the quad. This can be easily
proved as follows:
When a pair is looped, the resultant term will contain only the variables that
do not change form for both the squares in the pair. This is easily proved as 𝒀 = 𝑨 𝑩𝑪 𝑫 + 𝑨 𝑩𝑪𝑫 + 𝑨𝑩𝑪 𝑫 + 𝑨𝑩𝑪𝑫
follows: = 𝑨 𝑩𝑫 𝑪 + 𝑪 + 𝑨𝑩𝑫(𝑪 + 𝑪 )
= 𝑨 𝑩𝑫 + 𝑨𝑩𝑫 = 𝑩𝑫(𝑨 + 𝑨 )
𝒀 = 𝑨 𝑩′𝑪 + 𝑨 𝑩 𝑪 = 𝑨 𝑩 𝑪 + 𝑪 = 𝑨 𝑩′(𝟏) Thus, 𝒀 = 𝑩𝑫

Combinational Logic Circuits Combinational Logic Circuits

𝑨𝑩 Looping Groups of Eight (Octets)

𝑪𝑫 00 01 11 10 In a K-map, a group of eight 1s for minterms or 0s for maxterms that are
0 4 12 8 adjacent to one another is called an octet. An example of four variables K-
00 0 0 0 0 map that contains an adjacent octet of 1s is shown in Figure 4.7.
1 5 13 9 When an octet is looped, the resultant term will contain only the variables
01 0 1 1 0
that do not change form for all the squares in the octet. This can also be
7 15 11 easily proved as before.
11 0 3 1 1 0
𝑨𝑩
2 6 14 10 𝑪𝑫 00 01 11 10
10 0 0 0 0
0 4 12 8
00 0 0 0 0
Fig. 4.6 Example of looping quad of adjacent 1s.
1 5 13 9
01 1 1 1 1
To summarize: 7 15 11
11 1 3 1 1 1
Looping a quad of adjacent 1s in a K-map eliminates the two variables that
appear in both complemented and uncomplemented form. 2 6 14 10
10 0 0 0 0

Fig. 4.6 Example of looping octet of adjacent 1s.

11
 5/24/2024

Combinational Logic Circuits Combinational Logic Circuits

To summarize: For example, consider a switching problem described by the truth-table given
in table 4.6. The function can be written as
Looping an octet of adjacent 1s in a K-map eliminates the three variables
that appear in both complemented and uncomplemented form. 𝒇 𝒙𝟏 , 𝒙𝟐 , 𝒙𝟑 = 𝒎 𝟎, 𝟒, 𝟕 + 𝒅. 𝒄. 𝟐, 𝟔 .

Incompletely Specified Boolean/Switching Functions Where 𝒅. 𝒄. indicates don’t care states. The K-map is shown in Figure 4.7.

In case of switching/Boolean functions so far described, the value for the Table 4.6
function is specified for all 𝟐𝒏 possible input combinations of 𝒏 variables. 𝒙𝟏 𝒙𝟐
𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒇 𝒙𝟏 , 𝒙𝟐 , 𝒙𝟑
Sometimes however for some input combinations, the output of switching 𝒙𝟑 00 01 11 10
0 0 0 1
function hence switching circuit may mot be specified. It means that the
0 1 d d 1
outputs for those particular combinations are immaterial, as far as the ope- 0 0 1 0
ration of the switching function/circuit is concerned. This is also possible 0 1 0 𝒅
when certain input combinations can never occur due to some constraints 1 0 0 1 0
0 1 1 0
and, therefore, we do not care about the state of the output for these input
Fig. 4.7 K-map corresponding to the table 4.6
combinations. Such situations are indicated on the truth-table or K-map by 1 0 0 1
writing ‘𝒅’ or ‘𝒙’ as the functional value, rather than ‘0’ or ‘1’. Thus, these 1 0 1 0 For the purpose of simplification, ‘𝒅’ can be
conditions/situations are referred as don’t care states/conditions and the
1 1 0 𝒅 taken either as 1 or 0 so that the resultant
switching functions which include don’t care states are said to be income-
1 1 1 1 switching function is minimized.
pletely specified switching/Boolean functions.

Combinational Logic Circuits Combinational Logic Circuits

Prime Implicants (a) If 𝒇𝟐 ≤ 𝒇𝟏 , then 𝒇𝟐 + 𝒇𝟏 = 𝒇𝟏 and 𝒇𝟐. 𝒇𝟏 = 𝒇𝟐.

Before discussing the methods of minimizing or simplifying the switching (b) if 𝒕, 𝒕𝟏 and 𝒕𝟐 are product terms such that 𝒕 = 𝒕𝟏 .𝒕𝟐 , then 𝒕 ≤ 𝒕𝟐 ,
functions, the concept of implication and prime implicants need to be since 𝒕 + 𝒕𝟐 = 𝒕𝟏 .𝒕𝟐 + 𝒕𝟏 = 𝒕𝟏 , therefore, 𝒕 ≤ 𝒕𝟐 .
introduced.
A switching function 𝒇𝟏 is implied by a switching function 𝒇𝟐, if 𝒇𝟏 = 𝟏
whenever 𝒇𝟐 = 𝟏 and when 𝒇𝟐 = 𝟎, 𝒇𝟏 may be either 0 or 1. This is written as
𝒇𝟐 ≤ 𝒇𝟏 and read as “𝒇𝟐 is less than or equal to 𝒇𝟏” or “𝒇𝟐 is included in 𝒇𝟏”
or “𝒇𝟐 is covered by 𝒇𝟏”. As an example, consider the following functions:
Boolean algebraic theorems and postulates are used for the
𝒇𝟏 𝑨, 𝑩, 𝑪 = 𝒎 𝟎, 𝟐, 𝟓, 𝟕 manipulation of switching expressions or Boolean
expressions.
𝒇𝟐 𝑨, 𝑩, 𝑪 = 𝒎 𝟎, 𝟓

𝒇𝟑 𝑨, 𝑩, 𝑪 = 𝒎 𝟎, 𝟏, 𝟑, 𝟓, 𝟕 .

It can be noticed that 𝒇𝟐 ≤ 𝒇𝟏, 𝒇𝟐 ≤ 𝒇𝟑 , but 𝒇𝟑 ≰ 𝒇𝟏 , 𝒇𝟏 ≰ 𝒇𝟑 . Also from the defi-

nition of implication, the following properties may be noted.

12