Discrete Mathematics for Computer Science

Basic Definitions 227

Theorem 1. Let F and G be functions such that F = G. Then,

domain(F) = domain(G)

range(F) = range(G)

and, for each x E domain(F), F(x) = G(x).

Some authors would insist that for two functions to be equal, their codomains must

also be the same. We do not insist on that condition for the equality of two functions.

Boolean Functions and Combinatorial Networks

A boolean function of n boolean variables is a function of the form

B :{0, 1} x {0, 1} x ... x {0, 1) --* {0, 11

The domain of B contains 2n elements. A value of either 0 or 1 is assigned to each entry

of the 2' ordered n-tuples. An example of a boolean function on three boolean variables is

shown in Table 4.1.

Table 4.1 Boolean

Function of Three

Variables

p q r F(p, q, r)

1 1 1 1

1 1 0 0

1 0 1 1

1 0 0 1

(^0 1 1 1)
0 1 0 1
0 0 1 0
0r0 0 1
This function might represent a set of switches that react in an appropriate way or a
set of conditions that must be satisfied so that some action can be taken. It is useful to
be able to represent functions as in Table 4.1, but the real problem is often to embed this
function in a combinatorial network. We saw in Chapter 2, while discussing disjunctive
normal forms and conjunctive normal forms, how we can draw the combinatorial circuit
given one of these normal forms. In this case, we need to see how to represent a function
in terms of one of these normal forms.
For the function in Table 4.1, a disjunctive normal form is

F(p, q, r) = (p A q A r) V (p A -q A r) V (p A -q A -r)

V (-p A q A r) V (-p A q A -'r) V (-p A -q A -'r)

Consequently, the combinatorial circuit is the circuit shown in Figure 4.5.