LinkedIn Insight BSc.-Discrete Mathematics-Mumbai-November 2017 - Grad Plus

BSc.-Discrete Mathematics-Mumbai-November 2017

MUMBAI UNIVERSITY

Discrete Mathematics

Semester1

[Time: 21/2 Hours]
[ Marks:75]
Please check whether you have got the right question paper.
N.B 1 All questions are compulsory
2. Make suitable assumptions wherever necessary and state the assumptions made.
3. Answers to the same question must be written together.
4. Numbers to the right indicate marks.
5. Draw neat labeled diagrams wherever necessary.
6. Use of Non-programmable calculators is allowed.
____________________________________________________________________________________________________________________________

Q. 1) Attempt any three of the following: (15M)
a) 1) Which of the following sets are equal? Justify your answer

A = {0, 1, 2)

B = { X ∈ R |-1 ≤ x < 3)

C = { X ∈ R |-1< x < 3}

D = ( X ∈ Z |-1 < x< 3)

E = {X Z |-1< x < 3)

ii) Let A = {w, x, y, z) and B = (a, b). Use the set-roster notation to write each of the following sets, and indicate the number of elements that are in each set:

A x B, T X S , S x’S. T x T 

b) A relation C from R to R is defined as follows: For any (X, Y) ∈ R x R (x, y) ∈ C means that x2 + y = 1

i) Does (1,0) ∈ C? Does (0,0)∈ C? is-2 CO? Is 0 C (-1)? is 1 C1?

ii) What are the domain and co-domain of C?

iii) Draw a graph for C by plotting the points of in the Cartesian plane.

 

c) Let p be the statement “DATAENDFLAG is off,” q the statement “ERROR equals 0,” and r the statement “SUM is less than 1,000.” Express the following sentences in symbolic notation.

i) DATAENDFLAG is off, ERROR equals 0 and SUM is less than 1,000.

ii) DATAENDFLAG is off but ERROR is not equal to 0.

iii) DATAENDFLAG is off; however, ERROR is not o or SUM is greater than or equal to 1.000.

iv) DATAENDFLAG is on and ERROR equals o but SUM is greater than or equal to 1.000.

v) Either DATAENDFLAG is on or it is the case that both ERROR equals O and SUM is less than 1,000

 

d) The logician Raymond Smullyan describes an island containing two types of people: knights who always tell the truth and knaves who always lie. You visit the island and are approached by two natives who speak to you as follows:

A says: B is a knight.

B says: A and I are of opposite type,

What are A and B? Explain with logical reasoning.

 

e) Let sets R, S, and 7 be defined as follows:

R = { X ∈ Z | x is divisible by 2}

S = { y ∈ Z | y is divisible by 3}

T = { Z ∈ Z | z  is divisible by 6}

i) Is R ⊆ T? Explain.

ii) is T ⊆ R? Explain.

iii) Is T ⊆ S? Explain.

 

f) Given sets A and B, the symmetric difference of A and B, denoted A Δ B, is
A Δ B = (A – B) U (B – A).

Let A = (1, 2, 3, 4), B = {3,4,5,6), and C= {5, 6, 7, 8). Find each of the following sets:

i) A Δ B

ii) B Δ C

iii)  A Δ C

iv) (A Δ B) Δ C

 

 

Q. 2) Attempt any three of the following: (15M)

a) i) Give counter examples to prove that the following statements are false:

a) ∀ x ∈ R, x > 1/x

b) ∀a ∈ Z, (a – 1)/a is not an integer.

c) ∀ positive integers m and n, m X n ≥ m+n.

ii) Consider the following statement:

3 x ∈ R such that x2= 2.

Which of the following are equivalent ways of expressing this statement?

a) The square of each real number is 2.

b) Some real numbers have square 2.

c) The number x has square 2, for some real number x.

d) If x is a real number, then x2 = 2

e) There is at least one real number whose square is 2.

 

b) Write negation for each of the following statements:

i) ∀ real numbers x, if x 2≥ 1 then x > 0.

ii) integers d, if 6/d is an integer then d = 3.

iii) X ∈ R, if x(x + 1) >0 then x>0 or x < -1

iv) ∀n ∈ Z, if n is prime then n is odd or n = 2.

v) ∀  integers a, b and c, if a -b is even and b – c is even, then a-c is even.

 

c) i) Rewrite the following argument using quantifiers, variables, and predicate symbols. Is this argument valid? Why? Explain,
If an integer is even, then its square is even.
k is a particular integer that is even
∴ k2 is even

ii) Prove the following by using universal modus ponens: Suppose mand n are particular but arbitrarily chosen even integers. Then m = 2r for some integer and n=2s for some integer s. Hence m + n = 2r + 2s  by substitution

= 2(r+s) by factoring out the 2.

Now +sis an Integer, and so 21r+s) is even. Thus m+n is even.

 

d) i) Is 1 prime? Why?

ii) Is every integer greater than 1 either prime or composite? Prove.

iii) Prove the following: 3 an even integer n that can be written in two ways as a sum of two prime numbers.

iv) Suppose that rand s are integers. Prove the following: ∋ an integer k such that 22r + 18s = 2k.

v) Disprove the following statement by finding a counterexample:

∀ real numbers a and b, if a2 = b2 then a = b.

 

e) Prove that for all real numbers x and for all integers m. | x + m |= |x|+m

 

f) By using negation, prove that \sqrt2 is irrational.

 

 

Q. 3) Attempt any three of the following: (15M)

a) Transform the following summation by making the specified change of variable.

\sum_{k=1}^{n+1}\frac k{n+k}
change of variable: j = k-1
Transform the summation so obtained by changing all js to k’s

 

b) For all integers n ≥ 0.22n – 1 is divisible by 3.

 

c) Suppose a sequence b0 b1, b2. .. satisfies the recurrence relation

bk = 4bk-1 – 4bx-2 for all integers k ≥ 2 with initial conditions b0 = 1 and bi=3. Find an explicit formula for b0, b1 b2..

 

d) Define logarithm and logarithmic functions. Use the definition of logarithm 10 prove that for any positive real number  b with b ≠ 1. logs  b = 1 and logs I = 0.

 

e) A function Fis defined as ∴ R x R→R x R as follows: For all (x, y) ∈ R x R

F(x, y) = (x +y,x-y).

Is F a one-to-one correspondence from R x R to itself?

 

f) Define countably infinite, countable and uncountable sets. Show that the set Z of all integers is countable.

 

 

Q. 4) Attempt any three of the following: (15M)

a) A relation R from R to R as follows: For all (x,y)∈ R x R
x R y⇔ y =2 |x|
Draw the graphs of R and R-1in the Cartesian plane. Is R” a function?

 

b) A relation T on Z (the set of all integers) is defined as follows: For all integers m and n.
m T n ⇔ 3| (m-n).
Is T reflexive? Is 7 symmetric? Is T transitive! Prove.

 

c) It A is a set. R is an equivalence relation on A, and a and b are elements of A. then either [a]∩[b]= Φ or [a] =[b]

 

d) State and prove the handshake theorem.

 

e) Show that the graph below does not have an Euler circuit.

f) For each pair of graphs G and G’ in, determine whether G and G’ are isomorphic. If they are, give functions g: V(G) →V(G) and h: E(6) → E(G’) that define the isomorphism. If they are not, give an invariant for graph isomorphism that they do not share.

i

 

ii

 

Q. 5) Attempt any three of the following: (15M)

a) Teams A and B are to play each other repeatedly until one wins two games in a row or a total of three games. One way in which this tournament can be played is for A to win the first game, B to win the second, and A to win the third and fourth games. Denote this by writing A-B-A-A.

i) How many ways can the tournament be played?

ii) Assuming that all the ways of playing the tournament are equally likely, what is the probability that five games are needed to determine the tournament winner?

 

b) i) How many ways can the letters of the word QUICK be arranged in a row?

ii) How many ways can the letters of the word OUICK be arranged in a row if the and the U must remain next to each other in the order QU

iii) How many ways can the letters of the word QUICK be arranged in a row if the letters QU must remain together but may be in either the order QU or the order UQ?

c) Let A = { 1,2,3,4,5,6,7,8}

i) If five integers are selected from A, must at least one pair of the integers have a sum of 9? Explain

ii) If four integers are selected from A, must at least one pair of the integers have a sum of 9? Explain.

 

d) Suppose five members of a group of twelve are to be chosen to work as a team on a special project.

i) How many distinct live-person teams can be selected?

ii) Suppose two members of the group of twelve insist on working as a pair any team must contain either both on neither. How many five-person teams can be formed?

iii) Suppose the group consists of five men and seven women. How many teams of five contain at least one man?

 

e) A lottery game offers 2 million to the grand prize winner, 20 to each of 10.000-second prize winners, and 4 to each of 50.000 third prize winners. The cost of the lottery is 2 per ticket. Suppose that 1.5 million tickets are sold. What is the expected gain or loss of a ticket?

 

f) A coin is loaded so that the probability of heads is 0.6. Suppose the coin is tossed ten times.

i) What is the probability of obtaining eight heads?

ii) What is the probability of obtaining at least eight heads?

 

Scroll to Top