Andhra University
MCA - 1101 (2345/I/01)

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. In a complemented distributive lattice show that (a*b)' = a' b'
b. Show that ((P Q) ( P ( Q R))) ( P Q) ( P R) is a tautology

c. How many proper subsets of {1,2,3,4,5} contain the numbers 1 and 5?

d. Write the characteristic equation of the recurrence relation D(k) - 8D(k-1) + 16D(k-z) = 0 where D(2) = 16, D(3) = 80

e. Show that in any graph the sum of the degrees of all the vertices is always even.

f. Define a cut point of a graph and illustrate with an example.

g. Show that every finite semigroup has an idempotent.

2.
a. Show that in a lattice if a < = b and c < = d then a*c < = b*d

b. In any Boolean algebra, show that a < = b = > a + bc = b(a+c)

3.
a. Obtain the sum of the products canonical from of the Boolean Expression (x₁ x₂)' (x₁' * x₃)

b. Prove that (A B) (A ~B) = A and A (~A B) = A B where A,B are any two sets.

4.
a. Let T = {1,2,3,4,5}. How many subsets of T have less than 4 elements?

b. Show that ( x) M (x) follows logically from the premises (x)(H(x) -> M(x)) and ( x) H (x)

5.
a. List all possible functions from X = {a,b,c} to Y = {0,1} and indicate in each case whether the function is one-to-one, is onto and is one-to-one onto.

b. Obtain simplified Boolean expression for the equivalent expression m₀ + m₁ + m₂ + m₃ where 'm_j's are the minterms in the variables x₁, x₂, x₃ and x₄.

6. Design a parity-check machine which is to read a sequence of 0's and 1's from an input tape. The machine is to output a 1 if the input tape contains an even number of 1's or 0 otherwise.

7.
a. Prove that there is a unique path between any pair of vertices in a tree and coverage.

b. Prove that in any tree there are at least two pendant vertices

8.
a. Prove that every circuit has an even number edges on common with any cut-set.

b. Explain Dijkstra's algorithm for finding the shortest path between any pair of vertices in a graph.