Discrete Mathematics Answers

Check the validity of the following argument: “If I study then I will not fail in Mathematics. If I do not play Basket ball then I will study. I failed in Mathematics. Therefore I must have played Basketball

By using mathematical induction prove that (n+1)! > 2^(n+1) for n, where n is a positive integer greater than or equal to 4

In set using venn diagram: The are 60 sciences students in ss3, in a secondary school, 35 of whom study chemistry, 30 study technical drawing, 12 out of those students study biology and chemistry but not technical drawing, 10 study chemistry but neither biology nor technical drawing, 11 study only technical drawing and neither biology or chemistry, 10 also study chemistry and technical drawing only. How many students study all the 3 subjects? How many students study biology and technical drawing but not chemistry? How many students study biology only? How many students study biology all together?

2. Following algorithm calculates the sum of first n nonnegative integers. Prove the algorithm to be

correct using mathematical induction.

procedure sum(n: nonnegative integer)

if n = 0 then return 0

else return n + sum(n - 1)

{output is 0 + 1 + 2 + 3 + …… + n}

a. (10p) Show that basis step returns correct result

b. (10p) Write down the inductive hypothesis

c. (10p) What do you need to prove in the inductive step?

d. (10p) Complete the inductive step, stating where you use the inductive hypothesis

e. (10p) Explain why these steps show that this algorithm returns correct result for any

nonnegative integer n.

1. A. (20p) Give a Big-O estimate that is as good as possible for each of the following functions.

i. (n^3 + n)(logn + n)

ii. (n + 1000)(logn + 1)

B. (15p) If these are complexities of algorithms that solve the same problem, which one would you

prefer? Why?

C. (15p) Considering the Big-O complexity, how many times is your choice faster with respect to the

other solution for an input size of 2^16?

Note: The base of logarithm is 2

Show that {1, 2, 3, 4, . . .} and {2, 4, 6, 8, . . .} have the same cardinality.

Hint: find a mapping and show it is 1–1 and onto.

List the members of these sets:

(a) A={ x∣x is a real number ∋ x2=1}

(b) B={ x∣x is a positive integer less than 100 }

(c) C={ x∣x is the square of an integer and x <100 }

(d) D={ x∣x is an integer ∋ x2=2 }

1. Prove the validity of the arguments using rules of inference.

  { (p→q) ^ [ q → (r ^ s) ] ^ (p ^ w) ^ [~r v (~w v u) ] } → u

. Identify the contrapositive of the following statement. If x = 5, then x + 8 = 13

Write the set in the form { x | P(x) }

1.

{2, 4, 6, 8, 10}