Discrete Mathematics Answers

As for those three guys, John, Bill and Bob, I will only vote for one. Translate into proposition logic.

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.)

Consider two sets A and B such that A ⊆ B. Find the possible values of x if A = {2, 4, 6, x} and B = {2, 3, 5, 6, x+1}. Ans: x = 3. Please explain.

Consider a relation R= {(1, 1) (1, 3), (2, 2), (2,3) (3,1)on the set A = (1,2,3) Find transitive using warshalls algorithm... closure of the relation R consider

Consider a relation R= {(1, 1) (1, 3), (2, 2), (2,3) (3,123 on the set A = {1,2,37 Find transitive using warshalls algorithm... closure of the relation R consider

For each of the following pairs of functions, determine whether 𝒇(𝒏) = 𝑶(𝒈(𝒏)) or

𝒈(𝒏) = 𝑶(𝒇(𝒏)).

a. 𝑓(𝑛) = 𝑛(𝑛 − 1)⁄2 and 𝑔(𝑛) = 6𝑛

b. 𝑓(𝑛) = 𝑛 + 2√𝑛 and 𝑔(𝑛) = 𝑛^2

c. 𝑓(𝑛) = 𝑛 + log 𝑛 and 𝑔(𝑛) = 𝑛√𝑛

d. 𝑓(𝑛) = 𝑛 log 𝑛 and 𝑔(𝑛) = 𝑛√𝑛/2

e. 𝑓(𝑛) = 2(log 𝑛)^2

and 𝑔(𝑛) = log 𝑛 + 1

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)

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)

Define a relation R on {a,b,c, int i* e . a Reflexive but not symmetric ↳ Symmetric but not transitive <> Transitive but not reflexive