228
CHAPTER 4 Functions
P qp(qr
r
-
p -
-qAr
(p A qA r)
r
L~g•
v(pA-.qA r)
-----pAqA- r
V(pA-qA-r)
r - .(
P-P __)
P
Vp
~
v(-~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 convenience 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.