Fundamentals of Computers & Digital Systems Manipal University Jaipur (MUJ)
BACHELOR OF COMPUTER
APPLICATIONS
SEMESTER 1
FUNDAMENTALS OF COMPUTERS &
DIGITAL SYSTEMS
Unit 5: Boolean Algebra and Logic Gates 1
Fundamentals of Computers & Digital Systems Manipal University Jaipur (MUJ)
Unit 5
Boolean Algebra and Logic Gates
Table of Contents
SL Fig No / Table / SAQ /
Topic Page No
No Graph Activity
1 Introduction - -
3
1.1 Learning Objectives - -
2 Boolean Algebra - 1
4-6
2.1 Binary Operations - -
3 De-Morgan’s law 1, 2, 3, 4 2 7-10
4 Simplification of Boolean algebra - 3
11-16
4.1 Standard Form of Boolean Expression - -
5 Basic and Universal Logic Gates - 4
5.1 Basic Gate: NOT Gate, AND Gate, OR - - 17-22
Gate, XOR Gate, XNOR Gate
5.2 Universal Gate: NAND Gate, NOR Gate - -
6 Summary - - 23
7 Terminal Questions - - 24
8 Answers - - 24-25
Unit 5: Boolean Algebra and Logic Gates 2
Fundamentals of Computers & Digital Systems Manipal University Jaipur (MUJ)
1. INTRODUCTION
Boolean algebra and logic gates provide the foundational framework for designing and
understanding digital systems. They enable the manipulation and processing of binary
information, allowing us to create the complex and sophisticated technologies that shape our
digital world. Whether you're designing a simple logic circuit or working on advanced
computer architecture, a solid grasp of Boolean algebra and logic gates is essential for
success in the field of computer science and digital electronics.
Boolean algebra, named after the mathematician George Boole, provides a rigorous and
mathematical framework for working with binary variables. Unlike traditional algebra,
which operates on real numbers, Boolean algebra deals with binary values – often denoted
as '0' and '1.' These binary values correspond to 'false' and 'true,' 'off' and 'on,' or 'no' and
'yes' in various contexts.
The core operations in Boolean algebra include AND, OR, and NOT. These operations are
represented by logical operators, which take one or more binary inputs and produce binary
outputs.
1.1 Learning Objectives
At the end of this unit, students should be able to:
❖ Define Boolean algebra and its significance in digital logic.
❖ Explain the basic elements of Boolean algebra, such as binary variables, logical operators,
and truth tables.
❖ Comprehend De-Morgan's law and its role in simplifying Boolean expressions.
❖ Use Boolean algebra rules and techniques to simplify logical expressions.
❖ Identify and describe the basic logic gates: NOT, AND, and OR gates.
❖ Demonstrate the ability to design and implement simple logic circuits using basic logic
gates (NOT, AND, OR).
Unit 5: Boolean Algebra and Logic Gates 3
Fundamentals of Computers & Digital Systems Manipal University Jaipur (MUJ)
2. BOOLEAN ALGEBRA
Boolean algebra, named after the mathematician George Boole, is a fundamental
mathematical system that plays a pivotal role in computer science, digital electronics, and
various engineering fields—at its core, Boolean algebra deals with binary information,
making it the ideal tool for modelling and analysing digital systems, where everything boils
down to two states: true or false, on or off, 1 or 0.
Binary Foundation
At the heart of Boolean algebra lies the binary number system, which employs only two
digits, 0 and 1, to represent numbers and make logical decisions. This simplicity forms the
basis for Boolean logic, as it aligns with the binary states of digital electronic components
such as transistors, which can be in one of two states—on or off.
2.1 Binary Operations
Boolean algebra revolves around three primary logical operations: AND, OR, and NOT.
i. AND Operation (Conjunction):
• The AND operation returns true (1) only when both inputs are true (1). Otherwise,
it returns false (0).
• Symbolically represented as '∧'.
• For example, consider two binary inputs A and B. The AND operation (A ∧ B)
yields 1 only when both A and B are 1; otherwise, it results in 0.
Truth Table:
A B A^B
0 0 0
0 1 0
1 0 0
1 1 1
Unit 5: Boolean Algebra and Logic Gates 4
Fundamentals of Computers & Digital Systems Manipal University Jaipur (MUJ)
ii. OR Operation (Disjunction):
• The OR operation returns true (1) when at least one of its inputs is true (1). It
returns false (0) only when both inputs are false (0).
• Symbolically represented as '∨'.
• For example, for inputs A and B, the OR operation (A ∨ B) produces 1 if either A or
B (or both) is 1; otherwise, it results in 0.
Truth Table:
A B A∨B
0 0 0
0 1 1
1 0 1
1 1 1
iii. NOT Operation (Negation):
• The NOT operation inverts the input; it changes true (1) to false (0) and vice versa.
• Symbolically represented as '¬' or using a bar over the variable.
• For example, for input A, the NOT operation (¬A or A̅ ) produces the opposite value
of A.
Truth Table:
A ¬A
0 1
1 0
Unit 5: Boolean Algebra and Logic Gates 5
Fundamentals of Computers & Digital Systems Manipal University Jaipur (MUJ)
SELF-ASSESSMENT QUESTIONS – 1
1. What is the result of the Boolean operation A AND 0?
a) 0
b) 1
c) A
d) NOT A
2. Which of the following Boolean operations is represented by the symbol '+'?
a) AND
b) OR
c) XOR
d) NOT
3. What is the binary equivalent of the decimal number 9?
a) 1001
b) 1010
c) 1100
d) 1110
4. A ∨ B = ? when A=0 and B=1.
Unit 5: Boolean Algebra and Logic Gates 6
Fundamentals of Computers & Digital Systems Manipal University Jaipur (MUJ)
3. DE-MORGAN’S LAW
• De Morgan's Laws are a fundamental set of rules in Boolean algebra that describe
negating (invert) complex logical expressions involving the AND and OR operations.
There are two De Morgan's Laws:
i. De Morgan's First Law
ii. De Morgan's Second Law
i. De Morgan's First Law :
The complement (negation) of the union of two sets A and B is equal to the intersection of
the complements of A and B.
Mathematically: (A ∪ B)' = A' ∩ B'
Fig 1: Venn Diagram for (A ∪ B)’
Consider two sets, A and B, represented by circles in a Venn diagram:
• The shaded region represents A ∪ B, the union of sets A and B as shown in figure 1.
• The complement (negation) of A ∪ B is the region outside the shaded area, represented
by (A ∪ B)'.
Now, let's apply De Morgan's First Law:
• A' represents the complement of set A, which is the region outside circle A.
• B' represents the complement of set B, which is the region outside circle B.
The intersection of A' and B' is the region outside both circles A and B, which is exactly the
same as (A ∪ B)' as shown in figure 2.
Unit 5: Boolean Algebra and Logic Gates 7
Fundamentals of Computers & Digital Systems Manipal University Jaipur (MUJ)
Fig 2: Venn Diagram for A’ ∩ B’
Hence Mathematically, (A ∪ B)' = A' ∩ B' is proved.
ii. De Morgan's Second Law (for Sets):
The complement (negation) of the intersection of two sets, A and B, is equal to the union of
the complements of A and B.
Mathematically: (A ∩ B)' = A' ∪ B'
Fig 3: Venn Diagram for (A ∩ B)’
Consider the same two sets A and B represented by circles in a Venn diagram:
• The shaded region represents A ∩ B, which is the intersection of sets A and B.
• The complement (negation) of A ∩ B is the region outside the shaded area, represented
by (A ∩ B)' as shown in Figure 3.
Unit 5: Boolean Algebra and Logic Gates 8
Fundamentals of Computers & Digital Systems Manipal University Jaipur (MUJ)
Now, let's apply De Morgan's Second Law:
• A' represents the complement of set A, which is the region outside circle A.
• B' represents the complement of set B, which is the region outside circle B.
The union of A' and B' is the region outside either circle A or B, which is exactly the same as
(A ∩ B)' as shown in Figure 4.
Fig 4: Venn Diagram for A’ ∪ B’
Mathematically, (A ∩ B)' = A' ∪ B' is proved.
Unit 5: Boolean Algebra and Logic Gates 9
Fundamentals of Computers & Digital Systems Manipal University Jaipur (MUJ)
SELF-ASSESSMENT QUESTIONS – 2
5. What does De Morgan's First Law state?
a) The AND operation distributes over the OR operation.
b) The OR operation distributes over the AND operation.
c) The complement of the OR operation is equal to the OR of the complements.
d) The complement of the AND operation is equal to the AND of the
complements.
6. Which of the following is an application of De Morgan's Laws?
a) Adding two binary numbers.
b) Simplifying Boolean expressions.
c) Finding the sum of a series of numbers.
d) Calculating the square root of a number.
Unit 5: Boolean Algebra and Logic Gates 10
Fundamentals of Computers & Digital Systems Manipal University Jaipur (MUJ)
4. SIMPLIFICATION OF BOOLEAN ALGEBRA
Boolean algebraic expressions can be simplified using a few fundamental principles to its
variables, literals, and phrases.
a. Identity Law:
• A+0=A
• A*1=A
These laws state that the ORing of any Boolean variable with 0 or the ANDing of any
Boolean variable with 1 results in the original variable.
Example:
Let's say we have a Boolean variable A. Applying the identity law:
A + 0 = A (ORing with 0)
A * 1 = A (ANDing with 1)
b. Null Law:
• A + A' = 1,
• A * A' = 0
The null law states that the ORing of a Boolean variable with its complement (NOT of
the variable) results in 1, and the ANDing of a variable with its complement results in
0.
Example:
Using Boolean variable A:
• A + A' = 1 (ORing with its complement)
• A * A' = 0 (ANDing with its complement)
c. Idempotent Law:
• A+A=A
• A * A = A):
The idempotent law states that ORing or ANDing a variable with itself has no effect;
the result is the original variable.
Unit 5: Boolean Algebra and Logic Gates 11
Fundamentals of Computers & Digital Systems Manipal University Jaipur (MUJ)
Example:
Using Boolean variable A:
A + A = A (ORing with itself)
A * A = A (ANDing with itself)
d. Inverse Law:
• A + A' = 1
• A * A' = 0
This law specifies that the ORing of a Boolean variable with its complement (NOT of the
variable) results in 1, and the ANDing of a variable with its complement results in 0.
Example:
Using Boolean variable A:
A + A' = 1 (ORing with its complement)
A * A' = 0 (ANDing with its complement)
e. Commutative Law:
• A+B=B+A
• A*B=B*A
The commutative law states that the order of variables in an OR or AND operation
doesn't affect the result.
Example:
Using Boolean variables, A and B:
• A + B = B + A (ORing in different orders)
• A * B = B * A (ANDing in different orders)
f. Associative Law:
• (A + B) + C = A + (B + C)
• (A * B) * C = A * (B * C)):
The associative law states that the grouping of variables in an OR or AND operation
doesn't affect the result.
Unit 5: Boolean Algebra and Logic Gates 12
Fundamentals of Computers & Digital Systems Manipal University Jaipur (MUJ)
Example:
Using Boolean variables, A, B, and C:
(A + B) + C = A + (B + C) (Associative in OR)
(A * B) * C = A * (B * C) (Associative in AND)
g. Distributive Law:
• A + (B * C) = (A + B) * (A + C)
• A * (B + C) = (A * B) + (A * C)):
The distributive law describes how OR and AND operations can be distributed over one
another.
Example:
Using Boolean variables A, B, and C:
• A + (B * C) = (A + B) * (A + C) (Distributive with OR over AND)
• A * (B + C) = (A * B) + (A * C) (Distributive with AND over OR)
h. Absorption Law:
• A + (A * B) = A
• A * (A + B) = A):
The absorption law states that when you combine a variable with the result of an AND
or OR operation involving itself, it simplifies the variable.
Example:
Using Boolean variables, A and B:
A + (A * B) = A (Absorption with OR)
A * (A + B) = A (Absorption with AND)
i. Demorgan’s Law:
• (A + B)' = A' * B'
• (A * B)' = A' + B'
Unit 5: Boolean Algebra and Logic Gates 13
Fundamentals of Computers & Digital Systems Manipal University Jaipur (MUJ)
De Morgan's Laws describe distributing the NOT operation over OR and AND operations.
Example:
Simplify: AB + A (B + C) + B (B + C)
Solution: AB + AB + AC + BB + BC
AB + AB + AC + B + BC
AB + AC + B + BC
AB + AC + B
B + AC
Simplify: C + (BC)'
Solution: C + (B + C) '
= ( C + C') + B'
= 1 + B'
=1
4.1 Standard form of Boolean expression (Canonical Form)
Boolean expressions can be represented in different forms, with the two most common
forms being the Sum of Products (SOP) and Product of Sums (POS). The standard form of
Unit 5: Boolean Algebra and Logic Gates 14
Fundamentals of Computers & Digital Systems Manipal University Jaipur (MUJ)
a Boolean expression refers to a simplified representation where terms are combined using
AND and OR operations. It typically consists of minterms (in SOP) or maxterms (in POS).
Boolean expressions can be evaluated, simplified, and implemented in a much more
methodical and straightforward manner with standardisation.
a. The Sum of Products (SOP) Form: (sum of minterms)
The resulting expression after summing two or more product terms by Boolean addition is
called a sum-of-products (SOP). These product terms are also called ‘min-terms’.
Example:
If a function is given as; f (A, B, C)=∑m(3,5,6,7)
Y=m3+m5+m6+m7
Y=A 'BC+AB 'C+ABC '+ABC
b. The Products of Sums (POS) Form: (sum of max terms)
The resulting expression after multiplying two or more sum terms is called a Product-of-sum
(POS). These product terms are also called ‘min-terms’. These sum terms are also called max
terms.
Example:
If a function is given as; F (A, B, C) =ΠM (0,1,2,4)
Y=M0* M1* M2 * M4
Y=(A+B+C) (A+B+C') (A+B'+C) (A'+B+C)
Unit 5: Boolean Algebra and Logic Gates 15
Fundamentals of Computers & Digital Systems Manipal University Jaipur (MUJ)
SELF-ASSESSMENT QUESTIONS – 3
7. Which of the following is an application of De Morgan's Laws?
a) Adding two binary numbers.
b) Simplifying Boolean expressions.
c) Finding the sum of a series of numbers.
d) Calculating the square root of a number.
8. What is the standard form for a Boolean expression in SOP (Sum of Products)
form?
a) A sum of OR operations
b) A product of AND operations
c) A combination of AND and OR operations
d) A difference of two variables
Unit 5: Boolean Algebra and Logic Gates 16
Fundamentals of Computers & Digital Systems Manipal University Jaipur (MUJ)
5. BASIC AND UNIVERSAL LOGIC GATES
5.1 Basic Gate: NOT Gate, AND Gate, OR Gate.
Basic Gates form the building blocks of digital circuits. These gates manipulate binary (0 and
1) signals based on certain logical operations. The fundamental logic gates include:
a. Not Gate (Inverter)
A NOT gate, also known as an inverter, is a fundamental digital logic gate in electronics and
computer science. Its primary function is to perform the negation operation on a binary input
signal. In simple terms, a NOT gate takes an input signal and produces the opposite output.
If the input is 0 (or 'false'), the NOT gate outputs 1 (or 'true').
If the input is 1 (or 'true'), the NOT gate outputs 0 (or 'false').
Symbol:
Truth Table:
b. AND Gate
An AND gate is a fundamental digital logic gate in electronics and computer science. It has
two or more input terminals and a single output terminal. The AND gate produces a true
(logical 1) output only when all of its input terminals are true (logical 1). In other words, it
performs the logical "AND" operation, and its output is true if and only if all of its input
Unit 5: Boolean Algebra and Logic Gates 17
Fundamentals of Computers & Digital Systems Manipal University Jaipur (MUJ)
signals are true; otherwise, the output is false (logical 0). The symbol for an AND gate
typically consists of the AND operator (∧) enclosed within a circle, and it is used to create
and control logical conditions in various digital circuits and systems.
Symbol and Truth Table
c. OR Gate
An OR gate is a digital logic gate that takes one or more binary inputs and produces an output
based on the logical OR operation. The output of an OR gate is "true" (1) if at least one of its
inputs is "true" (1), and it is "false" (0) only when all of its inputs are "false" (0).
Symbol and Truth Table
Unit 5: Boolean Algebra and Logic Gates 18
Fundamentals of Computers & Digital Systems Manipal University Jaipur (MUJ)
d. XOR Gate
An XOR gate, the "Exclusive OR" gate, is a digital logic gate used in electronics and computer
engineering. It has two or more inputs and a single output. The XOR gate outputs a true
(logical 1) value if an odd number of its inputs are true, and it produces a false (logical 0)
value if an even number of inputs are true.
Symbol and Truth Table
e. XNOR Gate
An XNOR gate, also known as an equivalence gate or an exclusive-NOR gate, is a digital logic
gate in electronics. The XNOR gate has two or more inputs and one output. It performs a
specific logical operation on its inputs and produces an output based on that operation.
The XNOR gate operates as follows:
• If an even number of its inputs are set to the binary value '1' (true), it outputs '1' (true).
• If an odd number of its inputs are set to '1,' it outputs '0' (false).
Symbol and Truth Table
Unit 5: Boolean Algebra and Logic Gates 19
Fundamentals of Computers & Digital Systems Manipal University Jaipur (MUJ)
5.2 Universal Gate: NAND Gate, NOR Gate
A universal gate, in digital electronics, refers to a logic gate that can be used to implement
any other basic logic gate (AND, OR, NOT, NAND, NOR, XOR, XNOR).
The two most common universal gates are:
i. NAND Gate:
A NAND gate, short for "NOT-AND" gate, is a fundamental logic gate in digital electronics. It
has two or more inputs and one output. The primary function of a NAND gate is to perform
a logical AND operation on its inputs and then negate (invert) the result.
Here's how a NAND gate works:
• If all its inputs are 1 (true), the output is 0 (false).
• If any of its inputs are 0 (false), the output is 1 (true).
Symbol and Truth Table:
ii. NOR Gate
A NOR gate, in digital electronics, is a fundamental logic gate that performs a logical NOR
operation. It has two or more input terminals (typically two) and one output terminal. The
NOR gate produces a high output (often represented as '1' or 'true') only when none of its
input terminals are at a high level (0 or 'false'). In other words, it provides a 'true' output if
and only if all of its inputs are 'false.'
Unit 5: Boolean Algebra and Logic Gates 20
Fundamentals of Computers & Digital Systems Manipal University Jaipur (MUJ)
SELF-ASSESSMENT QUESTIONS – 4
9. Which of the following gates is NOT a universal gate?
a) AND gate
b) OR gate
c) NOT gate
d) NAND gate
10. Which Boolean operation does the AND gate correspond to?
a) Addition
b) Multiplication
c) Subtraction
d) Division
11. What is the standard form of a Boolean expression that represents the ORing
of multiple product terms?
a) Sum of Products (SOP)
b) Product of Sums (POS)
c) Standard of Sum (SOS)
d) Sum of Sums (SOS)
Unit 5: Boolean Algebra and Logic Gates 21
Fundamentals of Computers & Digital Systems Manipal University Jaipur (MUJ)
12. Which logic gate is considered a universal gate and can be used to create any
other basic logic gate?
a) AND gate
b) OR gate
c) XOR gate
d) NAND gate
13. What does an XNOR gate output when all of its inputs are '1'?
a) '1'
b) '0'
c) Undefined
d) 'X'
14. Which gate is the opposite of the XOR gate and outputs '1' when the number
of '1's in its inputs is even?
a) NOR gate
b) OR gate
c) AND gate
d) XNOR gate.
Unit 5: Boolean Algebra and Logic Gates 22
Fundamentals of Computers & Digital Systems Manipal University Jaipur (MUJ)
6. SUMMARY
Boolean algebra is a branch of mathematics that deals with binary variables and logical
operations. It's fundamental in digital logic design and computer science. Key concepts in
Boolean algebra include binary operations, De Morgan's laws, simplification of expressions,
and the use of logic gates.
Binary Operations: Binary operations in Boolean algebra involve the use of two binary
variables (0 and 1) and logical operations like AND, OR, NOT, XOR, and XNOR. These
operations are the building blocks for creating more complex logical expressions.
De-Morgan’s Law: De Morgan's laws are fundamental rules in Boolean algebra that describe
how to negate complex logical expressions involving AND and OR operations. They include
De Morgan's First Law (negation of OR) and De Morgan's Second Law (negation of AND).
Simplification of Boolean Algebra: Simplification in Boolean algebra involves reducing
complex logical expressions to their simplest form. It's essential for digital circuit design.
Techniques include using Boolean algebraic rules, Karnaugh maps, and algorithms like
Quine-McCluskey.
Standard Form of Boolean Expression: The standard form of a Boolean expression
represents a simplified version of the logical expression, either as a Sum of Products (SOP)
or a Product of Sums (POS), where terms are combined using AND and OR operations.
Basic and Universal Logic Gates: Basic logic gates are the fundamental building blocks of
digital circuits, performing logical operations. They include the NOT gate, AND gate, OR gate,
XOR gate, and XNOR gate. Universal gates, such as the NAND gate and NOR gate, can be used
to implement any other basic logic gate, making them versatile components in digital circuit
design.
Unit 5: Boolean Algebra and Logic Gates 23
Fundamentals of Computers & Digital Systems Manipal University Jaipur (MUJ)
7. TERMINAL QUESTIONS
1. Draw the logic diagram for the simplified expression using basic logic gates (NOT, AND,
OR, XOR, XNOR). (6.1)
2. Explain how De Morgan's laws can be applied to simplify complex Boolean expressions
and provide an example. (3)
3. Define the standard form of a Boolean expression and explain its significance in digital
circuit design. (4.1)
4. Elucidate the fundamental principles of Boolean algebraic expressions. (4)
5. Simplify: XY + X (B+Z) + Y(Y+Z) (4)
6. Explain universal gates with their symbols and truth table. (5.2)
8. ANSWERS
Self-Assessment Answers
1. 0
2. OR
3. 1001
4. 1
5. The complement of the AND operation is equal to the AND of the complements.
6. Simplifying Boolean expressions.
7. Products (AND operations)
8. A product of AND operations
9. AND Gate
10. Multiplication
11. Sum of Products (SOP)
12. NAND Gate
13. .1
14. XNOR Gate
Terminal Answers
1. Refer to Section 5.1
2. Refer to Section 3
3. Refer to Section 4.1
Unit 5: Boolean Algebra and Logic Gates 24
Fundamentals of Computers & Digital Systems Manipal University Jaipur (MUJ)
4. Refer to Section 4
5. Refer to Section 4
6. Refer to Section 5.2
Unit 5: Boolean Algebra and Logic Gates 25
