Discrete Mathematics Answers

Write the converse, inverse, and contrapositive of the following conditional

propositions. (Hint: If applicable, write each conditional proposition in standard

form first.)

a. Rose may graduate if she has 120 hours of OJT credits.

b. A necessary condition for Bill to buy a computer is that he obtains

P20,000.

c. A sufficient condition for Katrina to take the algorithms course is that

she passes discrete mathematics.

d. The program is readable only if it is well-structured.

For the relation R = {(p,p) ,(q,p),(q,q),(r,r),(r,s),(s,s) ,(s,m) ,(m,m)}

1.Using warshall algorithm find the transitive closure R* of R

2.write matrix representation of R*

3.Check whether the relation of R* is an equivalence relation or a partial order.

A pet store keeps track of the purchases of customers over a fours hour period. The store manager classifies purchases as containing a dog product, a cat product, a fish product, or product for a different kind of pet. He found!

83 purchased a dog product

101 purchased a cat product

22 purchased a fish product

31 purchased a dog and a cat product

8 purchased a dog and a fish product

10 purchased a cat and a fish product

6 purchased a dog, a cat, and a fish product

34 purchased a product for a pet other than a dog, cat, or fish.

Draw a Venn diagram to find that:

(1) How many purchases were for a dog product only?

(ii) How many purchases were for a cat product only?

How many purchases were for a dog or a fish product?

(iv) How many purchases were there in total?

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)

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 𝑛 = 𝑂(𝑛)

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

Let A, B, C, D denote, respectively, art, biology, chemistry, and drama courses.

Find the number N of students in a dormitory given the data:

12 take A, 5 takeAand B, 4 takeB and D, 2 take B, C,D,

20 take B, 7 takeAand C, 3 takeC and D, 3 take A, C,D,

20 take C, 4 takeAand D, 3 take A, B,C, 2 take all four,

8 take D, 16 takeB and C, 2 take A, B, D, 71 take none.

Draw a simple, undirected graph yourself, the vertices are connected with each other including 8 vertices and 14 edges. Find the shortest path from two arbitrary vertices:​

a) The weight of each edge is 1.​

b) Self-weighting for edges

Let a and b be two cardinal numbers. Modify Cantor’s definition of a < b to define a ≤ b. (Hint: Examine what happens if you drop condition (a) from Cantor’s definition of a < b.) 2. Prove that a ≤ a. 3. Prove that if a ≤ b and b ≤ c, then a ≤ c. 4. Do you think that a ≤ b and b ≤ a imply

a = b? Explain your reasoning. (Hint: This is not as trivial as it might look.)

Obtain the Conjunctive Normal Form of (x^y) V (-x^y)