640
Boolean Algebra and Computer Logic
ExamplE 8
x 3 , (x 1 + x 2 )′x 3 , (x 1 x 3 + x 4
′) x 2 , and (x 1
′ x 2 )′x 1 are all Boolean expressions.
Truth Functions
DEfinition TruTh FuncTion
A truth function is a function f such that f: 50, 16
n S 50, 16 for some integer
n ≥ 1.
The notation 50, 16
n
denotes the set of all n-tuples of 0s and 1s. A truth
function thus associates a value of 0 or 1 with each such n-tuple.
ExamplE 9
The truth table for the Boolean operation + describes a truth function
f with n = 2. The domain of f is 5(1, 1), (1, 0), (0, 1), (0, 0)6, and
f (1, 1) = 1, f (1, 0) = 1, f (0, 1) = 1, and f (0, 0) = 0. Similarly, the Boolean
operation # describes a different truth function with n = 2, and the Boolean
operation ′ describes a truth function for n = 1.
■
Practice 8
a. If we are writing a truth function f: 50, 16
n S 50, 16 in tabular form (like a truth table),
how many rows will the table have?
b. How many different truth functions are there that take 50, 16
2 S 50, 16?
c. How many different truth functions are there that take 50, 16
n S 50, 16?
Any Boolean expression defines a unique truth function, just as do the simple Boolean expressions x 1 + x 2 , x 1 x 2 , and x 1
′.
ExamplE 10
The Boolean expression x 1 x 2
′ + x 3 defines the truth function given in Table 8.3.
(This is just like doing the truth tables of Section 1.1.)
tablE 8.3
x 1
x 2
x 3
x 1 x 2
′ + x 3
1
1
1
1
1
1
0
0
1
0
1
1
1
0
0
1
0
1
1
1
0
1
0
0
0
0
1
1
0
0
0
0