DIGITAL ELECTRONICS
BASICS
Boolean Algebra:
The main operations of Boolean algebra are:
The Conjunction (ꓥ)
The Disjunction (ꓦ)
The Negation (¬)
Boolean Algebra Laws:
Logic Gate:
Logic gates are primarily implemented using diodes or transistors acting as electronic
switches.
It can also be constructed using vacuum tubes, electromagnetic relays, fluidic logic,
optics or even mechanical elements.
1. ‘NOT’ Gate (Inverter):
It represents not logical operator which is also known as ‘inverter’.
It is a unary operator, which simply complement the input.
Here switch off will turn on the bulb.
Here switch on will turn off the bulb.
This is because current will flow from low resistance path.
2. ‘OR’ Gate:
It is a logic gate that implements logical disjunction.
The output will be high if at least one of the input lines is high.
3. ‘AND’ Gate:
It is logic gate that implements logical conjunction.
Output will be high if and only if all inputs are high otherwise low.
4. ‘NOR’ Gate:
The output will be high if and only if all the inputs are low.
Or simple s ‘OR’ Gate followed by an inverter.
NOR gate is also called ‘Universal Gate’ because it can be used to implement any
other logic gate.
Conclusion:
(A + B)’ = A’ (A +A)’ ≠ A
(A + 0)’ = A’ ((A + B)’ + C)’ ≠ (A + (B + C)’)’
(A + 1)’ = 0 (A + B)’ = (B + A)’
(A + A’)’ = 0
5. ‘NAND’ Gate:
The output will be low if and only if all inputs are high.
Or simply an AND Gate followed by an inverter.
NAND Gate is also called ‘Universal Gate’ because it can be used to implement any
other logic Gate.
Conclusion:
(A·0)’ = 1 (A·A’) ≠ A
(A·A’)’ = 1 ((A·B)’ · C)’ ≠ (A · (B·C)’)’
(A·1)’ = A’ (A·B)’ = (B·A)’
(A·A)’ = A’
6. ‘EX-OR’ Gate:
A ⊕ B = AB + AB
For two inputs, output will be high if and only if both the input values are different.
The EX-OR (X-OR) Gate is a logical Gate that gives ‘high’ as output when the
number of ‘input-highs’ are odd.
Conclusion:
(A ⊕ (A ⊕ A) ≠ A
(A ⊕ ((A ⊕ B) ⊕ C) = (A ⊕ (B ⊕ C))
0) = A
(A ⊕ (A ⊕ B) = (B ⊕ A)
1) = A’
(A ⊕
A) = 0
A’) = 1
Question
7. ‘EX-NOR’ Gate:
For two inputs, output will be high if and only if both the input values are same.
AB = A B + AB
The EX-NOR (X-NOR) gate is a logic Gate that gives output ‘high’ when the number
of ‘input-lows’ are even.
Conclusion:
(A ⊙ (A ⊙ A) ≠ A
(A ⊙ ((A ⊙ B) ⊙ C) = (A ⊙ (B ⊙ C))
0) = A’
(A ⊙ (A ⊙ B) = (B ⊙ A)
1) = A
(A ⊙
A) = 1
A’) = 0
Question:
Note:
A⊕ B≠A⊙ B A⊕ B⊕ C=A⊙ B⊙ C
A⊕ B⊕ C⊕ D≠A⊙ B⊙ C⊙ D
X-OR and X-NOR Gate behave as a complement of each other if the number of input
variables (A, B, C, ….) are even.
X-OR and X-NOR Gate behave same if number input variables (A, B, C, ….) are odd.
Note:
BOOLEAN EXPRESSIONS
Boolean expressions are the methods using which we save the information about the
Boolean function, that when we get value ‘1’ and when we get value ‘0’ as output.
So, we convert the truth table of the function into expression, reading which we can
understand when the output is ‘1’ and when it is ‘0’.
There are two popular approaches for writing these expressions:
1. Sum of Product (SOP): It remembers when we get value ‘1’.
2. Product of Sum (POS): It remembers when we get value ‘0’.
Make a note of this as we are studying Boolean function, remembering both ‘0’ and
‘1’ is not required, so we can either concentrate on ‘0’ or ‘1’.
Power of SOP and POS is same i.e., any Boolean functions can be represented using
both SOP and POS.
Mathematically speaking, we should choose (0 or 1), whatever is less in number
because then it will be easy to represent.
1. Sum of Product (SOP):
A sum of product forms the expression contains product term (AND term) which are
sum together, that’s why it called sum of product.
Each product term (AND term) consists of one or more literals (variables) appearing
either in complemented or uncomplemented form. E.g.- A’B + B’C’ + ABC
Minterm: A product term which contains all the literals (variables) either in
complemented or uncomplemented form is called ‘Minterm’.
If the number of literals (variables) = ‘n’, then number of minterms = 2n.
The result of a product term must always be ‘1’, if a literal is having value ‘1’ then it
is okey, but if not, then complement those which is ‘0’ to make it ‘1’.
There is only one input sequence of variables for any minterm on which the output is
‘1’, so it represents information.
Then the sum of all product term (minterm) to form a function, and functions will
have value ‘1’, if at least one of the product terms (minterm) is ‘1’.
Canonical Logic Form:
Either in POS or SOP form, it is not essential that all product or sum terms contains
all the literals.
Canonical SOP Form:
In a sum of product form expression, if each AND term (product term) contains all the
literals (variables) appearing either in complemented or uncomplemented form. Then
that expression form is called canonical SOP. E.g.- A’BC + AB’C’ + ABC
2. Product of Sum (POS):
A product of sum (POS) form of expression contains sum (OR) terms which are
product (AND) together, that’s why called product of sum expression.
Each sum term consists of one or more literals (variables) appearing either in
complemented or uncomplemented form. E.g.- (A’ + B)(B’ + C’)(A + C).
A sum term which contains all the literals (variables) either in complemented or
uncomplemented form is called ‘Maxterm’.
If the number of literals = ‘n’, then the number of maxterms = 2n.
The result of the sum term must be ‘0’, so if a variable is having vale ‘0’ then it is
okey, but if not then we complement the variable to make it ‘0’.
There is only one input sequence for which the output of a maxterm is ‘0’ because, it
requires all values as zero.
Then the product of all sum term (maxterm), form a function, and function will have a
value ‘0’, if any of the sum term (maxterm) is ‘0’.
Canonical POS Form:
In a POS expression, if each sum term consists of all the literals (variables) appearing
either in complemented or uncomplemented form, then it is called canonical POS
form.
E.g.- (A’ + B + C)(A + B’ + C’)(A + B + C)
Number of Functions Possible:
Question:
With ‘n’ Boolean variables, how many different Boolean functions are possible?
Answer:
With ‘n’ binary variables, we can generate 2n combinations.
And as we know that a Boolean function can also have only two possible values,
either ‘0’ or ‘1’.
So, total number of different functions possible will be 2^(2n).
Similarly, we can generalize this idea as x^(yz) are the total number of functions
possible, where x is the nature (binary, ternary, …) of the function, y is nature (binary,
ternary, …) of the variable and z is the number of variables.
Complementation:
Let us consider a function f(a, b, c, d, …, 0, 1, +, ·), then the complement of the
function is defined as f’(a’, b’, c’, d’, …, 1, 0, ·, +).
OR→AND, AND→OR, ⊙→⊕, ⊕→⊙, then we will call them complement of the
That means, when all the variables are replaced by their complements, 0→1, 1→0,
function.
We can directly put a ‘bar’ on the entire Boolean expression to find the complement
of the function.
We can also directly deal in minterms and maxterms to write complement function.
Duality:
Let us consider a function f(a, b, c, d, …, z, 0, 1, +, ·), then the dual of the function is
defined as fd(a, b, c, d, …, z, 1, 0, ·, +).
⊙→⊕, ⊕→⊙, then they are called dual functions.
When the nature of variables remains same but 0→1, 1→0, OR→AND, AND→OR,
When we take dual of a function, then the functionality of a function remains the
same but a positive logic system is transformed into negative logic system.
If a function works corrects in positive logic system, then it must also work correct in
negative logic system as it does not depend on magnitude.
Neutral Function:
A function ‘f’ is said to be neutral if, it has equal number of minterms and maxterms.
|minterm| = |maxterm|
If a function is not neutral, then it can never be ‘Self Dual’ or ‘Orthogonal’ but if a
function is neutral then function may or may not be ‘Self Dual’ or ‘Orthogonal’.
f(A, B, C) = ∑m(0, 1, 6, 7) and f(A, B, C) = ∏M(2, 3, 4, 5). Here |minterms| = 4 and |
maxterm| = 4.
Self-Dual Function:
A function is said to be self-dual, if both the function and its dual are same.
f = fd
Example: f(A, B, C) = AB + BC + CA
Mutually Exclusive Minterm:
A pair of a minterm and its complement is called mutually exclusive minterm pair.
Check whether a Function is Self-Dual or Not:
Step-1: Check whether function is neutral or not (minterm = maxterm), if function is
not neutral then it will never be a self-dual function but if, function is neutral then go
to step-2.
Step-2: Must have exactly one minterm from each pair of mutually exclusive
minterms.
Step-3: If both previous conditions are true, then function is self-dual otherwise not.
Number of Self-Dual Functions Possible:
If number of variables in function = ‘n’.
Then the number of minterms possible = 2n.
The number of mutually exclusive pairs = 2n/2 = 2(n-1).
Then the total number of ‘Self-Dual’ functions = 2^(2(n-1)).
Relationship between Neutral & Self-Dual Function:
Self-Dual function is a subset of Neutral Function.
Question: Which of the followings given below functions are the self-dual functions?
Orthogonal Function:
A function is said to be orthogonal, if the compliment and dual of the function are
same.
f’ = fd
Example: f(A, B) = A ⊕ B
fd(A, B) = A ⊙ B (dual of function ‘f’)
f’(A, B) = A ⊙ B (complement of function ‘f’)
Hence, function ‘f’ is an orthogonal function.
Note:
A function can never be both orthogonal and self-dual because, it will imply that the
function is same to its complement, which is never possible.
Hence, a function and its complement can never be equal (f ≠ f’).
Check whether a Function is Orthogonal or Not:
Step-1: Check whether function is neutral or not (minterm = maxterm), if function is
not neutral then it will never be an orthogonal function but if, function is neutral then
go to step-2.
Step-2: It must have half number of mutually exclusive pairs (complete pair).
Step-3: If both previous conditions are true, then function is orthogonal otherwise not.
Number of Orthogonal Functions Possible:
If number of variables in function = ‘n’.
Then the number of minterms possible = 2n.
The number of mutually exclusive pairs = 2n/2 = 2(n-1).
Then, among 2(n-1), half number of pairs = 2(n-1)/2 = 2(n-2).
Then, the number of orthogonal functions = (2(n-1))C(2(n-2)).
Relationship between Neutral, Self-Dual & Orthogonal Functions:
Both Self-Dual and Orthogonal are the subset of Neutral function.
But Self-Dual and Orthogonal are mutually exclusive set of each other.
Question: Which of the followings given below functions are the orthogonal functions?
SIMPLIFICATION OF BOOLEAN EXPRESSION
There are following methods for simplifying a Boolean expression.
1. Using Karnaugh-Map
2. Using algebraic method (Boolean Laws)
1. Karnaugh Map:
It is a graphical representation, represents truth table by pictorial form, provides a
systematic method for simplifying or minimizing a Boolean expression.
For a ‘n’ variable K-Map, there will be 2n cells addressed by a ‘Gray Code’.
Each cell corresponds to one minterm or maxterm.
Sequence will always be ABCD.
Sequence will always be ABCD.
Sequence will always be ABC.
Sequence will always be AB.
K-Map for Product of Sum (POS):
Sequence will always be A + B + C + D.
Minimal Function:
A function is said to be minimal, if it is representing the function expression, if it is
using minimal number of literals to represent the function.
Rules of Grouping in K-Map:
Every minterm must be covered.
Group must have contiguous calls (circular).
Group must be in horizontal or vertical fashion (circular).
Number of cells in a group must be in power of 2 → (1, 2, 4, 8, …, 2n).
Try to make largest group possible, so that number of literals in the expression can be
reduced.
Can also take ‘Don’t Care’ term, if it helps in creating the larger group, otherwise
don’t consider it in the group.
Consider new implicant, if it covering some new minterm.
Don’t Care Condition:
Don’t Care cases are those cases which can never occur logically in that function.
It is not essential to cover don’t care conditions, but if Don’t Care are helping to
generate bigger prime implicants, then we can use them.
Examples of K-Map
First try to cover those minterms which do not have an option.
For some functions, more than one minimal Boolean expressions are possible.
Implicant:
Collection of adjacent minterms is called implicant.
Prime Implicant (PI):
An implicant is called prime implicant (PI), if it is not subset of any other implicant
(group).
Overlapping of minterms while grouping is allowed.
Example: f(A, B, C, D) = ∑ {4 ,5 , 6 , 7 , 8 , 10 ,11, 13 , 14 }
m
There are 4 possible solutions of the given example:
Essential Prime Implicant (EPI):
If a prime implicant (PI) have some unique minterm, which no other prime implicant
covers then, it is called essential prime implicant (EPI).
Essential prime implicant (EPI) must always be present in the minimal Boolean
Expression.
Example-1:
Example-2:
Example-3:
Example-4:
Functions:
Example-1:
Example-2:
Example-3:
Irredundant Function:
A function ‘f’ is said to be irredundant, if no product term can be removed from the
function without changing the functional capability of the function.
Minimal Function:
A function is said to be minimal, if it is representing the function expression, if it is
using minimal number of literals to represent the function.
Note:
If a function is irredundant then, it may or may not be minimal, but if a function is
minimal, then it is irredundant.
F(X, Y, Z) = XZ’ + Y’Z’ + YZ + XZ, this function is irredundant but not minimal.
Minimal ⊆ Irredundant
F(X, Y, Z) = X + YZ + Y’Z’, this function is bot minimal and irredundant.
Absorption Law:
A + AB = A A + A’B = A + B
A(A + B) = A A(A’ + B) = AB
Compensation Theorem:
AB + A’C + BC = AB + A’C // Ignoring BC
(A + B)(A’ + C)(B + C) = (A + B)(A’ + C) // Ignoring B + C
AND-OR Equivalence:
AND-OR (NAND-NAND) Implementation:
SOP Implementation:
Example: AB + CD
OR-AND (NOR-NOR) Implementation:
POS Implementation:
Example: (A + B)(C + D)
Implementing Every Gate with NAND Gate:
1. NOT Gate:
2. AND Gate:
3. OR Gate:
4. NOR Gate:
5. EX-OR Gate:
6. EX-NOR Gate:
Implementing Every Gate with NOR Gate:
1. NOT Gate:
2. AND Gate:
3. OR Gate:
4. NAND Gate:
5. EX-OR Gate:
6. EX-NOR:
Conclusion:
Number of Gates used:
Functionally Complete Function:
As we know, there are only three fundamental Boolean operators NOT, AND & OR.
All the other operators are derived from these operators.
We understand NOT along with OR gives NOR and NOT along with AND gives
NAND, which are used as universal Gates.
Any Boolean operation or function can be implemented with NAND or NOR Gates.
If any function can implement NOT along with either AND or OR then, we indirectly
prove that function can also implement any other function, so function can said to be
functionally complete.
Support of ‘0’, ‘1’ or ‘complemented form of variables’ is not allowed.
Partially Functionally Complete:
A function is said to be partially functionally complete, if it can implement any digital
circuit with the support of logic ‘0’, ‘1’ as input line.
But we can not use complemented form of variables.
Example-1:
Example-2:
Example-3:
