Discrete Mathematics for Computer Science

228 CHAPTER 4 Functions

Pqp(qr

r -

p - -qAr (p A qA r)

r L~g• v(pA-.qA r)

------ pAqA- r V(pA-qA-r)

P r -.( -P __) ~ Vp v(-~p P- AqA-)

q -

r ~V (-.p AqAr)

-p

q ",E-pAqA r

q -.

Figure 4.5 Combinatorial circuit for F(p, q, r).

Notice in Figure 4.5 that there are several inputs for a gate. This is as much for conve-

nience as for anything else, since we can obviously write a gate with three inputs as a set

of gates with two inputs each, as shown in Figure 4.6.

p - -- O -

rpAqAr ý

r -*

q ----------

q

:(p Aq) Ar~pA qAr

r

Figure 4.6 Combinatorial circuit for multiple inputs.

4.1.6 Restrictions of Functions

It is easy to write an algorithm to compute SqrR(x) = x^2 for x E R. By merely asserting

that only natural numbers should be used as input, one can make the same algorithm specify

Sqri, a function from N to N. This is an example of restricting a function to a smaller

domain. As usual, the formal definition is set theoretic.

Definition 4. Let A, B, and C be sets such that B C A. Let F : A -+ C be a function.

The restriction of F to B, denoted F I B, is a function from B to C defined as the set

F I B = {(x, y) E F :x B}

Figure 4.7 shows two examples of restrictions of the function Sqri.