MODULE-1

FUNDAMENTAL OF DIGITAL LOGIC

BOOLEAN ALGEBRA: - Boolean algebra is a type of algebra that is created

by operating the binary system. In the year 1854, George Boole, an English
mathematician, proposed this algebra. This is a variant of Aristotle’s
propositional logic that uses the symbols 0 and 1, or True and False.
Boolean algebra is concerned with binary variables and logic operations.
Boolean Algebra is fundamental in the development of digital electronics
systems as they all use the concept of Boolean Algebra to execute
commands. Apart from digital electronics this algebra also finds its
application in Set Theory, Statistics, and other branches of mathematics.
What is Boolean Algebra?
Boolean Algebra is a branch of algebra that deals with boolean
values—true and false. It is fundamental to digital logic design and
computer science, providing a mathematical framework for describing
logical operations and expressions
Boolean Algebra Operations
Various operations are used in Boolean algebra but the basic operations
that form the base of Boolean Algebra are.
●​ Negation or NOT Operation
●​ Conjunction or AND Operation
●​ Disjunction or OR Operation
These operations have their own symbols and precedence and the table
added below shows the symbol and the precedence of these operators.
Operator Symbol Precedence

NOT ‘ (or) ⇁ First

AND . (or) ∧ Second

OR + (or) ∨ Third

We can easily define these operations using two boolean variables.

Let’s take two boolean variables A and B that can have any of the two
values 0 or 1, i.e. they can be either OFF or ON. Then these operations are
explained as,
Negation or NOT Operation
Using the NOT operation reverse the value of the Boolean variable from 0
to 1 or vice-versa. This can be understood as:
●​ If A = 1, then using NOT operation we have (A)’ = 0
●​ If A = 0, then using the NOT operation we have (A)’ = 1
●​ We also represent the negation operation as ~A, i.e if A = 1, ~A =
0
Conjunction or AND Operation
Using the AND operation satisfies the condition if both the value of the
individual variables are true and if any of the value is false then this
operation gives the negative result. This can be understood as,
●​ If A = True, B = True, then A . B = True
●​ If A = True, B = False, Or A = false, B = True, then A . B = False
●​ If A = False, B = False, then A . B = False
Disjunction (OR) Operation
Using the OR operation satisfies the condition if any value of the individual
variables is true, it only gives a negative result if both the values are false.
This can be understood as,
●​ If A = True, B = True, then A + B = True
●​ If A = True, B = False, Or A = false, B = True, then A + B = True
●​ If A = False, B = False, then A + B = Falses
Boolean Algebra Table
Given Below is the Expression for the Boolean Algebra
Operation Symbol Definition

AND Operation ⋅ or ∧ Returns true only if both inputs are true.

OR Operation + or ∨ Returns true if at least one input is true.

NOT Operation ¬ or ∼ Reverses the input.

XOR Operation ⊕ Returns true if exactly one input is true.

NAND Operation ↓ Returns false only if both inputs are true.

NOR Operation ↑ Returns false if at least one input is true.

XNOR Operation ↔ Returns true if both inputs are equal.

Boolean Expression and Variables

Boolean expression is an expression that produces a Boolean value when
evaluated, i.e. it produces either a true value or a false value. Whereas
boolean variables are variables that store Boolean numbers.
P + Q = R is a Boolean phrase in which P, Q, and R are Boolean variables
that can only store two values: 0 and 1. The 0 and 1 are the synonyms for
false and True and are used in Boolean Algebra, sometimes we also use
“Yes” in place of True and “No” in place of False.
Thus, we can say that statements using Boolean variables and operating
on Boolean operations are Boolean Expressions. Some examples of
Boolean expressions are,
●​ A + B = True
●​ A.B = True
●​ (A)’ = False

Boolean Algebra Terminologies

There are various terminologies related to Boolean Algebra, which are
used to explain various parameters of Boolean Algebra. That includes,
●​ Boolean Variables
●​ Boolean Function
●​ Literal
●​ Complement
●​ Truth Table
Boolean Variables
Variables used in Boolean algebra that store the logical value of 0 and 1
are called the boolean variables. They are used to store either true or false
values. Boolean variables are fundamental in representing logical states or
propositions in Boolean expressions and functions.
Boolean Function
A function of the Boolean Algebra that is formed by the use of Boolean
variables and Boolean operators is called the Boolean function. It is formed
by combining Boolean variables and logical expressions such as AND, OR,
and NOT. It is used to model logical relationships, conditions, or operations.
Literal
A variable or the complement of the variable in Boolean Algebra is called
the Literal. Literals are the basic building blocks of the boolean expressions
and functions. They represent the operands in logical operations.
Complement
The inverse of the Boolean variable is called the complement of the
variable. The complement of 0 is 1 and the complement of 1 is 0. It is
represented by ‘ or (¬) over the variable. Complements are used to
represent logical negations in Boolean expressions and functions.
Truth Table
Table containing all the possible values of the logical variables and the
combination of the variable along with the given operation is called the truth
table. The number of rows in the truth table depends on the total Boolean
variables used in that function. It is given by using the formula,
Number of Rows in Truth Table = 2n
where “n” is the number of Boolean variables used.
Truth Tables in Boolean Algebra
A truth table represents all the combinations of input values and outputs in
a tabular manner. All the possibilities of the input and output are shown in it
and hence the name truth table. In logic problems, truth tables are
commonly used to represent various cases. T or 1 denotes ‘True’ & F or 0
denotes ‘False’ in the truth table.
Example: Draw the truth table of the conditions A + B and A.B where
A and b are boolean variables.
Solution:
The required Truth Table is,
A B Y = A.B
X=A+B

T T T T

T F T F

F T T F

F F F F

Boolean Algebra Rules

In Boolean Algebra there are different fundamental rules for logical
expression.
●​ Binary Representation: In Boolean Algebra the variables can
have only two values either 0 or 1 where 0 represents Low and 1
represents high. These variables represents logical states of the
system.
●​ Complement Representation: The complement of the variables
is represented by (¬) or (‘) over the variable. This indicates logical
negation or inversion of the variable’s value. So Complement of
variable A can be represented by A‾A,if the value of A=0 then its
complement is 1.
●​ OR Operation: The OR operation is represented by (+) between
the Variables. OR operation returns true if at least one of the
operands is true. For Examples let us take three variables A,B,C
the OR operation can be represented as A + B + C.
●​ AND Operation: The AND Operation is denoted by (.) between
the Variables. AND operation returns true only if all the operands
are true. For Examples let us take three variables A,B,C the AND
operation can be represented A.B.C or ABC.
Laws for Boolean Algebra
The basic laws of the Boolean Algebra are added in the table added below,
Law OR form AND form

Identity Law P+0=P P.1 = P

Idempotent Law P+P=P P.P = P

Commutative Law P+Q=Q+P P.Q = Q.P

Associative Law P + (Q + R) = (P + Q) + R P.(Q.R) = (P.Q).R

Distributive Law P + QR = (P + Q).(P + R) P.(Q + R) = P.Q + P.R

Inversion Law (A’)’ = A (A’)’ = A

De Morgan’s Law (P + Q)’ = (P)’.(Q)’ (P.Q)’ = (P)’ + (Q)’

Let’s learn about these laws in detail.

Identity Law
In the Boolean Algebra, we have identity elements for both AND(.) and
OR(+) operations. The identity law state that in boolean algebra we have
such variables that on operating with AND and OR operation we get the
same result, i.e.
●​ A + 0 = A
●​ A.1 = A
Commutative Law
Binary variables in Boolean Algebra follow the commutative law. This law
states that operating boolean variables A and B is similar to operating
boolean variables B and A. That is,
●​ A. B = B. A
●​ A + B = B + A
Associative Law
Associative law state that the order of performing Boolean operator is
illogical as their result is always the same. This can be understood as,
●​ ( A . B ) . C = A . ( B . C )
 ●​ ( A + B ) + C = A + ( B + C)
Distributive Law
Boolean Variables also follow the distributive law and the expression for
Distributive law is given as:
●​ A . ( B + C) = (A . B) + (A . C)
Inversion Law
Inversion law is the unique law of Boolean algebra this law states that, the
complement of the complement of any number is the number itself.
●​ (A’)’ = A
Apart from these other laws are mentioned below:
AND Law
AND law of the Boolean algebra uses AND operator and the AND law is,
●​ A . 0 = 0
●​ A . 1 = A
●​ A . A = A
OR Law
OR law of the Boolean algebra uses OR operator and the OR law is,
●​ A + 0 = A
●​ A + 1 = 1
●​ A + A = A
De Morgan’s Laws are also called De morgan’s Theorem. They are the
most important laws in Boolean Algebra and these are added below under
the heading Boolean Algebra Theorem
Boolean Algebra Theorems
There are two basic theorems of great importance in Boolean Algebra,
which are De Morgan’s First Laws, and De Morgan’s Second
Laws. These are also called De Morgan’s Theorems. Now let’s learn about
both in detail.
De Morgan’s First laws
De Morgan’s Law states that the complement of the product (AND) of two
Boolean variables (or expressions) is equal to the sum (OR) of the
complement of each Boolean variable (or expression).
(P.Q)’ = (P)’ + (Q)’
The truth table for the same is given below:
P Q (P)’ (Q)’ (P.Q)’ (P)’ + (Q)’

T T F F F F

T F F T T T
 P Q (P)’ (Q)’ (P.Q)’ (P)’ + (Q)’

F T T F T T

F F T T T T

We can clearly see that truth values for (P.Q)’ are equal to truth values for
(P)’ + (Q)’, corresponding to the same input. Thus, De Morgan’s First Law
is true.
De Morgan’s Second laws
Statement: The Complement of the sum (OR) of two Boolean variables (or
expressions) is equal to the product(AND) of the complement of each
Boolean variable (or expression).
(P + Q)’ = (P)’.(Q)’
Proof:
The truth table for the same is given below:
P Q (P)’ (Q)’ (P + Q)’ (P)’.(Q)’

T T F F F F

T F F T F F

F T T F F F

F F T T T T

We can clearly see that truth values for (P + Q)’ are equal to truth values
for (P)’.(Q)’, corresponding to the same input. Thus, De Morgan’s Second
Law is true.
Articles related to Boolean Algebra:
●​ Properties of Boolean Algebra
●​ Principle of Mathematical Induction
●​ Logic Gates
Solved Examples on Boolean Algebra
Draw Truth Table for P + P.Q = P
Solution:
The truth table for P + P.Q = P
 P Q P.Q P + P.Q

T T T T

T F F T

F T F F

F F F F

In the truth table, we can see that the truth values for P + P.Q is exactly the
same as P.
Draw Truth Table for P.Q + P + Q
Solution:
The truth table for P.Q + P + Q
P Q P.Q P.Q + P + Q

T T T T

T F F T

F T F T

F F F F

Solve A‾+B⋅CA+B⋅C
Solution:
Using De Morgan’s Law
A‾+B.C=A‾.(B+C)A+B.C=A.(B+C)
Using Distributive Law
A‾.(B+C)=A‾.B+A‾.CA.(B+C)=A.B+A.C
So, the simplified expression for the given equation
A‾.(B+C)=A‾.B+A‾.CA.(B+C)=A.B+A.C
Where is Boolean Algebra Used?
Boolean Algebra finds applications in many other fields of science related
to digital logic design, computer science, telecommunications, etc. It will
equip you with the basics of designing and analyzing digital circuits;
therefore, this is an introduction to the backbone of modern digital
electronics. Boolean Algebra also forms a framework of logical expressions
essential in simplification and optimization while programming and
designing algorithms.
Digital Logic Design:
Boolean Algebra acts as the backbone of digital logic design, being the
most important element in the creation and analysis of digital circuits used
in computers, smartphones, and all other electronic devices. It helps
simplify the logic gates and circuits so that in the design of digital systems,
they can be effectively designed and optimized.
Computer Science:
In computer science, Boolean Algebra is utilized in the design and study of
algorithms, particularly in fields that require decision-making processes. It’s
vital in database query optimization, where Boolean logic is utilized to filter
and obtain specific data based on circumstances.
Telecommunications:
Boolean Algebra finds application in the design and analysis of
communication systems in telecommunication. More specifically, it is used
in error detection and correction mechanisms. It is also used in the
modulation and encoding of signals so that data is efficiently and accurately
transmitted over networks.
Artificial Intelligence (AI):
Boolean Algebra is vital in AI, notably in the construction of
decision-making algorithms and neural networks. It’s used to model logical
thinking and decision trees, which are crucial in machine learning and
expert systems.
Electrical Engineering:
In electrical engineering, Boolean Algebra is employed to analyze and
design switching circuits, which are important in the operation of electrical
networks and systems.It aids in the optimization of these circuits, ensuring
minimal energy loss and effective functioning.
Advantages, Disadvantages, and Applications
Advantages
●​ Simplifies the design and analysis of digital circuits.
●​ Reduces the complexity of logical expressions and functions.
●​ Enhances efficiency in digital logic design and computer
programming.
Disadvantages
●​ Limited to binary values, which may not always represent
real-world complexities.
●​ Requires a strong understanding of logical operators and rules.
Applications
●​ Digital electronics and circuit design.
●​ Computer programming and algorithm optimization.
●​ Telecommunications for logical signal processing.
●​ Set theory and mathematical logic.

LOGIC GATES:-

Logic Gates are the fundamental building blocks in digital electronics.

There are basically seven main types of logic gates which are used to
perform various logical operations in digital systems. By combining
different logic gates complex operations are performed and circuits like
flip-flop, counters, and processors are designed.
What is a Logic Gate?
A logic gates are an electronic circuit that are designed by using electrical
components like diodes, transistors, resistors, and more. It is used to
perform logical operations based on the inputs provided to it and gives
logical output that can be either high(1) or low(0). The operation of logic
gates is based on the Boolean algebra or mathematics. Logic gate founds
its uses in our day to day basis such as in the architecture of our
telephone, laptops, tablets an memory devices.

Types of Logic Gates

Logic gates can be broadly classified into three main categories
AND GATE
An AND gate is used to perform logical Multiplication of binary input. The
Output state of the AND gate will be high(1) if both the input are high(1)
,else the output state will be low(0) if any of the input is low(0).
The Boolean Expression or logic for the AND gate is the logical
multiplication of inputs denoted by a full stop or single dot as
A.B=X
The value of X will be True when both the inputs will be True.

Properties of AND Gate

The following are two main properties of the AND gate
●​ AND gate can accept two or more than two input values at a
time.
●​ When all of the inputs are logic 1, the output of this gate is logic
1.
OR GATE
OR GATE is most widely used digital logic circuit. The output state of OR
gate will be high i.e.,(1) if any of the input state is high or 1, else output
state will be low i.e., 0.
The Boolean Expression for the OR gate is the logical addition of inputs
denoted by plus sign(+) as
X= A+B
The value of X will be high(true) when one of the inputs is set to high
(true).

Properties of OR Gate
An OR gate have the following two properties:
●​ It can have two or more input lines at a time.
●​ When all of the inputs to the OR gate are low or logic 0, the
output of it is low or logic 0.
NOT GATE
In digital electronics, the NOT gate is one of the basic logic gate having
only a single input and a single output. It is also known as inverter or
inverting buffer. When the input signal is “low” the output signal is “high”
and vice-versa.
The Boolean expression of NOT Gate is as follows
Y = Ā or
Y = A’
the value of Y will be high when A will be low.

Properties of NOT Gate

●​ The output of a NOT gate is complement or inverse of the input
applied to it.
●​ NOT gate takes only one output.
NOR GATE
The NOR gate is the type of universal logic gate. It takes two or more
inputs and gives only one output. The output state of the NOR gate will be
high(1) when all the inputs are low(0). NOR gate returns the complement
result of the OR gate. It is basically a combination of two basic logic gates
i.e., OR gate and NOT gate.
The Boolean expression of NOR gate is as follows :
If A and B are considered as two inputs, and O as output, then the
expression for a two input NOR gate will be
O = (A + B)’
The value of O will be true when all of its inputs are set to 0.
Properties of NOR Gate
The following are two important properties of NOR gate:
●​ A NOR gate can have two or more inputs and gives an output.
●​ A NOR gate gives a high or logic 1 output only when its all inputs
are low or logic 0.
NAND GATE
The NAND Gate is another type of Universal logic gate. The NAND gate or
“Not AND” is the combination of two basic logic gates AND gate and the
NOT gate connected in series. It takes two or more inputs and gives only
one output. The output of the NAND gate will give result high(1) when
either of its input is high(1) or both of its input are low(0). In simple, it
performs the inverted operation of AND gate.
The Boolean Expression of NAND Gate is as follows
Say we have two inputs, A and B and the output is called X, then the
expression is
X = (A . B)’
Properties of NAND Gate
The following are the two key properties of NAND Gate
●​ NAND gate can take two or more inputs at a time and produces
one output based on the combination of inputs applied.
●​ NAND gate produces a low or logic 0 output only when its all
inputs are high or logic 1.
XOR GATE
In digital electronics, there is a specially designed logic gate named, XOR
gate, which is used in digital circuits to perform modulo sum. It is also
referred to as Exclusive OR gate or Ex-OR gate. it is used extensively in
arithmetic logic circuits., logic comparators and error detection circuits. The
XOR gate can take only two inputs at a time and give an output. The
output of the XOR gate is high(1) only when its two inputs are dissimilar
i.e., if one of them is low(0) then other one will be high(1).
Say we have two inputs, A and B and the output is called X, then the
expression is
The Boolean expression of XOR Gate is as follows
X = A’B + AB’
Properties of XOR Gate
The following two are the main properties of the XOR gate:
●​ It can accept only two inputs at a time. There is nothing like a
three or more input XOR gate.
●​ The output of the XOR gate is logic 1 or high, when its inputs are
dissimilar.
XNOR GATE
The XNOR is the combination of XOR gate and NOT gate. The output of
the XNOR gate is high(1) when both the inputs are high(1) or low(0). In
other words, the output of the XNOR gate is high(1) when both the inputs
are the same. the XNOR gate can be sometimes be called as Equivalence
gate. In simple words, The XNOR gate is the complement of the XOR gate.
The following is the Boolean expression of the XNOR gate,
Y=A⊙B
Here, A and B are the input variables and Y is the output variable.
This expression can also be written as follows,
Y = AB + A’B’
We can also express the operation of an XNOR gate using XOR gate logic
as follows:
 Y = (A ⊕ B)’

Properties of XNOR Gate

The following are two key properties of XNOR gate:
●​ XNOR gate takes only two inputs and produces one output.
●​ The output of the XNOR gate is high or logic 1 only when it has
similar inputs.
Applications of Logic Gates
Logic gates are the fundamental building blocks of all digital circuits and
devices like computers. Here are some key digital devices in which logic
gates are utilized to design their circuits.
●​ Computers
●​ Microprocessors
●​ Microcontrollers
●​ Digital and smart watches
●​ Smartphones, etc.
Advantages of Logic Gates
●​ B
​ asic Functions : Logic gates carry out basic logical functions like
AND, OR, NOT, XOR, NAND, and NOR. All digital operations and
dat respective processing rely on these functions.
 ●​ S
​ peed : Their extremely high speed rates make them an essential
feature in today’s information processing systems that aim for
quickness in data analysis.
●​ Reliability : Being elements whose behaviors are accurately
defined means there is no uncertainty about how they behave
when used as part of a system.
●​ Scalability : Digital systems complexity increases by
interconnecting and replicating these components without
significant variations in size or complexity.
●​ Low Cost : Logic Gate costs are relatively low from production
viewpoint thus making it popular among those who want to
construct digital circuits inexpensively.
●​ Low Power Consumption : Power consumption is minimal with
logic gates; hence less energy is needed for operating hence
suitable for use with gadgets without batteries or devices running
low power consumption applications at all times.
Disadvantages of Logic Gates
Despite their numerous advantages, logic gates have their disadvantages.
The following paragraphs discuss some shortcomings of logic gates.
●​ Complexity : The advancement and complexity of digital systems
results in increasing number of logic gates and their
interconnections, which causes designs that are very difficult to
handle and troubleshoot.
●​ Propagation Delay : Small delay in the propagating signal is
introduced with every logic gate. When several such gates are
chained together, these delays can add up and have adverse
effects on the overall speed and performance of the circuit.
●​ Noise Sensitivity : Even noise, interference, and interfering fields
can make logic gates sensitive to errors in the output signal.
Proper shielding and conditioning of signals at times are needed
to reduce these effects.
●​ Power Dissipation : While logic gates are essentially low power,
their dissipation can grow with the complexity of the circuit.
Heavy energy loss can generate thermal energy which
necessitates supplementary cooling systems.
Minimization of Boolean Functions
every boolean function can be expressed as a sum of minterms or a
product of maxterms. Since the number of literals in such an expression is
usually high, and the complexity of the digital logic gates that implement a
Boolean function is directly related to the complexity of the algebraic
expression from which the function is implemented, it is preferable to have
the most simplified form of the algebraic expression. The process of
simplifying the algebraic expression of a boolean function is
called minimization. Minimization is important since it reduces the cost
and complexity of the associated circuit. For example, the function
can be minimized to .
The circuits associated with above expressions is –

It is clear
from the above image that the minimized version of the expression takes a
less number of logic gates and also reduces the complexity of the circuit
substantially. Minimization is hence important to find the most economic
equivalent representation of a boolean function. Minimization can be done
using Algebraic Manipulation or K-Map method. Each method has it’s own
merits and demerits.
Minimization using Algebraic Manipulation –
This method is the simplest of all methods used for minimization. It is
suitable for medium sized expressions involving 4 or 5 variables. Algebraic
manipulation is a manual method, hence it is prone to human error.
Common Laws used in algebraic manipulation :
every boolean function can be expressed as a sum of minterms or a
product of maxterms. Since the number of literals in such an expression is
usually high, and the complexity of the digital logic gates that implement a
Boolean function is directly related to the complexity of the algebraic
expression from which the function is implemented, it is preferable to have
the most simplified form of the algebraic expression. The process of
simplifying the algebraic expression of a boolean function is
called minimization. Minimization is important since it reduces the cost
and complexity of the associated circuit. For example, the function
can be minimized to .
The circuits associated with above expressions is –

It is clear
from the above image that the minimized version of the expression takes a
less number of logic gates and also reduces the complexity of the circuit
substantially. Minimization is hence important to find the most economic
equivalent representation of a boolean function. Minimization can be done
using Algebraic Manipulation or K-Map method. Each method has it’s own
merits and demerits.
Minimization using Algebraic Manipulation –
This method is the simplest of all methods used for minimization. It is
suitable for medium sized expressions involving 4 or 5 variables. Algebraic
manipulation is a manual method, hence it is prone to human error.
Common Laws used in algebraic manipulation :
1.​ A+A’ = 1
2.​ A+A’B = A + B
3.​ A + AB = A
●​ Example 1 – Minimize the following boolean function using
algebraic manipulation-

●​ Solution – Properties refer to the three common laws mentioned

above.

Minimization using K-Map –

The Algebraic manipulation method is tedious and cumbersome. The
K-Map method is faster and can be used to solve boolean functions of
upto 5 variables.
Example 2 – Consider the same expression from example-1 and minimize
it using K-Map.
●​ Solution – The following is a 4 variable K-Map of the given

expression.
●​
●​ 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+AD+AC