4.3. Functions 87
4.3 Functions
4.3.1 Domains and Images
Afunctionassigns an element of one set, called thedomain, to an element of an-
other set, called thecodomain. The notation
f WA!B
indicates thatf is a function with domain,A, and codomain,B. The familiar
notation “f.a/D b” indicates thatf assigns the elementb 2 Btoa. Hereb
would be called thevalueoffatargumenta.
Functions are often defined by formulas, as in:
f 1 .x/WWD
1
x^2
wherexis a real-valued variable, or
f 2 .y;z/WWDy 10 yz
whereyandzrange over binary strings, or
f 3 .x;n/WWDthe lengthnsequence.x;:::;x/
„ ƒ‚ ...
n x’s
wherenranges over the nonnegative integers.
A function with a finite domain could be specified by a table that shows the value
of the function at each element of the domain. For example, a functionf 4 .P;Q/
wherePandQare propositional variables is specified by:
P Q f 4 .P;Q/
T T T
T F F
F T T
F F T
Notice thatf 4 could also have been described by a formula:
f 4 .P;Q/WWDŒP IMPLIESQç:
A function might also be defined by a procedure for computing its value at any
element of its domain, or by some other kind of specification. For example, define
