A boolean variable assumes the value 0 or 1. A boolean function is a function f : B n ~ B, where B n = B • B x ... x B, the cartesian product of B with itself to n factors. Let (xl,x2,... ,Xn) ~ B n. Then the value of the boolean function f at (Xl,X2,... ,xn) is denoted by f ( x l , x 2 , . . . ,Xn), although technically it should be f ( ( x l , x 2 , . . . ,Xn)). Since codom(f) - B, the value of the boolean function for any input value (Xl,X2,... ,Xn) is either 0 or 1. [Recall that codom(f) denotes the codomain of the function.]
Boolean functions can be defined by logic tables. Tables 12.1 and 12.2 define two boolean functions from B 2 to B. The value f(x,y) is given for
every combination of values of x and y. (Notice the similarity between these tables and the truth tables for the disjunction and conjunction of two propositions.)
Boolean functions can also be defined by boolean expressions made up
of boolean variables and boolean operators. For instance, if x, y, and z are
boolean variables, then xy, (xy)',x +yz, andx +(xy)' are boolean expressions.
Next we define a boolean expression recursively.
A Recursive Definition of a Boolean Expression
Let x1,x2,... ,xn be n boolean variables. Then:
■ Basis clause 0, 1, x l , x 2 , . . . ,Xn are boolean expressions.
■ Recursive clause If E1 and E2 are boolean expressions, then so are
(E1),E'1,E1E2, and E1 + E2.
(The symbols 0 and 1 denote bits. Parentheses are dropped when no confusion results.)
Equality of Boolean Expressions
Two boolean expressions E1 (x1, x2, .. 9 ,xn) and E 2 ( x 1 , x 2 , . . . ,xn) are equal,
denoted by E1 ( x 1 , x2 , . . . , xn) = E2(xl,x2,... ,xn), if they yield the same
value for all (x1, x2,..., Xn) in B n .
When the boolean expressions E1 and E2 are fairly simple, logic tables can
determine if they are equal. This procedure is quite similar to verifying the logical
equivalence of two compound statements, as the next example illustrates.