Discrete Mathematics Answers

Briefly answer the following short questions

1) Determine if the following argument is valid and explain why. Every CS

major takes CMSC203. Mr. Ali is taking CMSC203, therefore he is a CS

major.

2) What is the time complexity (in Big-O notation) of the following code? Your

answer should be a function of n. Also, what is the value of “sum” after the

execution of the code with n = 10?

sum := 0;

for i := 1 to n

for j := i to n

sum := sum + 1

Find the domain and range of these functions.
i. The function that assigns to each pair of positive integers the first integer of the pair b) the
function that assigns to each positive integer its largest decimal digit
ii. The function that assigns to a bit string the number of ones minus the number of zeros in the
string
iii. The function that assigns to each positive integer the largest integer not exceeding the square
root of the integer
iv. The function that assigns to a bit string the longest string of ones in the string

Question No 05: [07 marks]
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 ◦ g = g ◦ f

Determine whether the relation R on the set of all people is irreflexive, where (a, b) ∈ R if and
only if :
i) a and b were born on the same day.
ii) a has the same first name as b.
iii) a and b have a common grandparent

Let A= {0, 1, 2, 3} and define relations R, S and T on A as follows:
R= { (0,0),(0,1),(0,3),(1,0),(1,1),(2,2),(3,0),(3,3)}
S= {(0, 0),(2,2),(1,1), (0, 2), (0, 3), (2, 3),(2,2)}
T= {(0, 1), (2, 3),(0,0),(2,2),(1,0),(3,3),(3,2)}
i. Is R Reflexive? Symmetric? AntiSymmetric?
ii. Is S Reflexive? Symmetric? AntiSymmetric?
iii. Is T Reflexive? Symmetric? AntiSymmetric?

How many strings of six lowercase letters from the English alphabet contain:
i.The letter a?
ii. The letters a and b?
iii. The letters a and b in consecutive positions with a preceding b, with all the letters distinct?
iv. The letters a and b, where a is somewhere to the left of b in the string, with all the letters
distinct?

Draw the Venn diagrams for each of these combinations of the sets A, B, C, and D.
a) (A ∩ B) ∪ (C ∩ D)
b) A
c U B
c U Cc U Dc
c) A − (B ∩ C ∩ D)
d) A ⊕ B

Solve the recurrence by substitution method.
T(n) = 2T (n/2)+n-1 and T (1) =1.

Is (p q) > I(p>q)> q] a tautology? Why or why not?

Translate the following Propositional Logic to English sentences. Let:
E-Lion is eating
H=Lion is hungry
a) E-H
b) EA-H
c)-(H-E)