CSE 140, Lecture 2

Combinational Logic
CK Cheng
CSE Dept.
UC San Diego

1
 Combinational Logic Outlines
1. Introduction
• Scope
• Boolean Algebra (Review)
• Definition
• Duality
• AND/OR Gates
• Expressions vs Circuits
• Handy Tools
• DeMorgan’s Theorem
• Consensus Theorem
• Shannon’s Expansion
2. Specification
3. Synthesis
2
1.1 Combinational Logic: Scope
• Description
– Language: e.g. C Programming, Verilog, VHDL
– Boolean algebra
– Truth table: Powerful engineering tool
• Design
– Schematic Diagram
– Inputs, Gates, Nets, Outputs
• Goal
– Validity: correctness, turnaround time
– Performance: power, timing, cost
– Testability: yield, diagnosis, robustness

3
Scope: Boolean algebra, switching algebra, logic
• Boolean Algebra: multiple-valued logic, i.e. each variable
have multiple values.
• Switching Algebra: binary logic, i.e. each variable can be
either 1 or 0.
• Boolean Algebra ≠ Switching Algebra

Switching Algebra

BB Two Level Logic

Boolean Algebra

<4>
Scope: Switching Algebra (Binary Values)
• Typically consider only two discrete values:
– 1’s and 0’s
– 1, TRUE, HIGH
– 0, FALSE, LOW
• 1 and 0 can be represented by specific voltage levels,
rotating gears, fluid levels, etc.
• Digital circuits usually depend on specific voltage levels to
represent 1 and 0
• Bit: Binary digit

Copyright © 2007 1-<5> 5

Elsevier
 Scope: Levels of Logic
• Multiple Level Logic: Many layers of two level logic with
some inverters, e.g. (((a+bc)’+ab’)+b’c+c’d)’bc+c’e
(A network of two level logic)
• Two Level Logic: Sum of products, or product of sums, e.g.
ab + a’c + a’b’, (a’+c )(a+b’)(a+b+c’)

Features of Digital Logic Design

Boolean Algebra
• Multiple Outputs
Switching Algebra
• Don’t care sets BB
Two Level Logic

<6>
 1.2 Boolean Algebra (Review)
George Boole, 1815-1864
• Born to working class parents: Son of a
shoemaker
• Taught himself mathematics and joined
the faculty of Queen’s College in Ireland.
• Wrote An Investigation of the Laws of
Thought (1854): systematize Aristotle’s
logic
• Introduced binary variables
• Introduced the three fundamental logic
operations: AND, OR, and NOT.

Copyright © 2007 Elsevier 1-<7>

 Review of Boolean Algebra
Let B be a nonempty set with two 2-input operations, a
1-input operation ` (complement), and two distinct
elements 0 and 1. Then B is called a Boolean algebra if
the following axioms hold.
• Associative laws: (a+b)+c=a+(b+c), (a·b) ·c=a·(b·c)
• Commutative laws: a+b=b+a, a·b=b·a
• Distributive laws: a+(b·c)=(a+b)·(a+c),
a·(b+c)=a·b+a·c
• Identity laws: a+0=a, a·1=a
• Complement laws: a+a’=1, a·a’=0

<8>
 Review of Boolean Algebra: Duality
Associative laws (a+b)+c=a+(b+c) (a·b) ·c=a·(b·c)

Commutative laws a+b=b+a a·b=b·a

Distributive laws a+(b·c)=(a+b)·(a+c) a·(b+c)=a·b+a·c

Identity laws a+0=a a·1=a

Complement laws a+a’=1 a·a’=0

Duality: We swap all operators between (+,.) and interchange all

elements between (0,1).
For a theorem if the statement can be proven with the laws of
Boolean algebra, then the duality of the statement is also
<9> true.
 1.3 Switching functions: Operators and Digital Logic Gates
id
AB Y AND A B Y OR A Y NOT
Y=AB Y=A+B Y=A’
0 0 0 0 0 0 0 0 1
1 0 1 0 0 1 1 1 0
2 1 0 0 1 0 1
3 1 1 1 1 1 1
A A
A 1
1 1
A A
0 A
0 0
Input 0 dominates Y Input 1 dominates Y
0 blocks the output 0 passes signal A
1 passes signal A 1 blocks the output 10
 1.3 Switching functions: Operators and Digital Logic Gates

AND OR
id A B C Y A B C Y Y=A+B+C
Y=ABC
0 0 0 0 0 0 0 0 0
1 0 0 1 0 0 blocks 0 0 1 1 0 passes
the output signal A
2 0 1 0 0 1 passes 0 1 0 1 1 blocks
signal A the output
3 0 1 1 0 For AND, 0 1 1 1 For OR,
4 1 0 0 0 only one 1 0 0 1 only one
row is true row is false
5 1 0 1 0 (minterm) 1 0 1 1 (maxterm)

6 1 1 0 0 1 1 0 1
7 1 1 1 1 1 1 1 1 11
 1.3 Switching functions: Example on AND and OR
AND OR
id A B C Y A B C Y
0 0 0 0 Y=A’B’C 0 0 0 Y=A’+B’+C

1 0 0 1 0 0 1
2 0 1 0 0 1 0
3 0 1 1 0 1 1
4 1 0 0 1 0 0
5 1 0 1 1 0 1
6 1 1 0 1 1 0
7 1 1 1 1 1 1 12
Switching Expressions vs Logic
Diagrams
Switching expression is related to logic
implementation
• Switching Expression: #literals, #operators
• Schematic Diagram: #gates, #nets, #pins

13
 Laws and Logic Diagrams

Associativity Laws
(A+B) + C = A + (B+C)
C A
A B
B C
(AB)C = A(BC)
C A
A B
B C

14
 Laws and Logic Diagrams
Identity Laws A∙ 1 =A A+1=1
A∙0=0 A+0=A
Complement Laws A + A’ = 1 A ∙ A’ = 0

Distributive Laws
A ∙(B+C) = A ∙ B + A ∙ C A
A B
B A
C
C
A+B ∙ C = (A+B) ∙(A+C)
A
A B
B A
C C
15
Switching Expression and Logic
a a·b Cost: #gates, #nets, #pins
b a·b + c·d
c y=e·(a·b+c·d)
d c·d
e
Schematic Diagram: Boolean Algebra:
5 primary inputs 5 variables
1 primary output 1 expression
4 gates (3 ANDs, 1 OR) 4 operators (3 ANDs, 1 OR)
9 signal nets 5 literals
12 pins
16
 Switching Expression and Logic
a
a·b
b
Schematic Diagram: a·b + c·d
c y=e·(a·b+c·d)
5 primary inputs d c·d
4 components (gates)
e Boolean Algebra:
9 signal nets
5 literals
12 pins
4 operators
A. #inputs I. #variables
B. #gates II. #operators
C. #nets III. #variables + #operators
D. #pins IV. #literals + 2 #operators - 1
E. None

17
Example: f(a,b,c)= ab+a’c+a’b’

18
Example: f(a,b,c)= (a’+c)(a+b’)(a+b+c)

19
 1.4 Handy Tools
Boolean Algebra
Boolean Algebra
• DeMorgan’s Law: Complements
Switching Algebra
• Consensus Theorem
BB
Two Level Logic
Switching Logic
• Shannon’s Expansion
• Truth Table
• Karnaugh Map (single output, two level logic)

<20>
 DeMorgan’s Theorem and Digital Logic
T12. DeMorgan’s Theorem (A+B)’ = A’B’ (AB)’ = A’ + B’

• Y = (AB)’ = A’ + B’ A
B
Y

A
Y
B

A
• Y = (A + B)’= A’B’ B
Y

A
Y
B

<21>
DeMorgan’s Theorem: Bubble Pushing
• Pushing bubbles backward (from the output) or forward
(from the inputs) changes the body of the gate from
AND to OR or vice versa.
• Pushing a bubble from the output back to the inputs puts
bubbles on all gate inputs.

A A
Y Y
B B

• Pushing bubbles on all gate inputs forward toward the

output puts a bubble on the output and changes the gate
body.
A A
Y Y
B B

<22>
 Consensus Theorem
• AB+AC+B’C • (A+B)(A+C)(B’+C)
=AB+B’C =(A+B)(B’+C)
The consensus of AB, B’C is: ?

Exercise: to prove the reduction using

(1) Venn Diagrams,
(2) Boolean algebra,
(3) Logic simulation and
(4) Shannon’s expansion

<23>
Consensus Theorem: Venn Diagrams
AB+AC+B’C : AB+B’C

A A

B C B C

<24>
Consensus Theorem: Boolean Algebra
• AB+AC+B’C • (A+B)(A+C)(B’+C)
=AB+B’C =(A+B)(B’+C)
AB+AC+B’C
=AB+AC1+B’C
=AB+AC(B+B’)+B’C
=AB+ABC+AB’C+B’C
=AB(1+C)+(A+1)B’C
=AB+B’C

<25>
Consensus Theorem: Logic Simulation
f(A,B,C)= AB+AC+B’C
g(A,B,C)=AB+B’C

Index A B C AB AC B’C f g
0 0 0 0 0 0 0
1 0 0 1 0 0 1
2 0 1 0 0 0 0
3 0 1 1 0 0 0
4 1 0 0 0 0 0
5 1 0 1 0 1 1
6 1 1 0 1 0 0
7 1 1 1 1 1 0
<26>
<27>
Consensus Theorem (Examples)
Which one is not a consensus of the
expressions on the right.

A. B 1. A+A’B
B. BC
2. A+A’BC
C. (B+C)D
D. BCD 3. A(B+C)+A’D
E. BCDE 4. ABC+A’D+BCDE

<28>
 Shannon’s Expansion
• Shannon’s expansion assumes a switching algebra
system
• Divide a switching function into smaller functions
• Pick a variable x, partition the switching function
into two cases: x=1 and x=0
– f(x,y,z,…)= xf(x=1,y,z,…) + x’f(x=0,y,z,…)
• For example
– f(x)=xf(1)+x’f(0)
– f(x,y)=xf(1,y)+x’f(0,y)

<29>
Shannon’s Expansion (Example)
𝑓 𝑎, 𝑏, 𝑐 = 𝑎′ 𝑏 ′ + 𝑏𝑐 + 𝑎𝑏′𝑐
Shannon’s expansion:
𝑓 𝑎, 𝑏, 𝑐 = 𝑎𝑓 1, 𝑏, 𝑐 + 𝑎′ 𝑓 0, 𝑏, 𝑐

1-<30>
 Shannon’s Expansion: Example
𝑓 𝑥, 𝑦, 𝑧 = 𝑥𝑓 𝑥 = 1, 𝑦, 𝑧 + 𝑥 ′ 𝑓(𝑥 = 0, 𝑦, 𝑧)

𝑓 𝑥, 𝑦 = (𝑥 + 𝑓 𝑥 =? , 𝑦 )(𝑥 ′ + 𝑓 𝑥 =?′ , 𝑦 )
• A. ?=0
• B. ?=1.

<31>
 Shannon’s Expansion
• Decompose the switching function into minterms
𝑓 𝑥, 𝑦 = 𝑥𝑓 1, 𝑦 + 𝑥 ′ 𝑓 0, 𝑦
= 𝑥 𝑦𝑓 1,1 + 𝑦 ′ 𝑓 1,0 + 𝑥′(𝑦 𝑓 0,1 + 𝑦 ′ 𝑓 0,0
= 𝑥𝑦𝑓 1,1 + 𝑥𝑦 ′ 𝑓 1,0 + 𝑥 ′ 𝑦𝑓 0,1 + 𝑥 ′ 𝑦 ′ 𝑓 0,0 .

id x y f(x,y)
0 0 0 f(0,0)
1 0 1 f(0,1)
2 1 0 f(1,0)
3 1 1 f(1,1)

Shannon’s expansion can decompose a switching

function into a truth table.
<32>
 Shannon’s Expansion vs Truth Table
Example: f(x,y)= x+ x’y

𝑓 𝑥, 𝑦 = 𝑥𝑓 1, 𝑦 + 𝑥 ′ 𝑓 0, 𝑦
= 𝑥 𝑦𝑓 1,1 + 𝑦 ′ 𝑓 1,0 + 𝑥′(𝑦 𝑓 0,1 + 𝑦 ′ 𝑓 0,0
= 𝑥𝑦𝑓 1,1 + 𝑥𝑦 ′ 𝑓 1,0 + 𝑥 ′ 𝑦𝑓 0,1 + 𝑥 ′ 𝑦 ′ 𝑓 0,0 .

id x y f(x,y)
0 0 0 f(0,0)
1 0 1 f(0,1)
2 1 0 f(1,0)
3 1 1 f(1,1)

Shannon’s expansion can decompose a switching

function into a truth table.
<33>
 Shannon’s Expansion
• Decompose the switching function into minterms
𝑓 𝑥, 𝑦 = 𝑥𝑓 1, 𝑦 + 𝑥 ′ 𝑓 0, 𝑦
= 𝑥 𝑦𝑓 1,1 + 𝑦 ′ 𝑓 1,0 + 𝑥′(𝑦 𝑓 0,1 + 𝑦 ′ 𝑓 0,0
= 𝑥𝑦𝑓 1,1 + 𝑥𝑦 ′ 𝑓 1,0 + 𝑥 ′ 𝑦𝑓 0,1 + 𝑥 ′ 𝑦 ′ 𝑓 0,0 .
• Decompose the switching function into maxterms
𝑓 𝑥, 𝑦 = (𝑥 ′ + 𝑓 1, 𝑦 ) ∙ (𝑥 + 𝑓 0, 𝑦 )
= (𝑥 ′ + (𝑦 ′ + 𝑓 1,1 ) ∙ 𝑦 + 𝑓 1,0 ) ∙ (𝑥 + 𝑦 ′ + 𝑓 0,1 ∙ 𝑦 + 𝑓 0,0 )
= 𝑥 ′ + 𝑦 ′ + 𝑓 1,1 𝑥 ′ + 𝑦 + 𝑓 1,0 𝑥 + 𝑦 ′ + 𝑓 0,1 𝑥 + 𝑦 + 𝑓 0,0

<34>
 Shannon’s Expansion: Example
Which variable in ab’+ac+bc can be used
for expansion?
A. a
B. b
C. c
D. None of the above

<35>
Shannon’s Expansion: Example
F(A,B,C)=AB’+AC+BC

<36>
Remark: The choice of the variable for
expansion is a nontrivial question.
<37>
 Review Summary: Switching Algebra
and Karnaugh Map
Shannon’s expansion and consensus theorem
are used for logic optimization
• Shannon’s expansion divides the problem into
smaller functions
• Consensus theorem finds common terms when we
merge small functions
• Karnaugh map mimics the above two operations in
two dimensional space as a visual aid.

<38>
 Part I. Combinational Logic
II) Specification
1. Language
2. Boolean Algebra
Canonical Expression: Sum of minterms and
Product of maxterms
3. Truth Table: minterms and maxterms
4. Incompletely Specified Function

39
II. Specification (use addition as an example)
Decimal Addition 5
+ 7
12
Carry Sum

Binary Addition 1 1 1 Carry bits

1 0 1 5
+ 1 1 1 7
12
1 1 0 0
Carryout Sums

40
II. Specification (use addition as an example)
Decimal Addition

Binary Addition

41
II. Specification (use addition as an example)

AB AB AB AB
Couta Cin Couta Cin Couta Cin Couta Cin

S S S S

42
 Binary Addition: Hardware
• Half Adder: Two inputs (a,b) and two
outputs (carry, sum).

• Full Adder: Three inputs (a,b,cin) and two

outputs (carry, sum).

43
 Half Adder
Truth Table

id a b carry sum
a 0 0 0 0 0
1 0 1 0 1
Sum 2 1 0 0 1
b 3 1 1 1 0
Carry

44
Switching Function
Switching Expressions:
Sum (a,b) = a’·b + a·b’
Carry (a, b) = a·b
Ex:
Sum (0,0) = 0’·0 + 0·0’ = 0 + 0 = 0
Sum (0,1) = 0’·1 + 0·1’ = 1 + 0 = 1
Sum (1,1) = 1’·1 + 1·1’ = 0 + 0 = 0

a
a
sum carry
b
b

45
 BSV notes
function Bit#(2) ha(Bit#(1) a, Bit#(1) b);
Bit#(1) s = (~a & b) | (a & ~b);
Bit#(1) c = a & b;
return {c,s};
endfunction

• {c, s} represents bit concatenation

CSE 140L W2017 L01-46

 Full Adder
id a b cin cout sum
0 0 0 0 0 0
cin 1 0 0 1 0 1
a 2 0 1 0 0 1
3 0 1 1 1 0
sum
4 1 0 0 0 1
b
5 1 0 1 1 0
cout
6 1 1 0 1 0
Arithmetic: 7 1 1 1 1 1
2cout+sum=a+b+cin
47
 Minterms
A product of all variables in the function.
A minterm is equal to 1 on exactly one row of the truth table.

id a b c carry sum
0 0 0 0 0 0
1 0 0 1 0 a’b’c
2 0 1 0 0 a’bc’
3 0 1 1 a’bc 0
4 1 0 0 0 ab’c’
5 1 0 1 ab’c 0
6 1 1 0 abc’ 0
7 1 1 1 abc abc 48
 Maxterms
A sum of all variables in the function.
A maxterm is equal to 0 on exactly one row of the truth table.

id a b c carry sum
0 0 0 0 a+b+c a+b+c
1 0 0 1 a+b+c’ 1
2 0 1 0 a+b’+c 1
3 0 1 1 1 a+b’+c’
4 1 0 0 a’+b+c 1
5 1 0 1 1 a’+b+c’
6 1 1 0 1 a’+b’+c
7 1 1 1 1 1 49
 Minterms and Maxterms
id a b c minterm maxterm
Minterms cover all
0 0 0 0 m0=a’b’c’ M0=a+b+c
the outputs which
1 0 0 1 m1=a’b’c M1=a+b+c’ are true (1).
Maxterms cover all
2 0 1 0 m2=a’bc’ M2=a+b’+c the outputs which
are false (0).
3 0 1 1 m3=a’bc M3=a+b’+c’

4 1 0 0 m4=ab’c’ M4=a’+b+c
5 1 0 1 m5=ab’c M5=a’+b+c’

6 1 1 0 m6=abc’ M6=a’+b’+c

7 1 1 1 m7=abc M7=a’+b’+c’
50
Minterms
f1(a,b,c) = a’bc + ab’c + abc’ + abc

a’bc = 1 iff (a,b,c,) = (0,1,1)

ab’c = 1 iff (a,b,c,) = (1,0,1)
abc’ = 1 iff (a,b,c,) = (1,1,0)
abc = 1 iff (a,b,c,) = (1,1,1)
f1(a,b,c) = 1 iff (a,b,c) = (0,1,1), (1,0,1), (1,1,0), or (1,1,1)

Ex: f1(1,0,1) = 1’01 + 10’1 + 101’ + 101 = 1

f1(1,0,0) = 1’00 + 10’0 + 100’ + 100 = 0

51
Maxterms
f2(a,b,c) = (a+b+c)(a+b+c’)(a+b’+c)(a’+b+c)

a + b + c = 0 iff (a,b,c,) = (0,0,0)

a + b + c’ = 0 iff (a,b,c,) = (0,0,1)
a + b’ + c = 0 iff (a,b,c,) = (0,1,0)
a’ + b + c = 0 iff (a,b,c,) = (1,0,0)
f2(a,b,c) = 0 iff (a,b,c) = (0,0,0), (0,0,1), (0,1,0), (1,0,0)

Ex: f2(1,0,1) = (1+0+1)(1+0+1’)(1+0’+1)(1’+0+1) = 1

f2(0,1,0) = (0+1+0)(0+1+0’)(0+1’+0)(0’+1+0) = 0

52
f1(a,b,c) = a’bc + ab’c + abc’ + abc
f2(a,b,c) = (a+b+c)(a+b+c’)(a+b’+c)(a’+b+c)
f1(a, b, c) = m3 + m5 + m6 + m7 = Sm(3,5,6,7)
f2(a, b, c) = M0M1M2M4 = PM(0, 1, 2, 4)

Does f1 = f2?
A. Yes
B. No.

53
The coverage of a single minterm. e.g. m4 = ab’c’

Id a b cin carry minterm 4 = ab’c’

0 0 0 0 0 0
1 0 0 1 0 0
2 0 1 0 0 0
3 0 1 1 1 0
4 1 0 0 0 1
5 1 0 1 1 0
6 1 1 0 1 0
7 1 1 1 1 0

Only one row has a 1.

54
The coverage of a single maxterm. E.g. M4 = a’+b+c

Id a b cin carry maxterm 4 = a+b+c

0 0 0 0 0 1
1 0 0 1 0 1
2 0 1 0 0 1
3 0 1 1 1 1
4 1 0 0 0 0
5 1 0 1 1 1
6 1 1 0 1 1
7 1 1 1 1 1

Only one row has a 0.

55
Minterms and Maxterms: Summary

f1(a,b,c) = a’bc + ab’c + abc’ + abc

f2(a,b,c) = (a+b+c)(a+b+c’)(a+b’+c)(a’+b+c)

Canonical presentation of logic functions

Conversion between truth tables and switching functions

56
 Incompletely Specified Function
Don’t care set is important because it allows us to
minimize the function
Id a b f (a, b)
1) The input does not
0 0 0 1 happen.
1 0 1 0
2 1 0 1 2) The input happens, but
3 1 1 - the output is ignored.

Examples:
-Decimal number 0… 9 uses 4 bits. (1,1,1,1) does not happen.
-Final carry out bit (output is ignored).

57
 Incompletely Specified Function
g1(a,b,c)=a’b’c+a’bc+ab’c’+abc
id a b c g =m1+m3+m4+m7
0 0 0 0 0 =∑ m(1,3,4,7)

1 0 0 1 1 g2(a,b,c)=(a+b+c)(a’+b’+c)
=M0M6
2 0 1 0 - =∏M(0,6)
3 0 1 1 1
4 1 0 0 1
5 1 0 1 -
6 1 1 0 0
7 1 1 1 1 59
 Incompletely Specified Function
g1(a,b,c)=∑ m(1,3,4,7)
id a b c g g2(a,b,c)=∏M(0,6)
0 0 0 0 0
1 0 0 1 1 Does g1(a,b,c) = g2(a,b,c)?
A: Yes
2 0 1 0 - B: No
3 0 1 1 1
4 1 0 0 1
5 1 0 1 -
6 1 1 0 0
7 1 1 1 1 60