BSc IT Sem I 2017 18 2017-18 Descrete Maths Question Paper - Mumbai University | munotes

Questions asked in this paper

• Please check whether you have got the right question paper

1. Q2 Make suitable assumptions wherever necessary and state the assumptions made
2. Q3 Answers to the same question must be written together
3. Q4 Numbers to the right indicate marks
4. Q6 Use of Non-programmable calculators is allowed
5. Q1 Attempt any three of the following: 15 marks
   • a) i. Which of the following sets are equal? Justify your answer:
   • 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:
   • b) Arelation C from R to R is defined as follows: For any (x, y) R
   • i. Does (1, C? Does (0, 0) C? 0? Is OC (-1)? Is
   • ii. What are the domain and co-domain of C?
   • iii. Draw for C by plotting the points of C in the Cartesian plane
   • c) Let p be the statement “DATAENDFLAG is off,” 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. is off but ERROR is not equal to 0 ili. DATAENDFLAG is off; however, ERROR is not SUM is greater than or equal to 1,000
   • iv. DATAENDFLAG is on and ERROR equals SUM is greater than or equal to 1,000
6. Q5 Either DATAENDFLAG or it is the case that both ERROR equals 0 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 are of opposite type What are A and B? Explain with logical reasoning
   • e) R, and T be defined as follows: R={x Z| xis divisible by 2} S={y yis divisible by 3} zis divisible by 6
   • i. T? Explain
   • ii. Is T Explain
   • iii. Is T SS? Explain
   • Q.P. Code :00901
   • f. Given sets A and B, the symmetric difference of A and B, denoted A A B, is Let A= {1, 2, 3, 4}, B= {3, 4, 5, 6}, and C= {5, 6, 7, 8}. Find each of the following sets:
   • ii. BAC
   • iii. AAC
7. Q2 Attempt any three of the following: 15 marks
   • a. i. Give counter examples to prove that the following statements are false:
   • b. Va not an integer
   • ii. Consider the following statement: Which of the following are equivalent ways of expressing this statement?
   • a. The square of each real 2
   • b. Some real numbers have square 2
   • c. x has square 2, for some real number x
   • d. number, then 2
   • e. There is at least one real number whose square is 2
   • b. Write negation for each of the following statements:
   • i. V real numbers x, if then x >0
   • ii. V integers d, if 6/dis an integer then d =3
   • iv. Vn if nis prime then n is odd orn
8. Q5 V integers a, b and.c, even.and cis even, then a is even
   • i. Rewrite the following argument using quantifiers, variables, and predicate symbols. Is this argument valid? Why? Explain integer is even, then its square is even kis a particular integer that is even
   • ii. Prove the following by using universal modus ponens: Suppose n are particular but arbitrarily chosen even integers. Then m = 2r for some integer 2s for some integer s. Hence =2(r+s) by factoring out the 2 and so 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 ili. Prove the following: 3 an even integer n that can be written in two ways as a sum of two prime
   • iv. Suppose that r ands are integers. Prove the following: 4 an integer k such that 22r + 18s = 2k Disprove the following statement by finding a counterexample: real numbers a and b, if a2 = b? then a=b. P.T.O
   • e. Prove that for all real numbers x and for all integers m, |x + = [x] + m
   • f. By using negation, prove that V2 is irrational
   • Q.P. Code :00901
9. Q3 Attempt any three of the following: 15 marks
   • a. Transform the following summation by making the specified change of variable Transform the summation so obtained by changing all j’s to k’s
   • b. For all integers n 1 is divisible by 3
   • c. Suppose a sequence bo, bi, bz, . satisfies the recurrence relation bx = 4bi-1 — for all integers k > 2, with initial conditions bo = | and b; = 3. Find. an explicit formula for bo, b1, b2,
   • d. Define logarithm and logarithmic functions. Use the definition of logarithm to prove that for any positive real number b with b # 1, b= 1 and logy 1 =0
   • e. A function F is defined as F: R x R — R x follows: For all (x,y) ER xR, 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
10. Q4 Attempt any three of the following: 15 marks
    • a. A relation R from R to R as follows: For all (x, xR, Draw the graphs of R and R in the Cartesian plane. Is a function?
    • b. A relation Z (the set of all integers) is defined as follows: For all integers m and n, Is T reflexive? Is T symmetric? Is T transitive? Prove
    • c. If Ris an equivalence relation on A, and a and b are elements of A, then either [a] M [b] =
    • d. State and prove the handshake theorem
    • e. Show that the graph below does not have an Euler circuit
    • Q.P. Code :00901
    • 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) and h: E(G) — E(G’) that define the isomorphism. If they are not, give an invariant for graph isomorphism that they do not share
    • Q.P. Code :00901
11. Q5 Attempt any three of the following: 15 marks
    • a. and Bare to play each other repeatedly until one wins two games in.a row ora 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 QUICK be arranged in a row if the Q and the U must remain next to each other in the order QU? ili. 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 8}
    • i. five integers are selected from A, must at least one pair of the integers have a sum of 9? ui. four integers are selected from A, must at least one pair of the integers have a sum of 9?
    • 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 five-person be selected? li. Suppose two members of the group of twelve insist on working as a pair—any team must contain either both or 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
    • e. A lottery game offers million to the grand prize winner, to each of 10,000 second prize winners, and [14 to each of 50,000 third prize winners. The cost of the lottery is 12 per ticket. Suppose that 1.5 million tickets are sold. What is the expected gain or loss of a ticket?
    • f. is loaded so that the probability of heads is 0.6. Suppose the coin is tossed ten times What is the probability of obtaining eight heads? ui. What is the probability of obtaining at least eight heads?

Read from the scan above, so a character or two may differ. The scan is the original.