Faculty of Engineering

Chapter (3)
1
Main Building Blocks
CSE001: Introduction to Computers & Programing
2
Logic Gates
Part (A)
3
Introduction
Switching Circuit:

AND OR
4
Basic Gates
Unary gate:

NOT (Inverter)
5
Basic Gates
Unary and binary gates:

NOT (Inverter)
6
Basic Gates
Unary and binary gates:

NOT (Inverter)
7
Basic Gates
Unary and binary gates:

NOT (Inverter)
8
Basic Gates
With 3 inputs: Guess the outputs ??
9
Basic Gates
With 3 inputs: Guess the outputs ??
10
Basic Gates
With 3 inputs: Guess the outputs ??
11
Basic Gates
With 3 inputs:
12
Inverted Basic Gates
Buffer: Inverted NOT:
13
Inverted Basic Gates
NAND: Inverted AND:
14
Inverted Basic Gates
NOR: Inverted OR:
15
Inverted Basic Gates
Exclusive NOR: Inverted XOR
Are they different? Are they similar?

𝑋 = 𝐴⨁𝐵 𝑋 =𝐴⊙𝐵
16
Summary
17
Summary
Any of those is enough for a full description of logic circuit:
Circuit diagram.
Boolean expression.
Truth table: A table that traces the output value for all the
possible inputs.
The binary gates can be expanded to more than two inputs:
18
Question ??
Which logic gate is equivalent to:

Step (1): Draw circuit diagram:

Start with each ( ).
Draw the NAND gate.
𝑋1 = 𝐴. 𝐵 𝑋1
19
Question ??
Which logic gate is equivalent to:

Draw circuit diagram:

Start with each ( ).
Draw the NAND gate.
𝑋1 = 𝐴. 𝐵 𝑋1
Draw the OR gate.
𝑋2 = 𝐴 + 𝐵 𝑋2
20
Question ??
Which logic gate is equivalent to:

Draw circuit diagram:

AND between 𝑋1 , 𝑋2
𝑋 = 𝑋1 . 𝑋2
𝑋1
𝑋 = 𝐴. 𝐵 . 𝐴 + 𝐵

𝑋2
21
Question ??
Which logic gate is equivalent to:

Draw circuit diagram:

AND between 𝑋1 , 𝑋2
𝑋 = 𝑋1 . 𝑋2
𝑋1
𝑋 = 𝐴. 𝐵 . 𝐴 + 𝐵
Optimize figure.
𝑋2
22
Question ??
Truth table of X:
Truth table of 𝑋1 =?? 𝑋1
𝑋1 = 𝐴. 𝐵

𝑋2
23
Question ??
Truth table of X:
Truth table of 𝑋1 =?? 𝑋1
𝑋1 = 𝐴. 𝐵

𝑋2
24
Question ??
Truth table of X:
Truth table of 𝑋1 =?? 𝑋1
𝑋1 = 𝐴. 𝐵
Truth table of 𝑋2 =??
𝑋2
𝑋2 = 𝐴 + 𝐵
25
Question ??
Truth table of X:
Truth table of 𝑋1 =?? 𝑋1
𝑋1 = 𝐴. 𝐵
Truth table of 𝑋2 =??
𝑋2
𝑋2 = 𝐴 + 𝐵
26
Question ??
Truth table of X:
Truth table of 𝑋=?? 𝑋1
𝑋 = 𝑋1 ∙ 𝑋2

𝑋2
27
Question ??
Truth table of X:
Truth table of 𝑋=?? 𝑋1
𝑋 = 𝑋1 ∙ 𝑋2

𝑋2
28
Question ??
Truth table of X:
Truth table of 𝑋=?? 𝑋1
𝑋 = 𝑋1 ∙ 𝑋2
Summary:
𝑋2
29
Question ??
Truth table of X:
Truth table of 𝑋=?? 𝑋1
𝑋 = 𝑋1 ∙ 𝑋2
Summary:
𝑋2

Compare the known truth tables of logic gates

It is the truth table of XOR.
30
Boolean Algebra
Part (B)
31
Boolean Algebra
Mathematician George Boole.
Introduced the concepts of the
3 main logical operations, AND,
OR, NOT, in the 19th century.
Then the Boolean algebra was
established to handle equations
of Boolean variables where
each variable is YES or NO.
It is used to design simplify
digital logic circuits.
32
Operations with 0
From the AND truth table:
Any AND with zero is zero.
0∙𝑋 =𝑋∙0=0

From the OR truth table:

The OR of any value with zero is the
same value.
0+𝑋 =𝑋+0=𝑋
33
Operations with 1
From the AND truth table:
The AND of any value with 1 is the same
value
1∙𝑋 =𝑋∙1=𝑋

From the OR truth table:

Any OR with 1 is 1
1+𝑋 =𝑋+1=1
34
Idempotent
The operation of a variable with itself:
From the AND truth table:
𝑋∙𝑋 =𝑋

From the OR truth table:

𝑋+𝑋 =𝑋
35
Complementarity
The operation of a variable with its
complement:
From the AND truth table:
 𝑋 ∙ 𝑋ത = 0

From the OR truth table:

 𝑋 + 𝑋ത = 1
36
XOR Properties
From truth table:
 Any value XOR'd with itself gives zero.
AA = 0
37
XOR Properties
From truth table:
 Any value XOR'd with itself gives zero.
AA = 0
Any value XOR'd with its complement gives
one.
AA' = 1
38
XOR Properties
From truth table:
 Any value XOR'd with itself gives zero.
AA = 0
Any value XOR'd with its complement gives
one.
AA' = 1
Any value XOR'd with zero left unchanged.
Y0 = Y
39
XOR Properties
From truth table:
 Any value XOR'd with itself gives zero.
AA = 0
Any value XOR'd with its complement gives
one.
AA' = 1
Any value XOR'd with zero left unchanged.
Y0 = Y
Any value XOR'd with one is complemented:
Y1 = Y'
40
Simple Laws
ҧ =𝐴+𝐵
𝐴 + 𝐴𝐵
Involution Law:
 𝑋′ ′
=𝑋
Commutative Laws:
𝑋 + 𝑌 = 𝑌 + 𝑋
𝑋𝑌 = 𝑌𝑋
Distributive laws
𝑋 𝑌 + 𝑍 = 𝑋𝑌 + 𝑋𝑍
𝑋 + 𝑌𝑍 = 𝑋 + 𝑌 ∙ 𝑋 + 𝑍
41
Associative Laws
𝑋+𝑌 +𝑍 =𝑋+ 𝑌+𝑍
=𝑋+𝑌+𝑍 X
Y
Z

X
Y
Z

X
Y
Z
42
Associative Laws
𝑋+𝑌 +𝑍 =𝑋+ 𝑌+𝑍
=𝑋+𝑌+𝑍 X
Y
Z

X
Y
Z

𝑋𝑌 𝑍 = 𝑋 𝑌𝑍 X
Y
= 𝑋𝑌𝑍 Z
43
DeMorgan’s Laws
DeMorgan's Laws:
 𝑋 + 𝑌 + 𝑍 = 𝑋ത ∙ 𝑌ത ∙ 𝑍ҧ
 𝑋 ∙ 𝑌 ∙ 𝑍 = 𝑋ത + 𝑌ത + 𝑍ҧ

Example: 𝑋 + 𝑌ത + 𝑍 = 𝑋ത ∙ 𝑌 ∙ 𝑍ҧ
Example: 𝑋 ∙ 𝑌ത + 𝑍 = 𝑋 ∙ 𝑌ത ∙ 𝑍ҧ = 𝑋ത + 𝑌 ∙ 𝑍ҧ
44
Example
Find the equation of the given A B C
circuit, use Boolean algebra to
simplify it, and draw the circuit
after simplification.
𝐹 = 𝐴 + 𝐵ത 𝐴 + 𝐶
𝐹 = 𝐴𝐴 + 𝐴𝐶 + 𝐴𝐵ത + 𝐵𝐶
ത
A B C
𝐹 = 𝐴 + 𝐴𝐶 + 𝐴𝐵ത + 𝐵𝐶
ത

𝐹 = 𝐴 1 + 𝐶 + 𝐵ത + 𝐵𝐶
ത
1
ത
𝐹 = 𝐴 + 𝐵𝐶
45
Example
Draw the circuit diagram that implements following
equation:
𝑌 = 𝐴𝐵 + 𝐴 𝐵 + 𝐶 + 𝐵 𝐵 + 𝐶
Simplify the expression and draw the circuit after
simplification.
46
Example
Draw the circuit diagram that implements following
equation:
𝑌 = 𝐴𝐵 + 𝐴 𝐵 + 𝐶 + 𝐵 𝐵 + 𝐶
Simplify the expression and draw the circuit after
simplification.
47
Example
Draw the circuit diagram that implements following
equation:
𝑌 = 𝐴𝐵 + 𝐴 𝐵 + 𝐶 + 𝐵 𝐵 + 𝐶
Simplify the expression and draw the circuit after
simplification.
48
Example
Draw the circuit diagram that implements following
equation:
𝑌 = 𝐴𝐵 + 𝐴 𝐵 + 𝐶 + 𝐵 𝐵 + 𝐶
Simplify the expression and draw the circuit after
simplification.
49
Example
Draw the circuit diagram that implements following
equation:
𝑌 = 𝐴𝐵 + 𝐴 𝐵 + 𝐶 + 𝐵 𝐵 + 𝐶
Simplify the expression and draw the circuit after
simplification.
50
Example
Draw the circuit diagram that implements following
equation:
𝑌 = 𝐴𝐵 + 𝐴 𝐵 + 𝐶 + 𝐵 𝐵 + 𝐶
Simplify the expression and draw the circuit after
simplification.
𝑌 = 𝐴𝐵 + 𝐴𝐵 + 𝐴𝐶 + 𝐵𝐵 + 𝐵𝐶
𝑌 = 𝐴𝐵 + 𝐴𝐶 + 𝐵 + 𝐵𝐶
𝑌 = 𝐴𝐶 + 𝐵 1 + 𝐴 + 𝐶
𝑌 = 𝐴𝐶 + 𝐵
51
Example
Draw the circuit diagram that implements following
equation:
𝑌 = 𝐴𝐵 + 𝐴 𝐵 + 𝐶 + 𝐵 𝐵 + 𝐶
Simplify the expression and draw the circuit after
simplification.
𝑌 = 𝐴𝐶 + 𝐵
52
Example
Draw the circuit diagram that implements following
equation:
𝑌 = 𝐴𝐵 + 𝐴 𝐵 + 𝐶 + 𝐵 𝐵 + 𝐶
Simplify the expression and draw the circuit after
simplification.
𝑌 = 𝐴𝐶 + 𝐵
53
Example
Draw the circuit diagram that implements following
equation:
𝑌 = 𝐴𝐵 + 𝐴 𝐵 + 𝐶 + 𝐵 𝐵 + 𝐶
Simplify the expression and draw the circuit after
simplification.
𝑌 = 𝐴𝐶 + 𝐵
54
Example
Find the percentage
of reduction in the
number of gates due
to simplification.
It is the difference in
number of gates as
percentage of
original number:
5−2
= × 100%
5
= 60%
55
Example
Using Boolean algebra, proof the following:
𝐴ҧ + 𝐵ത 𝐴 + 𝐵 = 𝐴𝐵ത + 𝐴𝐵 ҧ
Solution:
𝐴ҧ + 𝐵ത 𝐴 + 𝐵 = 𝐴𝐴
ҧ + 𝐴𝐵
ҧ + 𝐵𝐴
ത + 𝐵𝐵
ത

𝐴ҧ + 𝐵ത 𝐴 + 𝐵 = 𝐴𝐵ത + 𝐴𝐵
ҧ
56
Example
Apply DeMorgan’s law to simplify the following circuit:
𝐹 = 𝐴𝐵 𝐶𝐷 + 𝐴𝐶 ҧ
Solution:
ҧ
𝐹 = 𝐴𝐵 + 𝐶𝐷 + 𝐴𝐶

𝐹 = 𝐴ҧ + 𝐵ത + 𝐶𝐷 ⋅ 𝐴𝐶
ҧ

ഥ 𝐴ҧ + 𝐶ҧ
𝐹 = 𝐴ҧ + 𝐵ത + 𝐶ҧ + 𝐷
𝐹 = 𝐴ҧ + 𝐵ത + 𝐶ҧ + 𝐷
ഥ 𝐴 + 𝐶ҧ
𝐹 = 𝐴ҧ + 𝐵ത + 𝐶𝐴
ҧ + 𝐶ҧ 𝐶ҧ + 𝐷 ഥ 𝐶ҧ
ഥ𝐴 + 𝐷
57
Example
Apply DeMorgan’s law to simplify the following circuit:
𝐹 = 𝐴𝐵 𝐶𝐷 + 𝐴𝐶 ҧ
Solution:
𝐹 = 𝐴ҧ + 𝐵ത + 𝐶𝐴
ҧ + 𝐶ҧ + 𝐷 ഥ 𝐶ҧ
ഥ𝐴 + 𝐷
𝐹 = 𝐴ҧ + 𝐵ത + 𝐶ҧ 𝐴 + 1 + 𝐷
ഥ +𝐷
ഥ𝐴
𝐹 = 𝐴ҧ + 𝐵ത + 𝐶ҧ + 𝐷
ഥ𝐴
𝐹 = 𝐴ҧ + 𝐴𝐷
ഥ + 𝐵ത + 𝐶ҧ
𝐹 = 𝐴ҧ + 𝐵ത + 𝐶ҧ + 𝐷
ഥ
58
Equation to Truth Table
Find the truth table of Input Output
the following equation: A B C F
𝐹 = 𝐴𝐵𝐶 ത + 𝐴𝐵
How many inputs?
How many rows in the
truth table?
How to fill the input
side?
59
Equation to Truth Table
Find the truth table of Input Output
the following equation: A B C AB' C AB F
𝐹 = 𝐴𝐵𝐶 ത + 𝐴𝐵 0 0 0 0 0
How many inputs? 0 0 1 0 0
How many rows in the 0 1 0 0 0
truth table? 0 1 1 0 0
How to fill the input 1 0 0 0 0
side?
1 0 1 1 0
Find the truth table of
each separate term. 1 1 0 0 1
1 1 1 0 1
60
Equation to Truth Table
Find the truth table of Input Output
the following equation: A B C AB' C AB F
𝐹 = 𝐴𝐵𝐶 ത + 𝐴𝐵 0 0 0 0 0 0
How many inputs? 0 0 1 0 0 0
How many rows in the 0 1 0 0 0 0
truth table? 0 1 1 0 0 0
How to fill the input 1 0 0 0 0 0
side?
1 0 1 1 0 1
Find the truth table of
each separate term. 1 1 0 0 1 1
1 1 1 0 1 1
61
Truth Table to Equation
Find the simplified Boolean expression of Input Output
the following truth table: A B C F
The output is 1 in case of the 5th input OR 0 0 0 0
the 6th input OR the 7th input: 0 0 1 0
ത + 𝐴𝐵 𝐶ҧ + 𝐴𝐵𝐶
𝐹 = 𝐴𝐵𝐶 0 1 0 0
Simplify: 0 1 1 0
ത + 𝐴𝐵(𝐶ҧ + 𝐶)
𝐹 = 𝐴𝐵𝐶
1 0 0 0
ത + 𝐴𝐵
𝐹 = 𝐴𝐵𝐶 1 0 1 1
This is the equation of previous slide but: 1 1 0 1
ത =𝐴 𝐵+𝐶
𝐹 = 𝐴 𝐵 + 𝐵𝐶 1 1 1 1
62
XOR Gate
We know the XOR equation: 𝑋 = 𝐴 ⊕ 𝐵
Given its truth table, find the equation:
𝑋 = 𝐴𝐵 ҧ + 𝐴𝐵ത
𝐴 ⊕ 𝐵 = 𝐴𝐵 ҧ + 𝐴𝐵ത
Draw the circuit:
63
XOR Gate
We know the XOR equation: 𝑋 = 𝐴 ⊕ 𝐵
Given its truth table, find the equation:
𝑋 = 𝐴𝐵 ҧ + 𝐴𝐵ത
𝐴 ⊕ 𝐵 = 𝐴𝐵 ҧ + 𝐴𝐵ത
Draw the circuit:
64
XOR Gate
We know the XOR equation: 𝑋 = 𝐴 ⊕ 𝐵
Given its truth table, find the equation:
𝑋 = 𝐴𝐵 ҧ + 𝐴𝐵ത
𝐴 ⊕ 𝐵 = 𝐴𝐵 ҧ + 𝐴𝐵ത
Draw the circuit:
65
XOR Gate
We know the XOR equation: 𝑋 = 𝐴 ⊕ 𝐵
Given its truth table, find the equation:
𝑋 = 𝐴𝐵 ҧ + 𝐴𝐵ത
𝐴 ⊕ 𝐵 = 𝐴𝐵 ҧ + 𝐴𝐵ത
Draw the circuit:
66
XOR Gate
Similarly, for 3-input XOR: 𝑋 = 𝐴 ⊕ 𝐵 ⊕ 𝐶
Given its truth table, find the equation:
𝑋 = 𝐴ҧ𝐵𝐶ത + 𝐴𝐵 ҧ 𝐶ҧ + 𝐴𝐵ത 𝐶ҧ + 𝐴𝐵𝐶
𝐴 ⊕ 𝐵 ⊕ 𝐶 = 𝐴ҧ 𝐵𝐶 ത + 𝐴𝐵 ҧ 𝐶ҧ + 𝐴𝐵ത 𝐶ҧ + 𝐴𝐵𝐶
67
XOR Gate
Draw the circuit:
𝐴 ⊕ 𝐵 ⊕ 𝐶 = 𝐴𝐵𝐶 + 𝐴𝐵ത 𝐶ҧ + 𝐴𝐵
ҧ 𝐶ҧ + 𝐴ҧ𝐵𝐶
ത
68
XOR Gate
Draw the circuit:
𝐴 ⊕ 𝐵 ⊕ 𝐶 = 𝐴𝐵𝐶 + 𝐴𝐵ത 𝐶ҧ + 𝐴𝐵
ҧ 𝐶ҧ + 𝐴ҧ𝐵𝐶
ത

ABC
69
XOR Gate
Draw the circuit:
𝐴 ⊕ 𝐵 ⊕ 𝐶 = 𝐴𝐵𝐶 + 𝐴𝐵ത 𝐶ҧ + 𝐴𝐵
ҧ 𝐶ҧ + 𝐴ҧ𝐵𝐶
ത

ABC

AB'C'
70
XOR Gate
Draw the circuit:
𝐴 ⊕ 𝐵 ⊕ 𝐶 = 𝐴𝐵𝐶 + 𝐴𝐵ത 𝐶ҧ + 𝐴𝐵
ҧ 𝐶ҧ + 𝐴ҧ𝐵𝐶
ത

ABC

AB'C'

A'BC'

A'B'C
71
XOR Gate
Draw the circuit:
𝐴 ⊕ 𝐵 ⊕ 𝐶 = 𝐴𝐵𝐶 + 𝐴𝐵ത 𝐶ҧ + 𝐴𝐵
ҧ 𝐶ҧ + 𝐴ҧ𝐵𝐶
ത

ABC

AB'C'

A'BC'

A'B'C
72
XNOR Gate
We know the XNOR equation: 𝑋 = 𝐴 ⊕ 𝐵
Given its truth table, find the equation:
𝑋 = 𝐴ҧ 𝐵ത + 𝐴𝐵
𝐴 ⊕ 𝐵 = 𝐴ҧ 𝐵ത + 𝐴𝐵
Or by complementing the XOR equation:
𝐴 ⊕ 𝐵 = 𝐴𝐵 ҧ + 𝐴𝐵ത
𝐴 ⊕ 𝐵 = 𝐴𝐵 ҧ + 𝐴𝐵ത
𝐴 ⊕ 𝐵 = 𝐴 + 𝐵ത ∙ 𝐴ҧ + 𝐵
𝐴 ⊕ 𝐵 = 𝐴𝐴ҧ + 𝐴𝐵 + 𝐵ത 𝐴ҧ + 𝐵𝐵
ത
𝐴 ⊕ 𝐵 = 𝐴ҧ 𝐵ത + 𝐴𝐵
73
XNOR Gate
Draw the circuit 𝐴 ⊕ 𝐵 = 𝐴ҧ𝐵ത + 𝐴𝐵:

Find 𝐴 ⊕ 𝐵ത ?
Substitute in: 𝐴 ⊕ 𝐵 = 𝐴𝐵 ҧ + 𝐴𝐵ത
𝐴 ⊕ 𝐵ത = 𝐴ҧ𝐵ത + 𝐴𝐵
Similarly: 𝐴ҧ ⊕ 𝐵 = 𝐴ҧ𝐵ത + 𝐴𝐵
𝐴 ⊕ 𝐵 = 𝐴 ⊕ 𝐵ത = 𝐴ҧ ⊕ 𝐵
74
XNOR Gate
Similarly, for 3-input XNOR: 𝑋 = 𝐴 ⊕ 𝐵 ⊕ 𝐶
Given its truth table, find the equation:
𝑋 = 𝐴ҧ𝐵ത 𝐶ҧ + 𝐴𝐵𝐶
ҧ + 𝐴𝐵𝐶ത + 𝐴𝐵𝐶ҧ
𝐴 ⊕ 𝐵 ⊕ 𝐶 = 𝐴ҧ 𝐵ത 𝐶ҧ + 𝐴𝐵𝐶ҧ ത + 𝐴𝐵 𝐶ҧ
+ 𝐴𝐵𝐶
75
XNOR Gate
Draw the circuit:
𝐴 ⊕ 𝐵 ⊕ 𝐶 = 𝐴𝐵 𝐶ҧ + 𝐴𝐵𝐶 ҧ
ത + 𝐴𝐵𝐶 + 𝐴ҧ𝐵ത 𝐶ҧ
76
XNOR Gate
Draw the circuit:
𝐴 ⊕ 𝐵 ⊕ 𝐶 = 𝐴𝐵 𝐶ҧ + 𝐴𝐵𝐶 ҧ
ത + 𝐴𝐵𝐶 + 𝐴ҧ𝐵ത 𝐶ҧ
77
XNOR Gate
Draw the circuit:
𝐴 ⊕ 𝐵 ⊕ 𝐶 = 𝐴𝐵 𝐶ҧ + 𝐴𝐵𝐶 ҧ
ത + 𝐴𝐵𝐶 + 𝐴ҧ𝐵ത 𝐶ҧ
78
XNOR Gate
Draw the circuit:
𝐴 ⊕ 𝐵 ⊕ 𝐶 = 𝐴𝐵 𝐶ҧ + 𝐴𝐵𝐶 ҧ
ത + 𝐴𝐵𝐶 + 𝐴ҧ𝐵ത 𝐶ҧ
79
XNOR Gate
Draw the circuit:
𝐴 ⊕ 𝐵 ⊕ 𝐶 = 𝐴𝐵 𝐶ҧ + 𝐴𝐵𝐶 ҧ
ത + 𝐴𝐵𝐶 + 𝐴ҧ𝐵ത 𝐶ҧ
80
XNOR Gate
Draw the circuit:
𝐴 ⊕ 𝐵 ⊕ 𝐶 = 𝐴𝐵 𝐶ҧ + 𝐴𝐵𝐶 ҧ
ത + 𝐴𝐵𝐶 + 𝐴ҧ𝐵ത 𝐶ҧ
81
XOR with Three Inputs
Implementing 3-inputs XOR with 2-inputs XORs:
𝑋⨁𝑌⨁𝑍 = 𝑋⨁𝑌 ⨁𝑍 = 𝑋⨁ 𝑌⨁𝑍

X X
X
Y Y Y
Z
Z Z

This is NOT applied to XNOR.

Use the center configuration to extend to more than three
inputs
82
XOR with Four or More Inputs
Generally, implementing N-inputs XOR with 2-inputs XORs:
Cascaded:
83
XOR with Four or More Inputs
Generally, implementing N-inputs XOR with 2-inputs XORs:
Tree:
84
XNOR with Multiple Inputs
You can implement N-input XOR using any method and put
extra NOT gate at the output to give N-input XNOR.
85
Example
Using truth tables, proof DeMorgan’s law:
𝐴 ∙ 𝐵 = 𝐴ҧ + 𝐵ത
Find truth table for each side:
A B AB (AB)' A' B' A'+B'
0 0 0 1 1 1 1
0 1 0 1 1 0 1
1 0 0 1 0 1 1
1 1 1 0 0 0 0
ҧ = 𝐴 + 𝐵.
Similarly, we can proof other laws like: 𝐴 + 𝐴𝐵
86
Half and Full Adders
Part (C)
87
Remember
Addition of single bits:
1
0 1 0 1 +1
+0 +0 +1 +1 +1
0 1 1 10 11

Addition of two whole numbers:

1
7 1 1 1
+6 1 1 0

13 1 1 0 1
88
Addition Circuits
It is required to design a circuit that adds two corresponding
bits from the two numbers being added:
Half adder.
Full adder.
Then, we should use them to design an adder circuit for the
whole two numbers:
Parallel adder.
Then, we will modify this circuit to perform also the
subtraction of the two numbers:
Parallel adder/subtractor.
89
Half Adder
Example:
1
0 1 0 1 +1
+0 +0 +1 +1 +1
0 1 1 10 11

A half adder is a circuit that adds two bits to

half adder
form a sum bit and a carry. Design it!
How many inputs?
90
Half Adder
Example:
1
0 1 0 1 +1
+0 +0 +1 +1 +1
0 1 1 10 11

A half adder is a circuit that adds two bits to

half adder
form a sum bit and a carry. Design it!
How many inputs? Two inputs.
How many outputs?
91
Half Adder
Example:
1
0 1 0 1 +1
+0 +0 +1 +1 +1
0 1 1 10 11

A half adder is a circuit that adds two bits to

half adder
form a sum bit and a carry. Design it!
How many inputs? Two inputs.
How many outputs? Two outputs.
92
Half Adder
Construct the truth table.
How many rows and how to file the input ??
side?

half adder
93
Half Adder
Construct the truth table.
How many rows and how to file the input ??
side?

half adder
94
Half Adder
Construct the truth table.
How many rows and how to file the input
side?
Find the equation of Sum output?
𝑆 = 𝐴⨁𝐵

half adder
95
Half Adder
Construct the truth table.
How many rows and how to file the input
side?
Find the equation of Sum output?
𝑆 = 𝐴⨁𝐵
Find the equation of Carry output?
𝐶 = 𝐴𝐵 half adder
Draw the circuit.
96
Full Adder
Example:
1
7 1 1 1
+6 1 1 0

13 1 1 0 1
It is required to design a logic circuit
that adds two bits (from the two
numbers) and a carry in from previous
addition.
How many inputs?
97
Full Adder
Example:
1
7 1 1 1
+6 1 1 0

13 1 1 0 1
It is required to design a logic circuit
that adds two bits (from the two
numbers) and a carry in from previous
addition.
How many inputs? Three inputs.
98
Full Adder
Example:
1
7 1 1 1
+6 1 1 0

13 1 1 0 1
How many outputs?
99
Full Adder
Example:
1 ??
7 1 1 1
+6 1 1 0

13 1 1 0 1
How many outputs? Two outputs.
Construct the truth table.
How many rows and how to file the
input side?
100
Full Adder
Example:
1
7 1 1 1
+6 1 1 0 ??

13 1 1 0 1
How many outputs? Two outputs.
Construct the truth table.
How many rows and how to file the
input side?
101
Full Adder
Example:
1
7 1 1 1
+6 1 1 0

13 1 1 0 1
How many outputs? Two outputs.
Construct the truth table.
How many rows and how to file the
input side?
102
Full Adder
The full adder is a circuit that perform
a single bit to bit addition with carry in
and carry out. It perform a single stage
of this two number addition.
It adds three bits, one of them is
usually the carry in from previous
stage, to form a sum bit and a carry
out to the next stage.

Find the equation of Sum output?

103
Full Adder
Equation of Sum:
S = X'Y'Cin + X'YCin' + XY'Cin' +
XYCin
S = ??
104
Full Adder
Equation of Sum:
S = X'Y'Cin + X'YCin' + XY'Cin' +
XYCin
S = X  Y  Cin

Equation of Cout: ??
Cout = X'YCin + XY'Cin
+ XYCin' + XYCin
Cout = (X'Y+XY')Cin + XY(Cin'+Cin)
Cout = Cin(XY) + XY
105
Full Adder
Equations of full adder:
Cout = XY + Cin(XY)
S = X  Y  Cin
Draw the circuit:
X XY
Y
106
Full Adder
Equations of full adder:
Cout = XY + Cin(XY)
S = X  Y  Cin
Draw the circuit:
X XY
Y

(XY)Cin

XY
107
Full Adder
Equations of full adder:
Cout = XY + Cin(XY)
S = X  Y  Cin
Draw the circuit:
X XY
Y

(XY)Cin

XY
108
Full Adder
Equations of full adder:
Cout = XY + Cin(XY)
S = X  Y  Cin
Draw the circuit:
X XY
Y

(XY)Cin

XY
109
Example
Implement the full adder using two half adders and external
circuits.
110
Example
Implement the full adder using two half adders and external
circuits.
111
Example
Implement the full adder using two half adders and external
circuits.
112
Example
Implement the full adder using two half adders and external
circuits.

A S A S
B C B C
113
Example
Show how to add 1+0+1 on this circuit.

1 A S 1 A 0
S
0 B C 0 1 0
B C

1
1
114
Example
Show how to add 1+0+1 on the block diagram of full adder.
1 0

1 1

0
115
Parallel Adder
Example: 1 1 0
A=15 1 1 1 1
+ B= 6 1 1 0
21 1 0 1 0 1
A half adder adds the LSBs of each number.

HA
116
Parallel Adder
Example: 1 1 0
A=15 1 1 1 1
+ B= 6 1 1 0
21 1 0 1 0 1
The full adder adds 2 corresponding bit of each number.

HA
117
Parallel Adder
Example: 1 1 0
A=15 1 1 1 1
+ B= 6 1 1 0
21 1 0 1 0 1
The full adder adds 2 corresponding bit of each number.

HA
118
Parallel Adder
Example: 1 1 0
A=15 1 1 1 1
+ B= 6 1 1 0
21 1 0 1 0 1
The full adder adds 2 corresponding bit of each number.

HA
119
Parallel Adder
Example: 1 1 0
A=15 1 1 1 1
+ B= 6 1 1 0
21 1 0 1 0 1
Or we can use full adder for the LSBs with C0 = 0.
120
Parallel Adder
So, for adding any two n-bits numbers, n full adders are
required.
Example, adding two 4-bit numbers:
121
Parallel Adder/Subtractor
How to extend the previous circuit to also subtract the two
numbers?
To subtract A – B, we add A + (– B).
So, we need to find the two’s complement of B and add A.
122
Parallel Adder/Subtractor
Take the two’s complement of the second number and add.
+6 0 1 1 0 0 1 1 0
- (+7) 0 1 1 1 1 0 0 0
1
= -1 1 1 1 1
123
Parallel Adder/Subtractor
In other words, flip each bit in the second number and add 1.
+6 0 1 1 0 0 1 1 0
- (+7) 0 1 1 1 1 0 0 0
1
= -1 1 1 1 1
How to find the complement of each bit?
124
Parallel Adder/Subtractor
Remember: Any value XOR'd with zero left
unchanged:
𝐴⊕0=𝐴

𝐴
0
125
Parallel Adder/Subtractor
Remember: Any value XOR'd with one is
complemented:
𝐴 ⊕ 1 = 𝐴ҧ

𝐴ҧ
1
126
Parallel Adder/Subtractor
𝐴ҧ
Remember: A1 = A' 1

To subtract, put M = 1: The XOR is inverter and Cin = 1

127
Parallel Adder/Subtractor
𝐴
Remember: A0 = A 0

To add, put M = 0: The XOR is buffer and no Cin (previous

circuit).
128
Example
Design a 3-bit adder/subtractor and show on circuit how to
subtract A-B where A = 101 and B = 10:
A-B = 101-010 = 011
0 1 0

1 1 0 0 1 1

1 0 1 1

0 1 1