B3.2-R4: DISCRETE STRUCTURE
«QP_SRLNO»
NOTE:
Time: 3 Hours Total Marks: 100
1.
Using the set identities or Venn diagram show that C A U C).
Find the probability, that a family with five children does not have a boy, if the sexes of children
are independent and if the probability of a boy is 0.51.
In how many ways can three disciplinary subjects be selected from the two groups of 6 subjects
each, if at least one subject must be selected from each group?
Let f be a function from x is real and x to x is real and x given by
Find f-1.
Find whether the following Propositional formula is a Tautology, Contradiction or else: You may
use truth table.
Let A x ∈ R x 2 and B x ∈ x 1}. Define A B and B A by

Find o
ii) Are f and g inverses? Explain
Find a grammar that generates the language {anbn n .

2.
Prove by mathematical induction, that the Fibonacci number F3n is divisible by 2.
Define the relation R on the set by aRb if is a nonnegative even integer. Verify that R
defines a partial order. Is this partial order a total order?
Find the domain and range of the following function of a real variable:
x

3.
Define the asymptotic notation O Big and (Omega) used to describe the
asymptotic running time of algorithm.
ii) Prove the following identities:
6n2 (log n O (n2
log( n n log(n)
Define on Z by a b if and only if 3a b is a multiple of 4.
Prove that defines an equivalence relation.
ii) Find the equivalence class of 2.
Show the steps of merge sort algorithm applied to the list: 3.

4.
Use mathematical induction to prove that for the recurrence relation bn= bn-1 2bn-2, b2=
we have, bn
Let n be a positive integer and let Dn be the set of all positive divisors of n. Draw the Hasse
diagrams for D30. Determine whether the Hasse diagram represents a lattice giving reason?
Let and let R and S be relations on A whose matrices are
MR
1 0 1
1 1 1
0 1 1
and MS
1 0 0
0 1 1
1 0 1

Find MSoR and show that MSoR MR MS

1. Answer question 1 and any FOUR from questions 2 to 7.
2. Parts of the same question should be answered together and in the same sequence.
B3.2-R4 Page 2 of 2 July, 2017
5.
In a gathering of 30 people, there are 104 different pairs of people who know each other. Show
that some person must have at least seven acquaintances.
How many graphs are there on 4 nodes with degrees
Prove that a planar graph on n nodes has at most 3n-6 edges.

6.
Twenty varieties of chocolates are available and Shagun wants to buy eight chocolates. How
many choices does she have if his brother insists that at least one chocolate should have a
cherry center?
Find the minimal sum-of products forms for the Boolean function:

Design a finite state machine having an output of 1 exactly when the input string received to
that point ends in 101, assuming that the alphabet=

7.
Define group. Show that every group need not be abelion.
What do you mean by order of an element of a group? Find the order of each element of the
group G with binary operation: addition module 6.
State Lagrange's theorem and use it to show any group of prime order have no proper
subgroup.