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

ADCA / MCA (II Yr)
Term-End Examination

December, 2005

CS07 : Discrete Mathematics

Time: 3 hours
Maximum Marks: 75

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

(b) Consider the following graph :
-----DIAGRAM-----
(i) Is there a cut vertex in this graph ? Justify your answer.
(ii) Is the graph Eulerian ? Justify your answer.
(iii) Is there an odd cycle in this graph ? Justify your answer.
(iv) How many multiple edges are there in this graph ? (4)

(c) Consider the relation R defined by aRb if l a - b l > 2 on the set of natural numbers N.
(i) Is it reflexive ?
(ii) Is it symmetric ?
(iii) Is it transitive ?
Justify your answers. (3)

(d) Draw the Hasse diagram of the Poset
({{1, 2, 3}, {1}, {2}, {1, 3}, {2,3}}, ≤).
Also check whether this poset is a lattice. (4)

(e) Let
P : The dog barks at strangers.
Q : The dog barks at Ram.
R : Ram is a stranger.

Write the following statements using logical symbols.
(i) If the dog barks at strangers and the dog does not bark at Ram. then Ram is not a stranger.
(ii) If the dog doesn't bark at Ram, then either the dog doesn't bark at strangers or Ram is not a stranger. (4)

(f) Draw the graph with its adjacency matrix :

0  2  1  0
2  0  1  0
1  1  0  1
0  0  1  0

Also find the incidence matrix of the graph. (4)

(g) Consider the operation *, defined on the set of integers by
a * b = a + b - 1 .
Check whether
(i) * is a binary operation.
(ii) * is associative.
(iii) * is commutative.
Is there an identity element with respest to this operation ? Justify your answer. (4)

(h) Consider the lattice (D(45), g.c.d., l.c.m.).
(i) What are the atoms in this lattice ?
(ii) What is the complement of 5 ?
(iii) Is this lattice complemented? Why ? (3)

2. (a) Check, using truth tables, whether the following statements are consistent : (7)
"lf the electricity meter is faulty, the electricity bills are high."
"lf the consumers complain about electriciiy bills, electricity meters are faulty"
''lf the electricity bills are not high, consumers will not complain about bills."

(b) Draw a graph with vertex set V = {v₁, v₂, v₃, v₄, v₅} and such that d(v₁)= 2, d(v₂)= 2. d(v₃)= 4, d(v₄) = 1, and d(v₅) = 1. Is there a tree with given vertex set v and given degrees ? Justify your answer. (5)

(c) Let U = {1, 2, 3. 4, 5, 6, 7, 8, 9}, A = {2, 5, 6, 7}, B = {1, 2, 5, 8}, C = {3, 4, 5, 7, 9}
(i) Find A Δ B and A Δ C.
(ii) Check whether
A U (B ∩ C) = (A U B) ∩ (A U C) (3)

3. (a) Construct a finite state machine that takes as input 0 and 1 and outputs 1 if and only if the last 3 inputs received are 1. (7)

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

(c) Let X = {a, b, c, d, e} and let A and B be fuzzy sets given by
A = {a/0.1, b/0.2, c/0, d/0.1, e/0.4} and
B = {a/0.2, b/0.3, c/0.5, d/0.3, e/0.2}
State the DeMorgan's Laws and check them for the sets A and B. (4)

4. (a) Check whether B = {1, 2, 15, 30} is a subalgebra of (D(30), g.c.d., l.c.m.). Define a join irreducible element in a lattice. Give an examle of a join irreducible element in B. (4)

(b) A survey was conducted to get information regarding the viewership of 3 television programmes - a comedy serial, a detective serial and a quiz programme. Out of 500 people that took part in the survey, 300 People said they watched the comedy serial, 270 people said they watched the detective serial, 180 people said they watched the quiz programme, 150 people said they watched both the comedy serial and the detective serial, 80 said they watched both the comedy serial and the quiz programme and 60 said they watched both the detective serial and the quiz programme. Also, 30 people watched all the three programmes.

(i) How many watched none of the three programmes ?
(ii) How many watched the comedy serial alone ?
(iii) How many watched the detective serial and the quiz programme, but not the comedy serial ? (6)

(c) Find a minimum spanning tree in the following graph using Prim's algorithm, starting from the vertex v₁. (5)

5. (a) Determine the validity of the conclusion from the given set of premises
[A ⇒ (B ^ D), (B v D) ⇒ E, D v A] with the conclusion : E (5)

(b) Find the shortest path from v₁ to v₆ in the following graph using Dijkstra's algorithm : (6)
-----DIAGRAM-----

(c) Represent the following circuit as a gating network and calculate the corresponding Boolean expression : (4)
-----DIAGRAM-----