B3.2-R4 Page 1 of 4 January, 2018
B3.2-R4: DISCRETE STRUCTURE
NOTE:
Time: 3 Hours Total Marks: 100
1.
Find the power set of given that
Let the number, N where b is the smallest possible base for it. Convert
N into the bases of binary, octal, decimal and hexadecimal.
Let the two words, u a2ba3b2 and bab2. Find:
uv and and
ii) v2 and
Consider the language L over the set, A c}.
Find L0; L3; L−2.
Let a 233554(11)6 and b 255372 (13)2. Find:
gcd(a, and
ii) lcm(a, b).
Prove that K5 is not a planar graph.
Let G be the directed graph given below:
Describe G formally.
ii) Find all cycles in G.
iii) Is G unilaterally connected?
iv) Is G strongly connected?

2.
Let R and S be the relations on A given by
R
Find:
R
ii) Is
Prove by mathematical induction that, for all n 1
1 4 7 · · · (3n − n(3n −
If the order of groups G and H are relatively prime, then show that their
intersection contains only the identity.

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 4 January, 2018
3.
Let and r be the propositions:
'Grizzly bears have been seen in the area',.
'Hiking is safe on the trail' and
'Berries are ripe along the trail'.
Write the following propositions using and r and logical connectives (include
negations).
Grizzly bears have not been seen in the area and hiking on the trail is
safe, but berries are ripe along the trail.
ii) It is not safe to hike on the trail, but grizzly bears have not been seen in
the area and the berries along the trail are ripe.
ii) For hiking on the trail to be safe, it is necessary but not sufficient that
berries not be ripe along the trail and for grizzly bears not to have been
seen in the area.
iv) Hiking is not safe on the trail whenever grizzly bears have been seen in
the area and berries are ripe along the trail.
Let and be the statements "x is a baby," "x is logical," "x is
able to manage a crocodile," and "x is despised," respectively.
Suppose that the domain consists of all people. Express each of the following
statements using quantifiers; logical connectives; and and
Babies are illogical.
ii) Nobody is despised who can manage a crocodile.
iii) Illogical persons are despised.
iv) Babies cannot manage crocodiles.
Does statement follow from the statements and in the above
Part If not, is there a correct conclusion?

4.
Prove that the following statements are inconsistent:
"If Miranda does not take a course in discrete maths, then she will not
graduate".
"If Miranda does not graduate, then she is not qualified for the job."
"If Miranda reads this book, then she is qualified for the job."
"Miranda does not take a course in discrete Mathematics but she reads this
book."
Messages are transmitted over a communications channel using two signals. To
transmit one signal it requires 1 minute, whereas the other signal requires 2
minutes.
Find a recurrence relation for the number of different messages consisting of
sequences of these two signals, where each signal in the message is
immediately followed by the next signal that can be sent in n-microseconds.
ii) What are the initial conditions?
iii) How many different messages can be sent in 10 ms using these 2 signals?

B3.2-R4 Page 3 of 4 January, 2018
5.
In MERGE SORT algorithm, if we are given two sorted lists, LIST1 with n
elements and LIST2 with m elements, what is the maximum number of
comparisons required to merge these two lists into a single sorted list?
Let N . . be ordered by divisibility. State whether each of the following
subsets of N are linearly (totally) ordered?

ii) 15,
iii) 32,
iv) 30}.
Consider the multi graphs shown in the figure below:
Which of them are connected? If not connected, find its connected
components.
ii) Which are cycle-free (without cycles)?
iii) Which are loop-free (without loops)?
iv) Which are (simple) graphs?

6.
Let and f S × S × S be a Boolean function given by
Using a Karnaugh map, simplify the Boolean expression corresponding to
the function, f.
ii) Draw a gate implementation for the above simplified Boolean expression
in Part a).
Find a deterministic finite state machine whose state/transition table is given
below:
0 1 2
A A C B
B D E
C E
D D E
E D D
Here, final states are C and the initial state is and alphabet 2}.

B3.2-R4 Page 4 of 4 January, 2018
7.
Use Kruskal's algorithm to find a minimal spanning tree for the following weighted
graph. What is the total weight of the minimal spanning tree? Draw the minimal
spanning tree.
Let A and a relation R on A be given by
R
Draw the digraph of R.
ii) Is R an equivalence relation? Justify your answer.
Let B and R be a binary relation on defined by
∈ R iff C ⊆ D
Show that R is a partial order relation,
ii) Draw Hasse diagram for the relation and
iii) Give the least element and the greatest element, if they exist.