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

ADCA / MCA (II Yr)
Term-End Examination

December, 2005

CS07 (S): Discrete Mathematics

Time: 3 hours
Maximum Marks: 75

1. (a) Write the following formula in principal conjunctive normal form (Q => ⌉P) ^ (P v R). (4)

(b) Consider the following graph :
-----DIAGRAM-----
(i) ldentify a cut vertex in the graph. lf you remove the vertex, how many connected components will be there in the resulting graph ? (2)
(ii) Why is the graph non-Eulerian ? How can you make this graph Eulerian by removing an edge and adding a new edge ? (2)

(c) Define a relation R on the set of natural numbers as follows:
aRb if l a-b l < 3.
(i) Is R reflexive ?
(ii) ls R symmetric ?
(iii) ls R transitive ?
Give reasons for your answers. (3)

(d) Draw the Hasse diagram of the poset ({{1 , 2 , 3 , 4}, {1 , 2}, {1,3}, {1 , 2 , 3}, {1}}, €)
Check whether the poset is a lattice or not. (4)

(e) Let P : The electricity meter is faulty.
Q : The electricity charges are high
R : The consumers will complain about the bills.

Write the following staiements using logical symbols
(i) If the electricity meter is faulty and the electricity charges are high, the consumers will complain about the bills.
(ii) lf the consumer do not complain about the bills, either the electricity meters are not faulty or the electricity charges are not high. (4)

(f) Consider the following complete weighted graph :
-----DIAGRAM-----
Starting from the cycle v₁ v₂ v₃ v₄ v₅ v₁ apply the two-optimal algorithm to get a Hamiltonian cycle of weight less than 10. (4)

(g) Consider the binary operation * defined on the set of integers by a * b = a + b - ab. Check whether

(h) State the two distributive laws for lattices. Verify the laws for the elemenls 3,5 and 9 of the lattice (D(45), g.c.d, l.c.m) (3)

2. (a) Check, using truth tables, whether the following statemens are consistent:
"If the dog bark at Ram, Ram is a stranger."
"lf the dog doesn't bark at strangers, the dog does not bark at Ram."
"lf Ram is not a stranger, the dog barks at Ram." (7)

(b) Find a Minimum Spanning Tree graph using Kruskal's algorithm. (5)
-----DIAGRAM-----

(c) Let A = {1, 2, 3, 4}, B = {3, 4, 5, 6, 8}, C = {6, 8, 10. 12, 16, 18}. Let f : A -> B be defined by f(x) = x + 2, and g : B -> C be defined by g(x) = 2x. Find gof. Check whether gof is injective and surjective. (3)

3. (a) Construct a finite state machine that takes as input '0' and '1', and gives '1' as output if and only if it gets two '1's followed by a '0' as input. (7)

(b) Fill in the missing terms in the following table : (4)

(c) Let U = {a, b, c, d, e, f}, A = {a, b, c, d, e}, B = {a, d, e}.
(i) State the DeMorgan's laws and check them for A and B.
(ii) If C = {x l x is a letter in the word 'red'}, is B = C ? Give reasons for your answer. (4)

4. (a) check that B = {1, 2, 3}, {1, 2}, {3} , Ø } is a Boolean subalgebra of (P({1,2,3}), ∩, U. What are the atoms and anti-atoms in B ? (4)

(b) 300 computer users were asked if they have upgraded their computer after they bought them. 120 people said they have increased the RAM, 80 people said they have added a CD-writer, 60 people said they have added another hard disk, 20 people said they have increased the RAM and added a CD-writer, 15 said they have added RAM and an additional hard disk, 10 said they have added a CD-writer and added an additional hard disk, 5 have carried out all the three upgradations.

(i) How many people increased the RAM alone ?
(ii) How many people haven't upgraded anything ?
(iii) How many have added a hard disk, but not a CDwriter ? (7)

(c) Use the breadth first search algorithm to find the length of the shortest path from v₁ to each of the other vertices in the following graph. Also, find the length of the shortest path from v₁ to v₈. (4)
-----DIAGRAM-----

5. (a) Let C(x, y) mean that student x has registered for the course y, where the universe of discourse for x is the set of all MCA students of IGNOU and the universe of discourse for y is the set of all courses offered in the MCA programme. Rewrite each of the following statements in words :
(i) (C(Fahim, CS-07) ∧ ⌉C(Fahim, CS-60))
(ii) ∃x (C(x, CS-60) ∧ C(x, CS-07))
(iii) ∃y C(Shalini, y)
(iv) ∀x (C(x, CS-60) v C(x, CS-07)) (4)

(b) Find the binary tree representation of (x + 6y).xy. (4)

(c) Use the Karnaugh map to simplify the following expression:
x₁xbar₂x₃xbar₄ + x₁xbar₂xbar₃xbar₄ + x₁x₂xbar₃x₄ + x₁x₂x₃xbar₄ (7)