Discrete Mathematics Answers

1.     The following formulas have been abbreviated based on the common abbreviation rules. Follow the steps below and translate the formulas into good English.

·       Step 1: Re-add the omitted brackets.

·       Step 2: If necessary, convert them into some other logically equivalent formula

so as to make it more readable. Write out the rule(s) you use for conversion.

·       Step 3: Translate the formulas into `good' English. Try to make your translation as brief/understandable as possible. (For instance, `John and Bill are coming' is better than `John is coming and Bill is coming.')

p: John wants to come to the class.

q: John will come to the class today.

r: John audits the class.

s: John is enrolled in the class.

Hint:

`No matter whether John is going or not, I'm going.' is the translation for (j à i) ^ (⌐j à i),

in which j = John is going, i = I'm going.)

State TRUE or FALSE justifying your answer with proper reason.

a. 2𝑛^2 + 1 = 𝑂(𝑛^2 )

b. 𝑛^2 (1 + √𝑛) = 𝑂(𝑛^2 )

c. 𝑛^2 (1 + √𝑛) = 𝑂(𝑛^2 log 𝑛)

d. 3𝑛^2 + √𝑛 = 𝑂(𝑛 + 𝑛√𝑛 + √𝑛)

e. √𝑛 log 𝑛 = 𝑂(𝑛)

solve the following recurrence relations

a. 𝑇(𝑛) = 𝑇( 𝑛/4) + 𝑇( 𝑛/2 ) + 𝑛^2

b. T(n) = T(n/5) + T(4n/5) + n

c. 𝑇(𝑛) = 3𝑇( n/4 ) + 𝑐𝑛^2

f. 𝑇(𝑛) = (𝑛/𝑛−5) * 𝑇(𝑛 − 1) + 1

g. 𝑇(𝑛) = 𝑇(log 𝑛) + log 𝑛

h. 𝑇(𝑛) = 𝑇 (𝑛^ 1/ 4) + 1

i. 𝑇(𝑛) = 𝑛 + 7 √𝑛 ∙ 𝑇(√𝑛)

j. 𝑇(𝑛) = 𝑇 ( 3𝑛/4 ) + 1/root(n)

15.Determine whether f: R to R, defined as f (x) = −3x + 4 is a bijection. Is f invertible, and if it is, 

what is its inverse?

16.Find the inverse of f (x) =

𝑥+1

𝑥+2

, on a suitable subset of R.

Labelled and Unlabelled trees.

(a) How many labelled trees of order 5 are there?

(b) Draw all unlabeled tree of order 5 (under isomorphism). Hint: make cases on the diameter size.

How many 5 vertices unlabelled trees are there? How would I draw them?

show that ~Q,P—>Q=>~P in mathematical foundations of computer science

Define and what Cryptography in mathematical foundations of computer science

Define and what Cryptography in mathematical foundations of computer science

How many students are offering both biology and chemistry,if only 70 students are offering neither biology or chemistry.