No. of Printed Pages: 3 IBICS-OOSI
B.Tech. -VIEP -COMPUTER SCIENCE AND
ENGINEERING (BTCSVI)
Term-End Examination

OOE.gE. June, 2016
Slcs-ooa DISCRETE MATHEMATICAL STRUCTURES
Time: 3 hours Maximum Marks: 70
Note: Attempt any seven questions. All questions carry equal marks. All the questions are to be answered in English only.

1. A software company requires 60 engineers to perform Java programming jobs and 35 engineers to perform programming jobs. Also 15 engineers are required to perform both types of jobs. How many engineers are to be appointed for the purpose? 5

Let A be a set of real numbers. Then show that the relation

R a a,b E
is an equivalence relation. 5

2. Define one-one and onto functions. Give an example of a function which is one-one but not onto. Also write a function which is onto but not one-one. 5

Use mathematical induction to prove that 5n is divisible by for all natural numbers n. 5

3. Show that the intersection of two subgroups of a group G is again a subgroup of G. Give an example to show that the union of two subgroups of a group G need not be a subgroup of G. 6

Define ring and field with examples. 4

4. Show that the order of every subgroup of a finite group divides the order of the group. 6

Prove that every group of prime order is cyclic. 4

5. Find the truth table for a circuit whose Boolean sum-of-product expression is 5

Find the Boolean expression corresponding to the truth table =00010001. 5

6. Design a three-input-minimal AND-OR circuit with the following truth table 10

T L [00001111,00110011,01010101,11001101].

7. Constructing a truth table, test the validity of the following argument: 10

If I study, I will not fail in Maths.

If I do not watch cricket, then I will study.

But I failed in Maths.

I must have watched cricket.

8. Construct truth tables for the following: 5+5

V A A

A q)V r

9. Solve the recurrence relation: 10

an =2an-l n 2 with a0 a1 =4.

10. Write short notes on any two of the following: 5+5

Bipartite Graphs

Planar Graphs

Euler and Hamiltonian Paths