Module-2: Boolean Algebra and Logic Circuits

Dr. M. Rambabu

GITAM, Visakhapatnam

Boolean Algebra&Logic Circuits Dept. of CSE, GITAM, Visakhapatnam Dr. M. Rambabu 1/50
Boolean Algebra and Logic Gates

Why Boolean Algebra?

Foundation of all digital circuits and processors.
Allows simplification of logic expressions.
Reduces hardware cost by minimizing logic gates.
Used by CAD tools to optimize circuits with millions of gates.

Key Idea
Binary logic (0/1) forms the basis of computation. Boolean algebra is the
mathematical framework behind it.

Boolean Algebra&Logic Circuits Dept. of CSE, GITAM, Visakhapatnam Dr. M. Rambabu 2/50
Basic Definitions

Sets and Operators Key Properties

Set: Collection of elements, e.g., Closure
A = {1, 2, 3}. Commutativity
Binary operator: Maps (a, b) to a Associativity
single element in the set.
Identity element
Example: Addition is closed on
integers; subtraction is not closed Inverse
on natural numbers. Distributive law

Boolean Algebra&Logic Circuits Dept. of CSE, GITAM, Visakhapatnam Dr. M. Rambabu 3/50
Algebraic Properties (Part 1)

1. Closure
A set S is closed under ∗ if
a, b ∈ S ⇒ a ∗ b ∈ S.
N closed under + : 3 + 5 = 8
3. Commutative Law
Not closed under − : a ∗ b = b ∗ a.
2 − 5 = −3 ∈/N
4+9=9+4
2. Associative Law 3·7=7·3
(a ∗ b) ∗ c = a ∗ (b ∗ c). 8 − 5 ̸= 5 − 8
Addition: (2 + 3) + 4 = 2 + (3 + 4)
Multiplication: (2 · 3) · 4 = 2 · (3 · 4)
Subtraction not associative

Boolean Algebra&Logic Circuits Dept. of CSE, GITAM, Visakhapatnam Dr. M. Rambabu 4/50
Algebraic Properties (Part 2)

4. Identity Element
e is an identity if x ∗ e = e ∗ x = x.
Additive identity: 0
6. Distributive Law
Multiplicative identity: 1
a(b + c) = ab + ac.
N lacks additive identity
3(4 + 2) = 3 · 4 + 3 · 2

5. Inverse Addition does not distribute over

multiplication
y is inverse of x if x ∗ y = e.
Additive inverse: 5 + (−5) = 0
1
Multiplicative inverse: 4 · 4 =1

Boolean Algebra&Logic Circuits Dept. of CSE, GITAM, Visakhapatnam Dr. M. Rambabu 5/50
Axiomatic Definition of Boolean Algebra

Boolean Algebra is Defined by:

Set B = {0, 1}.
Operators: OR (+), AND (.), NOT (’), satisfying:

Postulates
Complement
Closure under + and .
For every x exists x ′ such
Identity: x + 0 = x, x · 1 = x.
that:
Commutativity: x + y = y + x.
x + x′ = 1
Distributivity: x(y + z) = xy + xz
x · x′ = 0
x + (yz) = (x + y )(x + z)

Boolean Algebra&Logic Circuits Dept. of CSE, GITAM, Visakhapatnam Dr. M. Rambabu 6/50
Two-Valued Boolean Algebra

Definition
Operator Tables
Set: B = {0, 1}
OR: 1 if any input is 1
Operators correspond to:
+ : OR AND: 1 if both inputs are 1
. : AND NOT: flips 0/1
’ : NOT

OR (+) AND (·)

NOT (x ′ )
x y x +y x y x ·y
0 0 0 x x′
0 0 0
0 1 1 0 1 0 0 1
1 0 1 1 0 0 1 0
1 1 1
1 1 1

Boolean Algebra&Logic Circuits Dept. of CSE, GITAM, Visakhapatnam Dr. M. Rambabu 7/50
Verification of Boolean Postulates (1–3)

1. Closure
Results of +, ·, and ′ are always in 3. Commutative Laws
{0, 1}.
x + y = y + x, x ·y =y ·x

2. Identity Elements Supported directly by symmetry of truth

tables.
x + 0 = x, x ·1=x
5. Complements
OR identity: 0 x + x ′ = 1, x · x′ = 0
AND identity: 1

Boolean Algebra&Logic Circuits Dept. of CSE, GITAM, Visakhapatnam Dr. M. Rambabu 8/50
Distributive Laws of Boolean Algebra

AND over OR OR over AND

x · (y + z) = (x · y ) + (x · z) x + (y · z) = (x + y )(x + z)

x y z y +z x(y + z) xy + xz x y z yz x + yz (x + y )(x + z)
0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 0 1 0 0 0
0 1 0 1 0 0 0 1 0 0 0 0
0 1 1 1 0 0 0 1 1 1 1 1
1 0 0 0 0 0 1 0 0 0 1 1
1 0 1 1 1 1 1 0 1 0 1 1
1 1 0 1 1 1 1 1 0 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1

Boolean Algebra&Logic Circuits Dept. of CSE, GITAM, Visakhapatnam Dr. M. Rambabu 9/50
Basic Postulates and Theorems of Boolean Algebra

Theorems
Postulates
T1 Idempotent x +x =x (a)
P2 Identity Laws x +0=x (a) xx = x (b)
x ·1=x (b)
T2 Null Laws x +1=1 (a)
P5 Complement Laws x + x′ = 1 x ·0=0 (b)
(a) x · x ′ = 0 (b)
T3 Involution (x ′ )′ = x
P3 Commutative x +y =y +x
(a) xy = yx (b) T4 DeMorgan (x + y )′ = x ′ y ′ (a)
(xy )′ = x ′ + y ′ (b)
P4 Distributive x(y + z) = xy + xz
(a) x + yz = (x + y )(x + z) (b) T5 Absorption x + xy = x (a)
x(x + y ) = x (b)

Boolean Algebra&Logic Circuits Dept. of CSE, GITAM, Visakhapatnam Dr. M. Rambabu 10/50
Basic Theorems of Boolean Algebra

Complement
Identity and Null x + x′ = 1
x +0=x
x · x′ = 0
x ·1=x
(x ′ )′ = x
x +1=1
x ·0=0 Absorption & DeMorgan
x + xy = x
Idempotent
x(x + y ) = x
x +x =x
(x + y )′ = x ′ y ′
x ·x =x
(xy )′ = x ′ + y ′

Boolean Algebra&Logic Circuits Dept. of CSE, GITAM, Visakhapatnam Dr. M. Rambabu 11/50
Operator Precedence in Boolean Algebra

Order of Evaluation
1 Parentheses
2 NOT (’)
3 AND (.)
4 OR (+)

Example
Expression: (x + y )′ z Evaluate as: 1. (x + y ) 2. (x + y )′ 3. (x + y )′ · z

Boolean Algebra&Logic Circuits Dept. of CSE, GITAM, Visakhapatnam Dr. M. Rambabu 12/50
Boolean Functions

Boolean algebra deals with binary variables and logic operations.

A Boolean function consists of:
Binary variables (x, y , z, . . . )
Constants 0 and 1
Logic operators (AND, OR, NOT)
For given inputs, the function output is either 0 or 1.
Example: F1 = x + y ′ z
F1 = 1 if x = 1 or y ′ = 1 and z = 1.
F1 = 0 otherwise.

Boolean Algebra&Logic Circuits Dept. of CSE, GITAM, Visakhapatnam Dr. M. Rambabu 13/50
Truth Table for F1 = x + y ′ z

x y z F1
0 0 0 0
0 0 1 1
0 1 0 0 Observation
0 1 1 0
F1 = 1 if x = 1 or y ′ = 1 and z = 1.
1 0 0 1
Truth table has 8 rows for 3 variables (23 ).
1 0 1 1
1 1 0 1
1 1 1 1

Boolean Algebra&Logic Circuits Dept. of CSE, GITAM, Visakhapatnam Dr. M. Rambabu 14/50
Circuit Implementation of F1

Inverter generates y ′ .
AND gate for term y ′ z.
OR gate combines x with y ′ z.

Boolean Algebra&Logic Circuits Dept. of CSE, GITAM, Visakhapatnam Dr. M. Rambabu 15/50
Simplify the following Boolean Functions

1. F1 = x(x ′ + y )
2. F2 = x + x ′ y
3. F3 = (x + y )(x + y ′ )
4. F4 = xy + x ′ z + yz
5. F5 = (x + y )(x ′ + z)(y + z)
6. F6 = xyz ′ + (xy )′ z + w ′ xy + wx ′ y + wxy
7. F7 = (x + y + z ′ )(x ′ + y ′ + z)

Boolean Algebra&Logic Circuits Dept. of CSE, GITAM, Visakhapatnam Dr. M. Rambabu 16/50
Simplification of Boolean Functions
Original: F2 = x ′ y ′ z + x ′ yz + xy ′
Apply Boolean algebra:

F2 = x ′ z(y ′ + y ) + xy ′ = x ′ z + xy ′

Simplified circuit uses fewer gates and literals.

Truth table verification confirms equivalence.

Boolean Algebra&Logic Circuits Dept. of CSE, GITAM, Visakhapatnam Dr. M. Rambabu 17/50
Complement of Boolean Functions

Complement F ′ : interchange 0’s and 1’s.

Derived using DeMorgan’s theorems:

(A + B + C )′ = A′ B ′ C ′ , (ABC )′ = A′ + B ′ + C ′

Example:

F1 = x ′ yz ′ + x ′ y ′ z =⇒ F1′ = (x + y ′ + z)(x + y + z ′ )

Dual method: swap AND ↔ OR and complement each literal.

Boolean Algebra&Logic Circuits Dept. of CSE, GITAM, Visakhapatnam Dr. M. Rambabu 18/50
Dual of a Boolean Function

Definition
The dual of a Boolean expression is obtained by:
Replacing every AND (·) with OR (+)
Replacing every OR (+) with AND (·)
Keeping all variables and complements unchanged
The dual follows the principle of interchanging operators but NOT
literals.

Example 1 Example 2
Original: F = AB + C’ Original: F = (A + B)(C + D’)
Dual: F D = (A + B)(C ′ ) Dual: F D = (AB) + (CD ′ )

Tip: Duality helps in NOR/NAND transformations and proving Boolean

theorems.

Boolean Algebra&Logic Circuits Dept. of CSE, GITAM, Visakhapatnam Dr. M. Rambabu 19/50
Canonical Forms Overview

Canonical forms represent Boolean functions in standardized formats.

Two types:
Sum of Minterms (SOP)
Product of Maxterms (POS)
Each minterm / maxterm includes all variables (complemented or
uncomplemented).

Boolean Algebra&Logic Circuits Dept. of CSE, GITAM, Visakhapatnam Dr. M. Rambabu 20/50
Minterms and Maxterms

Minterms Maxterms
Definition: A minterm is an AND Definition: A maxterm is an OR
term where each variable appears term where each variable appears
either in normal or complemented either in normal or complemented
form. form.
Example with variables (x, y ): Example with variables (x, y ):

x ′ y ′ , x ′ y , xy ′ , xy (x + y ), (x + y ′ ), (x ′ + y ), (x ′ + y ′ )

General Rule: For n variables  General Rule: For n variables 

2n minterms. 2n maxterms.

Boolean Algebra&Logic Circuits Dept. of CSE, GITAM, Visakhapatnam Dr. M. Rambabu 21/50
Minterms/Maxterms Table and SOP–POS Derivation
x y z Minterm Maxterm
0 0 0 x ′ y ′ z ′ (m0 ) x + y + z (M0 )
0 0 1 x ′ y ′ z (m1 ) x + y + z ′ (M1 )
0 1 0 x ′ yz ′ (m2 ) x + y ′ + z (M2 )
0 1 1 x ′ yz (m3 ) x + y ′ + z ′ (M3 )
1 0 0 xy ′ z ′ (m4 ) x ′ + y + z (M4 )
1 0 1 xy ′ z (m5 ) x ′ + y + z ′ (M5 )
1 1 0 xyz ′ (m6 ) x ′ + y ′ + z (M6 )
1 1 1 xyz (m7 ) x ′ + y ′ + z ′ (M7 )

Obtaining SOP Obtaining POS

Given: f1 = 1 for inputs 001, Zeros at minterms 0, 2, 3, 5, 6:
100, 111 f1′ = m0 + m2 + m3 + m5 + m6
Taking complement:
f1 = m1 + m4 + m7 f1 = M0 M2 M3 M5 M6
f1 = (x + y + z)(x + y ′ + z)(x + y ′ + z ′ )(x ′ +
f1 = x ′ y ′ z + xy ′ z ′ + xyz y + z ′ )(x ′ + y ′ + z)
Boolean Algebra&Logic Circuits Dept. of CSE, GITAM, Visakhapatnam Dr. M. Rambabu 22/50
Understanding SOP and POS using Truth Table

Given: F (x, y , z) = xy + x ′ z SOP Form (Sum of

Minterms)
x y z F F = 1 at minterms: 1, 3, 6, 7
0 0 0 0 So, X
0 0 1 1 F = (1, 3, 6, 7)
0 1 0 0
0 1 1 1
1 0 0 0 POS Form (Product of
1 0 1 0 Maxterms)
1 1 0 1
Missing (F=0) terms: 0,2,4,5 So,
1 1 1 1
Y
F = (0, 2, 4, 5)

Boolean Algebra&Logic Circuits Dept. of CSE, GITAM, Visakhapatnam Dr. M. Rambabu 23/50
Sum of Minterms and Canonical Expansion

Expanding to Canonical Form

Sum of Minterms Notation Expand:
Given: A + B ′C

F (A, B, C ) = A + B ′ C
A = AB + AB ′
Truth table gives 1’s at:
AB = ABC + ABC ′
1, 4, 5, 6, 7 AB ′ = AB ′ C + AB ′ C ′

Thus, B ′ C = AB ′ C + A′ B ′ C
X Final SOP:
F = (1, 4, 5, 6, 7)
F = m 1 + m 4 + m5 + m6 + m 7

Boolean Algebra&Logic Circuits Dept. of CSE, GITAM, Visakhapatnam Dr. M. Rambabu 24/50
Sum of Minterms and Canonical Expansion

Canonical SOP Expansion

Sum of Minterms Notation
Expand each term to include all
Given: variables:
F (A, B, C ) = A + B ′ C
A = A(B + B ′ )(C + C ′ )
From the truth table, the function is 1 = ABC + ABC ′ + AB ′ C + AB ′ C ′
for input combinations:

1, 4, 5, 6, 7 B ′ C = (A + A′ )B ′ C
= AB ′ C + A′ B ′ C
Thus,
X Collecting all minterms:
F = m(1, 4, 5, 6, 7)
F = m 1 + m 4 + m5 + m6 + m 7

Boolean Algebra&Logic Circuits Dept. of CSE, GITAM, Visakhapatnam Dr. M. Rambabu 25/50
Product of Maxterms
Given:
F (x, y , z) = xy + x ′ z
Determine the product of maxterms using the truth table.
The function output is 0 for input combinations:
0, 2, 4, 5
Corresponding maxterms are:
M0 = (x + y + z)
M2 = (x + y ′ + z)
M4 = (x ′ + y + z)
M5 = (x ′ + y + z ′ )
Thus, the product of maxterms form is:
F = (x + y + z)(x + y ′ + z)(x ′ + y + z)(x ′ + y + z ′ )
Y
F = M(0, 2, 4, 5)
Boolean Algebra&Logic Circuits Dept. of CSE, GITAM, Visakhapatnam Dr. M. Rambabu 26/50
Conversion Between Canonical Forms

Rule:
To convert: - Sum of Minterms 
Product of Maxterms - Product of
Maxterms 
Sum of Minterms
**Replace** Σ with Π **List the missing terms**.
Example:

F = Σ(1, 4, 5, 6, 7)
Total terms = 0–7 Missing: 0, 2, 3

F = Π(0, 2, 3)

Boolean Algebra&Logic Circuits Dept. of CSE, GITAM, Visakhapatnam Dr. M. Rambabu 27/50
Standard Forms

Two standard (but not canonical) forms:

Sum of Products (SOP)

F1 = y ′ + xy + x ′ yz ′

Product of Sums (POS)

F2 = x(y ′ + z)(x ′ + y + z ′ )

These forms do NOT require all variables in every term.

Boolean Algebra&Logic Circuits Dept. of CSE, GITAM, Visakhapatnam Dr. M. Rambabu 28/50
Two-Level Implementations

SOP  AND gates followed by OR gate

POS  OR gates followed by AND gate
Preferred for minimal propagation delay

Boolean Algebra&Logic Circuits Dept. of CSE, GITAM, Visakhapatnam Dr. M. Rambabu 29/50
Other Logic Operations (Overview)

Key Idea: For two binary variables (x, y ), the number of possible Boolean
functions is:
2
22 = 16
These 16 functions include:
2 constant functions (0 and 1)
4 unary functions (NOT, identity/transfer)
10 binary functions (AND, OR, NAND, NOR, XOR, XNOR,
inhibition, implication)

We study these functions using:

Truth tables + Boolean expressions + Operator symbols

Boolean Algebra&Logic Circuits Dept. of CSE, GITAM, Visakhapatnam Dr. M. Rambabu 30/50
Truth Tables for the 16 Functions of Two Variables

x y F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1
0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1
1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1
1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0

Boolean Algebra&Logic Circuits Dept. of CSE, GITAM, Visakhapatnam Dr. M. Rambabu 31/50
Boolean Expressions and Operator Names

Function Boolean Expression Operator Symbol Name / Meaning

F0 0 – Constant 0 (Null)
F1 xy ′ x · ȳ Inhibition (x but not y)
F2 x ′y x̄ · y Inhibition (y but not x)
F3 x – Transfer x
F4 x ′y ′ – NOR of (x,y) inputs both 0
F5 y – Transfer y
F6 x ⊕y ⊕ XOR (exclusive-OR)
F7 x +y + OR
F8 (x + y )′ ↓ NOR
F9 (x ⊕ y )′ ⊙ XNOR (equivalence)
F10 y′ – NOT y
F11 x + y′ – Implication (if y then x)
F12 x′ – NOT x
F13 x′ + y – Implication (if x then y)
F14 (xy )′ ↑ NAND
F15 1 – Constant 1 (Identity)

Boolean Algebra&Logic Circuits Dept. of CSE, GITAM, Visakhapatnam Dr. M. Rambabu 32/50
Classification of All 16 Functions

1. Constant Functions

F0 = 0 F15 = 1

2. Unary Functions (operate on a single variable)

x, x ′ , y , y ′

3. Binary Functions
Standard: AND, OR, NAND, NOR
Special: XOR, XNOR
Logic (less used in circuits): Inhibition, Implication

Boolean Algebra&Logic Circuits Dept. of CSE, GITAM, Visakhapatnam Dr. M. Rambabu 33/50
Digital Logic Gates: Overview

Boolean functions are implemented using AND, OR, NOT gates.

Additional useful gates: NAND, NOR, XOR, XNOR, Buffer.
Criteria when choosing gate types:
Feasibility & cost of physical implementation
Possibility of extending to more inputs
Operator properties (commutative, associative)
Ability to implement Boolean functions efficiently
Out of 16 possible Boolean functions, 8 form the standard logic gates.

Boolean Algebra&Logic Circuits Dept. of CSE, GITAM, Visakhapatnam Dr. M. Rambabu 34/50
Standard Logic Gates (Part 1)

AND Gate
Output 1 only when both inputs are
1.
Algebraic: F = xy

OR Gate
Output 1 if at least one input is 1.
Algebraic: F = x + y

NOT (Inverter)
Produces complement.
Algebraic: F = x ′

Buffer
Performs transfer function.
Used for power amplification.

Boolean Algebra&Logic Circuits Dept. of CSE, GITAM, Visakhapatnam Dr. M. Rambabu 35/50
Standard Logic Gates (Part 2)

NAND Gate
Complement of AND.
Algebraic: F = (xy )′
Most widely used in hardware.

NOR Gate
Complement of OR.
Algebraic: F = (x + y )′

XOR Gate
Outputs 1 for odd number of 1s.
Algebraic: F = x ′ y + xy ′

XNOR (Equivalence)
Complement of XOR.
Outputs 1 for even number of 1s.
Boolean Algebra&Logic Circuits Dept. of CSE, GITAM, Visakhapatnam Dr. M. Rambabu 36/50
Multiple-Input Logic Gates

AND and OR: associative + commutative  multi-input OK.

NAND/NOR: commutative but not associative as binary ops.
NAND(x1 , . . . , xn ) = ( xi )′ ,
Q
Multi-input gates definedP as:
NOR(x1 , . . . , xn ) = ( xi )′
Chaining binary gates ambiguous: (x ↑ y ) ↑ z ̸= x ↑ (y ↑ z),
(x ↓ y ) ↓ z ̸= x ↓ (y ↓ z)
XOR/XNOR: associative + commutative.
XOR: 1 if # of 1s is odd.
XNOR: 1 if # of 1s is even.

Boolean Algebra&Logic Circuits Dept. of CSE, GITAM, Visakhapatnam Dr. M. Rambabu 37/50
Three-Input XOR Example

Construction
Implemented by cascading 2-input
XORs.
Output = 1 if inputs contain an odd Truth Table
number of 1s. x y z 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

Boolean Algebra&Logic Circuits Dept. of CSE, GITAM, Visakhapatnam Dr. M. Rambabu 38/50
Positive and Negative Logic

Signal levels: High (H) and Low (L)

Positive logic: H=1, L=0
Example
Negative logic: H=0, L=1
Positive Logic AND ↔ Negative
Same physical gate can act as: Logic OR
AND (positive logic) Dual: AND ↔ OR
OR (negative logic)
Changing polarity ↔ function dual

Boolean Algebra&Logic Circuits Dept. of CSE, GITAM, Visakhapatnam Dr. M. Rambabu 39/50
Universal Gates

Definition
A universal gate is a logic gate that can implement any Boolean
function using only repeated combinations of itself.

The two universal gates are:

NAND Gate
NOR Gate
Both can be used to realize NOT, AND, OR, and all other logic
operations.

Boolean Algebra&Logic Circuits Dept. of CSE, GITAM, Visakhapatnam Dr. M. Rambabu 40/50
NAND as a Universal Gate

NOT using NAND:

NOT A = A NAND A
Key Idea
AND using NAND: NAND can reproduce:
Inverter
A · B = (A NAND B) NAND (A NAND B)
AND gate
OR using NAND: OR gate

A + B = (A NAND A) NAND (B NAND B)

Boolean Algebra&Logic Circuits Dept. of CSE, GITAM, Visakhapatnam Dr. M. Rambabu 41/50
NOR as a Universal Gate

NOT using NOR:

NOT A = A NOR A
Key Idea
OR using NOR: NOR can derive:
Inverter
A + B = (A NOR B) NOR (A NOR B)
OR gate
AND using NOR: AND gate

A · B = (A NOR A) NOR (B NOR B)

Boolean Algebra&Logic Circuits Dept. of CSE, GITAM, Visakhapatnam Dr. M. Rambabu 42/50
Universal Gates: Advantages, Disadvantages, and
Applications
Advantages
Simplicity – One gate implements all
logic.
Cost-Effective – Fewer types reduce
manufacturing cost.
Applications
Flexibility – Can realize any Boolean
Basic digital circuits (implement
function.
AND/OR/NOT).
High Reliability – Less variety in
Memory units: SRAM, DRAM, latches,
components.
flip-flops.
Easy Integration – Useful in large,
ALU design in microprocessors.
complex circuits.
Digital signal processing and
communication circuits.
Disadvantages
Embedded systems and small-scale digital
Increased gate count for complex circuits. controllers.
Higher power consumption.
More propagation delay  slower speed.
Design becomes more intricate.
Optimization may be limited.
Boolean Algebra&Logic Circuits Dept. of CSE, GITAM, Visakhapatnam Dr. M. Rambabu 43/50
Multilevel NAND Circuits: Overview

Concept
Two-level Boolean forms are common, but complex digital systems may
require three or more gate levels. Boolean functions are usually
expressed using AND, OR, and NOT operations before converting into an
all-NAND form.

F = (AB ′ + A′ B)(C + D ′ )

Boolean Algebra&Logic Circuits Dept. of CSE, GITAM, Visakhapatnam Dr. M. Rambabu 44/50
AND–OR to Multilevel NAND Conversion

Key Rules
Convert AND  NAND (AND-invert symbol)
Convert OR  NAND (invert-OR symbol)
Every bubble must be compensated
Add inverter or complement literal if bubble mismatch occurs

Boolean Algebra&Logic Circuits Dept. of CSE, GITAM, Visakhapatnam Dr. M. Rambabu 45/50
General NAND Conversion Procedure

Steps
1 Convert all AND gates to NAND gates.
2 Convert all OR gates to NAND gates.
3 Check for unpaired bubbles and fix them:
Insert an inverter, or
Complement the input literal.
4 For multilevel circuits, add final inverter if the output polarity
changes.

Boolean Algebra&Logic Circuits Dept. of CSE, GITAM, Visakhapatnam Dr. M. Rambabu 46/50
NOR Implementation: Essentials

NOR as Universal Gate

NOR logic is the dual of NAND logic.
All NAND rules apply in dual form:
OR gate OR-invert symbol
AND gate  invert-AND symbol

Basic Operations Using NOR

Inverter: One-input NOR
OR: Two NOR gates
AND: NOR gate with inverted
inputs

Boolean Algebra&Logic Circuits Dept. of CSE, GITAM, Visakhapatnam Dr. M. Rambabu 47/50
Two-Level NOR Implementation (POS Form)

F = (A + B)(C + D)E

Conversion Steps
Express function in POS form
Convert OR gates NOR (OR-invert)
Convert AND gate  NOR (invert-AND)
Complement single-literal inputs when required

Boolean Algebra&Logic Circuits Dept. of CSE, GITAM, Visakhapatnam Dr. M. Rambabu 48/50
Multilevel NOR Conversion

Procedure
Replace OR OR-invert
Replace AND  invert-AND
Fix unpaired bubbles by inserting inverters or complementing inputs

F = (AB ′ + A′ B)(C + D ′ )

Boolean Algebra&Logic Circuits Dept. of CSE, GITAM, Visakhapatnam Dr. M. Rambabu 49/50
Any Questions?

Let’s Discuss!
Your doubts help everyone learn better.

Boolean Algebra&Logic Circuits Dept. of CSE, GITAM, Visakhapatnam Dr. M. Rambabu 50/50