BSc.-Discrete Mathematics-Mumbai-April 2017
MUMBAI UNIVERSITY
Discrete Mathematics
Semester : 1
[Time: 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) Let A = {c, d, f, g}, B = {f, j}, and C = {d, g}.
Answer each of the following questions. Give reasons for your answers.
i) Is B ⊆ A?
ii) Is C ⊆ A?
iii) Is C ⊆ C?
iv) Is C a proper subset of A?
b) Let S = {2, 4, 6} and T = {1, 3, 5}. Use the set-roster notation to write each of the following sets, and indicate the number of elements that are in each set:
i) S × T
ii) T × S
iii) S × S
iv) T × T
c) Use De Morgan’s laws to write negations for the statements below
i) Hellen is a math major and Hellen’s sister is a computer science major.
ii) Sam is an orange belt and Kate is a red belt.
iii) The connector is loose or the machine is unplugged.
iv) This computer program has a logical error in the first ten lines or it is being run with an incomplete data set.
v) The dollar is at an all-time high and the stock market is at a record low.
vi) The train is late or my watch is fast.
d) Prove the following using a truth table
i) ????→????=¬????∧????
ii) ????↔????=(¬????∧????)∨(¬????∧????)
iii) ????∧(????∨????)=(????∧????)∨(????∧????)
e) Let A = {a, b}, B = {1, 2}, and C = {2, 3}. Find each of the following sets.
a) A × (B ∪ C)
b) (A × B) ∪ ( A × C)
f) Let E = {1, 2, 3} and F = {−2,−1, 0} and define a relation T from E to F as follows: For all (x, y) ∈E × F,(x, y) ∈T means that (x –y)/3is an integer.
i) Is 3 T 0? Is 1T (−1)? Is (2,−1) ∈T? Is (3,−2) ∈T ?
ii) Write T as a set of ordered pairs.
iii) Write the domain and co-domain of T.
iv) Draw an arrow diagram for T.
Q. 2) Attempt any three of the following: (15M)
a) Let D = {−48, −14, −8, 0, 1, 3, 16, 23, 26, 32, 36}.
Determine which of the following statements are true and which are false. Provide counterexamples for those statements that are false.
i) ∀x ∈D, if x is odd then x >0.
ii) ∀x ∈D, if x is less than 0 then x is even.
iii) ∀x ∈D, if x is even then x ≤ 0.
iv) ∀x ∈D, if the ones digit of x is 2, then the tens digit is 3 or 4.
v) ∀x ∈D, if the ones digit of x is 6, then the tens digit is 1 or 2.
b) Rewrite the statement “No good cars are cheap” in the form “∀x, if P(x) then ∼Q(x).” Indicate whether each of the following arguments is valid or invalid, and justify your answers.
a) No good car is cheap.
A Rimbaud is a good car.
∴A Rimbaud is not cheap.
b) No good car is cheap.
A Simbaru is not cheap.
∴A Simbaru is a good car.
c) No good car is cheap.
A VX Roadster is cheap.
∴A VX Roadster is not good.
d) No good car is cheap.
An Omnex is not a good car.
∴An Omnex is cheap.
c) Show that If r and s are any two rational numbers, then r+s2 is rational.
d) In a certain town 2/3 of the adult men are married to 3/5 of the adult women. Assume that all marriages are monogamous (no one is married to more than one other person).
Also, assume that there are at least 100 adult men in the town. What is the least possible number of adult men in the town and number of adult women in the town?
e) Prove that for all integers m and n, m + n and m – n are either both odd or both even.
f) Prove that for all integers n, n2− n + 3 is odd.
Q. 3) Attempt any three of the following: (15M)
a) Prove that n! + 2 is divisible by 2, for all integers n ≥ 2.
b) Prove that 7n− 1 is divisible by 6, for each integer n ≥ 0.
c) Let A = {0, 1, 2, 3, 4}, and define functions f : A→A and g : A→A as follows: For each x ∈ A,
f (x)=(x + 4)2mod 5 and g(x)=(x2+ 3x + 1) mod 5. Is f = g? Explain.
d) Define g: Z → Z by the rule g(n) = 4n − 5, for all integers n
i) Is g one-to-one? Prove or give a counterexample.
ii) Is g onto? Prove or give a counterexample.
e) Explain
i) One-one function
ii) Onto function
iii) Inverse of a function
iv) Cardinality
v) Composite function
f) Define G: R × R → R × R as follows:
G(x, y) = (y−2x) for all (x, y) ∈R × R.
i) Is G one-to-one? Prove or give a counterexample.
ii) Is G onto? Prove or give a counterexample.
Q. 4) Attempt any three of the following: (15M)
a) Define the following:
i) Trail ii) Connected Graph iii) Spanning Tree iv) Hamiltonian Graph v) Hamiltonian Cycle
b) Find Shortest Path from vertex v1 to all the vertices by applying Dijkstra’s Algorithm for the complete weighted graph given below:
c) Prove that every nontrivial tree has at least two vertices of degree 1 by filling in the details and completing the following argument: Let T be a nontrivial tree and let S be the set of all paths from one vertex to another of T . Among all the paths in S, choose a path P with the most edges. (Why is it possible to find such a P?) What can you say about the initial and final vertices of P? Why?
d) i) Draw all nonisomorphic graphs with six vertices, all having degree 2.
ii. Draw four nonisomorphic graphs with six vertices, two of degree 4 and four of degree 3.
e) Let S = {(0, 0), (0, 3), (1, 0), (1, 2), (2, 0), (3, 2)}. Find St, the transitive closure of S.
f) i) If R and S are reflexive, is R ∩ S reflexive? Why?
ii) If R and S are symmetric, is R ∩ S symmetric? Why?
iii) If R and S are transitive, is R ∩ S transitive? Why?
Q. 5) Attempt any three of the following: (15M)
a) i) How many five-digit integers (integers from 10,000 through 99,999) are divisible by 5?
ii) What is the probability that a five-digit integer chosen at random is divisible by 5?
b) i) If any seven digits could be used to form a telephone number, how many seven-digit telephone numbers would not have any repeated digits?
ii) How many seven-digit telephone numbers would have at least one repeated digit?
iii) What is the probability that a randomly chosen seven-digit telephone number would have at least one repeated digit?
c) i) How many distinguishable ways can the letters of the word MILLIMICRON be arranged in order?
ii) How many distinguishable orderings of the letters of MILLIMICRON begin with M and end with N?
iii) How many distinguishable orderings of the letters of MILLIMICRON contain the letters CR next to each other in order and also the letters ON next to each other in order?
d) A coin is loaded so that the probability of heads is 0.7 and the probability of tails is 0.3. Suppose that the coin is tossed twice and that the results of the tosses are independent.
i) What is the probability of obtaining exactly two heads?
ii) What is the probability of obtaining exactly one head?
iii) What is the probability of obtaining no heads?
iv) What is the probability of obtaining at least one head?
e) Prove that for all integers n ≥ 2, P(n + 1, 2) − P(n, 2) = 2P(n, 1).
f) Three officers—a president, a treasurer, and a secretary— are to be chosen from among four people: Ann, Bob, Cyd, and Dan. Suppose that Bob is not qualified to be treasurer and Cyd’s other commitments make it impossible for her to be a secretary. How many ways can the officers be chosen? Can the multiplication rule be used to solve this problem?