Scribd
Upload
67 views14 pages

Digital Circuits and Systems: Spring 2015 Week 2

This document discusses digital logic gates and Boolean expressions. It explains that AND, OR, and NOT gates are universal, meaning any Boolean function can be implemented using only those gates. Specifically, it shows how NAND and NOR gates are universal by demonstrating how to build AND, OR, and NOT gates using only NAND or only NOR gates. The document also discusses how to convert between Boolean expressions and truth tables by writing the expression in sum of products form or writing the truth table as a sum of minterms. It introduces Karnaugh maps as a systematic way to simplify Boolean expressions derived from truth tables.

Uploaded by

Chandra Kishore Paul
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
67 views14 pages

Digital Circuits and Systems: Spring 2015 Week 2

This document discusses digital logic gates and Boolean expressions. It explains that AND, OR, and NOT gates are universal, meaning any Boolean function can be implemented using only those gates. Specifically, it shows how NAND and NOR gates are universal by demonstrating how to build AND, OR, and NOT gates using only NAND or only NOR gates. The document also discusses how to convert between Boolean expressions and truth tables by writing the expression in sum of products form or writing the truth table as a sum of minterms. It introduces Karnaugh maps as a systematic way to simplify Boolean expressions derived from truth tables.

Uploaded by

Chandra Kishore Paul
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 14

Spring 2015 Week 2 Module 7

Digital Circuits and


Systems

Universality, Rearranging Truth Tables

Shankar Balachandran*
Associate Professor, CSE Department
Indian Institute of Technology Madras

*Currently a Visiting Professor at IIT Bombay


Summary of Digital Logic Gates

Universality, Rearranging Truth Tables 2


Summary of Digital Logic Gates

Universality, Rearranging Truth Tables 3


AND/OR CIRCUITS

 The simplest type of combinational logic design


consists of inverters, AND gates, and OR gates. This
is known as an AND/OR circuit.

 An AND/OR circuit can be designed to implement any


function by performing the following steps:

1. Put the expression in SOP form


2. Form complemented literals with inverters.
3. Form product terms with AND gates.
4. Sum the product terms with an OR gate

Universality, Rearranging Truth Tables 4


Example
f(x,y, z)  xy  xyz

x f
y
z

Exercise
Implement the function f(x, y, z)  ( x  y )( y  z )( x  x )
using OR/AND logic

Universality, Rearranging Truth Tables 5


Universality

 All Boolean functions can be implemented using


the set {AND, OR, NOT}
 Universal gates
 Gates which can implement any Boolean function
without the need to use any other type of gate
 NAND and NOR are universal gates

 To show universality of a gate:


 Show that AND, OR and NOT can be implemented using that
gate

Universality, Rearranging Truth Tables 6


NAND Universality
 AND, OR and NOT can be implemented using NAND only
NOT or INV

x
F = x.x = x

AND
x P = xy
y F = xy = xy

OR x
F= x.y =x+y=x+y
y

Universality, Rearranging Truth Tables 7


Exercises

 Show that NOR gate is a universal gate also

 Is XOR a universal gate?


 If so, show how {AND, OR, NOT} operations can be
done using XOR gates only.
 If not, show which operations can be done and which
cannot be.

Universality, Rearranging Truth Tables 8


Boolean Expression  Truth Table
 To convert boolean expression to truth table:
 Expand the expression into the minterms (i.e., canonical SOP form) and
enter 1’s in truth table rows (or, expand into canonical POS and enter 0’s
for each maxterm).

Example
x y z f
0 0 0 1
f x , y , z  z  y z 0 0 1 0
 
 z x  x  yz 0 1 0 1
0 1 1 1
 x z  yz  x z
   
 x z y  y  yz x  x  x z y  y   1
1
0
0
0
1
1
0
 xyz  xyz  xyz  xyz  xyz  xyz
1 1 0 1
  0, 2 , 3, 4, 6, 7  1 1 1 1
Universality, Rearranging Truth Tables 9
Truth Table  Boolean Expression
 To convert a truth table to a boolean expression:
 Write a canonical SOP expression that consists of all minterms
(or write a canonical POS using maxterms) and then simplify the
algebraic expression.
Example

f x , y , z   0, 2, 3, 4, 6, 7 

 xyz  xyz  xyz  xyz  xyz  xyz


  
 x z y  y  yz x  x  x z y  y   
 x z  yz  x z

 z x  x  yz 
 z  yz

Universality, Rearranging Truth Tables 10


Truth tables to Boolean Expression

 When the expressions get more complicated,


simplification gets harder
 You may miss out combinations
 More inputs, more the effort
 Systematic way to reduce effort
 Karnaugh Maps

Universality, Rearranging Truth Tables 11


Rearranging Truth Tables

x y z f Minterms f(x,y,z)
0 0 0 1 m0 1 x\yz 00 01 10 11
0 0 1 0 m1 0
0 1 0 1 1
0 1 0 1 m2 1
0 1 1 1 m3 1 1 1 0 1 1

1 0 0 1 m4 1
1 0 1 0 m5 0
1 1 0 1 m6 1 x\yz 00 01 11 10
1 1 1 1 m7 1
0 1 0 1 1
1 1 0 1 1

Universality, Rearranging Truth Tables 12


In General

x1 x2x3 00 01 11 10

0 m000 m001 m011 m010


1 m100 m101 m111 m110

x1 x2x3 00 01 11 10

0 m0 m1 m3 m2
1 m4 m5 m7 m6

Universality, Rearranging Truth Tables 13


End of Week 2: Module 7

Thank You

Universality, Rearranging Truth Tables 14

You might also like