EENG 2041 Lecture 2 2

2. Logic Gates and Boolean Algebra

Chapter Outline
• Digital Logic Gates
• Definition and Basic Properties of Boolean Algebra
• Theorems of Boolean Algebra
• Boolean Functions
• Simplification Of Boolean Expressions
 EENG 2041 Lecture 2 3

2. Logic Gates and Boolean Algebra

DIGITAL LOGIC GATES
• An Electronic Circuitry that operates on one or more input
signal to produce a output signal.
 EENG 2041 Lecture 2 4

2. Logic Gates and Boolean Algebra

DIGITAL LOGIC GATES
• As Boolean functions are expressed in terms of AND, OR,
and NOT operations
 EENG 2041 Lecture 2 5

2. Logic Gates and Boolean Algebra

DIGITAL LOGIC GATES
 EENG 2041 Lecture 2 6

2. Logic Gates and Boolean Algebra

Universal Gates
• NAND gates and NOR gates are called universal gates or
universal building blocks NOR gates
• any type of gates or logic functions can be implemented
by these gates
 EENG 2041 Lecture 2 7

2. Logic Gates and Boolean Algebra

Representation of basic gates with universal gates
 EENG 2041 Lecture 2 8

2. Logic Gates and Boolean Algebra

Definition and Basic Properties of Boolean Algebra
• a discrete algebra in which the variables can have
one of two values, either 0 or 1
• 1854, George Boole
 EENG 2041 Lecture 2 9

2. Logic Gates and Boolean Algebra

• Definition
• A closed algebraic system containing a set of K of two or
more elements and operator . (𝐴𝑁𝐷) and + (𝑂𝑅); such
that for every element 𝑎 and 𝑏 in set K,
• 𝑎. 𝑏 and 𝑎 + 𝑏 belongs to K
 EENG 2041 Lecture 2 10

2. Logic Gates and Boolean Algebra

Basic Postulates
1. Existence of 0 and 1 or Identity
A. 𝑎+0=𝑎
B. 𝑎 .1 = 𝑎
2. Commutativity
A. 𝑎+𝑏 =𝑏+𝑎
B. 𝑎. 𝑏 = 𝑏. 𝑎
 EENG 2041 Lecture 2 11

2. Logic Gates and Boolean Algebra

Basic Postulates
3. Associativity
a. 𝑎+ 𝑏+𝑐 = 𝑎+𝑏 +𝑐
b. 𝑎. 𝑏. 𝑐 = 𝑎. 𝑏 . 𝑐
4. Distributivity
a. 𝑎 + 𝑏. 𝑐 = 𝑎 + 𝑏 . (𝑎 + 𝑐)
b. 𝑎. 𝑏 + 𝑐 = 𝑎. 𝑏 + (𝑎. 𝑐)
5. Existence of Complement
a. 𝑎 + 𝑎ത = 1
b. 𝑎. 𝑎ത = 0
 EENG 2041 Lecture 2 12

2. Logic Gates and Boolean Algebra

Other Important Theorems
➢Theorem 1(a):A + A = A
➢Theorem 1(b):A . A = A
➢Theorem 2(a):A + 1 = 1
➢Theorem 2(b):A . 0 = 0
➢Theorem 3(a):A + A.B = A
➢Theorem 3(b): A ( A + B ) = A
 EENG 2041 Lecture 2 13

2. Logic Gates and Boolean Algebra

Properties of Boolean Algebra
Principle of Duality
✓Given a logic expression, its dual is obtained by replacing
all + operators with · operators, and vice versa, and by
replacing all 0s with 1s, and vice versa.
✓The dual of any true statement (axiom or theorem) in
Boolean algebra is also a true statement.
 EENG 2041 Lecture 2 14

2. Logic Gates and Boolean Algebra

DeMorgan's Law
• A complement of a product is equal to the sum of the
complements
𝐴. 𝐵 = 𝐴′ + 𝐵′
• A complement of a sum is equal to the product of the
complements.
𝐴 + 𝐵 = 𝐴′. 𝐵′
 EENG 2041 Lecture 2 15

2. Logic Gates and Boolean Algebra

• Summery postulates and Theorems
 EENG 2041 Lecture 2 16

2. Logic Gates and Boolean Algebra

The Venn Diagram
• a graphical illustration of various operations and relations
• In Boolean algebra there are only two values (elements)
in the universe B and, a set x,

B
𝑋ത
X
 EENG 2041 Lecture 2 17

2. Logic Gates and Boolean Algebra

BOOLEAN FUNCTIONS
• an expression formed with binary variables,
• the two binary operators AND and OR,
• one unary operator NOT
• function may be 0 or 1
• can also be represented by truth tables
 EENG 2041 Lecture 2 18

2. Logic Gates and Boolean Algebra

Exercise:
1. Manipulate the truth table and draw timing diagram for a Basic
and Derived Logic Gates functions.
2. Find the truth table for the following functions
A. F = AB′C
B. F = A + A′B
C. F= A′B′C + A′BC + AB′
D. F = AB + (AC)′+ AB′C(AB + C)
 EENG 2041 Lecture 2 19

2. Logic Gates and Boolean Algebra

Simplification Of Boolean Expressions
• Implemented with logic gates, each literal in the function
is designated as input to the gate.
• Less complex circuits as well as less number of gates
• Postulates and Theorems
• Karnaugh Map
• Standard (Canonical) Forms
• SOP{Sum of Product terms} and POS{Product of Sum terms}
• Minterms and Maxterms
 EENG 2041 Lecture 2 20

2. Logic Gates and Boolean Algebra

Simplification with postulates and theorems
Examples: Simplify the Boolean functions and draw the
logic circuit
A. 𝐹 = 𝐴𝐵 + 𝐵𝐶 + 𝐵′𝐶
B. 𝐹 = 𝐴 + 𝐴′𝐵
C. 𝐹 = 𝐴′𝐵′𝐶 + 𝐴′𝐵𝐶 + 𝐴𝐵′
D. 𝐹 = 𝐴𝐵 + (𝐴𝐶)′ + 𝐴𝐵′𝐶(𝐴𝐵 + 𝐶)
E. 𝐹 = ((𝑋𝑌′ + 𝑋𝑌𝑍)′ + 𝑋(𝑌 + 𝑋𝑌′))′
 EENG 2041 Lecture 2 21

2. Logic Gates and Boolean Algebra

CANONICAL AND STANDARD FORMS
Product Term:
• the logical product of several variables on which a
function depends
• AND function or standard product, Ex. 𝐴𝐵𝐶′
Sum Term:
• the logical sum of several variables on which a function
depends
• OR function or standard Sum, Ex. A+B+C′
 EENG 2041 Lecture 2 22

2. Logic Gates and Boolean Algebra

Standard Forms
Sum of Products(SOP)
• Logical Sum of two or more logical Product terms
• An OR operation on AND operated variables
• Y = AB + BC + AC or Y = A′B + BC + AC′
Product of Sums(POS)
• Logical Product of two or more logical Sum terms
• An AND operation on OR operated variables
• 𝑌 = 𝐴 + 𝐵 + 𝐶 𝐴 + 𝐵′ + 𝐶 𝐴 + 𝐵 + 𝐶 ′
• 𝑌 = (𝐴 + 𝐵 + 𝐶)(𝐴′ + 𝐵′ + 𝐶′)
 EENG 2041 Lecture 2 23

2. Logic Gates and Boolean Algebra

Canonical Forms
Minterm
• A product term containing all n variables of the function in
either un complemented or complemented form.
• obtained by an AND operation
• value 1 if it is in true or uncomplemented form
• value 0 if it is in complemented form
 EENG 2041 Lecture 2 24

2. Logic Gates and Boolean Algebra

For the function F(A, B, C)

A B C Minterm Minterms Minterm

Number symbol
0 0 0 0 𝑨’𝑩’𝑪’ 𝒎𝟎
0 0 1 1 𝑨’𝑩’𝑪 𝒎𝟏
0 1 0 2 𝑨’𝑩𝑪’ 𝒎𝟐
0 1 1 3 𝑨’𝑩𝑪 𝒎𝟑
1 0 0 4 𝑨𝑩’𝑪’ 𝒎𝟒
1 0 1 5 𝑨𝑩’𝑪 𝒎𝟓
1 1 0 6 𝑨𝑩𝑪’ 𝒎𝟔
1 1 1 7 𝑨𝑨𝑨 𝒎𝟕
 EENG 2041 Lecture 2 25

2. Logic Gates and Boolean Algebra

Canonical Sum of Product
• logical sum of all the minterms for which the value of the
function is 1
• Example: a function 𝐹(𝐴, 𝐵, 𝐶) = 𝐴′𝐵𝐶 + 𝐴𝐵′𝐶 + 𝐴𝐵𝐶′
can be represented as
• 𝐹 (𝐴, 𝐵, 𝐶) = (3,5,6)
• 𝐹 (𝐴, 𝐵, 𝐶) = 𝑚3 + 𝑚5 + 𝑚6
• 𝐹 (𝐴, 𝐵, 𝐶) = Σ𝑚(3,5,6)
 EENG 2041 Lecture 2 26

2. Logic Gates and Boolean Algebra

Exercise: Obtain the canonical sum of product of the
following functions
i. F (A, B) = A + B
ii. F (A, B, C) = A + BC
iii. F (A, B,C) = ABC + AB′C + ABC′+ AB′C′+ A′BC
 EENG 2041 Lecture 2 27

2. Logic Gates and Boolean Algebra

Canonical Forms
Maxterm
• A sum term containing all n variables of the function in
either un complemented or complemented form.
• obtained by an OR operation
• value 0 if it is in true or uncomplemented form
• value 1 if it is in complemented form
 EENG 2041 Lecture 2 28

2. Logic Gates and Boolean Algebra

For the function F(A, B, C)

A B C Maxterm Maxterms Maxterm

Number symbol
0 0 0 0 𝑨+𝑩+𝑪 𝑴𝟎
0 0 1 1 𝑨 + 𝑩 + 𝑪’ 𝑴𝟏
0 1 0 2 𝑨 + 𝑩’ + 𝑪 𝑴𝟐
0 1 1 3 𝑨 + 𝑩’ + 𝑪’ 𝑴𝟑
1 0 0 4 𝑨’ + 𝑩 + 𝑪 𝑴𝟒
1 0 1 5 𝑨’ + 𝑩 + 𝑪’ 𝑴𝟓
1 1 0 6 𝑨’ + 𝑩’ + 𝑪 𝑴𝟔
1 1 1 7 𝑨′ + 𝑩′ + 𝑪’ 𝑴𝟕
 EENG 2041 Lecture 2 29

2. Logic Gates and Boolean Algebra

Canonical Product of Sum
• logical product of all the Maxterms for which the value of
the function is 0.
• Example: a function 𝑭(𝑨, 𝑩, 𝑪) = (𝑨′ + 𝑩 + 𝑪 )( 𝑨 +𝑩′ +𝑪) ( 𝑨 + 𝑩+𝑪′ ) can
be represented as
• 𝐹 (𝐴, 𝐵, 𝐶) = (4,2,1)
• 𝐹 (𝐴, 𝐵, 𝐶) = 𝑀4 + 𝑀2 + 𝑀1
• 𝐹 (𝐴, 𝐵, 𝐶) = ς 𝑀(4,2,1)
 EENG 2041 Lecture 2 30

2. Logic Gates and Boolean Algebra

Exercise: Obtain the canonical product of sum of the
following functions
i. F (A, B, C) = (A + B′) (B + C) (A + C′)
ii. F (A, B, C) = A + B′C
iii. F (A, B) = (A + B + C)(A + B′ + C)(A + B + C′)(A + B′ + C′)(A′ + B + C)
 EENG 2041 Lecture 2 31

2. Logic Gates and Boolean Algebra

Karnaugh Map
• Simplification of Boolean Expressions
• Doesn’t guarantee simplest form of expression
• Terms are not obvious
• Skills of applying rules and laws
• K-map provides a systematic method
• An array of cells
• Used for simplifying 2, 3, 4 and 5 variable expressions
 EENG 2041 Lecture 2 32

2. Logic Gates and Boolean Algebra

3-Variable K-map
• Used for simplifying 3-variable expressions
• K-map has 8 cells representing the 8 minterms and 8
maxterms
• K-map can be represented in row format or column format
 EENG 2041 Lecture 2 33

2. Logic Gates and Boolean Algebra

3-Variable K-map

AB\C 0 1
A\BC 00 01 11 10

00 0 1 0 0 1 3 2

1 4 5 7 6
01 2 3

11 6 7

10 4 5
 EENG 2041 Lecture 2 34

2. Logic Gates and Boolean Algebra

4-Variable K-map
• Used for simplifying 4-variable expressions
• K-map has 16 cells representing the 16 minterms and 8
maxterms
• A 4-variable K-map has a square format
 EENG 2041 Lecture 2 35

2. Logic Gates and Boolean Algebra

4-Variable K-map
AB\CD 00 01 11 10

00 0 1 3 2

01 4 5 7 6

11 12 13 15 14

10 8 9 11 10
 EENG 2041 Lecture 2 36

2. Logic Gates and Boolean Algebra

Grouping & Adjacent Cells
• K-map is considered to be wrapped around
• All sides are adjacent to each other
• Groups of 2, 4, 8,16 and 32 adjacent cells are formed
• Groups can be row, column, square or rectangular.
• Groups of diagonal cells are not allowed
 EENG 2041 Lecture 2 37

2. Logic Gates and Boolean Algebra

Mapping of Standard SOP expression
• Selecting n-variable K-map
• 1 marked in cell for each minterm
• Remaining cells marked with 0
 EENG 2041 Lecture 2 38

2. Logic Gates and Boolean Algebra

• Example : Suppose the 3-variable SOP expression
• 𝐹 = 𝐴𝐵𝐶 ′ + 𝐴𝐵′ 𝐶 ′ + 𝐴′ 𝐵𝐶 ′

C 0 1 BC 00 01 11 10
AB A
00 0 0 0 0 0 0 1

01 1 0 1 1 0 0 1

11 1 0

10 1 0
 EENG 2041 Lecture 2 39

2. Logic Gates and Boolean Algebra

• Example : Suppose the 4-variable SOP expression
F = A.B.C.D + A.B.C.D + A.B.C.D + A.B.C.D + A.B.C.D + A.B.C.D + A.B.C.D

AB 00 01 11 10
CD

00 0 1 0 0

01 1 1 0 1

11 0 1 0 1

10 1 0 0 0
 EENG 2041 Lecture 2 40

2. Logic Gates and Boolean Algebra

• Mapping of Non-Standard SOP expression
• Selecting n-variable K-map
• 1 marked in all the cells where the non- standard product
term is present
• Remaining cells marked with 0
 EENG 2041 Lecture 2 41

2. Logic Gates and Boolean Algebra

• Example : Suppose the 3-variable Non-Standard SOP
expression
• 𝐹 = 𝐴 + 𝐵𝐶′

C 0 1
AB

00 0 0 BC 00 01 11 10
A
01 1 0
0 0 0 0 1
11 1 1
1 1 1 1 1
10 1 1
 EENG 2041 Lecture 2 42

2. Logic Gates and Boolean Algebra

• Example : Suppose the 4-variable Non-Standard SOP
expression
• 𝐹 = 𝐷 + 𝐴𝐶′ + 𝐵𝐶
AB
00 01 11 10
CD

00 0 1 1 0

01 0 1 1 1

11 1 1 1 1

10 1 1 1 0
 EENG 2041 Lecture 2 43

2. Logic Gates and Boolean Algebra

Simplification of SOP expressions using K-map
• Mapping of expression
• Forming of Groups of 1s
• Each group represents product term
3-variable K-map
• 1 cell group yields a 3 variable product term
• 2 cell group yields a 2 variable product term
• 4 cell group yields a 1 variable product term
• 8 cell group yields a value of 1 for function
 EENG 2041 Lecture 2 44

2. Logic Gates and Boolean Algebra

Simplification of SOP expressions using K-map
4-variable K-map
• 1 cell group yields a 4 variable product term
• 2 cell group yields a 3 variable product term
• 4 cell group yields a 2 variable product term
• 8 cell group yields a 1 variable product term
• 16 cell group yields a value of 1 for function
 EENG 2041 Lecture 2 45

2. Logic Gates and Boolean Algebra

• Example: Consider the 3-variable column based K-map
in which the SOP expression has been mapped
• 𝐹 = 𝐴𝐵𝐶 ′ + 𝐴𝐵′ 𝐶 ′ + 𝐴′ 𝐵𝐶 ′ = 𝐶′(𝐴 + 𝐵)

C 0 1
AB BC 00 01 11 10
A
00 0 0 BC′ 0 0 0 0 1
01 1 0
1 1 0 0 1
11 1 0
𝑨𝑪′
10 1 0 ∴ 𝐹 = 𝐴𝐶’ + 𝐵𝐶’ = 𝐶′(𝐴 + 𝐵)
 EENG 2041 Lecture 2 46

2. Logic Gates and Boolean Algebra

• Example : Suppose the 4-variable SOP expression
F = A.B.C.D + A.B.C.D + A.B.C.D + A.B.C.D + A.B.C.D + A.B.C.D + A.B.C.D

AB 00 01 11 10
CD

00 0 1 0 0

01 1 1 0 1

11 0 1 0 1

10 1 0 0 0
 EENG 2041 Lecture 2 47

2. Logic Gates and Boolean Algebra

• Exercise: Consider the 4-variable column based K-map
and drive the simplified function the 𝐹 map

AB
00 01 11 10
CD

00 0 1 1 0

01 0 1 1 0

11 0 1 0 0

10 0 0 1 0
 EENG 2041 Lecture 2 48

2. Logic Gates and Boolean Algebra

Don’t care Conditions
• Some input combinations never occur
• Outputs are assumed to be don’t care
• Don’t care outputs used as 0 or 1 during simplification.
• Results in simpler and shorter expressions
 EENG 2041 Lecture 2 49

2. Logic Gates and Boolean Algebra

Example: Consider the following function with Don’t care
Conditions

AB
00 01 11 10
CD

00 0 1 1 0

01 0 1 1 0

11 x x x x

10 0 x x x
 EENG 2041 Lecture 2 50

2. Logic Gates and Boolean Algebra

Exercise: Using the Karnaugh map method obtain the
minimal sum of the products and product of sums
expressions for the function
1. F(A,B,C) = A′B′C + A′BC + A′BC′+ AB′C + ABC
2. F(A,B,C,D) = Σm(1, 3, 4, 5, 6, 7, 9, 12, 13)
3. F(A,B,C,D) = Σm(0, 2, 3, 6, 7) +d (8, 10, 11, 15)
4. F (A, B, C, D, E) = Σ(0, 2, 5, 7, 9, 11, 13, 15, 16, 18, 21,
23, 25, 27, 29, 31)