 5.4.1: The accompanying figure represents a function. 5 6 4 7 8 8 9 10 11 ...
 5.4.2: The accompanying figure illustrates various binary relations from R...
 5.4.3: Using the equation f(x) = 2x 1 to describe the functional associati...
 5.4.4: Using the equation f(x) = x2 + 1 to describe the functional associa...
 5.4.5: If f: Z S Z is defined by f(x) = 3x, find f(A) for a. A = 51, 3, 56...
 5.4.6: If f: R S R is defined by f(x) = x2 , describe a. f(N). b. f(Z). c....
 5.4.7: The function f: 5all English words6 S Z. In each case, find f(S). a...
 5.4.8: The function f : 5binary strings6 S 5binary strings6. In each case,...
 5.4.9: True or false: a. An onto function means that every element in the ...
 5.4.10: True or false: a. If every element in the domain has an image, it m...
 5.4.11: Let S = 50, 2, 4, 66 and T = 51, 3, 5, 76. Determine whether each o...
 5.4.12: For any bijections in Exercise 11, describe the inverse function
 5.4.13: Let S = the set of all U. S. citizens alive today. Which of the fol...
 5.4.14: Let S = the set of people at a meeting, let T = the set of all shoe...
 5.4.15: Which of the following definitions describe functions from the doma...
 5.4.16: Which of the following definitions describe functions from the doma...
 5.4.17: Let f: R S R be defined by f(x) = xn , where n is a fixed, positive...
 5.4.18: Let f: R S R be defined by f(x) = n2x , where n is a fixed, positiv...
 5.4.19: Let A = 5x, y6 and let A* be the set of all strings of finite lengt...
 5.4.20: Let A = 5x, y6 and let A* be the set of all strings of finite lengt...
 5.4.21: Let A = 5x, y6 and let A* be the set of all strings of finite lengt...
 5.4.22: Let A = 5x, y6 and let A* be the set of all strings of finite lengt...
 5.4.23: Let P be the power set of 5a, b, c6. A function f: P S Z is defined...
 5.4.24: Let P be the power set of 5a, b6 and let S be the set of all binary...
 5.4.25: Let S = 5x 0 x [ R and x 16, and T = 5x 0 x [ R and 0 < x 16. Find ...
 5.4.26: Let S = 5a, b, c, d6 and T = 5x, y, z6. a. Give an example of a fun...
 5.4.27: Compute the following values. a. :3.4; b. <0.2= c. :0.5;
 5.4.28: Compute the following values. a. <51. 2= b. <5<1.2= = c. :2 * 3.7; ...
 5.4.29: What can be said about x if :x; =
 5.4.30: Prove that x= + 1 = <x + 1
 5.4.31: Prove that :x; = <x=.
 5.4.32: The ceiling function f(x) =
 5.4.33: Prove or disprove: a. < :x;= = x b. :2x; = 2:x;
 5.4.34: Prove or disprove: a. :x; + : y; = :x + y; b. :2x; = :x; + :x + 12;
 5.4.35: Prove that if 2k < n < 2k+1 then k = :log n; and k + 1 =
 5.4.36: Prove that if 2k n < 2k+1 then :log n; + 1 =
 5.4.37: Compute the value of the following expressions. a. 31 mod 11 b. 16 ...
 5.4.38: a. List five values x such that x mod 7 = 0. b. List five values x ...
 5.4.39: Prove or disprove: For any integers x and y, x mod 10 + y mod 10 = ...
 5.4.40: Prove that x y (mod n) if and only if x mod n = y mod n. (Recall th...
 5.4.41: Let S be a set and let A be a subset of S. The characteristic funct...
 5.4.42: Ackermanns function1 , mapping N2 to N, is a recursive function tha...
 5.4.43: Another rapidly growing function is the Smorynski function, which a...
 5.4.44: The Dwyer function also maps N2 to N and grows very rapidly, but it...
 5.4.45: Let S = 51, 2, 3, 46, T = 51, 2, 3, 4, 5, 66, and U = 56, 7, 8, 9, ...
 5.4.46: a. Let f: R S Z be defined by f(x) = :x;. Let g: Z S N be defined b...
 5.4.47: Let f : N S N be defined by f(x) = x + 1. Let g: N S N be defined b...
 5.4.48: The following functions map R to R. Give an equation describing the...
 5.4.49: Let f : S S T and g: T S U be functions. a. Prove that if g + f is ...
 5.4.50: a. Let f be a function, f : S S T. If there exists a function g: T ...
 5.4.51: For each of the following bijections f: R S R, find f 1 . a. f(x) =...
 5.4.52: Let f and g be bijections, f : S S T and g: T S U. Then f 1 and g1 ...
 5.4.53: Let A = 51, 2, 3, 4, 56. Write each of the following permutations o...
 5.4.54: Let A 5a, b, c, d6. Write each of the following permutations on A i...
 5.4.55: Let A be any set and let SA be the set of all permutations of A. Le...
 5.4.56: Find the composition of the following cycles representing permutati...
 5.4.57: Find the composition of the following cycles representing permutati...
 5.4.58: Find the composition of the following cycles representing permutati...
 5.4.59: Find the composition of the following cycles representing permutati...
 5.4.60: Find a permutation on an infinite set that cannot be written as a c...
 5.4.61: The function f written in cycle form as f = (4, 2, 8, 3) is a bijec...
 5.4.62: The pushdown store, or stack, is a storage structure that operates ...
 5.4.63: Let S = 52, 4, 6, 86 and T = 51, 5, 76. a. Find the number of funct...
 5.4.64: Let S = 5P, Q, R6 and T = 5k, l, m, n6. a. Find the number of funct...
 5.4.65: a. For 0S 0 = 2, 3, and 4, respectively, use the theorem on the num...
 5.4.66: Let A = 5a, b, c, d6. How many functions are in SA? How many of the...
 5.4.67: Let 0S 0 = n. In parts ae, find the number of a. functions from S ...
 5.4.68: a. A system development project calls for five different tasks to b...
 5.4.69: In a programming class of seven students, the instructor wants each...
 5.4.70: a. Find a calculus book and look up the Maclaurin series representa...
 5.4.71: Let f be a function, f : S S T. a. Define a binary relation r on S ...
 5.4.72: Prove that S(m, n), the number of ways to partition a set of m elem...
 5.4.73: By the definition of a function f from S to T, f is a subset of S T...
 5.4.74: Let f be a function, f: S S T. a. Show that for all subsets A and B...
 5.4.75: Let C be a collection of sets, and define a binary relation r on C ...
 5.4.76: Group the following sets into equivalence classes according to the ...
 5.4.77: a. Write a Scheme function to square a number. b. What is the outpu...
 5.4.78: Scheme also supports recursion, plus the usual control structures o...
Solutions for Chapter 5.4: Functions
Full solutions for Mathematical Structures for Computer Science  7th Edition
ISBN: 9781429215107
Solutions for Chapter 5.4: Functions
Get Full SolutionsSince 78 problems in chapter 5.4: Functions have been answered, more than 9349 students have viewed full stepbystep solutions from this chapter. Chapter 5.4: Functions includes 78 full stepbystep solutions. Mathematical Structures for Computer Science was written by and is associated to the ISBN: 9781429215107. This expansive textbook survival guide covers the following chapters and their solutions. This textbook survival guide was created for the textbook: Mathematical Structures for Computer Science, edition: 7.

Affine transformation
Tv = Av + Vo = linear transformation plus shift.

Back substitution.
Upper triangular systems are solved in reverse order Xn to Xl.

Big formula for n by n determinants.
Det(A) is a sum of n! terms. For each term: Multiply one entry from each row and column of A: rows in order 1, ... , nand column order given by a permutation P. Each of the n! P 's has a + or  sign.

Cholesky factorization
A = CTC = (L.J]))(L.J]))T for positive definite A.

Commuting matrices AB = BA.
If diagonalizable, they share n eigenvectors.

Condition number
cond(A) = c(A) = IIAIlIIAIII = amaxlamin. In Ax = b, the relative change Ilox III Ilx II is less than cond(A) times the relative change Ilob III lib IIĀ· Condition numbers measure the sensitivity of the output to change in the input.

Cyclic shift
S. Permutation with S21 = 1, S32 = 1, ... , finally SIn = 1. Its eigenvalues are the nth roots e2lrik/n of 1; eigenvectors are columns of the Fourier matrix F.

Dot product = Inner product x T y = XI Y 1 + ... + Xn Yn.
Complex dot product is x T Y . Perpendicular vectors have x T y = O. (AB)ij = (row i of A)T(column j of B).

Elimination.
A sequence of row operations that reduces A to an upper triangular U or to the reduced form R = rref(A). Then A = LU with multipliers eO in L, or P A = L U with row exchanges in P, or E A = R with an invertible E.

Fundamental Theorem.
The nullspace N (A) and row space C (AT) are orthogonal complements in Rn(perpendicular from Ax = 0 with dimensions rand n  r). Applied to AT, the column space C(A) is the orthogonal complement of N(AT) in Rm.

Hilbert matrix hilb(n).
Entries HU = 1/(i + j 1) = Jd X i 1 xj1dx. Positive definite but extremely small Amin and large condition number: H is illconditioned.

Linear combination cv + d w or L C jV j.
Vector addition and scalar multiplication.

Particular solution x p.
Any solution to Ax = b; often x p has free variables = o.

Pseudoinverse A+ (MoorePenrose inverse).
The n by m matrix that "inverts" A from column space back to row space, with N(A+) = N(AT). A+ A and AA+ are the projection matrices onto the row space and column space. Rank(A +) = rank(A).

Rank r (A)
= number of pivots = dimension of column space = dimension of row space.

Rayleigh quotient q (x) = X T Ax I x T x for symmetric A: Amin < q (x) < Amax.
Those extremes are reached at the eigenvectors x for Amin(A) and Amax(A).

Row picture of Ax = b.
Each equation gives a plane in Rn; the planes intersect at x.

Row space C (AT) = all combinations of rows of A.
Column vectors by convention.

Semidefinite matrix A.
(Positive) semidefinite: all x T Ax > 0, all A > 0; A = any RT R.

Vector v in Rn.
Sequence of n real numbers v = (VI, ... , Vn) = point in Rn.