 4.1.1: Let S = {2, 5, 17, 27}. Which of the following expressions are true...
 4.1.2: Let B = {x 0 x [ and 1 < x < 2}. Which of the following expressions...
 4.1.3: How many different sets are described here? What are they? {2, 3, 4...
 4.1.4: How many different sets are described here? What are they? {x 0 x =...
 4.1.5: Describe each of the following sets by listing its elements: a. {x ...
 4.1.6: Describe each of the following sets by listing its elements: a. {x ...
 4.1.7: Describe each of the following sets by giving a characterizing prop...
 4.1.8: Describe each of the following sets: a {x 0 x [ and (Eq)(q [ {2, 3}...
 4.1.9: Given the description of a set A as A = {2, 4, 8 }, do you think 16...
 4.1.10: What is the cardinality of each of the following sets? a. S = {a, {...
 4.1.11: Let A = {2, 5, 7} B = {1, 2, 4, 7, 8} C = {7, 8} Which of the follo...
 4.1.12: Let A = {x 0 x [ and 1 < x < 50} B = {x 0 x [ and 1 < x < 50} C = {...
 4.1.13: Let R = {1, 3, , 4.1, 9, 10} T = {1, 3, } S = {{1}, 3, 9, 10} U = {...
 4.1.14: Let R = {1, 3, , 4.1, 9, 10} T = {1, 3, } S = {{1}, 3, 9, 10} U = {...
 4.1.15: Let A = {a, {a}, {{a}}} B = {a} C = {[, {a, {a}}} Which of the foll...
 4.1.16: Let A = {[, {[, {[}}} B = [ C = {[} D = {[, {[}} Which of the follo...
 4.1.17: Let A = {(x, y) 0 (x, y) lies within 3 units of the point (1, 4)} a...
 4.1.18: Let A = {x 0 x [ and x2 4x + 3 < 0} and B = {x 0 x [ and 0 < x < 6}...
 4.1.19: Program QUAD finds and prints solutions to quadratic equations of t...
 4.1.20: Let A = {x 0 cos(x/2) = 0} and B ={x 0 sin x = 0}. Prove that A # B.
 4.1.21: Which of the following statements are true for all sets A, B, and C...
 4.1.22: Which of the following statements are true for all sets A, B, and C...
 4.1.23: Prove that if A # B and B # C, then A # C
 4.1.24: Prove that if A # B, then B # A.
 4.1.25: Prove that for any integer n 2, a set with n elements has n(n 1)/2 ...
 4.1.26: Prove that for any integer n 3, a set with n elements has n(n 1)(n ...
 4.1.27: Find (S) for S = {a}.
 4.1.28: Find (S) for S = {a, b}.
 4.1.29: Find (S) for S = {1, 2, 3, 4}. How many elements do you expect this...
 4.1.30: Find (S) for S = {[}.
 4.1.31: Find (S) for S = {[, {[}, {[, {[}}}
 4.1.32: Find ((S)) for S = {a, b}.
 4.1.33: What can be said about A if (A) = {[, {x}, {y}, {x, y}}?
 4.1.34: What can be said about A if (A) = {[, {a}, {{a}}}?
 4.1.35: Prove that if (A) = (B), then A = B.
 4.1.36: Prove that if A # B, then (A) # (B).
 4.1.37: Solve for x and y. a. (y, x + 2) = (5, 3) b. (2x, y) = (16, 7) c. (...
 4.1.38: a. Recall that ordered pairs must have the property that (x, y) = (...
 4.1.39: Which of the following candidates are binary or unary operations on...
 4.1.40: Which of the following candidates are binary or unary operations on...
 4.1.41: Which of the following candidates are binary or unary operations on...
 4.1.42: Which of the following candidates are binary or unary operations on...
 4.1.43: How many different unary operations can be defined on a set with n ...
 4.1.44: How many different binary operations can be defined on a set with n...
 4.1.45: We have written binary operations in infix notation, where the oper...
 4.1.46: Evaluate the following postfix expressions (see Exercise 45): a 2 4...
 4.1.47: Let A = { p, q, r, s} B = {r, t, v} C = { p, s, t, u} be subsets of...
 4.1.48: Let A = { p, q, r, s} B = {r, t, v} C = { p, s, t, u} be subsets of...
 4.1.49: Let A = {2, 4, 5, 6, 8} B = {1, 4, 5, 9} C = {x 0 x [ and 2 x < 5} ...
 4.1.50: Let A = {2, 4, 5, 6, 8} B = {1, 4, 5, 9} C = {x 0 x [ and 2 x < 5} ...
 4.1.51: Let A = {a, {a}, {{a}}} B = {[, {a}, {a, {a}}} C = {a} be subsets o...
 4.1.52: Let A = {x 0 x is the name of a former president of the United Stat...
 4.1.53: Let S = A B where A = {2, 3, 4} and B = {3, 5}. Which of the follow...
 4.1.54: Let A = {x 0 x is a word that appears before dog in an English lang...
 4.1.55: Consider the following subsets of : A = {x 0 (E y)( y [ and y 4 and...
 4.1.56: Let A = {x 0 x [ and 1 < x 3} B = {x 0 x [ and 2 x 5} Using set ope...
 4.1.57: Consider the following subsets of the set of all students: A = set ...
 4.1.58: Consider the following subsets of the set of all students: A = set ...
 4.1.59: Write the set expression for the desired results of the Web search ...
 4.1.60: Write the set expression for the desired results of the Web search ...
 4.1.61: Write the set expression for the desired results of the Web search ...
 4.1.62: Write the set expression for the desired results of the Web search ...
 4.1.63: Which of the following statements are true for all sets A, B, and C...
 4.1.64: Which of the following statements are true for all sets A, B, and C...
 4.1.65: Which of the following statements are true for all sets A, B, and C...
 4.1.66: Which of the following statements are true for all sets A, B, and C...
 4.1.67: For each of the following statements, find general conditions on se...
 4.1.68: For any finite set S, 0 S 0 denotes the number of elements in S. If...
 4.1.69: Prove that (A d B) # A where A and B are arbitrary sets.
 4.1.70: Prove that A # (A c B) where A and B are arbitrary sets.
 4.1.71: Prove that (A) d (B) = (A d B) where A and B are arbitrary sets.
 4.1.72: Prove that (A) c (B) # (A c B) where A and B are arbitrary sets
 4.1.73: Prove that if A c B = A B, then B = [. (Hint: Do a proof by contrad...
 4.1.74: Prove that if (A B) c (B A) = A c B, then A d B = [. (Hint: Do a pr...
 4.1.75: Prove that if C # B A, then A d C = [.
 4.1.76: Prove that if (A B) c B = A, then B # A.
 4.1.77: Prove that A # B if and only if A d B = [.
 4.1.78: Prove that (A d B) c C = A d (B c C ) if and only if C # A
 4.1.79: a. Draw a Venn diagram to illustrate A ! B. b. For A = {3, 5, 7, 9}...
 4.1.80: a. For an arbitrary set A, what is A ! A? What is [ ! A? b. Prove t...
 4.1.81: Verify the basic set identities on page 234 by showing set inclusio...
 4.1.82: A and B are subsets of a set S. Prove the following set identities ...
 4.1.83: A, B, and C are subsets of a set S. Prove the following set identit...
 4.1.84: A is a subset of a set S. Prove the following set identities: a. A ...
 4.1.85: A, B, and C are subsets of a set S. Prove the following set identit...
 4.1.86: A, B, and C are subsets of a set S. Prove the following set identit...
 4.1.87: The operation of set union can be defined as an nary operation for...
 4.1.88: Using the recursive definition of set union from Exercise 87(b), pr...
 4.1.89: The operation of set intersection can be defined as an nary operat...
 4.1.90: Using the recursive definition of set intersection from Exercise 89...
 4.1.91: Prove that for subsets A1, A2, , An and B of a set S, the following...
 4.1.92: Prove that for subsets A1, A2, , An of a set S, the following gener...
 4.1.93: The operations of set union and set intersection can be extended to...
 4.1.94: According to our use of the word set, if C is a subset of the unive...
 4.1.95: The principle of wellordering says that every nonempty set of posi...
 4.1.96: Prove that the principle of wellordering (see Exercise 95) implies...
 4.1.97: Prove that the set of odd positive integers is denumerable.
 4.1.98: Prove that the set of all integers is denumerable.
 4.1.99: Prove that the set of all finitelength strings of the letter a is ...
 4.1.100: Prove that the set of all finitelength binary strings is denumerable.
 4.1.101: Prove that the set is denumerable.
 4.1.102: In Example 23, the claim was made that 0.249999999 is the same numb...
 4.1.103: Use Cantors diagonalization method to show that the set of all infi...
 4.1.104: Use Cantors diagonalization method to show that the set of all infi...
 4.1.105: Explain why the union of any two denumerable sets is denumerable.
 4.1.106: Explain why any subset of a countable set is countable
 4.1.107: Sets can have sets as elements (see Exercise 13, for example). Let ...
Solutions for Chapter 4.1: Sets
Full solutions for Mathematical Structures for Computer Science  7th Edition
ISBN: 9781429215107
Solutions for Chapter 4.1: Sets
Get Full SolutionsSince 107 problems in chapter 4.1: Sets have been answered, more than 9421 students have viewed full stepbystep solutions from this chapter. Chapter 4.1: Sets includes 107 full stepbystep solutions. 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. Mathematical Structures for Computer Science was written by and is associated to the ISBN: 9781429215107.

Adjacency matrix of a graph.
Square matrix with aij = 1 when there is an edge from node i to node j; otherwise aij = O. A = AT when edges go both ways (undirected). Adjacency matrix of a graph. Square matrix with aij = 1 when there is an edge from node i to node j; otherwise aij = O. A = AT when edges go both ways (undirected).

Associative Law (AB)C = A(BC).
Parentheses can be removed to leave ABC.

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.

Circulant matrix C.
Constant diagonals wrap around as in cyclic shift S. Every circulant is Col + CIS + ... + Cn_lSn  l . Cx = convolution c * x. Eigenvectors in 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).

Factorization
A = L U. If elimination takes A to U without row exchanges, then the lower triangular L with multipliers eij (and eii = 1) brings U back to A.

Hermitian matrix A H = AT = A.
Complex analog a j i = aU of a symmetric matrix.

Hypercube matrix pl.
Row n + 1 counts corners, edges, faces, ... of a cube in Rn.

Iterative method.
A sequence of steps intended to approach the desired solution.

Jordan form 1 = M 1 AM.
If A has s independent eigenvectors, its "generalized" eigenvector matrix M gives 1 = diag(lt, ... , 1s). The block his Akh +Nk where Nk has 1 's on diagonall. Each block has one eigenvalue Ak and one eigenvector.

Kronecker product (tensor product) A ® B.
Blocks aij B, eigenvalues Ap(A)Aq(B).

Linearly dependent VI, ... , Vn.
A combination other than all Ci = 0 gives L Ci Vi = O.

Markov matrix M.
All mij > 0 and each column sum is 1. Largest eigenvalue A = 1. If mij > 0, the columns of Mk approach the steady state eigenvector M s = s > O.

Multiplier eij.
The pivot row j is multiplied by eij and subtracted from row i to eliminate the i, j entry: eij = (entry to eliminate) / (jth pivot).

Projection p = a(aTblaTa) onto the line through a.
P = aaT laTa has rank l.

Reflection matrix (Householder) Q = I 2uuT.
Unit vector u is reflected to Qu = u. All x intheplanemirroruTx = o have Qx = x. Notice QT = Q1 = Q.

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

Special solutions to As = O.
One free variable is Si = 1, other free variables = o.

Symmetric matrix A.
The transpose is AT = A, and aU = a ji. AI is also symmetric.

Vandermonde matrix V.
V c = b gives coefficients of p(x) = Co + ... + Cn_IXn 1 with P(Xi) = bi. Vij = (Xi)jI and det V = product of (Xk  Xi) for k > i.