Acharya Nagarjuna University (ANU) 2006 B.Sc Information Technology I - Discrete Mathematics - - Question Paper
B. Sc. IT, 1st Year Degree Examination, December 2006
Paper I - Discrete Mathematics
(DSDM 11)
B.Sc. IT, First Year DEGREE EXAMINATION, DECEMBER 2006 Paper I - DISCRETE MATHEMATICS Time : Three hours Maximum : 100 marks
Answer any FIVE questions.
All questions carry equal marks.
1. (a) If A and B are finite sets, then show that A'-jB Ar>B are finite and
h(A<jB) = n(A) + n(B) -n(Ar\B).
(b) If A, B and C are finite sets, then show that (iu5u C) = r;(A) + r?(5) + tf(C) n(Ar\B) n(Ar\C) - n(B nC) + ri(ArBr\C)
2. (a) Show that the propositions ~\(p n q) and|v "I? are logically equivalent.
(b) Prove that wC, 4 hCh =fl'1 Cr.
3. {a) Show that the symmetric functions form a Boolean algebra.
(b) Express each Boolean expression E(x,y,z) as a sum-of-products and then in its complete sum-of products form:
(i) E = + xy + yz)
(ii) E = z(x + j') + y
4. {a) Solve the recurrence relation -7a_, = 0 for H > 2 with a0 = 10 and a- =41.
(b) Show that in a lattice with two or more elements, no element is its own complement.
5. {a) Show that the two graphs are not isomorphic with an example.
(b) Explain Kruskals algorithm forfinding a minimal spanning tree.
6. {a) How many different directed trees are there with three nodes? How many different ordered trees are there with three nodes?
(b) Show that in a complete binary tree the total number of edges is given by 2(rcr -1), where rcr is the number of terminal nodes.
7. (a) Show that A xB = BxA o(A = $)v(B = d)v(A = B)
(b) Prove that AnB x (CnD) = (A x C)n(Bx D)
8. Given A = {1,2,3,4}. Consider the following relation in A.
J! = {ai)(2s2),C2,3)C3,2X4s2)C4,4)J
(a) Draw its Directed graph.
(b) Is R (i) reflexive (ii) symmetric (iii) transitive or (iv) antisymmetric?
(c) Find = R0R .
9. Give A ={1,2,3,4}
B = {*,>, z}. LetR be the following relation from A to B : R = {(1, v)(l, z)(3,j)(4,i)(4,z)}. {a) Determine the matrix of the relation.
(b) Draw the arrow diagram of R.
(c) Find the inverse relation or R.
(d) Determine the domain and range of R.
10. (a) Draw all possible nonsimilar trees T where:
{]) T is a binary tree with nodes
{ii) T is a 2-tree with four external nodes.
(b) Suppose a graph G is presented by the following table G = [A:B,C:B C.DC.C; D:BiE:<p]
(i) Find the number of vertices and edges in G.
{ii) Are there any sources or sinks?
{iii) Draw the graph of G.
{iv) Is G weakly connected? Unilaterally connected? Strongly connected?
|
Attachment: |
| Earning: Approval pending. |
