SWITCHING THEORY AND

LOGIC CIRCUITS
 COURSE OBJECTIVES
1. To understand the concepts and techniques associated with the
number systems and codes
2. To understand the simplification methods (Boolean algebra &
postulates, k-map method and tabular method) to simplify the
given Boolean function.
3. To understand the fundamentals of digital logic and to design
various combinational and sequential circuits.
4. To understand the concepts of programmable logic
devices(PLDs)
5. To understand formal procedure for the analysis and design of
synchronous and asynchronous sequential logic
 COURSE OUTCOMES
After completion of the course the student will be able to
1. Understand the concepts and techniques of number systems
and codes in representing numerical values in various number
systems and perform number conversions between different
number systems and codes.
2. Apply the simplification methods to simplify the given Boolean
function (Boolean algebra, k-map and Tabular method).
3. Implement given Boolean function using logic gates, MSI
circuits and/ or PLDs.
 COURSE OUTCOMES
After completion of the course the student will be able to
4. Design and analyze various combinational circuits like
decoders, encoders, multiplexers, and de-multiplexers,
arithmetic circuits (half adder, full adder, multiplier etc).
5. Design and analyze various sequential circuits like flip-flops,
registers, counters etc.
6. Analyze and Design synchronous and asynchronous sequential
circuits.
 UNIT-I
Introductory Concepts
(Number systems, Base conversions)
 Digital Systems

Digital systems consider discrete amounts of data

Examples
26 letters in the alphabet
10 decimal digits

Larger quantities can be built from discrete values:

Words made of letters
Numbers made of decimal digits (e.g. 239875.32)

Computers operate on binary values (0 and 1)

Easy to represent binary values electrically
Voltages and currents
Can be implemented using circuits
Create the building blocks of modern computers
 Understanding Decimal Numbers

Decimal numbers are made of decimal digits:

(0,1,2,3,4,5,6,7,8,9) Base = 10
How many items does decimal number 8653
represents? 1000 100 10 1 Weight
8653 = 8 x103 + 6 x102 + 5 x101 + 3 x100
Number = d3 x B3 + d2 x B2 + d1 x B1 + d0 x B0 = Value

What about fractions?

97654.35 = 9x104 + 7x103 + 6x102 + 5x101 + 4x100 + 3x10-1 + 5x10-2
In formal notation (97654.35)10
 Understanding Octal Numbers

Octal numbers are made of octal digits:

(0,1,2,3,4,5,6,7)
How many items does an octal number represent?
512 64 8 1 = Weights
(4536)8 = 4x83 + 5x82 + 3x81 + 6x80 = (2398)10

What about fractions?

(465.27)8 = 4x82 + 6x81 + 5x80 + 2x8-1 + 7x8-2

Octal numbers dont use digits 8 or 9

 Understanding Hexadecimal Numbers

Hexadecimal numbers are made of 16 digits:

(0,1,2,3,4,5,6,7,8,9,A, B, C, D, E, F)

How many items does a hex number represent?

4096 256 16 1 = Weights
(3A9F)16 = 3x163 + 10x162 + 9x161 + 15x160 = 1499910

What about fractions?

(2D3.5)16 = 2x162 + 13x161 + 3x160 + 5x16-1 = 723.312510

Note that each hexadecimal digit can be represented

with four bits
(1110)2 = (E)16

Groups of four bits are called a nibble

(1110)2
 Understanding Binary Numbers

Binary numbers are made of binary digits (bits):

0 and 1

How many items does a binary number represent?

8 4 2 1 = Weights
(1011)2 = 1x23 + 0x22 + 1x21 + 1x20 = (11)10

What about fractions?

(110.10)2 = 1x22 + 1x21 + 0x20 + 1x2-1 + 0x2-2

Groups of eight bits are called a byte

(11001001)2

Groups of four bits are called a nibble

(1101)2
 Putting It All Together

Binary, octal, and

hexadecimal are similar
Easy to build circuits to
operate on these
representations
Possible to convert
between the three
formats
 Why Use Binary Numbers?

Easy to represent 0 and 1

using electrical values
Possible to tolerate noise
Easy to transmit data
Easy to build binary circuits

1
AND Gate 0
0
 Conversion Between Number Bases

Learn to convert between bases

Already demonstrated how to convert
from binary to decimal

Octal
(base 8)

Decimal Binary
(base 10) (base 2)

Hexadecimal
(base 16)
 Convert an Integer from Decimal to Another Base

For each digit position:

1. Divide decimal number by the base (e.g. 2)
2. The remainder is the lowest-order digit
3. Repeat first two steps until no divisor remains

Example for (13)10:

Quotient Remainder Coefficient
13/2 = 6 + 1 a0 = 1
6/2 = 3 + 0 a1 = 0
3/2 = 1 + 1 a2 = 1
1/2 = 0 + 1 a3 = 1

Answer (13)10 = (a3 a2 a1 a0)2 = (1101)2

MSB LSB
 Convert a Fraction from Decimal to Another Base

For each digit position:

1. Multiply decimal number by the base (e.g. 2)
2. The integer is the highest-order digit
3. Repeat first two steps until fraction becomes zero

Example for (0.625)10:

Integer Fraction Coefficient

0.625 x 2 = 1 + 0.25 a-1 = 1

0.250 x 2 = 0 + 0.50 a-2 = 0
0.500 x 2 = 1 + 0 a-3 = 1

Answer (0.625)10 = (0.a-1 a-2 a-3 )2 = (0.101)2

MSB LSB
The Growth of Binary Numbers

n 2n n 2n
0 20=1 8 28=256
1 21=2 9 29=512
2 22=4 10 210=1024 Kilo

3 23=8 11 211=2048
4 24=16 12 212=4096
5 25=32 20 220=1M Mega

6 26=64 30 230=1G Giga

7 27=128 40 240=1T Tera

 Convert an Integer from Decimal to Octal

For each digit position:

1. Divide decimal number by the base (8)
2. The remainder is the lowest-order digit
3. Repeat first two steps until no divisor remains

Example for (175)10:

Quotient Remainder Coefficient

175/8 = 21 + 7 a0 = 7
21/8 = 2 + 5 a1 = 5
2/8 = 0 + 2 a2 = 2

Answer (175)10 = (a2 a1 a0)8 = (257)8

 Convert a Fraction from Decimal to Octal

For each digit position:

1. Multiply decimal number by the base (e.g. 8)
2. The integer is the highest-order digit
3. Repeat first two steps until fraction becomes zero

Example for (0.3125)10:

Integer Fraction Coefficient

0.3125 x 8 = 2 + 0.5 a-1 = 2

0.5000 x 8 = 4 + 0.0 a-2 = 4

Answer (0.3125)10 = (0.24)8

 Conversion Between Base 16 and Base 2

Conversion is easy!
Determine the 4-bit binary value for each hex digit
Note that there are 16 different values of four bits
Easier to read and write in hexadecimal
Representations are equivalent!

3A9F16 = 0011 1010 1001 11112

3 A 9 F
 Conversion Between Base 16 and Base 8
1. Convert from Base 16 to Base 2
2. Regroup bits into groups of three starting from right
3. Ignore leading zeros
4. Each group of three bits forms an octal digit

3A9F16 = 0011 1010 1001 11112

3 A 9 F

352378 = 011 101 010 011 1112

3 5 2 3 7
 Binary Addition

Binary addition is very simple

1 1 1 1 1 1 carries
11 1 1 0 1 = 61
+ 1 0 1 1 1 = 23
---------------------
1 0 1 0 1 0 0 = 84
 Binary Subtraction

We can also perform subtraction (with borrows in

place of carries)
Lets subtract (10111)2 from (1001101)2

1 10
0 10 10 0 0 10 borrows
1 0 0 1 1 0 1 = 77
- 1 0 1 1 1 = 23
------------------------
1 1 0 1 1 0 = 54
 Binary Multiplication

Binary multiplication is much the same as decimal

multiplication, except that the multiplication
operations are much simpler

1
0 1 1 1
X 1 0 1 0
-----------------------
0 0 0 0 0
1 0 1 1 1
0 0 0 0 0
1 0 1 1 1
-----------------------
1 1 1 0 0 1 1 0
 Summary

Binary numbers are made of binary digits (bits)

Binary and octal number systems
Conversion between number systems
Addition, subtraction, and multiplication in binary
Introductory Concepts
(Complements)
 How To Represent Signed Numbers

Plus and minus signs are used for decimal numbers:

25 (or +25), 16, etc
In computers, everything is represented as bits
Three types of signed binary number representations:
signed magnitude
1s complement
2s complement
In each case: left-most bit indicates the sign:
0 for positive and 1 for negative
 Signed Magnitude Representation

The left most bit is designated as the sign bit while

the remaining bits form the magnitude
The sign bit should not be included in addition /
subtraction operations

000011002 = 1210

Sign bit Magnitude

100011002 = 1210

Sign bit Magnitude

 Ones Complement Representation

The ones complement of a binary number is done

by complementing (i.e. inverting) all bits
1s comp of 00110011 is 11001100
1s comp of 10101010 is 01010101
For a n-bit number N the 1s complement is
(2n 1) N
Called diminished radix complement by Mano
To find the negative of a 1s complement number
take its 1s complement

000011002 = 1210 111100112 = 1210

Sign bit Magnitude Sign bit Code

 Ones Complement Representation

7 0111
4 bits 6 0110
. .
16 combinations . .
1 0001
0 0000
0 1111
1 1110
. .
. .
6 1001
7 1000
 Twos Complement Representation

The twos complement of a binary number is done

by complementing (inverting) all bits then adding 1
2s comp of 00110011 is 11001101
2s comp of 10101010 is 01010110
For an n-bit number N the 2s complement is
(2n1) N + 1
Called radix complement by Mano
To find the negative of a 2s complement number
take its 2s complement
000011002 = 1210 111101002 = 1210

Sign bit Magnitude Sign bit Code

 Twos Complement Shortcuts

Algorithm 1: Complement each bit then add 1 to the

result
N = 01100101 [N] = 10011011
10011010 01100100
+ 1 + 1
10011011 01100101
Algorithm 2: Starting with the least significant bit,
copy all of the bits up to and including the first 1
bit, then complement the remaining bits
N =01100110
[N] =10011010
 Twos Complement Representation

7 0111
4 bits 6 0110
. .
16 combinations . .
1 0001
0 0000
1 1111
2 1110
. .
. .
7 1001
8 1000
 Finite-Precision Number Representation

Machines that use 2s complement arithmetic can

represent integers in the range
2n-1 N 2n-1 1
n is the number of bits used for representing N
Note that 2n-1 1 = (011..11)2 and 2n-1 = (100..00)2
2s complement code has more negative numbers
than positive
1s complement code has 2 representations for zero
For a n-bit number in base (i.e. radix) z there are zn
different unsigned values (combinations)
(0, 1, zn-1)
 1s Complement Subtraction

Using 1s complement representation, subtracting

numbers is also easy
Step 1: Take 1s complement of 2nd operand
Step 2: Add binary numbers
0 1 1 0 0
Step 3: Add carry as a low order bit - 0 0 0 0 1
For example: (+12)10 (1)10 1 1
1s comp
0 1 1 0 0
(+12)10 = +(1100)2
+ 1 1 1 1 0
= 011002 Add --------------
(1)10 = (0001)2 1 0 1 0 1 0
Add carry 1
= 111102 in 1s comp.
--------------
Final
Result
0 1 0 1 1
 2s Complement Subtraction

Using 2s complement representation, subtracting

numbers is also easy
Step 1: Take 2s complement of 2nd operand
Step 2: Add binary numbers
Step 3: Ignore the resulting carry bit 0 1 1 0 0
- 0 0 0 0 1
For example: (+12)10 (1)10
2s comp 1 1
(+12)10 = +(1100)2 0 1 1 0 0
= 011002 Add + 1 1 1 1 1
(1)10 = (0001)2 Final
--------------
= 111112 in 2s comp. Result 1 0 1 0 1 1

Ignore
Carry
 2s Complement Subtraction

Example 2: (13)10 (5)10

(13)10 = +(1101)2 = (01101)2
(5)10 = (0101)2 = (11011)2
Adding these two 5-bit codes:
01101
+ 11011
Carry 1 01000
Discarding the carry bit, the sign bit is seen to be
zero, indicating a positive result
Indeed: (01000)2 = +(8)10
 2s Complement Subtraction

Example 3: (5)10 (12)10

(5)10 = +(0101)2 = (00101)2
(12)10 = (1100)2 = (10100)2
Adding these two 5-bit codes:
00101
+ 10100
Carry 0 11001
Here, there is no carry bit and the sign bit is 1.
This indicates a negative result, which is what we
expect: (11001)2 = (7)10
 Summary

Binary numbers can also be represented in octal and

hexadecimal
Easy to convert between binary, octal, and
hexadecimal
Signed numbers are represented in 3 codes: signed
magnitude, 1s complement, or 2s complement
2s complement code is most important
(only 1 representation for zero)
Important to understand the treatment of the sign bit
for 1s and 2s complement codes
Introductory Concepts
(Codes)
 Binary Coded Decimal

Binary Coded Decimal (BCD) represents each

decimal digit with four bits
Ex. 0011 0010 1001 = 32910
3 2 9

This is NOT the same as 0011001010012

Why do this? Because people think in decimal

Digit BCD Digit BCD

Code Code
0 0000 5 0101
1 0001 6 0110
2 0010 7 0111
3 0011 8 1000
4 0100 9 1001
 Putting It All Together

BCD is not very efficient

Used in early computers
(1940s, 1950s)
Used to encode numbers
for seven-segment
displays
Easier to read?
 Digit Binary Gray
Code
Gray Code 0 0000 0000
1 0001 0001
Gray code is not a number 2 0010 0011
system
3 0011 0010
It is an alternate way to 4 0100 0110
represent four bit data 5 0101 0111

Only one bit changes from one 6 0110 0101

decimal digit to the next 7 0111 0100
8 1000 1100
Useful for reducing errors in
9 1001 1101
communication
10 1010 1111
Can be scaled to larger 11 1011 1110
numbers 12 1100 1010
13 1101 1011
14 1110 1001
15 1111 1000
 ASCII Code
American Standard Code for Information Interchange
ASCII is a 7-bit code, frequently used with a 8th bit for
error detection (more about that later)

Character ASCII (bin) ASCII (hex) Decimal Octal

A 1000001 41 65 101
B 1000010 42 66 102
C 1000011 43 67 103

Z
a

1

 ASCII Codes and Data Transmission

ASCII Codes
A Z (26 codes), a z (26 codes)
0 9 (10 codes), others (@#$%^&*.)
Transmission susceptible to noise
Typical transmission rates (1500 Kbps, 56.6 Kbps)
How to keep data transmission accurate?
 Parity Codes

Parity codes are formed by concatenating a parity

bit, P to each code word C
In an even-parity code, the parity bit is specified so
that the total number of ones is even
In an odd-parity code, the parity bit is specified so
that the total number of ones is odd

P Information Bits

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

Added even parity bit Added odd parity bit
 Parity Code Example

Concatenate a parity bit to the ASCII code for the

characters 0, X, and = to produce both odd-
parity and even-parity codes

Character ASCII Odd-Parity Even-Parity

ASCII ASCII

0 0110000 10110000 00110000

X 1011000 01011000 11011000

= 0111100 10111100 00111100

 Binary Data Storage

Binary cells store individual bits of data

Multiple cells form a register
Data in registers can indicate different values
Hex (binary)
BCD
ASCII

0 0 1 0 1 0 1 1

Binary Cell
 Register Transfer

Data can move from a register to a register

Digital logic used to process data

Register A Register B

Digital Logic
Circuits

Register C
 Transfer of Information

Data input at keyboard

Shifted into place
Stored in memory

NOTE: Data input in ASCII

 Building a Computer

We need processing
We need storage
We need communication

You will learn to use and

design these components
 Summary

Although 2s complement is most important, other

number codes exist
ASCII code is used to represent characters (such as
those on the keyboard)
Registers store binary data
 Unit-II
Boolean Algebra and
Logic gates
 Digital Systems

Analysis problem:

. Logic .
Inputs Outputs
Circuit
. .

Determine the binary output for each input combination

Design problem: given a task, develop a circuit

that accomplishes that task
Many possible implementations
Best circuit: based on some criterion (size, power,
performance, etc.)
 Toll Booth Controller

Consider the design of a toll booth controller

Inputs: quarter, car sensor
Outputs: gate-lift signal, gate-close signal

$.25 Logic Raise gate

Car? Circuit Close gate

If driver pitches in quarter, raise gate

When car has cleared gate, close gate
 Describing Circuit Functionality: Inverter

Basic logic functions have symbols

The same functionality can be
represented with a truth table
Truth table completely specifies outputs for all input
combinations
This is an inverter Truth Table

An input of 0 is inverted to a 1 A Y
An input of 1 is inverted to a 0 0 1

1 0
A Y
Input Output
Symbol
 The AND Gate

This is an AND gate Truth Table

If the two input signals A B Y

are asserted (i.e. high) the 0 0 0
output will also be asserted. 0 1 0
Otherwise, the output will 1 0 0
be deasserted (i.e. low) 1 1 1

A A B
Y
B
 The OR Gate

This is an OR gate
A B Y
If either of the two
0 0 0
input signals is
0 1 1
asserted, or both of
1 0 1
them are, the output
1 1 1
will be asserted
A

A B
Y
B
 Describing Circuit Functionality: Waveforms

Waveforms provide another approach for

representing functionality
Values are either high (logic 1) or low (logic 0)
Can you create a truth table from the waveforms?

AND Gate

x y f
0 0 0
0 1 0
1 0 0
1 1 1
Consider three-input gates

3 Input OR Gate
 Ordering Boolean Functions

How to interpret A B + C?
Is it A B ORed with C ?
Is it A ANDed with B + C ?
Order of precedence for Boolean algebra: AND
before OR
Note that parentheses are needed here:
 Boolean Algebra

A Boolean algebra is defined as a closed algebraic

system containing a set K of two or more elements
and the two operators, and +
Useful for identifying and minimizing circuit
functionality
Identity elements
a+0=a
a1=a
0 is the identity element for the + operation
1 is the identity element for the operation
 Commutativity and Associativity of the Operators

Commutative Property:
For every a and b in K,
a+b=b+a
ab=ba
Associative Property:
For every a, b, and c in K,
a + (b + c) = (a + b) + c
a (b c) = (a b) c
 Distributivity of the Operators and Complements

Distributive Property:
For every a, b, and c in K,
a+(bc)=(a+b)(a+c)
a(b+c)=(ab)+(ac)

The Existence of the Complement:

For every a in K there exists a unique element called a (or )
(complement of a) such that,
a + a = 1
a a = 0

To simplify notation, the operator is frequently

omitted. When two elements are written next to
each other, the AND () operator is implied
a+bc=(a+b)(a+c)
a + bc = ( a + b )( a + c )
 Duality

The principle of duality is an important concept:

If an expression is valid in Boolean algebra, the
dual of that expression is also valid
To form the dual of an expression, replace all +
operators with operators, all operators with +
operators, all ones with zeros, and all zeros with
ones
Form the dual of the equation:
a + (bc) = (a + b)(a + c)

Following the replacement rules:

a(b + c) = ab + ac

Take care not to alter the location of the

parentheses if they are present
 Involution

This theorem states:

a = a a=a
Remember that:
aa = 0 aa=0
a+a=1 a+a=1
Therefore, a is the complement of a
and a is also the complement of a
Taking the double inverse of a value produces the
initial value
 Absorption

This theorem states:

a + ab = a a(a+b) = a
To prove the first half of this theorem:
a + ab = a 1 + ab
= a (1 + b)
= a (b + 1)
= a (1)
a + ab = a
 DeMorgans Theorem

A key theorem in simplifying Boolean algebra

expressions is DeMorgans Theorem. It states:
(a + b) = ab (ab) = a + b
a+b =ab ab =a +b
Example: Complement and simplify the expression
a(b + z(x + a))
a (b + z ( x + a)) = a + (b + z (x + a))
= a + b (z (x + a))
= a + b (z + (x + a))
= a + b (z + x a)
= a + b (z + x a)
 Summary

Basic logic functions can be made from AND, OR, and

NOT (invert) functions
The behavior of digital circuits can be represented
with waveforms, truth tables, or symbols
Primitive gates can be combined to form larger
circuits
Boolean algebra defines how binary variables can be
combined
Rules for associativity, commutativity, and
distribution are similar to algebra
DeMorgans rules are important
Will allow us to reduce circuit sizes
 UNIT-II
Boolean Algebra and Logic
gates
 Boolean Functions

Boolean algebra deals with binary variables and

logic operations
Function results in binary 0 or 1

x y z xy yz G
0 0 0 0 0 0
0 0 1 0 0 0 x xy
0 1 0 0 0 0 y
0 1 1 0 1 1 G = xy +yz
1 0 0 0 0 0 z
yz
1 0 1 0 0 0
1 1 0 1 0 1 How to transit between an equation, a
1 1 1 1 1 1 circuit, and a truth table?
 Representation Conversion

Need to transit between a Boolean expression, a

truth table, and a circuit (symbols)
Conversion between truth table and expression is
easy
Conversion between expression and circuit is easy
Conversion to truth table is more difficult

Circuit Boolean
Expression

Truth
Table
 Truth Table to Expression

Converting a truth table to an expression

Each row with an output of 1 becomes a product term
Sum the product terms together

x y z G
0 0 0 0 Any Boolean Expression can be
0 0 1 0 represented in sum of products form!
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 1
xyz + xyz + xyz
 Equivalent Representations of Circuits

All three formats are equivalent

Number of 1s in truth table output column equals
AND terms for Sum-of-Products (SOP)
x y z G
0 0 0 0
0 0 1 0

0 1 0 0 G

0 1 1 1

1 0 0 0
1 0 1 0

1 1 0 1
1 1 1 1

x y z
G = xyz + xyz + xyz
 Reducing Boolean Expressions

Is this the smallest possible implementation of this

expression? No! G = xyz + xyz + xyz
Use Boolean Algebra rules to reduce complexity
while preserving functionality
Step 1: Use Theorem 1 (a + a = a)
xyz + xyz + xyz = xyz + xyz + xyz + xyz
Step 2: Use distributive rule a(b + c) = ab + ac
xyz + xyz + xyz + xyz = xy(z + z) + yz(x + x)
Step 3: Use Postulate 3 (a + a = 1)
xy(z + z) + yz(x + x) = xy.1 + yz.1

Step 4: Use Postulate 2 (a . 1 = a)

xy.1 + yz.1 = xy + yz = xyz + xyz + xyz
 Reduced Hardware Implementation

Reduced equation requires less hardware!

Same function is implemented!
x y z G
0 0 0 0
0 0 1 0
0 1 0 0 G
0 1 1 1
1 0 0 0
1 0 1 0

1 1 0 1
1 1 1 1

x y z
G = xyz + xyz + xyz = xy + yz
 Minterms and Maxterms

Each variable in a Boolean expression is a literal

Boolean variables can appear in normal (x) or
complemented form (x)
Each AND combination of terms is a minterm
Each OR combination of terms is a maxterm
For example: For example:

x y z Minterm x y z Maxterm
0 0 0 xyz m0 0 0 0 x+y+z M0
0 0 1 xyz m1 0 0 1 x+y+z M1

1 0 0 xyz m4 1 0 0 x+y+z M4

1 1 1 xyz m7 1 1 1 x+y+z M7
 Representing Functions with Minterms

Minterm number is same as row position in truth table

(starting with 0 at the top)
Shorthand way to represent functions

x y z G
0 0 0 0 G = xyz + xyz + xyz
0 0 1 0
0 1 0 0
0 1 1 1 G = m7 + m6 + m3 = (3, 6, 7)
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 1
 Complementing Functions

Minterm number is same as row position in truth table

(starting with 0 at the top)
Shorthand way to represent functions

x y z G G
0 0 0 0 1 G = xyz + xyz + xyz
0 0 1 0 1
0 1 0 0 1
0 1 1 1 0 G = (xyz + xyz + xyz) = ?
1 0 0 0 1
1 0 1 0 1
1 1 0 1 0 Can we find a simpler representation?
1 1 1 1 0
 Complementing Functions

Step 1: assign temporary names

b+ c z G = a + b+ c
(a + z) = G G = (a + b + c)
Step 2: Use DeMorgans Law
(a + z) = a z
Step 3: Resubstitute (b+c) for z
a z = a (b + c)

Step 4: Use DeMorgans Law

G = a + b+ c
a (b + c) = a (b c)
G = a b c = abc
Step 5: Associative rule
a (b c) = a b c
 Complementation Example

Find complement of F = xz + yz
F = (xz + yz)
DeMorgans
F = (xz) (yz)
DeMorgans
F = (x+z) (y+z)
Reduction eliminate double negation on x
F = (x+z) (y+z)

This format is called product of sums

 Conversion Between Canonical Forms

Easy to convert between minterm and maxterm

representations
For maxterm representation, select rows with 0s

x y z G G = xyz + xyz + xyz

0 0 0 0
0 0 1 0
0 1 0 0 G = m7 + m6 + m3 = (3, 6, 7)
0 1 1 1
1 0 0 0
1 0 1 0 G = M0M1M2M4M5 = (0,1,2,4,5)
1 1 0 1
1 1 1 1
G = (x+y+z)(x+y+z)(x+y+z)(x+y+z)(x+y+z)
 Representation of Circuits

Any logic expression can be represented in a 2-level

circuit
Circuits can be reduced to minimal 2-level
representations
Sumofproducts representation is most common in
industry
 Summary

Truth table, circuit, and Boolean expression

formats are equivalent
Easy to translate a truth table to SOP and POS
representations
Boolean algebra rules can be used to reduce circuit
size while maintaining functionality
All logic functions can be made from AND, OR, and
NOT
Easiest way to understand: Do examples!
 UNIT-II
Boolean Algebra and
Logic Gates
 Boolean Functions

Boolean algebra deals with binary variables and

logic operations
Function results in binary 0 or 1

x y z F
0 0 0 0
0 0 1 0 x
0 1 0 0 y
0 1 1 0 F = x(y+z)
z y+z
1 0 0 1 z
1 0 1 0
1 1 0 1
1 1 1 1 F = x(y+z)
 Logic functions of N variables

Each truth table represents one possible function

(AND, OR etc)
2N
If there are N inputs, there are 2
For example, if N is 2 then there are 16 possible
truth tables
So far, we have defined 2 of these functions
14 more are possible
x y G
Why consider new functions?
0 0 0
Cheaper hardware, more flexibility 0 1 0
1 0 0
1 1 1
 The NAND Gate

The NAND gate is a combination of an AND gate

followed by an inverter
NAND gates have several interesting properties
NAND(a,a) (aa) = a NOT(a)
NAND(a,b) (ab) = ab AND(a,b)
NAND(a,b) (ab) = a+b OR(a,b)

A B Y
A
Y 0 0 1
B 0 1 1
1 0 1
Y=AB 1 1 0
 The NAND Gate

Those three properties show that:

a NAND gate with both of its inputs driven by the same
signal is equivalent to a NOT gate
a NAND gate whose output is complemented is equivalent to
an AND gate
a NAND gate with complemented inputs acts as an OR gate
Hence, we can use a NAND gate to implement all
three of the elementary operators
(AND, OR, NOT)
Therefore, ANY switching function can be
constructed using only NAND gates. Such a gate is
said to be primitive or functionally complete
(Universal Gate)
 NAND Gates into Other Gates

What are these circuits?

A
Y

NOT Gate A
B Y

A AND Gate

Y
B

OR Gate
 The NOR Gate

A NOR gate is a combination of an OR gate followed

by an inverter
NOR gates also have several interesting properties
NOR(a,a) (a+a) = a NOT(a)
NOR(a,b) (a+b) = a+b OR(a,b)
NOR(a,b) (a+b) = ab AND(a,b)
A B Y

0 0 1
A
Y 0 1 0
B
1 0 0

Y=A+B 1 1 0
 Functionally Complete Gates

Just like the NAND gate, the NOR gate is functionally

completeany logic function can be implemented
using just NOR gates
Both NAND and NOR gates are very valuable as any
design can be realized using either one
It is easier to build an IC chip using all NAND or NOR
gates than to combine AND, OR, and NOT gates
NAND/NOR gates are typically faster in switching and
cheaper to produce
 NOR Gates into Other Gates

What are these circuits?

A
Y

NOT Gate A
B Y

A OR Gate

Y
B

AND Gate
 The XOR Gate (Exclusive-OR)

This is a XOR gate

A B Y
XOR gates assert their output
0 0 0
when exactly one of the inputs
0 1 1
is asserted, hence the name
1 0 1
The switching algebra symbol
1 1 0
for this operation is :
1 1 = 0 and 1 0 = 1

A
Y=AB Y
B
 The XNOR Gate

This is a XNOR gate

A B Y
This functions as an
0 0 1
exclusive-NOR gate, or
0 1 0
simply the complement of
1 0 0
the XOR gate
1 1 1
The switching algebra symbol
for this operation is :
1 1 = 1 and 1 0 = 0
A
Y
Y=AB B
 NOR Gate Equivalence

NOR Symbol, Equivalent Circuit, Truth Table

 DeMorgans Theorem

A key theorem in simplifying Boolean algebra

expression is DeMorgans Theorem. It states:
(a + b) = ab (ab) = a + b
a+b =ab ab =a +b
Example: Complement and simplify the expression
a(b + z(x + a))
a (b + z ( x + a)) = a + (b + z (x + a))
= a + b (z (x + a))
= a + b (z + (x + a))
= a + b (z + x a)
= a + b (z + x a)
 Example

Determine the output expression for the following

circuit and simplify it using DeMorgans Theorem
Universality of NAND gate
Universality of NOR gate
Example
 Interpretation of the two NAND gate symbols

DeMorgans Theorem
 Interpretation of the two OR gate symbols

DeMorgans Theorem
 Summary

Basic logic functions can be made from NAND, and

NOR functions
The behavior of digital circuits can be represented
with waveforms, truth tables, or Boolean expressions
Primitive gates can be combined to form larger
circuits
Boolean algebra defines how binary variables can be
combined with NAND, NOR
DeMorgans rules are important
Allow conversion to NAND/NOR representations
K-MAP
 Karnaugh maps

Alternate way of representing Boolean functions

A Karnaugh map is a graphical tool for assisting in
the general simplification procedure
Each row in the truth table is represented by a square
Each square represents a minterm

x y F
y
x 0 1 0 0 1
0 1 1 0 1 1
y
1 0 0 1 0 0
y
x 0 1 1 1 0
0 xy xy
x
1 xy xy F = (m0,m1) = xy + xy
 Karnaugh Maps

Two variable maps

B B
A 0 1 A 0 1
0 0 1 F=AB+AB 00 1 F=AB +AB +AB
11 0 11 1

Three variable maps A B C F

0 0 0 0
0 0 1 1
BC 0 1 0 1
00 01 11 10
A 0 1 1 0
00 1 0 1 1 0 0 1
1 0 1 1
11 1 1 1 1 1 0 1
+
1 1 1 1

F=ABC +ABC +ABC + ABC + ABC + ABC

 Karnaugh maps

Numbering scheme is based on Gray code

e.g. 00, 01, 11, 10
Only a single bit changes in code for adjacent map cells
Observe the variable transitions
BC B B
00 01 11 10 BC
A A 00 01 11 10
0 0 0 1 1 0
G(A,B,C) = B 0 1 3 2
A 1 0 0 1 1 A 1 4 5 7 6
C C
BC B
A 00 01 11 10

0 1 0 0 1 F(A,B,C) = m(0,2,6,7) = AC +AB

A 1 0 0 1 1
C
 Karnaugh Maps

Two variable maps

B B
A 0 1 A 0 1
0 0 1 F=AB+AB 00 1 F=AB +AB +AB
11 0 11 1 F=A+B

Three variable maps

BC
00 01 11 10
A
00 1 0 1
11 1 1 1 F=A +BC +BC

F=ABC +ABC +ABC + ABC + ABC + ABC

 More Karnaugh Map Examples
Examples b b
a 0 1 a 0 1
0 0 1 0 1 1
1 0 1 1 0 0
f=b f = a'

bc bc
a 00 01 11 10 a 00 01 11 10
0 0 0 1 0 0 0 0 1 1
1 0 1 1 1 1 0 0 1 1
cout = ac+bc + ab f=b

1. Circle the largest groups possible

2. Group dimensions must be a power of 2
3. Remember what circling means!
 Application of Karnaugh Maps: The One-bit Adder

Cin A B Cin S Cout

0 0 0 0 0
0 0 1 1 0
0 1 0 1 0 How to use a Karnaugh
A 0 1 1 0 1
Adder S Map instead of the
1 0 0 1 0
B Algebraic simplification?
1 0 1 0 1
1 1 0 0 1
+
1 1 1 1 1
Cout

S = ABCin + ABCin + ABCin + ABCin

Cout = ABCin + A BCin + ABCin + ABCin
= ABCin + ABCin + ABCin + ABCin + ABCin + ABCin
= (A + A)BCin + (B + B)ACin + (Cin + Cin)AB
= 1BCin + 1 ACin + 1 AB
= BCin + ACin + AB
 Application of Karnaugh Maps: The One-bit Adder
Cin
A B Cin S Cout
0 0 0 0 0
0 0 1 1 0
A 0 1 0 1 0
Adder S 0 1 1 0 1
B 1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
Cout +
1 1 1 1 1
B
BC
A 00 01 11 10

0 Now we have to cover all the 1s in the

0 0 1 0 Karnaugh Map using the largest
A 1 rectangles and as few rectangles
0 1 1 1 as we can.
C Cout = BCin + AB + ACin

Karnaugh Map for Cout

 Application of Karnaugh Maps: The One-bit Adder
Cin
A B Cin S Cout
0 0 0 0 0
0 0 1 1 0
A 0 1 0 1 0
Adder S 0 1 1 0 1
B 1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
Cout +
1 1 1 1 1
B
BC
A 00 01 11 10

0
Now we have to cover all the 1s in the
0 1 0 1 Karnaugh Map using the largest
1
rectangles and as few rectangles
A 1 0 1 0 as we can.
C S = A B Cin + ABCin + A B Cin+A BCin
No Possible Reduction!
Karnaugh Map for S
 Summary

Karnaugh map allows us to represent functions with

new notation
Representation allows for logic reduction
Implement same function with less logic

Each square represents one minterm

Each circle leads to one product term
Not all functions can be reduced
K-MAP
 Karnaugh Maps for 4Input Functions

Represent functions of 4 inputs with 16 minterms

Use same rules developed for 3-input functions
 F(A,B,C,D) = m( 0, 2, 3, 5, 6, 7, 8, 10, 11, 14, 15)

1 0 1 1

0 1 1 1

0 0 1 1

1 0 1 1

F = C + ABD + BD
 Design Examples

K-map for LT

0 1 1 1

0 0 1 1

0 0 0 0

0 0 1 0

F = AC + ABD + BCD
 Design Examples

K-map for EQ

1 0 0 0

0 1 0 0

0 0 1 0

0 0 0 1

F = ABCD + ABCD + ABCD + ABCD

 Design Examples

K-map for GT

0 0 0 0

1 0 0 0

1 1 0 1

1 1 0 0

F = AC + BCD + ABD
 Physical Implementation

Step 1: Truth table

Step 2: K-map
Step 3: Minimized sum-of-products
Step 4: Physical implementation
with gates
 Physical Implementation
K-map for EQ
A B C D

1 0 0 0
EQ
EQ
0 1 0 0

0 0 1 0

0 0 0 1

F = ABCD + ABCD + ABCD + ABCD

 Karnaugh Maps

Four variable maps

CD
00 01 11 10
AB F=ABC +ACD +ABC
00 0 0 0 1
+AB CD +ABC +AB C
01 1 1 0 1
11 1 1 1 1 F=BC + AC +CD + AD
10 1 0 1 1

Need to make sure all 1s are covered

Try to minimize total product terms
Design could be implemented using NANDs and NORs
 Karnaugh Maps: Dont Cares

In some cases, outputs are undefined

We dont care if the circuit produces a 0 or a 1
This knowledge can be used to simplify functions
A
AB
CD 00 01 11 10
00 0 0 X 0 - Treat Xs like either 1s or 0s
01 - Very useful
1 1 X 1
D - OK to leave some Xs uncovered
11 1 1 0 0
C
10 0 X 0 0

B
 Karnaugh Maps: Dont Cares

F(A,B,C,D) = (1,3,5,7,9) + d(6,12,13) A B C D F

C 0 0 0 0 0
CD 0 0 0 1 1
AB 00 01 11 10 0 0 1 0 0
0 0 1 1 1
00 0 1 1 0 0 1 0 0 0
0 1 0 1 1
01 0 1 1 X 0 1 1 0 X
B
0 1 1 1 1
11 X X 0 0
+ +

1 0 0 0 0
A 1 0 0 1 1
10 0 1 0 0
1 0 1 0 0
D 1 0 1 1 0
1 1 0 0 X
1 1 0 1 X
1 1 1 0 0
F=AD + BCD Without dont cares 1 1 1 1 0
f = A'D + B'C'D
F=AD + CD
without don't cares
With dont cares
 Dont Care Conditions

In some situations, we dont care about the value of a

function for certain combinations of the variables
these combinations may be impossible in certain contexts
or the value of the function may not matter when the
combinations occur
In such situations we say the function is incompletely
specified and there are multiple (completely specified)
logic functions that can be used in the design
so we can select a function that gives the simplest circuit
When constructing the terms in the simplification
procedure, we can choose to either cover or not cover
the dont care conditions
 Map Simplification with Dont Cares

CD
00 01 11 10
AB
00 0 1 0 0
01 x x x 1 F=ACD+B +AC
11 1 1 1 x
10 x 0 1 1

CD
00 01 11 10
AB
00 0 1 0 0
01 x x x 1
11 1 1 1 x F= ABCD +BC +AC+ABC
10 x 0 1 1
Alternative covering:
 Karnaugh Maps: Product of Sums
F(A,B,C,D) = (2,3,9,11,13) + d(6,14)

CD
AB 00 01 11 10
00 0 0 1 1

01 0 0 0 x

11 0 1 0 x
00 01 11
10 0 1 1 0

F = ACD + ABD + ABC

 Karnaugh Maps: Product of Sums
G(A,B,C,D) = (0,1,4,5,7,8,10,12,15) + d(6,14)

CD
AB 00 01 11 10
00 1 1 0 0

01 1 1 1 x

11 1 0 1 x
00 01 11
10 1 0 0 1

G = AD + AC + BC
 Karnaugh Maps: Product of Sums
F(A,B,C,D) = (2,3,9,11,13) + d(6,14)

CD
AB 00 01 11 10
00 0 0 1 1

01 0 0 0 x

11 0 1 0 x
00 01 11
10 0 1 1 0

F = ACD + ABC+
ABC ABD (A+C)(A+D)
F= (B+C) (A+C)
 Prime Implicants

Any single 1 or group of 1s in the Karnaugh map of a

function F is an implicant of F.
A product term is called a prime implicant of F if it
cannot be combined with another term to eliminate a
variable.
(a) ABC
CD (b) BD
00 01 11 10 (c) ABCD
AB (d) AC
00 1 1 1 (e) ABD Implicants:
01 1 1 (a),(c),(d),(e)
11 1 Prime Implicants:
10 1 1 (d),(e)
 Essential Prime Implicants
A product term is an essential prime implicant if there is a
minterm that is only covered by that prime implicant
The minimal sum-of-products form of F must include
all the essential prime implicants of F
 Examples to Illustrate Terms

CD C

AB 00 01 11 10
00 0 X 1 0 AD, AC, ABC, CD, BC'D'

01 1 1 1 0
B essential
11 1 0 1 1
A minimum cover: AC + AD + BC'D'
10 0 0 1 1

D
 Examples to Illustrate Terms
CD C
AB 00 01 11 10 5 prime implicants:
00 0 0 1 0 BD, ABC,
ABC AC'D, A'BC'
A'BC, A'CD
01 1 1 1 0
B
11 0 1 1 1
A
10 0 1 0 0
minimum cover: 4 essential implicants
D
 Summary

K-maps of four literals were considered

Larger examples exist
Dont care conditions help minimize functions
Output for dont cares are originally undefined
Result of minimization is a minimal sum-of-products
Result contains prime implicants
Essential prime implicants are required in the
implementation
 NAND-NAND & NOR-NOR Networks

DeMorgans Law:
(a + b) = a b (a b) = a + b
a+b = ab ab =a +b

a + b = (a b) (a b) = (a + b)
a+b = a b ab = a +b

push bubbles or introduce in pairs or remove pairs

 NAND-NAND Networks
Mapping from AND/OR to NAND/NAND
 Implementations of 2-Level Logic

Sum-of-products
AND gates to form product terms
(minterms)
OR gate to form sum

Product-of-sums
OR gates to form sum terms
(maxterms)
AND gates to form product
 Two-level Logic using NAND Gates

Replace minterm AND gates with NAND gates

Place compensating inversion at inputs of OR gate
 Two-level Logic using NAND Gates (contd)

OR gate with inverted inputs is a NAND gate

DeMorgan's: A' + B' = (A B)' A+B=AB
Two-level NAND-NAND network
Inverted inputs are not counted
In a typical circuit, inversion is done once and signal is
then distributed
 Conversion Between Forms (contd)
Example: verify equivalence of two forms

A A
NAND
B B
Z NAND Z
C C
NAND
D D

Z = [ (A B)' (C D)' ]'

= [ (A' + B') (C' + D') ]'
= [ (A' + B')' + (C' + D')' ]
= (A B) + (C D)
 Multi-level Logic

x = (A + B + C) (D + E) F + G
Factored form not written as two-level S-o-P
1 x 3-input OR gate, 2 x 2-input OR gates, 1 x 3-input AND gate
10 wires (7 literals plus 3 internal wires)

A
B
C
X
D
E
F
G
 Conversion of Multi-level Logic to NAND Gates

F = A (B + C D) + B C'
 Exclusive-OR Circuits

Exclusive-OR (XOR) produces a HIGH output

whenever the two inputs are at opposite levels
 Exclusive-NOR Circuits

Exclusive-NOR (XNOR) produces a HIGH output

whenever the two inputs are at the same level
 XOR Function

XOR function can also be implemented with AND/OR

gates (also NANDs)
 XOR Function

Even function even number of inputs are 1

Odd function odd number of inputs are 1
Parity Generation and Checking
 Summary

Follow rules to convert between AND/OR

representation and symbols
Conversions are based on DeMorgans Law
NOR gate implementations are also possible
XORs provide straightforward implementation for
some functions
Used for parity generation and checking
XOR circuits can also be implemented using
AND/ORs
 The Problem

How can we convert from a circuit drawing to an

equation or truth table?
Two approaches
Create intermediate equations
Create intermediate truth tables

A
B
C
Out
A
B

C
 Label Gate Outputs

1. Label all gate outputs that are functions of input

variables
2. Label gates that are functions of input variables
and previously labeled gates
3. Repeat process until all outputs are labeled

A R
B
C
Out
S T
A
B

C
 Approach 1: Create Intermediate Equations

Step 1: Create an equation for each gate output

based on its inputs
R = ABC
S=A+B
T = CS
Out = R + T
A R
B
C
Out
S T
A
B

C
 Approach 1: Substitute in subexpressions

Step 2: Form a relationship based on input variables

R = ABC
S=A+B
T = CS = C (A + B)
Out = R+T = ABC + C(A+B)

A R
B
C
Out
S T
A
B

C
 Approach 1: Substitute in subexpressions

Step 3: Expand equation to SOP

Out = ABC + C(A+B) = ABC + AC + BC

A
B
C
Out
A
C

B
C
 Approach 2: Truth Table

Step 1: Determine outputs for A B C R S

functions of input variables 0 0 0 0 0
0 0 1 0 0
0 1 0 0 1
0 1 1 0 1
1 0 0 0 1
1 0 1 0 1
1 1 0 0 1
A R 1 1 1 1 1
B
C
Out
S T
A
B

C
 Approach 2: Truth Table

Step 2: Determine outputs for

A B C C R S T
functions of intermediate
0 0 0 1 0 0 0
variables.
0 0 1 0 0 0 0
0 1 0 1 0 1 1
T = S C
0 1 1 0 0 1 0
1 0 0 1 0 1 1
1 0 1 0 0 1 0
1 1 0 1 0 1 1
A R 1 1 1 0 1 1 0
B
C
Out
S T
A
B

C
 Approach 2: Truth Table

Step 3: Determine outputs

A B C R S T Out
for function.
0 0 0 0 0 0 0
0 0 1 0 0 0 0
0 1 0 0 1 1 1
Out = R + T 0 1 1 0 1 0 0
1 0 0 0 1 1 1
1 0 1 0 1 0 0
1 1 0 0 1 1 1
A R 1 1 1 1 1 0 1
B
C
Out
S T
A
B

C
 More Difficult Example

Note labels on interior nodes

 More Difficult Example: Truth Table

Remember to determine intermediate variables

starting from the inputs
When all inputs are determined for a gate,
determine its output
The truth table can be reduced using K-maps
A B C F2 F2 T1 T2 T3 F1
0 0 0 0 1 0 0 0 0
0 0 1 0 1 1 0 1 1
0 1 0 0 1 1 0 1 1
0 1 1 1 0 1 0 0 0
1 0 0 0 1 1 0 1 1
1 0 1 1 0 1 0 0 0
1 1 0 1 0 1 0 0 0
1 1 1 1 0 1 1 0 1
 Summary

Important to be able to convert circuits into truth table

and equation form
WHY? Leads to minimized sum of products representation

Two approaches illustrated

Approach 1: Create an equation with circuit outputs
dependent on circuit inputs
Approach 2: Create a truth table which shows relationship
between circuit inputs and circuit outputs

Both results can then be minimized using K-maps