Andhra University
MCA - 1101 (2015/I/02)

MCA Degree Examination
First Year - First Semester

DISCRETE MATHEMATICAL STRUCTURES

(Effective from the admitted batch of 2000-2001)

Time: Three hours
Maximum: 75 marks

Answer any FIVE questions.
First Questions is compulsory.
It comprises of seven sub-questions.
Each of the remaining questions carries 15 marks.

1.
a. Define ordered pairs. Give examples for a relation which is reflexive and transitive but not symmetric.
b. What is tautology? What is absurding?
c. Define a lattice and give examples.
d. How many integers between 1 and 1000 have sum of digits equal to 7.
e. Define bipartite graph.
f. What is Dual graph and Chromatic number of a path graph.
g. Define a finite state machine.

2. a. Show that if (A B) C = (A C) (B C)

b. For the poset (I₁₅:/) draw a poset diagram and determine all maximal and minimal elements and greatest and least elements, if exists.

3. Show that in Boolean Algebra
i. (a+b)' = a' + b'
b. (a.b) + [(a+b)' . b ]' = 1

4.
a. Obtain the principal disjunctive and conjunctive normal forms of ( P -> (Q R )) [ ~ P -> (~Q R ))

b. Show that: [(p q) ~ (~p (~q ~r))) (~p ~q) (~p ~r) is a tautology.

5.
a. In how many ways can 30 distinguishable books be distributed among 3 people A,B and C so that
i. A and B together receive exactly twice as many books as C
ii. c receives at least 2 books; B receive at least twice as many books as C and A receive at least 3 times as many books as B.

b. Solve the recurrence relation: a_n - 7a_n-1 + 10a_n-2 = 0 for n => 2

6.
a. Show that the following graphs are isomorphic:

b. Differentiate between Eulerian path, Hamiltonian Path and Spanning tree.

7.
a. Find the minimal spanning tree of the following graph

b. Prove that a tree with n vertices has exactly (n-1) edges.

8.
a. Write the differences between Mealey and Moore machines.
b. Define a sequential machine. Let s be any state in a sequential machine and x and y be any words, then prove that (s,xy) = (s,x), y) and (s,xy) = ( (s,x),y)