discrete mathematics Homework Help

College of Arts & Sciences Computer Science Department CS 3653 - Discrete Mathematics for Computer Science BA # 6 Chapter # 5 Max. Points # 10 QUESTIONS Pts Use the Principle of Mathematical Induction to prove: SN 1 Any integer amount of postage from 18 cents on up can be made from an infinite supply of 4-cent and 7-cent stamps. 2 Use the Principle of Mathematical Induction to prove: 1 + 5 + 9 + ... + (4n - 3) = n(2n - 1) for every positive integer n. 5 5 Spring - 2024 Page 1 of 1

Question 1 12 pts Let A = {1, 2, 3, 4}. Let the functions F, G, and H be given with domain and codomain A defined as F(1)=3,F(2)=2,F(3)=2,and F(4)=4; G(1) =1,G(2) =3,G(3) = 4, and G(4) = 2; H(1) =2, H(2) =4, H(3) = 1, and H(4) = 3. Find the following: (a) Fo G (b) Ho F (c) G o H (d) Fo Go H Edit View Insert Format Tools Table 12pt v Paragraph V B I U AV & VTV V 3º V V V : Time Attem 5 Da' Secol p 0 words </> Question 2 10 pts Given: f ={(a, 1), (b, 2), (c, 3), (d, 4)} g-1={(2,1),(3,2),(4,3), (1,4)} Verify the following: (g o f)-1 (x) = f-1 og-1(x) Edit View Insert Format Tools Table 12pt v V Paragraph BIUAV T2 > V V D V V : p 0 words > Question 3 10 pts If f : R\{-1} -> R\{1} is defined by f(x) = 1+x 1-x and g : R -> R is defined by g(x) = 1+22, then 2x prove that f o g(x) =(f(x))2. Edit View Insert Format Tools Table 12pt v Paragraph B I U A V & V TV 00 V > > ... p 0 words </> Question 4 8 pts Let f(x) = ax + b and g(x) = cx + d, where a, b, c, and d are constants. Determine necessary and sufficient conditions on the constants a, b, c, and d so that f og = go f. Edit View Insert Format Tools Table 12pt v V Paragraph B I U A V & V TV V V A VE V : p 0 words Question 5 9 pts Prove the following using the Pigeonhole Principle. (a) Prove that among any group of 27 English words, there are at least two words that start with the same letter. (b) Prove that among any group of 13 people, there are at least two people who have the same number of friends within the group, when each person does not know atleast one person. (c) In a group of 101 people, each person in the group knows a unique set of 10 languages. Prove that there are two people in the group who can communicate with each other in at least two different languages. Edit View Insert Format Tools Table 12pt Paragraph v B I U A V & V TV 20 V V D V : p 0 words 7 Question 6 16 pts For the following sequences find their closed AND recursive expressions. Be sure to add in all parts for both (a) (3, 7, 11, 15, ... ) (b) (2, 6, 12, 20, ... ) (c) (1, -2, 3, -4, ... ) (d) (1, 3, 6, 10, ... ) Edit View Insert Format Tools Table 12pt Paragraph V B I U A V & V TV 00 V V V V ... p 0 words </> 1 Question 7 12 pts Use and/or ][ notation to rewrite the following (a) (x+y+1)-(x+y+2)+(x+y+3) -... +(x+y+57) (b) (x+1)(x2 +2)(x3+3) ... (x20 +20) (c) 1(0+1) +2(0+1+2)+3(0+1+2+3) Edit View Insert Format Tools Table 12pt v V Paragraph BIUA > > T2 V 30 V V A > ilılı V : p 0 words

9) [5] The partial ordering relation S is shown with the Hasse diagram to the right. List the elements S. 20 10

8) [6] Consider the undirected graph to the right. a) List the vertices. b) List the edges. c) List the degree of each vertex in a table. d) Is it a simple graph? Why or why not?

7) [10] Let A = {1,2,3,4}. Define the relation R on A by aRb if and only if a > b - 1. a) List the elements of R. b) Use technology to create a digraph. Paste to the right. (6 points) You will earn half credit for a hand drawn picture. A nice free program: graphonline.ru/en/ c) Is R reflexive? Why or why not? d) Is R transitive? Why or why not?

5) [3] Let R and S be relations on Z where R = {(n,n) VnE Z} and S = {(1, 2) Vn E Z}. Hint: write out some of the terms of R and S for insight into the problem. a) Find RS. b) Find SR.

4) [5] Let R and S be relations on A = {1,2,3,4,5,6} such that R = {(1,3), (1,4), (2,2), (4,1),(5,2), (6,3)} and S = {(2,2), (2,4), (3,1),(4,1), (3,5)}. a) Find RS. b) Find SR.

3) [4] Let R be a relation from A = {2,4,6,8,10} to B = {-1,0,1} such that R = {(a, b) = A x BV a = 2b +6}and S be a relation from B = {-1,0,1} to C = {2,3,4} such that S = {(b, c) € B x C Vc - bisodd}. a) List the element of R. b) List the element of S.

2) [9] Let A = {2,4,6,8,10}. Let S be a relation on A defined by (a, b) ES if and only if a V b (a divides b). a) List the elements of S. b) Is S reflexive? Why or why not? c) Is S symmetric? Why or why not? d) Is Santisymmetric? Why or why not? e) Is Stransitive? Why or why not? f) Is Sa partial ordering? Why or why not? g) Is San equivalence relation? Why or why not?

1) [4] Let A = {2,4,6,8,10}. Let R be a relation on A defined by (a, b) E R if and only if a > b+ 1. Are the following elements of R? Why or why not? a) (4,4) b) (8,2) c) (2,10) d) (6,0)

4. Define a relation on the plane by setting (xo, yo) < (x1, y₁) if either yo − x² < y₁ − x², or yo – x² = y₁ − x² and x < x₁. Show that this is an order relation on the plane, and describe it geometrically.

2. Let C be a relation on a set A. If Ao C A, define the restriction of C to Ao to be the relation Cn (Ao x Ao). Show that the restriction of an equivalence relation is an equivalence relation.

FEB. 16 1. Let f A B. Let Ao C A and Bo C B. (a) Show that Ao C f¹(f(Ao)) and that equality holds if f is injective. (b) Show that f(f-¹ (Bo)) C Bo and that equality holds if f is surjective.

Problem 5. A perfect square is an integer which is also square of an integer. More formally, n E Z is a perfect square if n = a² for some a € Z. Prove or disprove the following two claims. a) If m and n are perfect squares, then the product mn is also a perfect square. b) If m and n are perfect squares, then the sum m + n is also a perfect square.

Problem 4. Let the universe for the variables in the following statement consist of all real numbers. Negate and simplify Vx+y[(lx] = [y]) → (y = ±x)].

Problem 3. Consider each of the following arguments. If the argument is valid, identify the rule of inference that establishes its validity. If not, explain why. a) Andrea can program in C++, and she can program in Java. Therefore, she can program in C++. b) If Ron's computer program is correct, then he'll be able to complete his computer science assignment in at most two hours. It takes Ron over two hours to complete his computer science assignment. Therefore, Ron's computer program is not correct. c) If interest rates fall, then the stock market will rise. Interest rates are not falling. Therefore, the stock market will not rise.

Problem 2. Assuming proposition q is true (T), determine all truth value assignments for the propositions p, r, and s for which the truth value of the following compound proposition is false (F). (q→ [(p^r) v¬s]) V[s → (r^q)] Explain your reasoning.

Problem 1. Verify that [p → (q→r)] → [(p → q) → (p →r)] is a tautology.