Design Constraints: If a system is designed with only two levels of gates, it is also
possible that to obtain the desired functions more complex logic is required and hence
the designs are not very easy ones.
Potential for Increased Gate Usage: There are typical situations, where using of two-
level logic with required function may increase the number of gates compared to the
cases, where multi-level solution can be used.
Implementation of Two Variable Boolean Function
Consider a Boolean function of two variables,
We have to implement this Boolean function using logic gates.
For implementing this Boolean function start with the final expression AB'+AB. Since, it is
a summation of two terms, thus it must be the output of a two-input OR gate. So draw an
OR gate with two inputs as shown in Figure-4.
Now, the term AB' is the output of a two input AND gate whose inputs are A and B'. Where, B'
is in turn output of a NOT gate whose input is B. The term AB is the output of a two input AND
gate whose inputs are A and B. Hence, the logic circuit will become as shown in Figure-5.
In this way, we can implement a two variable Boolean function using logic gates.
Implementation of Three Variable Boolean Function
Consider a three-variable Boolean function,
We have to implement this Boolean function using logic gates.
We will start implement with the final expression F=AB ̅̅̅̅̅̅̅̅̅
̅̅̅̅ +ABC+(B + C) . As we can see that it
is a summation of three terms, hence it must be the output of a three-input OR gate.
Therefore, we will draw an OR gate with three inputs as shown in Figure-6.
̅̅̅̅̅must be the output of a NOT gate whose input is AB. The second term
Here, the term (AB)
ABC must be the output of a three-input AND gate whose inputs are A, B, and C, and the third
̅̅̅̅̅̅̅̅̅
term (B + C) must be the output of a NOT gate whose input is B + C. Thus, we introduce two
NOT gates and one AND gate in the logic circuit as shown in Figure-7.
Now, AB must be the output of a two-input AND gate whose inputs are A and B. And B + C
must be the output of a two input OR gate whose inputs are B and C. So, we introduce an
AND gate and an OR gate in the logic circuit as shown in Figure-8.
This is the complete implementation of the given Boolean function using logic gates. Hence,
in this way, we can implement any Boolean function of any number of variables using logic
gates.
In Boolean or logic algebra, a logic function is a mathematical expression which specifies the
relationship between inputs and outputs of a logic circuit. Boolean functions can be classified
into two types namely, completely specified logic functions and incompletely specified logic
functions.
A completely specified logic function is one whose output is determined or defined for every
possible combination of inputs, while a Boolean function whose output value is unspecified
for at least one combination of inputs is called incompletely specified logic function.
In an incompletely specified logic function, the combinations of input variables for which the
output is not defined are called don't care combinations.
In this article, we will discuss the minimization of incompletely specified logic functions with
the help of examples.
Example 1
Minimize the Boolean expression to its minimal form,
F(A,B,C,D)=∑m(0,3,7,8,9,10,11,15)+d(2,4)
Solution
We can observe that the given Boolean function has two don't cares, i.e. 2 and 4, hence it is
an incompletely specified logic function. We can minimize this function using K-Map
(Karnaugh Map) minimization technique.
The K-map representation of the given incompletely specified logic function is shown in
Figure-1 below.
In the K-Map shown in Figure-1, the reduction is done as per the following steps ?
Step 1 ?There are no isolated 1s.
Step 2 ?The minterm m0 makes four square with minterms m2 (don't care), m8, and
̅D
m10. Make the four square and read it as B ̅
Step 3 ? The minterm m3 makes a four square with minterms m7, m11, and m15.
Make the four square and read it as CD.
Step 4 ?The minterm m8 makes a four square with minterms m9, m10, and m11.
̅B
Make the four square and read it as A ̅
Step 5 ?Write all the product terms in SOP (Sum of Product) form.
Thus, the minimal SOP expression of the given incompletely specified logic function is,
Example 2
Minimize the following Boolean expression,
F(A,B,C,D)=∑m(1,3,7,11,15)+d(0,2,5)F(A,B,C,D)=∑m(1,3,7,11,15)+d(0,2,5)
Solution
We can observe that the given Boolean function has three don't care minterms. Hence, it is
an incompletely specified logic function.
Now, let us use the K-Map reduction technique to minimize this expression to the minimal
form. The K-map representation of the given function is shown in Figure-2.
In the K-map shown in Figure-2, the minimization of the incompletely specified
function is done as per the following steps ?
Step 1 ? There are no isolated 1s.
Step 2 ? The minterm m1 forms a four square with minterms m0 (don't care), m2 (don't care),
and m3. Make this four square and read it as 𝐴̅𝐵
̅
Step 3 ? The minterm m7 makes a four square with minterms m7, m11, and m15. Make this
four square and read it as CDCD.
Step 4 ? Write all the product terms in SOP form.
So, the minimal Boolean expression of the given incompletely specified logic function is,
̅B
Fmin=A ̅ +CD
This is all about the minimization of incompletely specified logic functions in Boolean algebra.
Implementation of Logic Functions using Logic Gates
Implementation of a Logic Function Using OR and AND Gates
We can realize or implement a Boolean expression or a logic function as hardware using logic
gates. The easiest method of implementing a logic function as hardware using logic gates is to
start with the output and moves towards the inputs.
The implementation of a logic function with the help of logic gates involves connecting
different logic gates in a specific manner. In this article, we shall confine our attention to
implementing a logic function using the OR and AND gates only. Let's start the article with a
brief introduction of OR and AND gates.
In this section, we will understand the implementation of a logic function using OR and AND
gates with the help of examples.
Example 1
Consider a logic function AB + A + ABC, we have to implement this Boolean expression using
OR and AND gates. To realize this logic function, we will follow the following steps ?
Step 1 - Start with the final expression, i.e. output. We can see that there are three terms in
the logic function. Hence, we require a three input OR gate for this.
Step 2 - As we can see, the first and third terms, i.e. AB and ABC of the logic function
require AND operation. The term AB requires a two input AND gate, and the term ABC
requires three input AND gate.
Step 3 - Finally, by combining the hardware realized in step-1 and setp-2, we get the
complete hardware logic realization of the given logic function, which is shown in the
following figure.
In this way, we can easily implement a logic function using OR and AND gates
Example 2
Consider another logic function (A+B).(A+C).(B+C), we have to implement this logic function
using OR and AND gates only.
By observing this logical expression, we can interpret that we need a three input AND gate at
the final output stage, and three two input OR gates to implement each of the three terms.
Therefore, we can follow the following steps to implement the given logic function using OR
and AND gates ?
Step 1 - Implement the final expression of the given logic function. As we can observe, we
can implement it using a three-input AND gate as shown in the following figure.
Step 2 - Now, implement the three terms of the given logic function, i.e. (A+B), (A+C), (B+C),
by using three two-input OR gates as shown in the following figure.
Step 3 - Finally, obtain the complete hardware realization of the given logic function by
combining the logic circuits of the above two steps. The following figure shows the
implementation of complement logic function using OR and AND gates.
Therefore, in the above two examples, we studied the process of implementation of a logic
function using OR and AND gates.
Implementation of Logic Function using NAND Gates
Like any other logic gate, the NAND gate can also be used to implement logic functions. The
important point to remember about the NAND gate is that it performs the inverse operation
of the basic AND gate. Therefore, the output of the NAND gate is equivalent to the
complement of the output of the AND gate.
Now, let us understand the realization of logic functions using NAND gates with the help of
examples. Consider a logic function of three variables,
We have implement this logic function by using NAND gates only.
In the NAND gate implementation of a logic function, we use only NAND gates at input as well
output sides of the logic circuit.
The step-by- step procedure for the realization of a logic function using NAND gates is shown
below
Step 1
First, realize the given logic function using AND gates and OR Gates. The AND-OR realization
of the given logic function is shown in Figure-2.
Step 2
Convert all the AND gates into NAND gates by introducing a bubble or complement at the
output of each AND gate. But, in order to compensate the effect of bubble, the input of the
next gate must be complemented by introducing a bubble. The implementation of AND with
bubble at output is shown in Figure-3.
Step 3
Now, to maintain uniformity at the input, if a logic gate has one input with a bubble
(complement), then the other input must also have a bubble. To compensate the effect of the
bubble, the output of the preceding logic gate must be introduced with a bubble. This
implementation is shown in Figure-4.
Step 4
According to the DeMorgan's Theorem, an OR gate with two bubbled inputs is equal to a
NAND gate, i.e. A'+B' = (AB)'. Therefore, we can replace all the bubbled OR gate with NAND
gates. By doing this, we get the final logic implementation of the given logic function using
NAND gates only. This implementation is shown in Figure-5.
In this way, we can realize any logic (or Boolean) function using NAND gates only.
Simplification of expressions
Minimization of Boolean Functions
Boolean functions are used to represent logical expressions in terms of sum of minterms or
product of maxterms. Number of these literals (minterms or maxterms) increases as the
complexity of the digital circuit increases. This can lead to large and inefficient circuits.
By minimizing Boolean functions, we can reduce the number of logic gates, simplify circuit
design, and improve performance in terms of speed, cost, and power consumption.
For example, let the Boolean function:
F2 = x’y’z + x’yz + xy’
This function can be further minimized by
Grouping first two terms: x’y’z + x’yz = x’(y’z + yz)
Simplify inside: y’z + yz = z, so it becomes x’z
Add the remaining term: x’z + xy’
The minimized Boolean function will be:
F2 = xy' + x’z
In the diagram below we can see the implementation of the Boolean function:
Instead of building a circuit with 3 big parts (one for each term), the minimized version needs
only 2.
Various methods and techniques, such as Karnaugh maps, Quine-McCluskey algorithm, and
the use of Boolean algebra, help achieve this simplification.
Main Methods for Minimizing BooleanExpressions
The two main methods for minimizing Boolean expressions are:
1. Boolean Algebra
Boolean algebra involves using a set of rules and laws (like distributive, associative, and
complement laws) to simplify Boolean expressions. This method focuses on applying algebraic
manipulations to reduce the complexity of the expression by eliminating redundant terms.
Table lists 12 basic rules that are useful in manipulating and simplifyingBoolean expressions.
Rules 1 through 9 will be viewed in terms of theirapplication to logic gates. Rules 10 through
12 will be derived in terms ofthe simpler rules and the laws previously discussed.
Refer Number systems unit for names of rules.
The above rules are explained in AND and OR form in detail below
Rule 1. A + 0 = A
Rule 2.A + 1 = 1
Rule 3. A . 0 = 0
Rule 4. A . 1 = A
Rule 5. A + A = A
̅=1
Rule 6. A + A
Rule 7. A . A = A
̅=0
Rule 8. A . A
Rule 9. A = ̿A
Rule 10. A + AB = A
Rule 11. A + AB = A + B
This rule can be proved as follows:
A + AB = (A + AB) + AB Rule 10: A = A + AB
= (AA + AB) + AB Rule 7: A = AA
=AA +AB +AA +AB Rule 8: adding AA = 0
= (A + A)(A + B) Factoring
= 1. (A + B) Rule 6: A + A = 1
=A + B Rule 4: drop the 1
Rule 12. (A + B)(A + C) = A + BC
This rule can be proved as follows:
(A + B)(A + C) = AA + AC + AB + BC Distributive law
= A + AC + AB + BC Rule 7: AA = A
= A( 1 + C) + AB + BC Rule 2: 1 + C = 1
= A. 1 + AB + BC Factoring (distributive law)
= A(1 + B) + BC Rule 2: 1 + B = 1
= A. 1 + BC Rule 4: A . 1 = A
= A + BC
Examples for Simplification
1. Simplify the Boolean expression:
XYZ + XY’Z + XYZ’
Solution:
XYZ + XY’Z + XYZ’ = XZ(Y + Y’) + XYZ’
= XZ + XYZ’, as Y + Y’ = 1
= X(Z + YZ’)
= X[(Z + Y).(Z + Z’)], by distributive law
= X[(Z + Y).1], as Z + Z’ = 1
= X(Z + Y)
= X(Y + Z).
2. Simplify the Boolean expression in order to prove L.H.S = R.H.S.
XY + YZ + Y’Z = XY + Z
Solution:
L.H.S. = XY + YZ + Y’Z
= XY + Z(Y + Y’)
= XY + Z.1, as Z + Z’ = 1
= XY + Z
= R.H.S.
⇒L.H.S = R.H.S.
3. Draw the truth table for the expression: A = B’.C.
Solution: The truth table for the given expression is given below:
B C B’ A = B’.C
0 0 1 0
0 1 1 1
1 0 0 0
1 1 0 1
4. Draw the truth table for the expression: (A + B)(A + C).
Solution: The truth table for the given expression is given below:
A B C A+B A+C (A+B)(A+C)
0 0 0 0 0 0
0 0 1 0 1 0
0 1 0 1 0 0
0 1 1 1 1 1
1 0 0 1 1 1
1 0 1 1 1 1
1 1 0 1 1 1
1 1 1 1 1 1
Example: Simplify the Boolean function F = AB + (AC)′ + AB′C(AB + C).
Solution: F = AB + (AC)′ + AB′C(AB + C)
= AB + A′ + C′+ AB′[Link] + AB′C.C
= AB + A′ + C′ + 0 + AB′C (B.B′ = 0 and C.C = C)
= ABC + ABC′ + A′ + C′ + AB′C (AB = AB(C + C′) = ABC + ABC′)
= AC(B + B′) + C′(AB + 1) + A′
= AC + C′+A′ (B + B′ = 1 and AB + 1 = 1)
= AC + (AC)′ = 1
2. K-Map
The Karnaugh Map is a graphical technique used to simplify Boolean expressions by grouping
adjacent cells containing 1s (minterms). This visual method makes it easier to identify patterns
and minimize the expression by combining terms that can be grouped together. It is especially
useful for functions with 4 or fewer variables.
Questions Based on Minimization of Boolean Functions
Example: Minimize the following Boolean function using algebraic manipulation
F = ABC'D' + ABC'D + AB'C'D + ABCD + AB'CD + ABCD' AB'CD'
Solution:
1. Using Boolean Laws
F = ABC'(D' + D) + AB'C'D + ACD(B + B') ACD'(B + B')
= ABC' + AB'C'D + ACD + ACD'
= ABC' + AB'C'D + AC(D + D')
= ABC' + AB'C'D + AC
= A(BC' + C) + AB'C'D
= A(B + C) + AB'C'D
= AB + AC + AB'C'D
= AB + AC + AC'D
= AB + AC + AD
2. Using K-Map
The above figure highlights the prime implicants in green, red and blue.
The green one spans the whole third row, which gives us – AB
The red one spans 4 squares, which gives us – AD
The blue one spans 4 squares, which gives us – AC
So, the minimized Boolean expression is - AB + AC + AD
Example
Using Boolean algebra techniques, simplify this expression:
AB + A(B + C) + B(B + C)
Solution
Step 1:Apply the distributive law to the second and third terms in the
expression, as follows:
AB + AB + AC + BB + BC
Step 2: Apply rule 7 (BB = B) to the fourth term.
AB + AB + AC + B + BC
Step 3: Apply rule 5 (AB + AB = AB) to the first two terms.
AB + AC + B + BC
Step 4: Apply rule 10 (B + BC = B) to the last two terms.
AB + AC + B
Step 5: Apply rule 10 (AB + B = B) to the first and third terms.
B+AC
At this point the expression is simplified as much as possible.