Test Papers / Previous Question Papers of IGNOU CS07 Discrete Mathematics June 2005

ADCA / MCA (II Yr)
Term-End Examination

June, 2005

CS07: Discrete Mathematics

Time: 3 hours
Maximum Marks: 75

1. (a) (a) Which of the following are statements ? Give reasons for your answer. (4)
(i) What a lovely day ! (ii) 2 + 3 = 6 (iii) 2 + x = 7 (iv) What is the time now ?

(b) Give an example of a finite linearly ordered set. You have to verify all the properties of a linearly ordered set for your example. (4)

(c) Find the product G₁ x G₂ of the following graphs :
-----DIAGRAM-----
Give a cycle of length 6 in G₁ x G₂, if one exists (4)

(d) Let U = {1, 2, 3, 4, 5, 6,7}, A = {1,2 ,7}, B = {1, 2, 3, 4, 5}, C = {4, 6, 7}.
(i) Findnd A-B and B-C.
(ii) Check that (A U B) ∩ C = (A ∩ C) U (B ∩ C).
(iii) State and verify any one of the De Morgan's laws for A and B. (4)

(e) Write the equivalent form of the following using Predicate Calculus : (4)
(i) Every MCA graduate knows either C++ programming of Java programming.
(ii) There are web programmers who know PERL but not PHP.

(f) Let A = {1, 2, 3} and R₁ and R₂ be relations on A given by
R₁ = {(1, 1), (1, 2), (2,3)}
R₂ = {{1, 3), (2, 1), (1, 1), (3, 1)}
(i) Write the relation matrices of R₁ and R₂.
(ii) Find the relation matrix of R₁R₂.
(iii) Check wheiher R₁R₂ is an equivalence relation. (3)

(g) For the lattice (D(231), g.c.d., l.c.m.) draw the Hasse diagram. Also check that the lattice is complemented. (3)

(h) Find the diameter and radius of the following graph : (4)
-----DIAGRAM-----

2. (a) Determine if the following system specifications are consistent using a truth table. (6)
'The diagnostic message is stored in the buffer or it is retransmitted'
'The diagnostic message is not stored in the buffer'
'If the diagnostic message is stored in the buffer it is retransmitted'

(b) Let f = 1  2  3  4  5 and
	       2  3  1  5  4
g = 1  2  3  4  5
     3  4  2  5  1

(c) Find the binary tree representation of (x + y) (7x - xy). (4)

3. (a) The adjacency rnatrix of a graph G is

				0  0  1  1  0
				0  0  1  1  1
			  A = 1  1  0  0  1
				1  1  0  0  0
				0  1  1  0  0

(b) Check that (P v Q) ⇔ (⌉P ⇒ Q) is a tautology. (5)

(c) Draw the switching circuit corresponding to the function ((x + y) . (yz)) + (x+z). (4)

4. (a) ln a survey, 80 Computer Science teachers were asked which of the three programming languages, Pascal, Fortran and C, have they used to introduce programming to students- 40 teachers said they have used Pascal, 35 said they have used Fortran, 25 said they have used C, 20 said they have used both Pascal and Fortran, 17 said they have used Pascal and C, 5 said they have used Fortran and C, and 3 said they have used all the three languages.

(i) How many teachers have used Fortran alone ?
(ii) How many teachers have used both Pascal and C ?
(iii) How rnany teachers have used Fortran, but not C ?
(iv) How many used none of the three languages? (6)

(b) Apply Dijktra's algorithm to find the shortest path between a and Z in the following weighted graph. (7)
-----DIAGRAM-----

(c) Express (P ^ Q) v (Q ^ R) in disjunctive normal form. (2)

5. (a) Simplify the following boolean expression using a Karnaugh map : (7) x₁x₂x₃xBAR;₄ + x₁xBAR₂x₃x₄ + xBAR₁xBAR₂x₃x₄ + xBAR₁x₂xBAR₃x₄ + x₁x₂xBAR₃xBAR₄

(b) Write -92 and 120 in 1's complement and use this to find 120 - 92 in 1's complement form. (3)

(c) Let X = {1, 2, 3, 4, 5, 6}.
A = {0/1, 0.4/2, 0.3/3, 0.5/4, 0.1/5, 1/6}
B = {0.1/1, 0.3/2, 0.1/3, 0.1/4, 0.2/5, 0.1/6}