CSE 205: DIGITAL LOGIC

DESIGN
BOOLEAN (BINARY) LOGIC
 Deals with binary variables and binary logic
functions
 Has two discrete values

 0, False, Open
 1, True, Close
 Three basic logical operations

 AND (.); OR (+); NOT (‘)

 We need to define algebra for binary values

 Boolean Algebra: Developed by George
Boole in 1854
BOOLEAN ALGEBRA
 Why study Boolean Algebra?
 To find the simplest circuit implementation
with the smallest number of gates or wires.

 The simpler that we can make a Boolean

function, the smaller the circuit that will result.
 Simpler circuits are cheaper to build,
consume less power, and run faster than
complex circuits.

 With this in mind, we always want to reduce

our Boolean functions to their simplest form.
ALGEBRA

 What is an algebra?
 Mathematical system consisting of
 Set of elements

 Set of operators

 Axioms or postulates: facts that can be

taken as true; they do not require proof

AXIOMATIC DEFINITION OF
BOOLEAN ALGEBRA
 A Boolean algebra requires
A set of elements B, consisting of two elements
(0 and 1)
 Two binary operations OR and AND
 The axioms below must always be true

1. x +y  B x  yB Closure
2. x +0 =x x  1 =x I dentity
3. x +y =y +x x  y =y  x Commutativity
4. x(y +z) =xy +xz x +yz =(x +y)(x +z) Distributivity
5. x +x’ =1 x  x’ =0 Complement
6. At least 2 elements: x,y  B such that x  y Cardinality
AXIOMATIC DEFINITION OF
BOOLEAN ALGEBRA

 Based on axiom #5, we can develop a unary

(one-argument) operation NOT

x x’
0 1
1 0

6
AXIOMATIC DEFINITION OF
BOOLEAN ALGEBRA
 The distributive laws

x y z y+z x ． (y+z) x．y x．z (x ． y)+(x ． z)

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

7
DUALITY PRINCIPLE
 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 expression

a + (bc) = (a + b)(a + c)
 Following the replacement rules…

a(b + c) = ab + ac
DUALITY PRINCIPLE
 The left and right columns of axioms are
duals
 exchange all ANDs with ORs, and 0s with 1s

1. x +y  B x  yB Closure
2. x +0 =x x  1 =x I dentity
3. x +y =y +x x  y =y  x Commutativity
4. x(y +z) =xy +xz x +yz =(x +y)(x +z) Distributivity
5. x +x’ =1 x  x’ =0 Complement
6. At least 2 elements: x,y  B such that x  y Cardinality

9
BASIC THEOREMS OF BOOLEAN
ALGEBRA
 In addition to the axioms, additional laws can be derived;
they are called theorems of Boolean Algebra
 These theorems are useful in performing algebraic
manipulations of Boolean expressions

1. x +x =x x  x =x I dempotency
2. x +1 =1 x  0 =0
3. yx +x =x (y +x)  x =x Absorption
4. (x’)’ =x I nvolution
5. x +(y +z) =(x +y) +z x(yz) =(xy)z Associative
6. (x +y)’ =x’y’ (xy)’ =x’ +y’ DeMorgan’s
PROOF OF X+X=X
 We can only use Post. 2: (a) x+0=x, (b) x·1=x
Huntington postulates:Post. 3: (a) x+y=y+x, (b) x·y=y·x
Post. 4: (a) x(y+z) = xy+xz,
(b) x+yz = (x+y)(x+z)
Post. 5: (a) x+x’=1, (b) x·x’=0

 Show that x+x=x.

x+x = (x+x)·1 by 2(b)
= (x+x)(x+x’) by 5(a)
= x+xx’ by 4(b)
= x+0 by 5(b)
= x by 2(a)
 We can now use Theorem 1(a) in future
proofs
PROOF OF X·X=X
 Similar to previous Post. 2: (a) x+0=x, (b) x·1=x
proof Post. 3: (a) x+y=y+x, (b) x·y=y·x
Post. 4: (a) x(y+z) = xy+xz,
(b) x+yz = (x+y)(x+z)
Post. 5: (a) x+x’=1, (b) x·x’=0
Th. 1: (a) x+x=x

 Show that x·x = x.

x·x = xx+0 by 2(a)
= xx+xx’ by 5(b)
= x(x+x’) by 4(a)
= x·1 by 5(a)
= x by 2(b)
PROOF OF X+1=1
 Theorem 2(a): x + 1 = 1 Post. 2: (a) x+0=x, (b) x·1=x
Post. 3: (a) x+y=y+x, (b) x·y=y·x
x + 1 = 1 ． (x + 1) by 2(b)
Post. 4: (a) x(y+z) = xy+xz,
=(x + x')(x + 1) 5(a) (b) x+yz = (x+y)(x+z)
= x + x' 1 Post. 5: (a) x+x’=1,
4(b) (b) x·x’=0
Th. 1: (a) x+x=x, (b) x.x =x
= x + x' 2(b)
=1
 Theorem 2(b): x ． 0 = 0 by duality
 Theorem 4: (x')' = x
 Postulate 5 defines the complement of x, x + x' =
1 and x x' = 0
 The complement of x' is x is also (x')'
ABSORPTION PROPERTY (COVERING)
Theorem 6(a): x + xy = x Post. 2: (a) x+0=x, (b) x·1=x
x + xy = x ． 1 + xy by 2(b)
Post. 3: (a) x+y=y+x, (b) x·y=y·x
= x (1 + y) 4(a) Post. 4: (a) x(y+z) = xy+xz,
(b) x+yz = (x+y)(x+z)
= x (y + 1) 3(a) Post. 5: (a) x+x’=1, (b) x·x’=0
Th. 1: (a) x+x=x, (b) x.x =x
= x．1 Th 2(a)
Th. 2: (a) x + 1 = 1, (b) x.0 =0
=x 2(b)

 Theorem 6(b): x (x + y) = x by duality

 By means of truth table (another way to
proof )
ABSORPTION PROPERTY (COVERING)
Theorem 6(a): x + xy = x

x y xy x+xy
0 0 0 0
0 1 0 0
1 0 0 1
1 1 1 1
DEMORGAN’S THEOREM
 Theorem 5(a): (x + y)’ = x’y’
 Theorem 5(b): (xy)’ = x’ + y’
 By means of truth table

x y x’ y’ x+y (x+y) x’y’ xy x’+y' (xy)’

’
0 0 1 1 0 1 1 0 1 1
0 1 1 0 1 0 0 0 1 1
1 0 0 1 1 0 0 0 1 1
1 1 0 0 1 0 0 1 0 0
CONSENSUS THEOREM

AB + A'C + BC = AB + A'C

 The consensus or resolvent of the terms AB

and A'C is BC
 It is the conjunction of all the unique literals of
the terms, excluding the literal that appears
unnegated in one term and negated in the
other
 CONSENSUS THEOREM
1. xy + x’z + yz = xy + x’z
2. (x+y)•(x’+z)•(y+z) = (x+y)•(x’+z) --
(dual)
 Proof:
xy + x’z + yz = xy + x’z + (x+x’)yz
= xy + x’z + xyz + x’yz
= (xy + xyz) + (x’z + x’zy)
= xy(1+z) + x’z (1+y)
= xy + x’z
BOOLEAN FUNCTION
 A Boolean function expresses the logical relationship
between binary variables and is evaluated by
determining the binary value of the expression for all
possible values of the variables.
f(x,y,z) = (x + y’)z + x’
 Some terminology, notation and precedence:
 f is the name of the function.
 (x,y,z) are the input variables, each representing 1
or 0.
 A literal is a single variable within a term, in
complemented or uncomplemented form. The
function above has four literals: x, y’, z, and x’.
 NOT has the highest precedence, followed by AND,
and then OR.
 BOOLEAN FUNCTION
 A Boolean function can be represented in a
truth table.
f(x,y,z) = (x + y’)z
+ x’ x y z f (x,y,z)
0 0 0 1
f(0,0,0) = (0 + 1)0 + 1 = 1
0 0 1 1
f(0,0,1) = (0 + 1)1 + 1 = 1
f(0,1,0) = (0 + 0)0 + 1 = 1 0 1 0 1
f(0,1,1) = (0 + 0)1 + 1 = 1 0 1 1 1
f(1,0,0) = (1 + 1)0 + 0 = 0 1 0 0 0
f(1,0,1) = (1 + 1)1 + 0 = 1 1 0 1 1
f(1,1,0) = (1 + 0)0 + 0 = 0 1 1 0 0
f(1,1,1) = (1 + 0)1 + 0 = 1
1 1 1 1
COMPLEMENT OF A FUNCTION
 The complement of a function always outputs
0 where the original function outputted 1, and
1 where the original produced 0.
f(x,y,z) = (x + y’)z
x y z f (x,y,z) + x’ x y z f ’ (x,y,z)
0 0 0 0 0 0 0 1
0 0 1 0 0 0 1 1
0 1 0 0 0 1 0 1
0 1 1 0 0 1 1 1
1 0 0 1 1 0 0 0
1 0 1 0 1 0 1 1
1 1 0 0 1 1 0 1
1 1 1 1 1 1 1 0
GATE IMPLEMENTATION OF A
FUNCTION
GATE IMPLEMENTATION OF A
FUNCTION
PRACTICE
 Simplify the following Boolean expressions to a
minimum number of literals:
 xyz + x'y + xyz’
 (A + B)'(A' + B') '

 xyz + x'y + xyz' = xy(z + z') + x'y = xy + x'y

=y

 (A + B)'(A' + B')' = (A'B')(A B) = (A'B')(BA) = 0

 COMPLEMENT OF A FUNCTION
 Applying DeMorgan’s theorems:

f(x,y,z) = x(y’z’ + yz)

f ’(x,y,z) = (x(y’z’ + yz))’ [ complement both sides ]
= x’ + (y’z’ + yz)’[ because (xy)’ = x’ + y’ ]
= x’ + (y’z’)’ (yz)’[ because (x + y)’ = x’ y’ ]
= x’ + (y + z)(y’ + z’) [ because (xy)’ = x’ + y’, twic
COMPLEMENT OF A FUNCTION
 By taking the dual of f and complementing
each literal:

 If
f(x,y,z) = x(y’z’ + yz)…
 …the dual of f is x + (y’ + z’)(y + z)…
 …then complementing each literal gives

x’ + (y + z)(y’ + z’)…
 …so f’(x,y,z) = x’ + (y + z)(y’ + z’)
PRACTICE
 Find the complement of the following
expressions:
 xy' + x'y
 [(x' + y + z')(x + y')(x + z)]
 F' = (xy' + x'y)'

= (xy')'(x'y)'
= (x' + y)(x + y')
= xy + x'y‘
 F' = [(x' + y + z')(x + y')(x + z)]'

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

= xy'z + x'y + x'z'
MINTERMS
 A minterm is an AND term in which every
variable or its complement in a function occurs
once.
 F(x,y) has 4 minterms x’y’, x’y, xy’, xy

 An n variable function has 2n valid minterms

 A minterm equals 1 at exactly one input

combination and is equal to 0 otherwise
 Example: x’y’z’ = 1 only when x=0, y=0,
z=0
MAXTERMS
 A maxterm is an OR term in which every
variable or its complement in a function occurs
once
 F(x,y) has 4 maxterms x’+y’, x’+y, x+y’,
x+y

 An n variable function has 2n valid maxterms

 A maxterm equals 0 at exactly one input

combination and is equal to 1 otherwise
 Example: (x+y+z) = 0 only when x=0, y=0,
z=0
EXAMPLE: THREE BINARY VARIABLES
CANONICAL FORM
 Any boolean function that is expressed as a
sum of minterms or as a product of
maxterms is said to be in its canonical form.
SUM OF MINTERMS

 A Boolean function can be expressed

algebraically from a given truth table
 by forming a minterm for each combination
of the variables that produces a 1 in the
function and
 then taking the OR of all those terms.
SUM OF MINTERMS

 F1(x, y, z) = ∑(1,4,5,6,7) = m1 + m4 + m5 + m6
+ m7
=x' y' z + xy' z’ + xy' z + xyz’ + xyz
SUM OF MINTERMS: EXAMPLE
 F = x + yz
= x(y + y’)(z + z’) + (x + x’)yz
= xyz + xyz’ + xy’z + xy’z’ + xyz + x’yz
= x’yz + xy’z’ + xy’z + xyz’ + xyz
= (3,4,5,6,7)

 Or convert the expression into truth-table and

then read the minterms from the table
PRODUCT OF MAXTERMS

 A Boolean function can be expressed

algebraically from a given truth table
 by forming a maxterm for each combination
of the variables that produces a 0 in the
function, and
 then taking the AND of all those maxterms.
PRODUCT OF MAXTERMS

 F1(x, y, z) = ∏(0,2,3) = M0 ×M2 ×M3

= (x + y + z)(x + y'+z)(x + y'+z')
PRODUCT OF MAXTERMS: EXAMPLE
 F = xy + x’z = (xy+x’)(xy+z)
= (x+x’)(y+x’)(x+z)(y+z) = (x’+y)(x+z)(y+z)

x’+y = x’+y+zz’ = (x’+y+z)(x’+y+z’)

x+z = x+z+yy’ = (x+y+z)(x+y’+z)
y+z = y+z+xx ’ = (x+y+z)(x ’+y+z)

F =(x+y+z)(x+y’+z)(x’+y+z)(x’+y+z’)
=M0M2M4M5= ∏(0, 2, 4,5)

 Or convert the expression into truth-table and

then read the maxterms from the table
CONVERSION BETWEEN CANONICAL
FORMS
 Conversion between minterms and maxterms
m0 = x’y’z’ = (x+y+z)’ = (M0)’
 In general, mi = (Mi)’

 Sum of minterms  Product of maxterms:

f = (0,1,2,3,6)
f’= (4,5,7) = m4 + m5 + m7
(f’)’= (m4 + m5 + m7)’
f = m4’ m5’ m7’ [DeMorgan’s law]
= M4 M5 M7 = ∏(4,5,7)
CONVERSION BETWEEN CANONICAL
FORMS
 In general, to convert from one canonical form
to another, interchange the symbols  and ∏
and list those numbers missing from the
original form.

 Example: f = (0,1,2,3,6) = ∏(4,5,7)

PRACTICE
 Express the following function (four variables:
A, B, C, D) as a sum of minterms and as a
product of maxterms:
 F = B'D + A'D + BD

 F = ∑(1, 3, 5, 7, 9, 11,13, 15)

= ∏(0, 2, 4, 6, 8, 10, 12, 14)
STANDARD FORM
 Any boolean function that is expressed as a
sum of products (SOP) or as a product of
sums (POS), where each product-term or
sum-term may contain one, two, or any
number of variables, is said to be in its
standard form.

 SOP: f(x,y,z) = xy + x’yz + xy’z

 POS: f(x,y,z) = (x’ + y’)(x + y’ + z’)(x’ + y +

z’)
NON-STANDARD AND STANDARD
FORMS
PRACTICE
 Convert the following expression into sum of
products and product of sums:
 (AB + C)(B + C'D)

 (AB + C)(B + C'D)

= AB + BC + ABC'D + CC'D
= AB(1 + C'D) + BC
= AB + BC (SOP form)
= B(A + C) (POS form)
CANONICAL AND STANDARD FORMS
 Canonical forms
 Sum of minterms (SOM)
 Product of maxterms (POM)
 Standard forms (may use less gates)

 Sum of products (SOP)

 Product of sums (POS)
 F = ab+a’ (already sum of products:SOP)

 F = ab + a’(b+b’) (expanding term)

 F = ab + a’b + a’b’ (it is canonical

form:SOM)
OTHER LOGIC OPERATIONS
 2n rows in the truth table of n binary variables.
 22n functions for n binary variables.

 16 functions of two binary variables.

BOOLEAN EXPRESSIONS
DIGITAL LOGIC GATES
 Boolean expression: AND, OR and NOT
operations
 Constructing gates of other logic operations

 The feasibility and economy;

 The possibility of extending gate's inputs;
 The basic properties of the binary
operations (commutative and associative);
 The ability of the gate to implement Boolean
functions.
SUMMARY OF LOGIC GATES

Figure 2.5 Digital logic gates

SUMMARY OF LOGIC GATES

Figure 2.5 Digital logic gates

MULTIPLE INPUTS
 Extension to multiple inputs
 A gate can be extended to multiple inputs.
 If its binary operation is commutative and

associative.
 AND and OR are commutative and
associative.
 OR

 x+y = y+x

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

 AND

 xy = yx

 (x y)z = x(y z) = x y z
MULTIPLE INPUTS
 NAND and NOR are commutative but not
associative → they are not extendable.
MULTIPLE INPUTS
 Multiple NOR = a complement of OR gate,
Multiple NAND = a complement of AND.
 The cascaded NAND operations = sum of

products.
 The cascaded NOR operations = product of

sums.
MULTIPLE INPUTS
 The XOR and XNOR gates are commutative and
associative.
 Multiple-input XOR gates are uncommon

 XOR is an odd function: it is equal to 1 if the

inputs variables have an odd number of 1's.

POSITIVE AND NEGATIVE LOGIC
 Positive and Negative
Logic
 Two signal values <=>
two logic values
 Positive logic: H=1;
L=0
 Negative logic: H=0;
L=1
 Consider a TTL gate

 A positive logic AND

gate
 A negative logic OR
gate
POSITIVE AND NEGATIVE LOGIC
SYLLABUS
 Chapter 2 (Excluding Section 2.9)