ECE 2372 Section 2.2

```ECE 2372
Modern Digital System Design
Section 2.2
Boolean Functions
1
Boolean Functions
• A function in numerical algebra is an operation that
results in an output value for each input value.
y
f (x )
x
2
Boolean Functions
• In like manner a Boolean function is an operation that
results in a logical value (0 or 1) for each set of input logical
values (0 or 1).
x = {0,1}
f (x)
{0,1}
3
Boolean Functions
• Consider the function of n variables:
f (x 1 , x 2 , ... x n )
E ach of the variables x i m ay take on
the value 0 or 1
T he function f (x 1 , x 2 , ... x n ) m ay take
on the value 0 or 1
So there are 2
2
n
different switching functions of n variables.
4
Boolean Functions
1
For o n e variab le (n = 1 ) th er e ar e 2
2
= 4 fu n ction s,
th ey are
f 0 (x) = 0
f 1 (x) = x
–
f 2 (x) = x
f 3 (x) = 1
5
Boolean Functions
2
2
For two variables (n = 2) there are 2 = 16 functions, they are
ab
00
01
10
11
f0
0
0
0
0
f1
1
0
0
0
f2
0
1
0
0
f3
1
1
0
0
f4
0
0
1
0
f5
1
0
1
0
f6
0
1
1
0
f7
1
1
1
0
f8
0
0
0
1
f9
1
0
0
1
f10
0
1
0
1
f11
1
1
0
1
f12
0
0
1
1
f13
1
0
1
1
f14
0
1
1
1
f15
1
1
1
1
6
Boolean Functions
• These functions may be written out algebraically:
ab
00
01
10
11
f0
0
0
0
0
f1
1
0
0
0
f2
0
1
0
0
f3
1
1
0
0
f4
0
0
1
0
f5
1
0
1
0
f6
0
1
1
0
f7
1
1
1
0
f8
0
0
0
1
f9
1
0
0
1
f10
0
1
0
1
f11
1
1
0
1
f12
0
0
1
1
f13
1
0
1
1
f14
0
1
1
1
f15
1
1
1
1
f0(a, b) = 0
–
–
f1(a, b) = a b
f2(a, b) = –
ab
– –
–
–
f3(a, b) = a b + a b = a
7
Boolean Functions
• These functions may be written out algebraically:
ab
00
01
10
11
f0
0
0
0
0
f1
1
0
0
0
f2
0
1
0
0
f3
1
1
0
0
f4
0
0
1
0
f5
1
0
1
0
f6
0
1
1
0
f7
1
1
1
0
f8
0
0
0
1
f9
1
0
0
1
f10
0
1
0
1
f11
1
1
0
1
f12
0
0
1
1
f13
1
0
1
1
f14
0
1
1
1
f15
1
1
1
1
–
f4(a, b) = a b
– –– –
f5(a, b) = a b + a b = b
– –
f6(a, b) = a b + a b
– –
– – –
–
f7(a, b) = a b + a b + a b = a + b
8
Boolean Functions
• These functions may be written out algebraically:
ab
00
01
10
11
f0
0
0
0
0
f1
1
0
0
0
f2
0
1
0
0
f3
1
1
0
0
f4
0
0
1
0
f5
1
0
1
0
f6
0
1
1
0
f7
1
1
1
0
f8
0
0
0
1
f9
1
0
0
1
f10
0
1
0
1
f11
1
1
0
1
f12
0
0
1
1
f13
1
0
1
1
f14
0
1
1
1
f15
1
1
1
1
f8(a, b) = a b
––
f9(a, b) = a b + a b
f10(a, b) = a b + –a b = b
–
–– –
f11(a, b) = a b + a b + a b = a + b
9
Boolean Functions
• These functions may be written out algebraically:
ab
00
01
10
11
f0
0
0
0
0
f1
1
0
0
0
f2
0
1
0
0
f3
1
1
0
0
f4
0
0
1
0
f5
1
0
1
0
f6
0
1
1
0
f7
1
1
1
0
f8
0
0
0
1
f9
1
0
0
1
f10
0
1
0
1
f11
1
1
0
1
f12
0
0
1
1
f13
1
0
1
1
f14
0
1
1
1
f15
1
1
1
1
–
f12(a, b) = a b + a b = a
– ––
–
f13(a, b) = a b + a b + a b = a + b
– –
f14(a, b) = a b + a b + a b = a + b
– –
–
–
f (a, b) = a b + a b + a b + a b = 1
15
10
Boolean Functions
• Truth Tables may be used to define switching functions:
11
Boolean Functions
–
–
–
Example f (x, y, z) = x z + x y z + y z
xyz
000
001
010
011
100
101
110
111
–
x
1
1
1
1
0
0
0
0
–
y
1
1
0
0
1
1
0
0
–
z
1
0
1
0
1
0
1
0
–
xz
0
1
0
1
0
0
0
0
–
xy z
0
0
0
0
0
1
0
0
–
yz
0
0
1
0
0
0
1
0
f (xyz)
0
1
1
1
0
1
1
0
12
Algebraic Forms of Switching Functions
• "Sum-of-Products" (SOP) Form: (Not really the sum of
products, but it resembles a sum of products).
• Example:
“S um ”
_
__
_ _
f (a,b,c,d) = ab c + b d + a cd
“P roducts”
13
Algebraic Forms of Switching Functions
• "Product-of-Sums" (POS) Form: (Not really the product
of sums, but it resembles a product of sums).
• Example:
P roduct
_
_ _ _
_
f (a,b,c,d) = ( a + b + c )( b + d )( a + c + d )
S um s
14
Algebraic Forms of Switching Functions
• Canonical Forms are SOP or POS forms with special
characteristics.
• Minterms: Given a function of n variables, if a product
term (in the SOP form) contains each variable exactly once
(in complemented or uncomplemented form), the product is
called a minterm.
_
_
f (a ,b ,c ) = a b c + a b c + a b c + b c
m interm
not a m interm
15
Algebraic Forms of Switching Functions
• If a function contains only minterms, it is said to be in
Canonical (or Standard) SOP form.
• A function may be expanded to Canonical SOP form.
f (a , b , c)
=
=
=
=
–
abc
–
abc
–
abc
–
abc
–
+ abc +abc + bc
–
–
+ a b c + a b c + (a + a )b c
–
–
+ ab c +abc + abc + abc
–
–
+ abc +abc + abc
(Stan dard S O P F orm )
16
Algebraic Forms of Switching Functions
–
–
f (a , b , c ) = (a b + c )(a + b + c)
–
–– –
–
= a a b + a bb + a b c + a c + b c + c c
_
––
= ab + a0 + abc + ac + cb + 0
– –
–
– ––
= a b (c + c ) + a b c + a (b + b ) c + (a + a )b c
––
–– –– –
–
–
= abc + abc + abc + ab c + ab c + ab c + ab c
– – –– –
–
= abc + abc +ab c + ab c
(Sta n da r d S O P F or m )
• The switching function may be verified with a truth table.
17
Algebraic Forms of Switching Functions
–
–
f (a , b , c ) = (a b + c )(a + b + c )
a bc
–
ab + c
–
a+b+ c
f (a , b, c)
000
1
1
1
001
0
1
0
1
010
1
0
0
2
011
0
1
0
3
S O P Term
–––
ab c
––
ab c
R ow
0
100
1
1
1
4
101
0
1
0
110
1
1
1
–
ab c
6
111
1
1
1
a bc
7
5
18
Algebraic Forms of Switching Functions
_
–– –––
T his fu n ctio n f (a , b , c ) = a b c + a b c + a b c + a b c
m a y b e ta bu la te d
m inter m
– ––
ab c
––
ab c
–
abc
m inter m c od e
m inter m nu m b er
000
m0
100
m4
110
m6
abc
111
m7
19
Algebraic Forms of Switching Functions
–– – – –
–
T he f (a , b , c ) = a b c + a b c + a b c + a b c
m a y b e w ritte n
f  (a , b , c ) = m 0 + m 4 + m 6 + m 7
or
f  (a , b , c ) =

m (0 , 4 , 6 , 7 ) ( m inter m L ist F or m )
20
Algebraic Forms of Switching Functions
T he C a no nica l F or m o f th e sw itch in g fu nc tion is
f  (a , b , c ) =
m0 + m4 + m6 + m7
(0 0 0 ) (1 0 0 ) (11 0 ) (1 1 1 )
––
–––
–
= a b c + a b c + a bc + a b c
N ote: T h e ord er o f the va ria ble s in f  (a , b , c ) is e sse ntial.
f (a , b , c ) =
f (c , b , a ) =


m (1 , 2 , 6 ) a n d
m (1 , 2 , 6 )
a re tw o differ e nt fu n ction s.
21
T he co m plem ent o f f (a ,b ,c ), tha t is, f (a ,b ,c ) m ay also
be r ead dir ectly fro m the tru th ta ble.
a bc
–
ab + c
–
a+b + c
f (a , b, c)
000
1
1
1
001
0
1
0
1
010
1
0
0
2
011
0
1
0
3
S O P Term
–––
ab c
––
ab c
R ow
0
100
1
1
1
101
0
1
0
110
1
1
1
–
ab c
6
111
1
1
1
a bc
7
f (a ,b ,c ) =

4
5
–
––
– – –
m (1 , 2 , 3 , 5 ) = a b c + a b c + a b c + a b c
22
minterms for three variables
110
Pro du c t
T erm
– – –
x y z
– –
x y z
– –
x y z
–
x yz
– –
x y z
–
x y z
–
xy z
111
xyz
xyz
000
001
010
011
100
101
Sy m bo l
m0
m1
m2
m3
m4
m5
m6
m7
m0
1
0
0
0
0
0
0
0
m1
0
1
0
0
0
0
0
0
m2
0
0
1
0
0
0
0
0
m3
0
0
0
1
0
0
0
0
m4
0
0
0
0
1
0
0
0
m5
0
0
0
0
0
1
0
0
m6
0
0
0
0
0
0
1
0
m7
0
0
0
0
0
0
0
1
23
Algebraic Forms of Switching Functions
• Maxterms: Given a function of n variables, if a sum term
(in the POS form) contains each variable exactly once (in
complemented or uncomplemented form) the sum is called
a Maxterm.
–
–
f (a ,b ,c ) = (a + b + c)(a + b + c )(a + b + c)(b + c)
M axterm
not a M axterm
24
Algebraic Forms of Switching Functions
• If a function contains only Maxterms, it is said to be in
Canonical (or Standard) POS Form.
• A function may be expanded to Canonical POS Form.
f (a , b , c)
= (a +
= (a +
= (a +
–
–
= (a + b + c )(a + b + c )(a + b + c)(b + c )
–
–
–
b + c )(a + b + c )(a + b + c )[a a + (b + c )]
–
–
–
b + c )(a + b + c )(a + b + c )(a + b + c )( a + b + c )
–
–
–
b + c )(a + b + c )(a + b + c )( a + b + c )
(C a no nica l PO S For m )
25
Algebraic Forms of Switching Functions
• A function may expanded to Canonical POS form:
_
f (a, b, c) = ab + ac + abc
_
= a(b + c + bc)
_
= a(b (1 + c) + c )
_
= a(b + c )
26
Algebraic Forms of Switching Functions
• A function may expanded to Canonical POS form:
_
f (a , b , c) = a (b + c )
_
_
–
–
= (a + b b + c c )( a a + b + c )
_
_
_
–
–
= ((a + b )(a + b ) + c c ) (a + b + c )(a + b + c )
_
_
_
_
–
–
= (a + b + c c )(a + b + c c ) (a + b + c )(a + b + c )
– –
–
–
= (a + b + c)(a + b + c )(a + b + c)(a + b + c )
_
_
–
(a + b + c )( a + b + c )
_
– – –
–
–
= (a + b + c)(a + b + c )(a + b + c)(a + b + c )( a + b + c )
27
• The switching function may be verified with a truth table.
–
f (a , b , c ) = a b + a c + a b c
abc
000
001
010
011
100
101
110
111
ab
0
0
0
0
0
0
1
1
–
ac
0
0
0
0
1
0
1
0
abc
0
0
0
0
0
0
0
1
f (a , b , c )
0
0
0
0
1
0
1
1
28
• The switching function may be verified with a truth table.
–
– –
–
–
–
f (a , b , c) = (a + b + c)(a + b + c )(a + b + c)(a + b + c )( a + b + c )
abc
000
001
010
011
100
101
110
111
a+ b+ c
0
1
1
1
1
1
1
1
–
a+ b+ c
1
0
1
1
1
1
1
1
–
a+b+ c
1
1
0
1
1
1
1
1
– –
a+b+ c
1
1
1
0
1
1
1
1
–
–
a+ b+ c
1
1
1
1
1
0
1
1
f (a, b, c)
0
0
0
0
1
0
1
1
29
–
– –
–
–
–
f (a , b , c ) = (a + b + c )(a + b + c )(a + b + c )(a + b + c )( a + b + c )
T he M a xter m list fo r m is fou n d b y c od in g th e
U n co m ple m ente d va ria ble: 0
C o m p lem e nte d V a ria ble: 1
M a xter m
M a xter m
C o de
M a xter m L ist
a + b + c
–
a + b + c
–
a + b + c
– –
a + b + c
–
–
a + b + c
000
M0
001
M1
010
M2
011
M3
101
M5
f  (a , b , c ) = M 0 M 1 M 2 M 3 M 5
f  (a , b , c ) =

M (0 , 1 , 2 , 3 , 5 ) M a xter m L ist F or m
30
Algebraic Forms of Switching Functions
• Example
f (a, b, c) =  M(1, 2, 5, 7)
001
010
101
111
–
– –
–
–
–
–
f (a, b, c) = (a + b +c )(a + b +c)( a + b +c )( a + b + c )
which may be demonstrated by the Truth Table
31
Algebraic Forms of Switching Functions
• Example
–
– –
–
–
–
–
f (a, b, c) = (a + b +c )(a + b +c)( a + b +c )( a + b + c )
abc
000
001
010
011
100
101
110
111
a + b +c–
1
0
1
1
1
1
1
1
–
a + b +c
1
1
0
1
1
1
1
1
–
a + b +c–
1
1
1
1
1
0
1
1
– –
–
a+b+c
1
1
1
1
1
1
1
0
f (a, b, c)
1
0
0
1
1
0
1
0
32
Algebraic Forms of Switching Functions
f (a, b, c) =  M(1, 2, 5, 7)
abc
000
001
010
011
100
101
110
111
f (a, b, c)
1
0
0
1
1
0
1
0
Maxterms
M1
M2
M5
M7
The same function may be expressed by it's minterm list, or
f(a, b, c) =  M(1, 2, 5, 7) =  m(0, 3, 4, 6)
33
Maxterms for three variables
xyz
000
001
010
011
100
101
110
111
Su m
T erm
x+ y+ z
–
x+ y+ z
–
x+ y + z
– –
x+ y + z
–
x + y+ z
–
–
x + y+ z
– –
x + y + z
– – –
x + y + z
Sy m bo l
M0
M1
M2
M3
M4
M5
M6
M7
M0
0
1
1
1
1
1
1
1
M1
1
0
1
1
1
1
1
1
M2
1
1
0
1
1
1
1
1
M3
1
1
1
0
1
1
1
1
M4
1
1
1
1
0
1
1
1
M5
1
1
1
1
1
0
1
1
M6
1
1
1
1
1
1
0
1
M7
1
1
1
1
1
1
1
0
34
Algebraic Forms of Switching Functions
f (a , b , c ) =

M (1 , 2 , 5 , 7 )
T he c o m ple m e nt o f this fu n ctio n is
f (a , b , c ) =

m (1 , 2 , 5 , 7 ) = m 1 + m 2 + m 5 + m 7
–
– –
– –
f (a , b , c ) = a b c + a b c + a b c + a b c
so
–
– –
– –
f(a , b , c ) = a b c + a b c + a b c + a b c
a pplyin g D eM or ga n 's T he or e m ( tw ic e)
35
Algebraic Forms of Switching Functions
–
––
– –
f (a , b , c ) = a b c + a b c + a b c + a b c
––
f (a , b , c ) = ( a b c )
| – –
( abc )
–
( abc )
|
( abc )
–
–
–
– – – –
f (a , b , c ) = (a + b + c )(a + b + c )( a + b + c )( a + b + c )
M a xter m s:
f (a , b , c ) =
001

010
M (1 , 2 , 5 , 7 ) =
101

111
m (1 , 2 , 5 , 7 )
36
Algebraic Forms of Switching Functions
W e c o nc lu d e
–
– –
m 1 = |a b c
–
= a + b + c = M1
a nd in g e n era l
—
–
=
m i = M i , and M i = m i = m i
m inter m s a nd M a xter m s a r e c o m ple m e nts.
37
Incompletely Specified Functions:
• On occasion, a switching function may include optional
minterms or Maxterms. These are "don't-care" conditions.
Such conditions may aid in simplifying the functions.
• "Don't-care" conditions occur when not all combinations of
variables are present in a switching function.
38
Incompletely Specified Functions:
• Example:
f (a , b , c) =  m (0 , 3 , 7 ) w ith d (a , b , c) =
––
–
– –– –
= a b c + a b c + a b c + {ab c + a b c}
––
–
– ––
–
= a b c + ( a + a )b c + { a b c + a b c}
––
–
– ––
= a b c + 1 b c + { a b c + a b c}
––
–
– ––
= a b c + b c + { a b c + a b c}

m (4 ,5 )
39
Incompletely Specified Functions:
• A switching function that performs the same action
(although it is not mathematically equivalent) may be
derived by including the first "don't-care" term:
––
– ––
f (a , b , c ) = a b c + b c + a b c
––
–
= ( a + a )b c + b c
––
= 1b c + bc
––
= bc + bc
40
```