Logic Gates

Logic Gates
In digital electronics, logic gate is physical device implementing a boolean
function, it perform logical operation, takes one or more inputs and produce
single binary output signals.
Logic gates are implemented generally using diodes, transistors, semiconducto
devices etc.
Basic building blocks from which many kinds of logic circuits can be
constructed.

Types of Logic Gate

OR gate
An OR gate have two or more input and give single output.
It performs logical addition of the inputs.
It is denoted by plus (+) sign.
Its diagram and truth table are shown below.

a
a+b
a b a+b
b 0 0 0
0 1 1
1 0 1
OR gate diagram
1 1 1
truth table

Characteristics: It give 1 when there is atleast 1 in given equation

otherwise it give 0.

AND gate
An AND gate has two or more inputs and give single output.
It multiplies the input, it is denotedd by dot (.) sign.
Its diagram and truth table are shown below.

a
a.b
a b a.b
b 0 0 0
0 1 0
1 0 0
AND gate diagram
1 1 1
truth table

Characteristics: An AND gate gives output 1 when all inputs are 1 other
wise it gives 0.

NAND gate
It is simple AND gate followed by a NOT gate.
So the output will be low (0) if and only if all the input are high (1).
It complements the output of AND gate.
A NAND gate has two or more inputs and give single output.

a
a.b
a b a.b
b 0 0 1
0 1 1
1 0 1
1 1 0
truth table

NAND gate diagram

NOR gate
It is simple OR gate followed by a NOT gate.
So the output will be high (1) if and only if all inputs are low (0).

a
a+b
a b a+b
b 0 0 1
0 1 0
1 0 0
1 1 0
truth table

NOR gate diagram

XOR Gate (exclusive OR) (EX-OR)

An X-OR gate has two or more input and give single output.
Its symbol and circuit diagram and truth table are shown below :

a truth table
a + b Y=A + B +C
b a b a+b A B C Y
0 0 0 0 0 0 0
0 1 1 0 0 1 1
It is combination of gates 1 0 1 0 1 0 1
1 1 0 0 1 1 0
A B
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 1
AB

A + B = AB + AB

AB

Characteristics: It gives o/p 1 when number of 1 in I/Ps is an odd

number.

XNOR gate
A XNOR gate has 2 or more I/Ps and single O/P.
The Exclusive NOR gate is sometimes reffered to as the ‘COINCIDENCE’
or ‘EQUIVALENCE’ gate.
Its logic diagram and truth table is shown below:

A
Y=A . B
B = AB + A′B′

Observe that it is the XOR symbol with the added invert bubble
on the output side. The Boolean expression for XNOR is
therefore, the complement of XOR function denoted by symbol .

A . B = (A + B)'
= (AB′ + A′B)′
= (A′ + B) . (A + B′)
= AA′ + A′B′ + AB + BB′
= AB + A′B′
truth table

a b a.b
0 0 1
0 1 0
1 0 0
1 1 1

Notice that the output of XNOR gate is the complement of XOR truth table.

3-I/P XNOR GATE

Y=A . B . C

A B C Y
0 0 0 1
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 0
=A′BC + AB′C + ABC′ + A′B′C′

Characteristics: It gives o/p 1 when number of 0 in I/Ps is an odd number.

Questions
Generate output for the given logic circuit ↓

Solution ↓

A Y1 = A+B

B' Y3 = Y1.Y2 Y3'

Y2 = A.B'

Input Output

A B B' Y1 = A+B Y2 = A.B' Y3 = Y1.Y2 Y3'

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

Implement xy + x'y' using baisc gates ↓

x x.y
y x.y + x'y'
x'
x'.y'
y'

Implement x'(y+z) using basic gates ↓

x'
x
x'(y+z)
y y+z
z

Universal gates
A logic gate can be an universal gate if we implement AND, OR, and NOT
gate by using it.
NAND and NOR gates are called universal gate because we can design any
Boolean function using either NAND or NOR gate only.

NAND gate as universal gate

Logic Symbol Circuit using NAND gates only
Function
A
Inverter A A' A'

A A
AND A.B
B B A.B

A
A
OR A+B
B
A+B
B

NOR gate as universal gate

Logic Symbol Circuit using NOR gates only
Function
A
Inverter A A' A'

A
A
AND A.B
B A.B
B

A A
OR A+B B A+B
B

Implementation of boolean expression

using NAND gate
Video lecture ⇗
Steps ↓
1. Draw logic diagram using basic gates (NOT, AND, OR)
2. Applying bubbles at the output of AND gate and at the input of OR gate.
3. Applying NOT gate where we have found bubbles.
4. Look out for double inversion (NOT gate) and cancel it.
5. Place equivalent NAND gate.

Implement x'y + y'x using only NAND gate ↓

step 1 = Draw logic diagram using basic gates.
x

step 2 = Placing bubbles

x

step 3 = Placing NOT gate near bubbles

x

step 4 = Cancelling double not gate

x

step 5 = place equivalent NAND gate at all places.

x

This can be replaced by

NAND gate.

replaced

Implement xy + x'y' using only NAND gate ↓

x (xy)'

((xy)'(x'y')')'

y
x'
(x'y')'
y'

((xy)'(x'y')')'
= (xy)''+(x'y')''
= (xy)+(x'y')

Implement AB'C + A'BC' using only NAND gate ↓

A
B' AB'C
B
C
((AB'C)'(A'BC'))'

A'
A'BC'
C'
((AB'C)'(A'BC'))'
= (AB'C)''+(A'BC')'
=(AB'C) + (A'BC')

Implement A + A'B' using only NAND gate ↓

A
B

Implementation of boolean expression

using NOR gate
Video lecture ⇗
Steps ↓
1. Draw Logic Circuit using basic gates (OR, NOT, AND).
2. Apply bubbles at the end of OR gate and at the input of AND gate.
3. Apply NOT gate where we had applied bubbles.
4. Look out for double inservion (NOT gate) and cancel it.
5. Place equivalent NOR gate.

A' + B'.C' ↓
step 1 = Draw logic diagram using basic gates.
A

B
C

step 2 = Placing bubbles

A

B
C

step 3 = Placing NOT gate near bubbles

A

B
C
step 4 = Cancelling double not gate
A

B
C

step 5 = place equivalent NOR gate at all places.

B
C

This can be replaced by

NOR gate.

B
C

ab' + a'b ↓
a
b

ab + a'b' ↓
a
b

Boolean Algebra
Boolean algebra is a branch of algebra in which the values of the variables
are truth value T/F, usually denoted by 1/0.
Main operations are negation (~), disjunction (∨)(+) and conjunction (∧)(.)

a ~a a b avb a b a^b
F T F F F F F F
T F F T T F T F
T F T T F F
T T T T T T

Boolean Laws
1: Idempotent law 5: De-Morgan's law
a.a=a
a+a=a (a + b) = a . b

(a . b) = a + b
2: Associative law
a . (b . c) = (a . b) . c 6: Identity law
a + (b + c) = (a + b) + c
a+0=a
a.0=0
3: Commutative law a+1=1
a.b=b.a a.1=a
a+b=b+a
7: Compliment law

4: Distributive law 0=1

a . (b + c) = (a . b) + (a . c) 1=0
a + (b . c) = (a + b) . (a + c) a.a=0
a+a=1

8: Invaluation law

(a)=a

. = intersection (⋂)
+ = union (⋃)

Boolean algebra may be defined with a set of elements, a set of operators,

and a number of unproved axioms or postulates.
A set of elements is any collection of objets having a common property.
If S is a set, and x and y are its objects, then x ∈ S denotes that x is a
member of the set S, and Y ∉ S denotes that y is not an element of S.
The postulates of a mathematical system form the basic assumptions from which
is possible to deduce the rules, theoroms, and properties of the system. The most
common postulates used to formulate various algebraic structures are:

1. Closure: If we apply binary operator (+, -, etc) between elements of a set S,

then we get an element that also belongs to set S.
For example, the set of natural numbers N = {1, 2, 3, 4, ...} is closed with
respect to the binary operator plus (+). 2 + 3 = 5. 5 is also a member of set
S.
2. Associative law:
(x * y) * z = x * (y * z) ∀ x, y, z ∈ S
3. Commutative law:
x * y = y * z ∀ x, y ∈
4. Identity element:
e*x=x*e∀x∈S
here e is an identity element.

Axiomatic Definition of Boolean Algebra

In 1854 George Boole introduced a systematic treatment of logic, called
Boolean Algebra.
In 1938 C. E Shannon introduced a two-value Boolean Algebra called
switching algebra.

Postulate 2 x + 0 = x x . 1 = x
------------------------------------------------------------------------
Postulate 3 x + y = y + x xy = yx
(Commutative)
------------------------------------------------------------------------
Postulate 4 x.(y + z) = x.y + x.z x + (y.z)
(Distributive)
------------------------------------------------------------------------
Postulate 5 x + x' = 1 x . x' = 0

________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________

Theorem 1 x + x = x x . x = x
------------------------------------------------------------------------
Theorem 2 x + 1 = 1 x . 0 = 0
------------------------------------------------------------------------
Theorem 3 (x')' = x
(Involution)
------------------------------------------------------------------------
Theorem 4 x + (y + z) = (x + y) + z x(yz) = (x
(Associative)
------------------------------------------------------------------------
Theorem 5 (x + y)' = x'y' (xy)' = x'
(De Morgan)
------------------------------------------------------------------------
Theorem 6 x + xy = x x(x + y) =
(Absorption)

some questions

(i) Prove (x+y) (x+z) = x + yz

LHS = (x+y) (x+z)

= (x.x) + (x.z) + (y.x) + (y.z)
= x + xz + yx + yz [as x.x = x]
= x(1 + z + y) + yz
= x + yz [since 1 + k = 1]
= RHS

(ii) Prove xy + xz + yz' = xz + yz'

LHS = xy + xz + yz'
= xy(z+z') + xz(y+y') + yz'(x+x') [as x+x' = 1]
= xyz + xyz' + xyz + xy'z + xyz' + x'yz'
= xyz + xyz' + xy'z + x'yz' [as xyz + xyz = xyz]
= xyz + xy'z + xyz' + x'yz' [rearranging]
= xz(y+y') + yz'(x+x')
= xz + yz' [as y+y' = 1]

(iii) Simplify F = ABCD + ABCD'

= ABCD + ABCD'
= ABC(D+D')
= ABC [as D+D' = 1]

Boolean Expression
Boolean expression is a method using which we represent information about
boolean function i.e. when it give 0 or 1.
We convert truth table of boolean function into boolean expression which
contains all information.
Two types of boolean expression:

1. Sum of product (SOP) expression

(Which remember where is 1)
2. Product of sum (POS) expression
(Which remember where is 0)

SOP
It contains product term (AND term) which are sum (OR) together that's
why called sum of product.
Each product term consists of one or more literals (variables) appearing
either in complemented or uncomplemented form, e.g. a'b' + a'b.

Example for SOP:

f(a,b) = a'b' + ab'

truth table
a b f
-------------
0 0 1
0 1 0
1 0 1
1 1 0
A product term which contains all the literals (variables) either in
complemented or uncomplemented for is called minterm. In a n variable
function 2n minterm can be there.
If a leteral have value 1 then ok, but if not, then we complement one
which is zero.
There is only one input sequence for any minterm on which output is 1 so
it represent info.
Function will have value 1, if atleast one of the product term is 1.
Another example with 3 variable. ↓

sequence binary minterm designation

representation
-----------------------------------------------------------------
0 000 a'b'c' m0
1 001 a'b'c m1
2 010 a'bc' m2
3 011 a'bc m3
4 100 ab'c' m4
5 101 ab'c m5
6 110 abc' m6
7 111 abc m7

Example for minterm

f(a,b) = a'b' + ab' ✓

f(a,b) = a' + ab' ✗

One more example ↓

a b c f
--------------
0 0 0 0 m0
0 0 1 1 m1
0 1 0 1 m2
0 1 1 0 m3
1 0 0 1 m4
1 0 1 0 m5
1 1 0 0 m6
1 1 1 0 m7

We know we have to remember where 1 is in the function.

at m1, m2 and m4 we have 1 which is a'b'c + a'bc' + ab'c'
f(a,b,c) = ∑m(1,2,4)

Canonical SOP expression

In SOP expression if each product term (AND term) consists of all the
literals appearing either in complemented or uncomplemented form.
Example ↓

a b c f
--------------
0 0 0 1
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 0
1 1 1 1

f(a,b,c) = a'b'c + a'b'c + ab'c' + ab'c + abc

simplifying it
= a'b'(c+c') + ab'(c'+c) + abc
= a'b' + ab' + abc
= b'(a'+a) + abc
= b' + abc
we optimized it so that cost of implementation is less
now b' is available in a'b'c, a'b'c, ab'c', ab'c
Example (optimized function)

f(a,b,c) = a'b + ab'c + c'

convert this to canonical form so that we can identify minterm.
= a'b(c'+c) + ab'c + (a'+a)(b'+b)c'
= a'bc' + a'bc + ab'c + (a'b' + a'b + ab' + ab)c'
= a'bc' + a'bc + ab'c + a'b'c' + a'bc' + ab'c' + abc' (canonical
= a'bc' + a'bc + ab'c + a'b'c' + ab'c' + abc' (after uniting com
= ∑m(0, 2, 3, 4, 5, 6)

Pros: easy to read and understand.

Cons: if the expression is in canonical form then its cost of
implementation is more.

POS
Contains SUM (OR) terms which are AND (product) together.
Each sum term consist of one or more literals (variables), either in
complemented or uncomplemented form.

f(a,b,c) = (a + b') . (a' + b' + c')

(a + b') = (a + b' + c) . (a + b' + c') [not optimized]
Sum term which contains all the literals is called maxterm.
In a n-variable function there will be 2n maxterms.
Result of a sum term must be 0, so if a literal is having value 0 then it is
ok, but if not we complement the variable to make it 0. (a = 0, a' = 1)
There is only one value sequence for every maxterm on which i will give
0.
3 variable representation ↓

sequence binary maxterm designation

representation
-----------------------------------------------------------------
0 000 a+b+c M0
1 001 a+b+c' M1
2 010 a+b'+c M2
3 011 a+b'+c' M3
4 100 a'+b+c M4
5 101 a'+b+c' M5
6 110 a'+b'+c M6
7 111 a'+b'+c' M7
function example ↓

a b c f
-------------
0 0 0 0 M0
0 0 1 0 M1
0 1 0 1 M2
0 1 1 1 M3
1 0 0 0 M4
1 0 1 1 M5
1 1 0 1 M6
1 1 1 0 M7

we have to remember where 0 is occuring

= (a+b+c) . (a+b+c') . (a'+b+c) . (a'+b'+c')
= πM(0,1,4,7)

Canonical POS form

If each sum (OR) term consists of all the literals, either in
complemented or uncomplemented form, then it is called POS form.
Here each sum term represent a maxterm.
Converting non-canonical form to canonical form

1. (a) . (a' + b) . (a' + b' + c')

= (a + b'.b + c'.c) . (a' + b + c'.c) . (a' + b' + c')
= [(a+b').(a+b)+c'.c] . (a' + b + c') + (a' + b + c) . (a' + b' + c')
= (a+b'+c') . (a+b'+c) . (a+b+c') . (a+b+c) . (a'+b+c') . (a'+b+c) . (
= πM(0,1,2,3,4,5,7)

pros: improve readability and understandability of expression

cons: implementation of circuit is hard, cost increases.

Practise question
1. Simplify - (P+Q'+R') . (P+Q'+R) . (P+Q+R')
2. Obtain boolean eq. for:

F(x,y,z) = ∑(4,6,7)
F(a,b,c) = π(1,3,6)

3. Convert SOP to POS

(XY'Z' + XYZ' + XYZ)

4. Convert the following to canonical form:

f(p,q,r) = p'q + p'qr' + q'

Simplification of boolean expression

After deriving a boolean expression from the truth table next important step
is to minimize it, so that the cost of implementation into hardware is reduced
because of additional gates can be reduced.
We Karnaugh-map to reduce the boolean expression.

Karnaugh Map
In 1953, Maurice Karnaugh developed K-map for reducing boolean
equations so that we have a small logic circuit.
The K-map is a diagram made up of squares, and each square represent
one minterm/maxterm.
Problems with other methods: The algebraic procedure using boolean
laws and rule for minimizing boolean expression becomes difficult when a
function becomes complex, because we have to identify where is the
scope of minimization based on some boolean laws and it is difficult to
understand where we reach saturation point or not.
Karnaugh map is one of the most extensively used tool, it is a graphical
representation, represents truth table by pictorial form, provides a
systematic method for simplifying or minimizing a boolean expression.
For n-variable K-map, there will be 2n cells addressed by a gray code.
Each cell corresponds to one minterm or maxterm.
we are using gray code here because that it is cyclic and we can easily
minimize adjacent term.

K-MAP
2 Variable K-MAP
A 2 variable K-map is used for the boolean equation that has only two
binary variables. For example → xy + xy'.
With 2 i/ps, there are 4 possible combinations, so we have 4 squares in a
2 variable K-map. Each square shows one minterm or maxterm.

y
x y' y

x'
m0 m1

x
m2 m3

3 variable K-MAP
The number of cells in 3 variable K-map is eight, since the number of
variable is three, the following figure shows 3 variable K-map.

yz y'z' y'z yz yz'

x 00 01 11 10

x' 0
m0 m1 m3 m2

x 1
m4 m5 m7 m6

4 variable K-MAP
The number of cells in 4 variable K-map is sixteen, since the number of
variables if four. The following figure shows 4 variable K-Map.

yz y'z' y'z yz yz'

wx 00 01 11 10

w'x' 00
m0 m1 m3 m2

w'x 01
m4 m5 m7 m6

wx 11
m12 m13 m15 m14

wx' 10
m8 m9 m11 m10

5 variable K-MAP
The number of cells in 5 variable K-map is thirty two since the number of
varaibles is 5. The following figure shows 5 variable K-map, we combine 2
maps of 16 boxes.

st
qr 00 01 11 10 00 01 11 10

00
0 1 2 3 16 17 19 18

01
4 5 7 6 20 21 23 22

11
12 13 15 14 28 29 31 30

10
8 9 11 10 24 25 27 26

p=0 p=1

K-MAP for POS

c+d
a+b c+d c+d' c'+d' c'+d
00 01 11 10

a+b 00
0 1 2 3

a+b' 01
4 5 7 6

a'+b' 11
12 13 15 14

a'+b 10
8 9 11 10

K-MAP questions:
f(x,y,z) = (0, 1, 5, 6)

yz y'z' y'z yz yz'

x 00 01 11 10
1
x' 0 1 1

2
3
x 1 1 1

x'y' + y'z + xyz'

1 2 3

f(x,y,z) = (0, 1, 3)

yz y'z' y'z yz yz'

x 00 01 11 10
1 2
x' 0 1 1 1

x 1

x'y' + x'z
1 2

f(x,y,z) = x'y'z' + x'yz' + xy'z' + xyz'

yz y'z' y'z yz yz'

x 00 01 11 10

1 1
x' 0 1 1

2
x 1 1 1

x'z' + xy'
1 2

f(w,x,y,z) = (2,3,5,6,11,12,15)
f(w,x,y,z) = (0,1,4,7,8,9,10,13,14)
yz y'z' y'z yz yz'
wx 00 01 11 10

w'x' 00 1 1

w'x 01 1 1

wx 11 1 1

wx' 10 1 1 1

Y = x'y' + w'y'z' + wy'z + w'xyz + wyz' SOP

Y' = (x'y' + w'y'z' + wy'z + w'xyz + wyz')'

Y' = (x'y')' . (w'y'z')' . (wy'z)' . (w'xyz)' . (wyz')'
Y' = (x+y) . (w+y+z) . (w'+y+z') . (w+x'+y'+z') . (w'+y'+z) POS

f(x,y,z) = (x+y'z') (x'+y+z') (x'+y'+z') (x+y+z)

f(x,y,z) = x'yz + xy'z + xyz + x'y'z'
yz y'z' y'z yz yz'
x 00 01 11 10

x' 0 1 1

x 1 1 1

x'y'z' + yz + xz
f(x,y,z) = x'y'z' + x'yz' + xy'z' + d(6)
yz y'z' y'z yz yz'
x 00 01 11 10

x' 0 1 1

x 1 1 X

x'y' + y'z'

5-variable K-MAP
Video one ⇗
Video two ⇗
6-variable K-MAP
Video one ⇗

Previous Year Questions

Simplify the following Boolean function using K Map:

F(x, y, z) = ∑(1, 3, 5, 7)
F(A, B, C, D) = ∑(0, 1, 5, 8, 9)

Draw the following logic gate with their truth tables:

AND
XNOR
NAND
X-OR
NOR

Find the standard product of sum (POS) for the logic

expression F = (A + B'C)C.

What do you mean by universal gates?

Draw AND, OR, NOT, EX-OR, NOR using NAND gates only.

What is De Morgan's theorem? Verify this theorem with

the help of truth table.

Obtain:
1. Minimal sum of product and
2. Product of sum expressions for the function given below:
F(A, B, C, D) = ∑m(1, 3, 7, 11, 15) + ∑d(0, 2, 5)

Minimize the following logical expressions using K-Map:

1. F(x, y, z) = E(3, 4, 6, 5, 7)

'E' represents Sum of Products

2. Y = A'BCD + AB'C'D + A'B'C'D + ABCD + A'B'C'D' + ABC'D

3. Y = (A + B + C) (A + C) (A + B') (A' + B' + C') (A + C')
4. F(A, B, C, D) = π (1, 2, 7, 8, 3, 10, 11, 15, 12, 13)

Design a circuit:
1. That obtain AND opertion using NAND gate.
2. That obtain OR opertion using NAND gate.
3. That obtain OR opertion using NOR gate.
4. That obtain AND opertion using NOR gate.

State whether the expressions are in SOP or POS form:

AB + ABC + CDE
(A + B) * (A + B + C) * (C + D)
(A + B)' * (C + D + E')
(AB)' + ABC + CDE'
ABC
A + B + CD
A+B+C+D
AB + CD
(A + B)' . (A' + B) . (A' + B')
A'B + A'B + AB