CS-07 : DISCRETE
MATHEMATICS DEC 1999
| Time : 3 Hours |
Max. Marks : 75 |
Note : Question number 1 is compulsory. Answer any three
from the rest.
| 1. | (a). | Check whether the following equivalence is valid or not : |
| ((P ^ Q) => R) = (P => R) ^ (Q =>R) | ||
| Explain why or why not. | ||
| (b). | Obtain Principal Disjunctive Normal Form for (7P V Q) | |
| (c). | Determine the validity (or invalidity) of the following argument : | |
| The conclusion Q follows from the following premises P, 7S and [(P =>Q) => R]=> S | ||
| (d) | A graph G has the following adjacency matrix. Check whether it is connected : | |
| A(G)= | ||
| (e) | Write down either Prime algorithm or Kruskal's algorithm for finding minimal spanning tree for a given connected graph. | |
| (f) | A relational R is defined on I, the set of
integers by 'aRb if and only if ab > 0 for all a, b belongs to I'. Find
whether R is (i) Reflexive (ii) Anti-symmetric (iii) Transitive. |
|
| (g) | Let the function f: R |
|
| f(x) = | ||
| Find out f-1(5). | ||
| (h) | Let X = { 1, 2, 3 } Y = {6, 7, 8, 9} Defined a fuzzy relation R from X to Y such that for x belongs X and y belongs Y, the strength of relation xRy is given by 1/(x2 + y) |
|
| (j) | Draw Hasse diagram of all lattices of exactly five elements. | |
| (k) | Use Karnaugh map representation to find a minimal sum of products expression for the boolean expression f(x, y, z, u) = S (0, 2, 4, 6). | |
| 2. | (a) | Translate the following into
Propositional/Predicate Calculus : (i) Sum of two positive integers is greater than either of the integers. (ii) For some irrational numbers x and y, the number xy, is a rational number. (iii) Americans will stop driving big cars only if there are comfortable small cars. (iv) Couple's only surviving child is a male. |
| (b) | The logical binary operation NAND denoted
by
|
|
| (P |
||
| Show that the set of binary operations { |
||
| 3. | (a) | Apply Dijkstra's Algorithm to find the shortest path from A to G in the graph given below : |
| The numbers along edges are weights. | ||
| (b) | Using Two Optimal Algorithm or The Closet Insertion Algorithm (mention explicitly the one you are using) construct a Hamiltonian cycle of minimum weight for the following weighted graph. | |
| 4. | (a) | In a class of 100 students, 10 students have opted both Mathematics and History, 20 students opted neither History nor Mathematics. Further, number of students in History is less than number of students in Mathematics. Find number of students opting History and number of students opting Mathematics. |
| (b) | For a relation R on a set A = { 1, 2, 3, 4, 5} given by R = { (1, 3), (1, 2), (2, 2), (3, 4)}, find reflexive closure, symmetric closure and transitive closure of R on the given set A. | |
| (c) | Explain the concept of Totally Ordered Set and Well-Ordered Set alongwith suitable examples. | |
| 5. | (a) | For the following two permutations |
| f = and
g= |
||
| find the product f . g and express f and g each as product of cycles. Then express each of f and g as product of transpositions. | ||
| (b) | In the context of fuzzy sets, define the following concepts and further illustrate each with suitable examples: | |
| (i) Union (ii) Intersection (iii) Containment (iv) a-cut or a -level set (v) Support (vi) Normal |
||
| (c) | what is a sequent? When is a sequent said to be true ? When is a sequent said to be true ? When is a sequent said to be an axiom. | |
| 6. | (a) | If (L,<=) is a lattice, then for a, b, c belong to L, prove that a<=c<=>a v (b^c) ?<= (a v b) ^ c |
| (b) | Let si and ci+1respectively denote the ith sum bit and (i+1)th carry-bit obtained by binary addition of three bits xi, yi and ci. Represent by truth-table si and ci+1 as function of xi, yi and ci. Further draw full-adder circuit as obtained from the truth-table. | |
| (c) | Simplify the following expressions -6 + 13 and (-6) + (-13) | |
| using 5-bit 2's complement arithmetic. Explain reason for surprises, if any. |