Logic Gates

M. ARIFUR RAHMAN
LECTURER, CS, AIUB
EMAIL: ARIF@[Link]
 Learning Objectives

In this chapter you will learn about:

 Logic gates
 Logic circuits and Boolean expressions
 Combinational circuits and design
 Logic Gates

 Logic gates are electronic circuits that operate on

one or more input signals to produce standard output
signal
 Are the building blocks of all the circuits in a
computer
 Some of the most basic and useful logic gates are
AND, OR, NOT, NAND and NOR gates
 AND Gate

 Physical realization of multiplication (AND)

operatio logical
n
 Generates an signal of 1 if all input
output signals are only
also 1
AND Gate (Block Diagram Symbol and Truth Table)

A
C= A
B
B
Inputs Output
A B C=AB
0 0 0
0 1 0
1 0 0
1 1 1
 OR Gate

 Physical realization of logical addition (OR) operation

 Generates an output signal of 1 if at least one of the

input signals is also 1
OR Gate (Block Diagram Symbol and Truth Table)

A
C=A+B
B

Inputs Output

A B C=A +
B
0 0 0

0 1 1

1 0 1

1 1 1
 NOT Gate

 Physical realization of complementation operation

 Generates an output signal, which is the reverse of

the input signal
NOT Gate (Block Diagram Symbol and Truth Table)

A A

Input Output

A A
0 1

1 0
 NAND Gate

 Complemented AND gate

 Generates an output signal of:

 1 if any one of the inputs is a 0

 0 when all the inputs are 1
NAND Gate (Block Diagram Symbol and Truth
Table)

A
B C= A B= AB= A
+B
Inputs Output

A B C = A +B
0 0 1

0 1 1

1 0 1

1 1 0
 NOR Gate

 Complemented OR gate

 Generates an output signal of:

 1 only when all inputs are 0

 0 if any one of inputs is a 1
NOR Gate (Block Diagram Symbol and Truth Table)

A
B C= A B= A B= A
B
Inputs Output

A B C=AB
0 0 1

0 1 0

1 0 0

1 1 0
 Logic Circuits

 When logic gates are interconnected to form a gating /

logic network, it is known as a combinational logic circuit
 The Boolean algebra expression for a given logic circuit
can be derived by systematically progressing from input
to output on the gates
 The three logic gates (AND, OR, and NOT) are logically
complete because any Boolean expression can be
realized as a logic circuit using only these three gates
 Computer Fundamentals: Pradeep K. Sinha & Priti Sinha

Finding Boolean Expression

of a Logic Circuit (Example 1)

A
A

NOT
D= AB +
B B+C AND
C
C OR
Finding Boolean Expression
of a Logic Circuit (Example 2)

OR

A A
B
B
C=A

A B A AND
B +BAB

AND NOT
Constructing a Logic Circuit from a Boolean Expression
(Example 1)

Boolean Expression = A B
+C
AND
A A
B
A B
B
C +C
OR
Constructing a Logic Circuit from a Boolean Expression
(Example 2)

Boolean Expression = A B + C D +
E F
AND NOT
A A A
B B
B AND AND
C C D
D A B + C D +
E F
AND
E E F E
F
NOT
F
 Universal NAND Gate

 NAND is an universal gate, it is alone

gate
sufficient to implement any Boolean
expression
 To understand this, consider:

 Basic logic gates (AND, OR, and NOT) are

logically complete
 Sufficient to show that AND, OR, and NOT
gates can be implemented with NAND
gates
Implementation of NOT, AND and OR Gates by NAND
Gates

AA=A+A= A
A
(a) NOT gate implementation.

A A B A B A
B
B (b) AND gate implementation.

(Continued on next slide)

Implementation of NOT, AND and OR Gates by
NAND Gates
(Continued from previous slide..)
and OR Gates
by

AA
A =A A B  A + B  A
B B B
B
=B
(c) OR gate implementation.
Method of Implementing a Boolean Expression with Only
NAND Gates

Step 1: From the given algebraic

expression, draw the logic diagram with AND,
both theOR, and NOT gates. Assume inputs
(A) and complement (A)
normal that are
available
Step 2: Draw a second logic diagram with the equivalent NAND
logic substituted for each AND, OR, and NOT gate

Step 3: all pairs of cascaded

Remove inverters from the as double
logical function.
diagram inversionAlso remove
does not connected to
perform
single inverters
external
any and the
corresponding
inputs input variable complement
Implementing a Boolean Expression with Only NAND
Gates (Example)

Boolean Expression =
A  B + C  A + B

A A D 
B A  B + C  A + B
B
B B D 
D A
D +BD

A C A
C
(a) Step 1: AND/OR implementation
+BD
(Continued on next slide)
Implementing a Boolean Expression with Only NAND
Gates (Example)
(Continued from previous slide..)

AND
OR
A AB
1

5
B
AND OR
B
2 BD A+BD
3
D
A B +
A
C A+BD

AND

4
C
C A+B
(b) Step 2: Substituting equivalent NAND functions
D (Continued on next slide)
Implementing a Boolean Expression with Only NAND
Gates (Example)
(Continued from previous slide..)

A
1
B 5 A B + C  A
B 2
+BD
D 3
A
4
C

(c) Step NAND implementation.

3:
 Universal NOR Gate
 NOR gate is an universal gate, it is alone sufficient
to implement any Boolean expression
 To understand this, consider:

 Basic logic gates (AND, OR, and NOT) are logically

complete
 Sufficient to show that AND, OR, and NOT gates can
be implemented with NOR gates
Implementation of NOT, OR and AND Gates by NOR
Gates and AND Gates
by

AA=AA= A
A

(a) NOT gate implementation.

A A B A  BA 
B
B
(b) OR gate implementation.

(Continued on next slide)

Implementation of NOT, OR and AND Gates by NOR
Gates
and AND Gates
(Continued from previous slide..)

by

A A  A =A
A + B  A B  A
B

B
B  B =B
(c) AND gate implementation.
Method of Implementing a Boolean Expression
with Only NOR Gates

Step 1: For the given algebraic expression, draw the

logic
diagram with AND, OR, and NOT gates. Assume
that
available

both the normal A and complement A inputs are

Step 2:

Draw a second logic diagram with equivalent NOR logic
substituted for each AND, OR, and NOT gate

Step 3: Remove all parts of

cascaded inverters from the diagram
logical as
function.
double
Also remove inversion connected
does not to
inverters
perform
single external
any complemen
inputs the
corresponding
and input variable t
Implementing a Boolean Expression with Only NOR
Gates (Examples)
(Continued from previous slide..)

Boolean Expression A B + C  A
= 
+BD
A AB
B
A B + C A
B B
D A +BD
D +BD

A C A
C (a) Step 1: AND/OR implementation.
+BD
(Continued on next slide)
 Implementing a Boolean Expression with Only
NOR Gates (Examples)
(Continued from previous slide..)

A AN
D
A B
1

B OR
5 6
A
A  B + C 
AN
+BD
B D
B
2
D
D OR
AN
D
A3
4

C C A

A +BD
+BD 
(b) Step Substituting equivalent NOR functions.
2:
(Continued on next slide)
Implementing a Boolean Expression with Only NOR
Gates (Examples)
(Continued from previous slide..)

A 1

B 5 6 A B + C A
B 2
+BD
D 3

A 4

(c) Step NOR implementation.

C 3:
 Exclusive-OR Function

AB=AB+A
B
A C = A B = A B+ A
B
B
A 
C = A B = A B+ A
B
B

Also, A B   C = A  B  C = A B
C (Continued on next slide)
 Exclusive-OR Function (Truth Table)
(Continued from previous slide..)

Inputs Output

A B C = A B
0 0 0

0 1 1

1 0 1

1 1 0
 Computer Fundamentals: Pradeep K. Sinha & Priti Sinha

Equivalence Function with Block Diagram

Symbol

A © B = A  B+ A 
B
A
C=A©B= A B+ A
B B
Also, (A © B) © = A © (B © C) = A © B ©
C

(Continued on next slide)

Equivalence Function (Truth Table)

Inputs Output

A B C=A©B

0 0 1

0 1 0

1 0 0

1 1 1
Steps in Designing Combinational Circuits

1. State the given problem completely and exactly

2. Interpret the problem and determine the available input

variables and required output variables

3. Assign a letter symbol to each input and output

variables

4. Design the truth table that defines the required relations

between inputs and outputs

5. Obtain the simplified Boolean function for each output

6. Draw the logic circuit diagram to implement the Boolean

function
Designing a Combinational Circuit Example 1 – Half-
Adder Design

Inputs Outputs
A B C S
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 0

S = AB+
Boolean functions for the two outputs.
AB C =
AB
Designing a Combinational Circuit Example 1 – Half-
Adder Design
(Continued from previous slide..)

A A
A
B

S = AB+
AB

B
B A
B
A
C=
B AB

Logic circuit diagram to implement the Boolean functions

Designing a Combinational Circuit Example 2 – Full-
Adder Design

Inputs Outputs
A B D C S
0 0 0 0 0
0 0 1 0 1
0 1 0 0 1
0 1 1 1 0
1 0 0 0 1
1 0 1 1 0
1 1 0 1 0
1 1 1 1 1
Truth table for a full adder
(Continued on next slide)
Designing a Combinational Circuit Example 2 – Full-
Adder Design
(Continued from previous slide..)

Boolean functions for the two

outputs:

S = ABD+ ABD+ ABD+

ABD
= AB+C = ABD+ ABD+
(when simplified)
ABD+ ABD
AD+BD

(Continued on next slide)

Designing a Combinational Circuit Example 2 – Full-
Adder Design
(Continued from previous slide..)

A B A B
D
D

A A B
B
D D

S
A
B A B
D
D
A A B
D
DB

(a) Logic circuit diagram for sums

(Continued on next slide)
Designing a Combinational Circuit Example 2 – Full-
Adder Design
(Continued from previous slide..)

A A
B
B

A AD C

B BD

D
(b) Logic circuit diagram for carry
 Key Words/Phrases

 Absorption law  Equivalence function  NOT gate

 AND gate  Exclusive-OR function  Operator precedence
 Associative law  Exhaustive  OR gate
 Boolean algebra enumeration method  Parallel Binary Adder
 Boolean expression  Half-adder  Perfect induction
 Boolean functions  Idempotent law method
 Boolean identities  Involution law  Postulates of
 Canonical forms  Literal Boolean algebra
for Boolean  Logic circuits  Principle of duality
functions  Logic gates  Product-of-Sums
 Combination logic  Logical addition expression
circuits  Logical multiplication  Standard forms
 Cumulative law  Maxterms  Sum-of
 Complement of  Minimization of Products
a function Boolean functions expression
 Complementatio  Minterms  Truth table
n  NAND gate  Universal NAND
 De Morgan’s law gate
 Distributive law  Universal NOR
 Dual identities gate
THANK YOU