Chapter 3

Fundamentals of Logic Elements

Digital Logic, Logic Functions; Boolean
Algebra; Rules, Laws and Theorems,
Standard Form of Boolean Expression,
Simplification with Boolean Algebra and KV-
Diagram; Logic Circuits

1
Digital Logic
 The foundation/basis of digital electronic
systems, e.g computers.
 It provides information through zeros and
ones
 Logic signal is a representation of binary
information in physical systems;
 Voltage-0 and 5v
 Current-4 and 20 mAmp
 Switch- open and closed

The representation is in terms of 0s and 1s and

not in terms of the value of the voltage or
current
2
Logic Functions
 Logic function is mathematical relationship that
determines if a situation is true or false.
 The functions produces a precisely defined output
information to a given input information
 Both input and output information are preferably binary
values (0, 1)
 1=valve open ,flow/pressure present or current, light
present
 0=valve closed…..
 There are 3 basic logic functions
– OR
– AND
– NOT
 Other 2 common universal logic functions are
– NOR
– NAND 3
Logic gates
 These are logic circuits with one
output signal and two or more input
signals
 Types of Basic Logic Gates
– Combinational Logic Gate
• Logic Gate whose output logic value
depends only on the input logic values
– Sequential Logic Gate
• Logic Gate whose output logic value
depends on the input values and the
state (stored information) of the blocks
4
Truth Table

A truth table
– Is the most elementary specification of the
function of a logic circuit
– shows all the input possibilities for a given
logic circuit/statement and their
corresponding output
– For n logic variables, there are 2n possible
input combinations

5
Name Logic Gate Function Truth Table
A X=A•B A B X
X or 0 0 0
AND B X = AB
0
1
1
0
0
0
1 1 1
A A B X
X X=A+B 0 0 0
OR B 0 1 1
1 0 1
1 1 1
A X
A X X=A
NOT 0
1
1
0
A X
Buffer A X X=A 0 0
1 1
A A B X
0 0 1
X X = (AB)
NAND B
0
1
1
0
1
1
1 1 0
A B X
A
0 0 1
NOR B
X X = (A + B) 0 1 0
1 0 0
1 1 0
A X=A B A B X
XOR X or 0 0 0
Exclusive OR B X = AB + AB 0 1 1
1 0 1
1 1 0
A X = (A  B) A B X
XNOR X or 0
0
0
1
1
0
Exclusive NOR B X = AB + AB
or Equivalence 1 0 0
1 1 1
6
Logic gates Summary
• AND gate is a logic circuit that gives a high output
(1) only if all its inputs are high. A dot (.) is used to
show the AND operation i.e. A.B.
• OR gate is a logic circuit that gives a high output (1)
if one or more of its inputs are high. A plus (+) is
used to show the OR operation.
• NOT gate is a logic circuit that produces an inverted
version of the input at its output.
• NAND gate is a NOT-AND gate which is equal to an
AND gate followed by a NOT gate. The outputs of
all NAND gates are high if any of the inputs are low.
The symbol is an AND gate with a small circle on the
output.
7
Logic gates Summary
• NOR gate is a NOT-OR gate which is equal to an OR
gate followed by a NOT gate. The outputs of all
NOR gates are low if any of the inputs are high.
– The symbol is an OR gate with a small circle on
the output. The small circle represents inversion
• The 'Exclusive-OR' gate is a circuit which will
give a high output if either, but not both, of its
two inputs are high. An encircled plus sign is
used to show the XOR operation.
• XOR is also known as non equivalence gate

8
Logic gates Summary
• The 'Exclusive-NOR' gate circuit does the opposite
to the XOR gate. It will give a low output if either,
but not both, of its two inputs are high. The
symbol is an XNOR gate with a small circle on the
output. The small circle represents inversion
• XNOR is also known as Equivalence gate
• The NAND and NOR gates are called universal
gates since with either; one of the AND, OR and
NOT functions can be generated.

9
Boolean Algebra
• Developed by G. Boole in 1854
• Deals with the algebra of binary variables (two
outcomes(yes/no))
• Boolean algebra analyze and simplify logic
networks so that less components are used in
building the circuits
• Boolean variables are designated by 0 and 1
• Boolean function is a function whose inputs
and outputs are 0,1

10
Rules and Laws
• Several rules and laws are involved in
Boolean algebra
• These must be appreciated before embarking
on the design of logic circuits
Identity Laws
A+0 = A
A.1 = A
A.O=0
Idempotent Laws
A+A =A
A.A =A 11
Rules and Laws (Cont.)
Commutative Laws
A+B=B+A
A.B = B.A
Associative Laws
(A+B)+C = A+(B+C)
(A.B).C = A.(B.C)
Distributive Laws
A.(B+C) = A.B + A.C
(A+B).(C+D) = A.C + A.D + B.C + B.D
Involution Property
A= A
12
Rules and Laws (Cont.)
Complement Laws
A.A = 0
A+A=1
Absorption Laws
A+A.B = A
A +A.B =A+B

13
De-Morgan's Theorems
These theorems state that:

• The complement of the sum of variables is

equal to the product of their complements
A+B = A . B

• The complement of the product of variables

is equal to the sum of their complements
A.B = A + B
14
Forms of Boolean Expressions

• Sum-of-products (SOP)
– e.g.: X = ABC + DEF + AEF
– the product (AND) terms are formed first, then
summed (OR)
• Product-of-sums (POS)
– e.g.: Y = (A+B+E)(C+D+E)(B+F)
– the sum (OR) terms are formed first, then the
product (AND)
• • It is possible to convert between the two forms
using DeMorgan’s theorems.
15
Forms of Boolean Expressions

Canonical form
• In the canonical form of a Boolean expression,
every variable appears in every term
– e.g.: f (A, B,C,D) = ABCD + ABCD + ABCD
• Canonical form is not an efficient way of
writing the Boolean expression, but is useful
sometimes in design and analysis

16
Forms of Boolean Expressions
How do we find the canonical form of an
expression?
– Start with the SOP (sum-of-products) form
– AND each incomplete expression with X + X
where X is the missing variable
• e.g.: f (A B C) = AB + BC
= AB(C +C) + BC(A +A)
=ABC + ABC + ABC
• The product term in a canonical SOP
expression is called a ‘minterm’ 17
Canonical form and Σ notation
Construct the truth table for the function:
f (A, B,C) = ABC + ABC + ABC

Row number A B C f
0 0 0 0 0
1 0 0 1 0
2 0 1 0 0
3 0 1 1 1
4 1 0 0 0
5 1 0 1 0
6 1 1 0 1
7 1 1 1 1

18
Simplifying logic circuits
 Obtaining the expression of the circuit’s function, then trying
to simplify
 Two methods may be used:
 Algebraic
 Karnaugh maps
 3 tools you can try when simplifying by Boolean Algebra
 Grouping
 ANDing with redundant logic (x+ x)
 DeMorgan’s Theorem

 Example: Design a logic circuit having three inputs (A,B,C)

that will have its output HIGH only when the majority of the
inputs are HIGH
19
Logic Function Simplification-
Karnaugh-Veitch (KV) Map
 KV map is one of the useful method of
minimizing/simplifying logic functions
 Each possible input combination is
represented by one square called a CELL
 The cells are arranged in a Gray Code (also
known as reflected binary code). This is a
binary system where adjacent cells differ
from one another by one variable

20
Logic Function Simplification-
Karnaugh-Veitch (KV) Map
 The KV map is like a truth table written out in
a particular form

21
KV Map (Cont)

 The KV map is written out in a particular form

for 3 variables

22
KV Map (Cont)

 The KV map is written out in a particular form

for 4 variables

23
KV Map (Cont)

 From given truth table, the KV map can be

constructed

A B C f
0
 0 0 0
AB
0 0 1 0 00 01 11 10
0 1 0 1 C 0 0 1 1 1
0
A 1 1 0 1 0 0 0 1
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 0
24
KV Map (Cont)

 From given truth table, the KV map can be

constructed
 From the filled table the number of 1s can be
circled should be 1,2,4,8,……(power of 2)
 Then,

25
KV Map (Cont)

 From filled KV map constructed

 Looking for variable that does not change in two cells

f(A,B,C) = BC’ + AB’

26
Examples of KV Maps
 A three variable function: f(A,B,C)
BC
00 01 11 10
A 0
1

 A four variable function

CD
00 01 11 10
00

AB 01
11
10 27
Filling out a KV Map
 Write the Boolean expression in SOP form
 For each product term, write a 1 in all the
squares which are included in the term
 Write a 0 in the remaining blank squares
 X= ABC +ABC + ABC
BC
00 01 11 10
0
A 1

28
Simplification
 X= ABC +ABC + ABC
 BC
00 01 11 10
A 0 0 0 1 0
1 0 0 1 1

 The adjacent squares A’BC and ABC differ only in A, therefore

they can be combined into just BC…..draw a box around
squares to be combined….do that for larger groups of 1s (of
4,8,….)
 ‘Cover’ all the 1s with the largest groups
 The simplified Boolean expression is found by summing all
the terms corresponding to each group.
 Note: all 1s must be part of a group, even a single group. All
groups must be of size 1, 2, 4, 8, 16,….. 29
KV-Map Simplification Summary
1. Construct the K-map and place 1s and 0s in the
squares according to the SOP expression or truth
table
2. Find the largest grouping of 1s that are not already
in a group. If there is more than one possibility,
choose a grouping that minimizes the total number
of groups
3. Repeat step 2 until only isolated 1s remain
4. Form single groups of the remaining isolated 1s
5. Find the product term that corresponds to each
group
6. OR together all the product terms. 30
KV Map (Cont.)

KV Simplification Rules:
(1)Identify the input combinations with 1s
output which actually form a logic function
Example: Inputs A and B; output X)

A B X
0 0 0
_ _
0 1 1 X=AB+AB+AB
1 0 1
1 1 1 31
KV Map (Cont.)

(2) Draw the KV map placing the outputs in the

respective cells
_
B B

A 1 1 _ _
X=AB+AB+AB
_
A 1 0

32
KV Map (Cont.)
(3) Only adjacent 1s can be grouped together
either horizontally or vertically
(4) The number of 1s in a group should fall in 2n
i.e. 1, 2, 4, 8, etc.
(5) A grouped 1s can appear in more than one
group if necessary
_
B B

A 1 1
X= A + B
_
A 1 0
33
KV Map (Cont.)

(6) The KV map is considered to be a sphere

with sides being adjacent to each other
_ _ _ _
BC BC BC
BC

A 1 1

_
A
(7) Keep the number of groups to the minimum
as much as possible
34
Logic Circuits
 Logic functions can be realized from several
ways including
– Truth table
– Switching network
– Logic statements
 The logic function can then be converted into
logic circuits for the actual implementation of
logic system

35
Logic circuits (Cont.)

36
Logic Circuits (Cont.)

37