Boolean Algebra and Digital Logic Design
Dr. Preeti Mehta
September 11, 2025
Contents
1 Minterms 2
1.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.4 Canonical Sum of Products (SOP) . . . . . . . . . . . . . . . . . . . . . 2
2 Maxterms 2
2.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.2 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.3 Relationship between Minterms and Maxterms . . . . . . . . . . . . . . . 3
2.4 Canonical Product of Sums (POS) . . . . . . . . . . . . . . . . . . . . . 3
3 Precedence of Logical Operators 3
3.1 Operator Hierarchy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
3.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
4 Formation of Boolean Expressions from Truth Tables 4
4.1 Sum of Products (SOP) Method . . . . . . . . . . . . . . . . . . . . . . . 4
4.2 Product of Sums (POS) Method . . . . . . . . . . . . . . . . . . . . . . . 4
5 Universal Gates 5
5.1 Implementation of all logic gates using NAND gate . . . . . . . . . . . . 5
5.2 Implementation of all logic gates using NOR gate . . . . . . . . . . . . . 6
6 Conclusion 7
7 Practice Questions 7
7.1 Answer Guidelines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1
2 MAXTERMS Boolean Algebra and Digital Logic
1 Minterms
1.1 Definition
A minterm is a Boolean expression where all variables appear exactly once, either in
true or complemented form, connected by AND operations. For n variables, there are 2n
possible minterms.
1.2 Notation
For variables A, B, and C, minterms are denoted as mi where i is the decimal equivalent
of the binary combination:
m0 = A · B · C (0002 = 010 ) (1)
m1 = A · B · C (0012 = 110 ) (2)
m2 = A · B · C (0102 = 210 ) (3)
m3 = A · B · C (0112 = 310 ) (4)
m4 = A · B · C (1002 = 410 ) (5)
m5 = A · B · C (1012 = 510 ) (6)
m6 = A · B · C (1102 = 610 ) (7)
m7 = A · B · C (1112 = 710 ) (8)
1.3 Properties
Each minterm evaluates to 1 for exactly one combination of input variables
The sum of all minterms for n variables always equals 1
Minterms are mutually exclusive: mi · mj = 0 for i ̸= j
1.4 Canonical Sum of Products (SOP)
Any Boolean function can be expressed as a sum of minterms:
X
f (A, B, C) = mi
i
where the sum includes all minterms for which f = 1.
2 Maxterms
2.1 Definition
A maxterm is a Boolean expression where all variables appear exactly once, either in
true or complemented form, connected by OR operations.
2
3 PRECEDENCE OF LOGICAL OPERATORS Boolean Algebra and Digital Logic
2.2 Notation
Maxterms are denoted as Mi where i corresponds to the row where the function equals
0:
M0 = A + B + C (9)
M1 = A + B + C (10)
M2 = A + B + C (11)
M3 = A + B + C (12)
M4 = A + B + C (13)
M5 = A + B + C (14)
M6 = A + B + C (15)
M7 = A + B + C (16)
2.3 Relationship between Minterms and Maxterms
De Morgan’s theorem establishes the relationship:
mi = Mi
Mi = mi
2.4 Canonical Product of Sums (POS)
Any Boolean function can be expressed as a product of maxterms:
Y
f (A, B, C) = Mj
j
where the product includes all maxterms for which f = 0.
3 Precedence of Logical Operators
3.1 Operator Hierarchy
The precedence of Boolean operators, from highest to lowest:
1. Parentheses ( )
2. NOT (Complement) A, A′ , ¬A
3. AND (Conjunction) A · B, AB, A ∧ B
4. OR (Disjunction) A + B, A ∨ B
5. XOR (Exclusive OR) A ⊕ B
6. NAND A ↑ B
7. NOR A ↓ B
3
4 FORMATION OF BOOLEAN EXPRESSIONS FROM
Boolean
TRUTH
AlgebraTABLES
and Digital Logic
3.2 Examples
A + B · C = A + (B · C) (17)
A · B + C = (A · B) + C (18)
A · B + C · D = (A · B) + (C · D) (19)
4 Formation of Boolean Expressions from Truth Ta-
bles
4.1 Sum of Products (SOP) Method
To derive SOP from a truth table:
1. Identify rows where output f = 1
2. Write the minterm for each row
3. Sum all identified minterms
Example: For the truth table:
A B C f
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 1
SOP expression: f = m1 + m2 + m4 + m7 = ABC + ABC + ABC + ABC
4.2 Product of Sums (POS) Method
To derive POS from a truth table:
1. Identify rows where output f = 0
2. Write the maxterm for each row
3. Take the product of all identified maxterms
Using the same truth table: POS expression: f = M0 · M3 · M5 · M6 = (A + B +
C)(A + B + C)(A + B + C)(A + B + C)
4
5 UNIVERSAL GATES Boolean Algebra and Digital Logic
5 Universal Gates
5.1 Implementation of all logic gates using NAND gate
NOT Gate
A = (A · A)′
AND Gate
′
A · B = (A · B)′′ = (A · B)′ · (A · B)′
OR Gate
′
A + B = (A · B)′ = (A · A)′ · (B · B)′
XOR Gate
′ ′
A ⊕ B = A · (A · B)′ · B · (A · B)′
XNOR Gate
A ⊙ B = (A ⊕ B)′
5
5 UNIVERSAL GATES Boolean Algebra and Digital Logic
5.2 Implementation of all logic gates using NOR gate
NOT Gate
A = (A + A)′
OR Gate
′
A + B = (A + B)′′ = (A + B)′ + (A + B)′
AND Gate
′
A · B = (A + B)′ = (A + A)′ + (B + B)′
XOR Gate
′
A ⊕ B = (A + (A + B)′ )′ + (B + (A + B)′ )′
6
7 PRACTICE QUESTIONS Boolean Algebra and Digital Logic
XNOR Gate
A ⊙ B = (A ⊕ B)′
6 Conclusion
This document has covered the fundamental concepts of Boolean algebra and digital logic
design, including minterms and maxterms for canonical expressions, operator precedence
for proper evaluation, methods for deriving Boolean expressions from truth tables, and the
implementation of all logic gates using universal NAND and NOR gates. These concepts
form the foundation for more advanced digital system design, including combinational
and sequential circuit analysis and synthesis.
Understanding these principles enables engineers to design efficient digital systems, op-
timize Boolean expressions, and implement complex logic functions using minimal hard-
ware resources. The universal nature of NAND and NOR gates makes them particularly
valuable in practical circuit implementations where gate variety needs to be minimized
for cost and complexity considerations.
7 Practice Questions
P
Question 1: Given the Boolean function f (A, B, C) = m(1, 3, 5, 7), express this
function in:
(a) Canonical SOP form
(b) Canonical POS form
(c) Simplified SOP form using Boolean algebra
Question 2: Design a 3-input majority function using only NAND gates. The output
should be 1 when at least 2 of the 3 inputs are 1. Show the truth table, derive the Boolean
expression, and draw the complete circuit diagram.
Question 3: Evaluate the following Boolean expressions considering operator prece-
dence:
(a) A + B · C + D · E
(b) A + B · C + D · E + F
(c) (A + B) · C + D ⊕ E · F
Show the step-by-step evaluation with proper parentheses.
Question 4: Convert the following truth table to both SOP and POS forms, then
implement the SOP form using only NOR gates:
7
7 PRACTICE QUESTIONS Boolean Algebra and Digital Logic
X Y Z F
0 0 0 1
0 0 1 0
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 1
Question 5: Prove that any Boolean function can be implemented using only NAND
gates by showing the step-by-step conversion of the following expression to NAND-only
form: f (A, B, C, D) = AB + CD + ABC
Question 6: Design a full adder circuit using only NAND gates. The full adder has
three inputs (A, B, Cin) and two outputs (Sum, Cout). Show:
(a) Truth table
(b) Boolean expressions for Sum and Cout
(c) Complete circuit diagram using only NAND gates
(d) Calculate the total number of NAND gates required
7.1 Answer Guidelines
For SOP/POS conversions, clearly identify minterms and maxterms
When drawing circuits, label all gates and connections clearly
Show all intermediate steps in Boolean algebra simplifications
Verify your answers by testing with sample input combinations
For universal gate implementations, start with the basic expression and systemati-
cally replace each operation
