CHAPTER 2

Logic Circuits

Chapter Objectives

In this chapter you will be introduced to:

Logic functions and circuits

Boolean algebra for dealing with logic
circuits
Logic gates and synthesis of simple circuits
CAD tools and the VHDL hardware
description language

Binary Switch

x =0

x =1
(a) Two states of a switch

S
x
(b) Symbol for a switch

Light Controlled by a Switch

S
Battery

Light

(a) Simple connection to a battery

S
Power
supply

Light

(b) Using a ground connection as the return path

AND and OR Logic Functions

Power
supply

x1

x2

Light

(a) The logical AND function (series connection)

S
x1
Power
supply

Light

x2
(b) The logical OR function (parallel connection)

Series-Parallel Connection

Power
supply

X1

X3

X2

Light

Inverting Circuit

R
Power
supply

Light

Truth Table for Two Input

Variables

Truth Table for Three Input

Variables

The Basic Gates

x1
x2

x1 x2
(a) AND gate

x1
x2

x1 +x2
(b) OR gate

x
(c) NOT gate

Inverter (NOT Circuit)

Performs a basic logic function called inversion or

complementation

Changes one logic level (HIGH / LOW) to the opposite logic level

In terms of bits, it changes a 1 to a 0 and vice versa

INPUT

OUTPUT

The AND Gate

Composed of two or more inputs and a single output

Performs logical multiplication.

The logical operation of the AND gate is such that the

output is HIGH (1) when all the inputs are HIGH, otherwise
it is LOW (0)
INPUT

OUTPUT

A.B

The OR Gate

Composed of two or more inputs and a single output

Performs logical addition

The logical operation of the OR gate is such that the output is

HIGH (1) when any of the inputs are HIGH, otherwise it is LOW
(0)
INPUT

OUTPUT

A + B

X = AB + A

INPUT

OUTPUT

X = AB + A

What is the Truth Table?

x
1
x
2
x
3

f = x + x x
1
2
3

Logic Network Example

x1
x2

0 0 1 1

1 1 0 0
0 0 0 1

0 1 0 1

(a) Network that implements

x1 x2
f ( x1 , x2 )
0
0
1
1

0
1
0
1

1
1
0
1

(b) Truth table

x1 1
0
x2 1
0
1
A 0
1
B 0
f 1
0

1 1 0 1

f = x1 + x1 x2
A

Time
(c) Timing diagram

Boolean Algebra

A mathematical system for formulating logical

statements with symbols so that problems can be
solved in a manner similar to ordinary algebra.
Boolean algebra is the mathematics of digital
systems.

Axioms of Boolean Algebra

Commutative Laws of Boolean

Algebra

The commutative law of addition for two

variables is algebraically expressed as:

The commutative law of multiplication for

two variables is expressed as:

x+y=y+x

xy = yx

In summary, the order in which the

variables are ORed or ANDed make no
difference.

Associative Laws of Boolean

Algebra

The associative law of addition of three

variables is expressed as:

The associative law of multiplication of three

variables is expressed as:

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

x(yz) = (xy)z

In summary, ORing or ANDing a grouping of

variables produces the same result
regardless of the grouping of the variables.

Distributive Law of Boolean

Algebra

The distributive law of three variables is

expressed as follows:

x (y+z) = xy + xz

This law states that ORing several

variables and ANDing the result is
equivalent of ANDing the single variable
with each of the variables in the grouping,
then ORing the result.

Single Variable Theorems

Rule Number
5 a.
5 b.
6 a.
6 b.
7 a.
7 b.
8 a.
8 b.
9.

Boolean Expression

x*0=0
x+1=1
x * 1= x
x+0=x
x*x=x
x+x=x
x * x =0
x + x =1
(x) = x

Duality

To reflect the principle of duality, the

axioms and single-variable theorems are
listed in pairs.
For example, see 5a and 3a.

When x =0, by 5a, the result is 0.

When x =1, by 5a, the result is 0, which is
also proved by 3a.

Two- and Three-Variable

Properties
Property

Boolean Expression

10 a. Commutative

x * y = y *x

10 b. Commutative

x+y=y+x

11 a. Associative

x * (y * z) = (x * y) * z

11 b. Associative

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

12 a. Distributive

x * (y + z) = x * y + x * z

12 b. Distributive

x + (y * z) = (x + y) * (x + z)

13 a. Absorption

x+x*y=x

13 b. Absorption

x * ( x + y) = x

Two- and Three-Variable

Properties
Property

Boolean Expression

14 a. Combining

x * y + x * y= x

14 b. Combining

(x + y ) * ( x + y) = x

15 a. DeMorgans Theorem

(x * y)= (x+ y)

15 b. DeMorgans Theorem

(x + y)= x * y

16 a.

x + x * y = x + y

16 b.

x * (x + y) = x * y

17 a. Consensus
17 b. Consensus

x * y + x * z + y * z = x * y + x * z
(x + y ) * (x + z) * (y + z )
= (x + y) * (x+ z)

Boolean Simplification

Example 1:

F = AB + CD + AB + CD
= AB + CD (by identity 5)

Example 2:

F = ABC + ABC + AC
= AB(C + C) + AC (by identity 13)
= AB(1) + AC (by identity 7)
= AB +AC (by identity 4)

Logic Circuit
Implementation

DeMorgans Theorem

(A B) = A + B

That is, the complement of the product is

equivalent to the sum of the complements.
This is true for any number of variables.
(A B C Z) = A + B + C + + Z

(A + B) = A B

(1)

(2)

Similarly, the complement of the sum is

equivalent to the product of the
complements.
Similarly, (A + B + C + + Z) = A * B * C
* * Z

Proof of DeMorgans
Theorem

Methods to Complement a
Function

Interchange 1s and 0s for the values of F in

the truth table
Use DeMorgans theorem on algebraic function

Change F to F, and F to F
Change OR to AND
Change AND to OR
Complement each individual variable

Example 1:

F = AB+ CD + BD
Applying DeMorgans theorem,
F = (A + B)(C + D)(B + D)

Methods to Complement a
Function

Example 2:

Simplify F = (x1 + x3) . (x1+ x3)

F = x1 x1+ x1 x3 + x3 x1+ x3 x3 (Distributive
Property)
x1 x1 and x3 x3 = 0 ( Identity 8)
F = x 1 x3 + x 1 x3

Example 3:

F = xyz + xyz +xz

= xy(z + z ) + xz (Factoring out)
= xy .1 + xz ( By Identity 6)
= xy + xz ( By Identity 4)

Practice Problems
Find the complement: (xyz)
Expand: x + yz
Simplify:

xy +xy + xy

xy + xz + xy + yz
wy + wyz + wxy + wxy

Venn Diagram
Representation

(a) Constant 1

x
(c) Variable

(b) Constant 0

x
x

(d)

Venn Diagram
Representation

x
(e)

x
(f)

x y

x+y

x
x

y
z

(g)

x y

(h)

x y + z

Verification of the Distributive

Property
x

z
(a)

z
(d)

z
(b)

z
(e)

y +z

x y + z

x z

z
(c)

x y

y
z

(f)

x y + x z

Verify xy + xz + yz = xy +
xz
x

x y

x y

x z

y z

x z

y
z

x y + x z + y z

y
z

x y + x z

Boolean Functions

Example 1:

Prove: (A + B) (A + B) = AB + AB
LHS

= AA + AB + BA + BB (by distributive
property)
= O + AB + BA + O = AB + AB = RHS

Example 2:

Prove: AC + B C + AC + BC = AB + AB + AB
LHS

= A(C+C) + B(C+C) = A*1 + B*1 = A + B

RHS = AB + AB + AB = AB + A(B + B) = A B +
A = A + B (by identity 11)
LHS = RHS

Precedence of Operations
NOT, AND, and then OR
Example: A*B + A*B
1. Complements
2. AND operations
3. OR operation

Synthesis Using Gates

f=m

* 1 + m1 * 1 + m2 * 0 + m3 *1

Two Implementations
x1
x2

(a) Canonical sum-of-products

x1

x2
(b) Minimal-cost realization

Terms and Definitions

Synthesis

The designing of a new system that

implements a desired functional behavior.

Analysis

The task of determining the function

performed by a system.

Terms and Definitions

Sum-of-Products (SOP)
Product-of-Sums (POS)
Canonical SOP
Canonical POS
Minterm

A product term with all n variables in

asserted or negated form.

Maxterm

The complement of a minterm

Three-Variable Minterms and

Maxterms

A Three-Variable Function

A Three-Variable Function

Canonical Sum-of-Products

f(x1, x2, x3) = x1x2x3 + x1x2x3 + x1x2x3 + x1x2x3

=

(m1, m4, m5, m6)

= m(1, 4, 5, 6)

Canonical Product-of-Sums

f(x1, x2, x3) = x1x2x3 + x1x2x3 + x1x2x3 + x1x2x3

f(x1, x2, x3) = (x1+x2+x3)(x1+x2+x3)(x1+x2+x3)
(x1+x2+x3)
=

(M0, M2, M3, M7)

= M(0, 2, 3, 7)

Practice Problems

Show that the minimal Sum-of-Products

is:

f(x1, x2, x3) = x2x3 + x1x3

Show that the minimal Product of Sums

is:

f(x1, x2, x3) = (x1 + x3)(x2 + x3)

Minimal Realizations
x2
f
x3
x1
(a) A minimal sum-of-products realization
1

x3
f

x2

(b) A minimal product-of-sums realization

More Practice Problems

Determine the canonical Sum-of-Products

expressions for the following functions:

f(x1, x2, x3) = m(2, 3, 4, 6, 7)

f(x1, x2, x3, x4) = m(3, 7, 9, 12, 13, 14, 15)

Now determine the minimized SOPs for

these two functions.
Find the canonical Product of Sums
expression for:

f(x1, x2, x) = M(0, 1, 5)

Four More Logic Gates

NAND
NOR
Exclusive OR (XOR)
Exclusive NOR (XNOR)

The NAND Gate

The NAND, which is composed of two or more inputs and a

single output, is a very popular logic element because it
may be used as a universal function.
It may be employed to construct an inverter, an AND gate,
an OR gate, or any combination of these functions.
The term NAND is formed by the concatenation NOT-AND
and implies an AND function with an inverted output.
The logical operation of the NAND gate is such that the
output is LOW (0) only when all the inputs are HIGH (1).
INPUT

OUTPUT

X = (AB)

The NOR gate

The NOR gate, which is composed of two or more inputs and a

single output, also has a universal property.
The term NOR is formed by the concatenation NOT-OR and
implies an OR function with an inverted output.
The logical operation of the NOR gate is such that the output is
HIGH (1) only when all the inputs are LOW.

The Exclusive-OR (XOR) and Exclusive

NOR (XNOR) Gates

These gates are usually formed

from the combination of the other
logic gates already discussed.
Because of their functional
importance, these gates are treated
as basic gates with their own
unique symbols.
The Exclusive-OR is an "inequality"
function and the output is HIGH (1)
when the inputs are not equal to
each other.
The Exclusive-NOR is an "equality"
function and the output is HIGH (0)
when the inputs are equal to each
other.

INPUT

XOR
XNOR
OUTPUT OUTPUT

AB

(AB)

NAND and NOR Gates

x1
x1
x2

x2
x1 x2 xn

x1 x2
xn
(a) NAND gates

x1
x1
x2

x2
x1 + x2

x1 + x2 + + xn
xn

(b) NOR gates

DeMorgans Theorem in Terms

of Logic Gates
x1
x2

x1

x1
x2

x2
(a)

x1
x2

x1x2 = x1 +x2

x1

x1
x2

x2
(b)

x1 +x2 = x1x2

Using NAND Gates to

Implement a Sum-of-Products
x1
x2

x1
x2

x3
x4
x5

x3
x4
x5

x1
x2
x3
x4
x5

Using NOR Gates to Implement

a Product-of-Sums
x1

x1

x2

x2

x3

x3

x4

x4

x5

x5

x1
x2
x3
x4
x5

NOR Gate Realization of an

Example Function
x1
x2

x3
(a) POS implementation

x1
x2

x3
(b) NOR implementation

NAND Gate Realization of an

Example Function
x1
f

x2
x3
(a) SOP implementation

x1
f

x2
x3
(b) NAND implementation

Truth Table for a Three-Way

Light Control

SOP and POS Realizations

x1
x2
x3
(a) Sum-of-products realization

x3
x2
x1
f

(b) Product-of-sums realization

Implementation of a
Multiplexer
x1
s x1 x2

f (s, x1, x2)

000

001

010

011

100

101

s
x2
(b) Circuit
s

110

x1

111

x2

(a)Truth table

0
1

s
f

(c) Graphical symbol

f (s, x1, x2)

x1

x2

(d) More compact truth-table representation

A Typical CAD System

See Figure 2.29, page 61, in your

textbook.

A Simple Logic Function

x1
x2
f
x3

VHDL

VHSIC Hardware Description Language

Very High Speed Integrated Circuit

Entity Declaration

Describes Ports
Input
Output

Architecture Declaration

Describes Functions

VHDL Entity Declaration

ENTITY example1 IS
PORT ( x1, x2, x3
f
END example1 ;

: IN BIT ;
: OUT BIT ) ;

VHDL Architecture for the

Entity
ARCHITECTURE LogicFunc OF example1 IS
BEGIN
f <= (x1 AND x2) OR (NOT x2 AND x3) ;
END LogicFunc ;

Complete VHDL Code for the

Circuit

VHDL Code for a Four-Input

Function

Logic Circuit for the VHDL

Code

Example 2.10

A circuit that controls a given digital system has

three inputs: x1, x2, and x3.
It has to recognize three different conditions:

Condition A is true if x3 is true and either x1 is true or x2

is false.
Condition B is true if x1 is true and either x2 or x3 is
false.
Condition C is true if x2 is true and either x1 is true or x3
is false.

The control circuit must produce an output of 1 if at

least two of the conditions A, B, and C are true.
Design the simplest circuit that can be used for this
purpose.

Solution to Example 2.10

Using 1 for true and 0 for false, express

the three conditions A, B, and C as:

A = x3(x1 + x2) = x3x1 + x3x2

B = x1(x2 + x3) = x1x2 + x1x3
C = x2(x1 + x3) = x2x1 + x2x3

The desired output can be expressed as:

f(x1, x2, x3) = AB + AC + BC

Solution to Example 2.10

Determine the product term AB:

= (x3x1 + x3x2)(x1x2 + x1x3)

= x3x1x1x2 + x3x1x1x3 + x3x2x1x2 +
x3x2x1x3
= x3x1x2 + O + x3x2x1 + O
= x1x2x3

Determine the product term AC = x1x2x3

Determine the product term BC = x1x2x3

Solution to Example 2.10

f(x1, x2, x3 ) = AB + AC + BC

= x1x2x3 + x1x2x3 + x1x2x3

= x1(x2 + x2)x3 + x1x2(x3 + x3)
= x1x3 + x1x2
=x1(x3 + x2)

Example 2.11

Solve Example 2.10 using Venn Diagrams

Solution to Example 2.11

x1

x2

x1

x3

x3

(a) Function A

x2

x1

x2

x3

(c) Function C

(b) Function B

x1

x2

x3

(d) Function f