离散数学习题及答案.pdf

CIS 607: Mathematical Basis for Computing SOLUTIONS OF HOMEWORK 2 Homework 2 Sets, Functions and Relations Due Date: March 9, 2017 In this homework, you will answer the following questions. Prepare a pdf file for your solutions and upload that pdf file into the blackboard system. Q1) a) Find the power set of each of these sets, where a and b are distinct elements. a, b, c PS(a,b,c) = , a,b,c,a,ba,c,b,c,a,b,c , PS(, ) = , , b) Find A3 if A = a. A3 = (a, a, a) A = 0, a. A3 = (0, 0, 0), (0, 0, a), (0, a, 0), (0, a, a), (a, 0, 0), (a, 0, a), (a, a, 0), (a, a, a) c) Cardinalities of Cartesian products. How many different elements does A B have if A has m elements and B has n elements? mn How many different elements does A B C have if A has m elements, B has n elements, and C has p elements? mnp How many different elements does An have when A has m elements and n is a positive integer? mn Q2) a) Let A, B, and C be sets. Show that _ _ _ _ A B C = A B C Suppose that x in the left side. x A B C x A or x B or x C x in the right side. Suppose that x in the right side. x is not in A, or x is not in B or x is not in C. So, x is not in A B C So, x is the left side. (A B) C A C Suppose that x (A B) C. Then x is in AB but not in C. Since x AB, we know that x A. Since we have established that x A but x C, we have proved that x A C. (A C) (C B) = To show that the set given on the left-hand side is empty, it suffices to assume that x is some element in that set and derive a contradiction, thereby showing that no such x exists. So suppose that x (AC) (C B). Then x ay+b=az+b y=z f is one-to-one o f is also onto since y=(x-b)/a for all y in R. f1(x) = (x-b)/a Q5) a) Find the solution to each of these recurrence relations with the given initial conditions. Use an iterative approach. an = an1, a0 = 5 an = an1 n, a0 = 4 a0 an = 2an1 3, a0 = 1 an = 2nan1, a0 = 3 b) A person deposits $1000 in an account that yields 9% interest compounded annually. Set up a recurrence relation for the amount in the account at the end of n years. Find an explicit formula for the amount in the account at the end of n years. How much money will the account contain after 100 years? c) An employee joined a company in 2009 with a starting salary of $50,000. Every year this employee receives a raise of $1000 plus 5% of the salary of the previous year. Set up a recurrence relation for the salary of this employee n years after 2009. What will the salary of this employee be in 2017? Find an explicit formula for the salary of this employee n years after 2009. Q6) a) Determine whether each of these sets is countable or uncountable. For those that are countably infinite, exhibit a one-to-one correspondence between the set of positive integers and that set. integers not divisible by 3 the real numbers with decimal representations consisting of all 1s the real numbers with decimal representations of all 1s or 9s This set is countable but a little tricky. We can arrange the numbers in a 2-dimensional table as follows: Thus we have shown that our set is the countable union of countable sets (each of the countable sets is one row of this table). Therefore, the entire set is countable. For an explicit correspondence with the positive integers, we can zigzag along the positive-sloping diagonals 1 .1, 2 1.1, 3 .1, 4 .11, 5 1, and so on. This set is not countable. We can prove it by the same diagonalization argument as was used to prove that the set of all reals is uncountable. All we need to do is choose di = 1 when dii = 9 and choose di = 9 when dii = 1 or dii is blank (if the decimal expansion is finite). b) Give an example of two uncountable sets A and B such that A B is finite. countably infinite. uncountable. Q7) a) Determine whether the relation R on the set of all real numbers is reflexive, symmetric, antisymmetric, and/or transitive, where (x, y) R if and only if x + y = 0. x = y. x = 2y. xy 0. b) For each of these relations on the set 1, 2, 3, 4, decide whether it is reflexive, whether it is symmetric, whether it is antisymmetric, and whether it is transitive. (2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4) not reflexive ; not symmetric ; not antisymmetric ; transitive (1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4) reflexive ; symmetric ; not antisymmetric ; transitive (2, 4), (4, 2) not reflexive ; symmetric ; not antisymmetric ; not transitive (1, 2), (2, 3), (3, 4) not reflexive ; not symmetric ; antisymmetric ; not transitive c) Write all binary relations on the set A=a,b. Determine which ones are reflexive, symmetric, antisymmetric, transitive and/or functions from A to A. not reflexive ; symmetric ; antisymmetric ; transitive ; not function (a,a) not reflexive ; symmetric ; antisymmetric ; transitive ; not function (a,b) not reflexive ; not symmetric ; antisymmetric ; transitive ; not function (b,a) not reflexive ; not symmetric ; antisymmetric ; transitive ; not function (b,b) not reflexive ; symmetric ; antisymmetric ; transitive ; not function (a,a),(a,b) not reflexive ; not symmetric ; antisymmetric ; transitive ; not function (a,a),(b,a) not reflexive ; not symmetric ; antisymmetric ; transitive ; function (a,a),(b,b) reflexive ; symmetric ; antisymmetric ; transitive ; function (a,b),(b,a) not reflexive ; symmetric ; antisymmetric ; not transitive ; function (a,b),(b,b) not reflexive ; not symmetric ; antisymmetric ; transitive ; function (b,a),(b,b) not reflexive ; not symmetric ; antisymmetric ; transitive ; not function (a,a),(a,b),(b,a) not reflexive ; symmetric ; not antisymmetric ; not transitive ; not function (a,a),(a,b),(b,b) reflexive ; not symmetric ; antisymmetric ; transitive ; not function (a,a),(b,a),(b,b) reflexive ; not symmetric ; antisymmetric ; transitive ; not function (a,b),(b,a),(b,b) not reflexive ; symmetric ; antisymmetric ; not transitive ; not function (a,a),(a,b),(b,a),(b,b) reflexive ; symmetric ; not antisymmetric ; transitive ; not function Q8) a) Suppose that R and S are reflexive relations on a set A. Prove or disprove each of these statements. R S is reflexive. R S is reflexive. S R is reflexive. b) Show the following properties on relations Show that the relation R on a set A is symmetric if and only if R = R1, where R1 is the inverse relation. Let (x,y) R (y,x) R since R is symmetric (x,y) and (y,x) R1 by definition of inverse relation So, R=R1 Show that the relation R on a set A is antisymmetric if and only if R R1 is a subset of the diagonal relation = (a, a) | a A. Show that the relation R on a set A is reflexive if and only if the inverse relation R1 is reflexive. R is reflexive iff xxU (x,x) R iff xxU (x,x) R-1 by definition of inverse relation R-1 is reflexive Q9) a) Which of these relations on the set of all people are equivalence relations? Determine the properties of an equivalence relation that the others lack. (a, b) | a and b are the same age equivalence relation (a, b) | a and b have the same parents equivalence relation (a, b) | a and b share a common parent This is not an equivalence relation, since it need not be transitive. (We assume that biological parentage is at issue here, so it is possible for A to be the child of W and X, B to be the child of X and Y, and C to be the child of Y and Z . Then A is related to B, and B is related to C, but A is not related to C.) (a, b) | a and b speak a common language This is not an equivalence relation, since it need not be transitive. b) Show that the relation R consisting of all pairs (x, y) s