BSc IT Sem I ATKT DISCRETE MATHEMATICS Question Paper - Mumbai University | munotes

Questions asked in this paper

1. Q1 Attempt any three of the following: 15 marks
   • a. Define Universal statement, conditional statement and existential statement. Give example
   • b. Define domain, co-domain and function. Define functions H and K from R to R by the following formulas: For all x R,
   • c. Inasurvey of 60 people, it was found that 26 read Fortune 9 read both Newsweek and Fortune 11 read both Newsweek and Time 8 read both Time and Fortune 3 read all three magazines
   • i. Find the number of people who read at least one of the three magazines
   • ii. Draw a Venn diagram and fill the correct numbers in each of the regions
   • d. Prove the following by contradiction: There is no computer algorithm that will accept any algorithm Xand data set D as input and then will output “halts” or “loops forever” to indicate whether or not X terminates in a finite number of steps when Xis run with data set D
   • e. He is rich q: He is happy Write each of the following statements in symbolic form using p and q
   • i. poor li. Ifheis rich, then he is unhappy
   • iv. necessary to be poor in order to be happy
   • v. To be poor is to be unhappy
   • f. 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: Aand I are of opposite type What are A and B?
2. Q2 Attempt any three of the following: 15 marks
   • a. Predicate, its domain and truth set. Let Q(x) be the predicate “x is a factor of 12 Find the truth set of Q(x) if the domain of n is the set Z* of all positive integers li. — the domain of n is the set Z of all integers Consider a statement of the form: Vx D, if P(x) then Q(x). Write its contrapositive, converse and inverse. Write a formal and an informal contrapositive, converse, and inverse for the following statement: If a real number is greater than 2, then its square is greater than 4
   • c. State which are valid and which are invalid. Justify your answers
   • i. All healthy people eat an apple a day Keisha eats an apple a day Keisha is a healthy person ui. All freshmen must take writing Caroline is a freshman Caroline must take writing
   • iii. All healthy people eat an apple a day Herbert is not a healthy person Herbert does not eat an apple a day
   • iv. Ifa product of two numbers is 0, then at least one of the numbers is 0 For a particular number x, neither (2x + 1) nor (x= 7) equals 0 The product (2x + 7) is not 0
   • v. is even, then twice that number is even The number 2n is even, for a particular number n The particular number
   • d. i. Prove that every integer is a rational number li. Consider the statement: The negative of any rational number is rational e Write the statement formally using a quantifier variable e Determine whether the statement is true or false and justify Define floor and ceiling. Prove that for all real. numbers x and all integers m,
   • f. 1. Prove that if and r are integers such and 0 <r < d, then li. Prove that for all positive integers a and b, gcd(a, b) = Icm(a, b) if, and only if, a=
3. Q3 Attempt any three of the following: x isa real number not divisible by z, then for all integers n > 1, prove by using method of induction that: 15 marks
   • b. begin solving a jigsaw puzzle by finding two pieces that match and fitting them together. Each subsequent step of the solution consists of fitting together two blocks made one or more pieces that have previously been assembled. Use strong mathematical induction to prove that the number of steps required to put together all n pieces of a jigsaw
   • c. the recurrence relation a, = — — With Let Js = (0, 1, 2, 3,4}. Then 2, 3, 4} Student to define a function R : Js Js {0} as follows: For each x {0}, is the number y so that (xy) mod 5 = 1 Student B claims that R is not well defined. Who is right: student A or student B? Justify Define F: Z + Z and G: Z Z by the rules F(a) = 7a and G(a) = amod 5 for all
   • f. i. Prove that any infinite set contains a countably infinite subset
   • ii. If Ais any countably infinite set, B is any set, and g: A— Bis onto, then B is countable
4. Q4 Attempt any three of the following: a i. Define inverse relation 15 marks
   • ii. Let A= 5} and B = {4, 5, 6} and let R be the “less than” relation. That is, (xy) AX & x < y. State explicitly which ordered pairs are in R and
   • i. reflexive, then is reflexive li. If Rand S are reflexive, is RM S reflexive? Why? c Define an equivalence relation. Suppose Ais a set, Ris an equivalence relation on A, and a and b are elements of A.If a R b, then prove that [a] = [b] that any sum of an odd number of odd integers is odd e Determine whether G and G’ are isomorphic. If they are, function g: V(G) — V(G’) that defines the isomorphism. If they are not, give an invariant for graph isomorphism that they do not share Use Kruskal’s algorithm to find a minimum spanning tree for the following graph Indicate the order in which edges are added to form each tree
5. Q5 Attempt any three of the following: 15 marks
   • a. contains two blue balls (denoted BI and B2) and one white ball (denoted W). One ball is drawn, its color is recorded, and it is replaced in the urn. Then another ball is drawn, and its color is recorded
   • i. Let B1W denote the outcome that the first ball drawn is B1 and the second ball drawn is W. Because the first ball is replaced before the second ball is drawn, the outcomes of the experiment are equally likely. List all nine possible outcomes of the experiment
   • ii. Consider the event that the two balls that are drawn are both blue. List all outcomes in the event. What is the probability of the event?
   • iii. Consider the event that the two balls that are drawn are of different colors. List all outcomes in the event. What is the probability of the event?
   • b. i. buying a personal computer system is choice of three models of the basic unit, two models of keyboard, and two models of printer. How many distinct systems can be purchased?
   • ii. How many integers are there from 10 through 99?
   • iii. How many odd integers are there from 10 through 99?
   • iv. How many integers from 10 through 99 have distinct digits?
   • v. A bit string is a finite sequence of 0’s and 1’s. How many bit strings have length 8?
   • c. How many positive integers less than 1,000 have no common factors with 1,000? (Use De Morgan’s laws and the inclusion/exclusion rule)
   • d. i. Ifseven integers are chosen from between and 12 inclusive, must at least one of them be odd? Why?
   • ii. integers are chosen from between 1 and 20 inclusive, must at least one of them be 1 integers are chosen from the set where n is a positive integer, must at least one of them be odd? Why?
   • iv. How many cards must you pick from a standard 52-card deck to be sure of getting at least 1 red card? Why?
   • v. Acertain college class has 40 students. All the students in the class are known to be from 17 through 34 years of age. You want to make a bet that the class contains at least x students of the same age. How large can you make x and yet be sure to win your bet?
   • e. Anurn contains four balls numbered person selects a set of two balls at random, what is the expected value of the sum of the numbers on the balls?
   • f. A student taking a multiple-choice exam does not know the answers to two questions. All have five choices for the answer. For. one of the two questions, the student can eliminate two answer choices as incorrect but has no idea about the other answer choices. For the other question, the student has no clue about the correct answer at all. Assume that whether the student chooses the correct answer on one of the questions does not affect whether the student chooses the correct answer on the other question is the probability that the student will answer both questions correctly?
   • ii. What is the probability that the student will answer exactly one of the questions What is the probability that the student will answer neither question correctly?

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