CS-07 : DISCRETE
MATHEMATICS JUNE 1999
| Time: 3 Hours |
Max. Marks: 75 |
Note: Question no. 1 is compulsory. Answer any three from the rest
| 1. | (a). | Establish the equivalence |
| (P v Q) => R = (P => R) n (Q => R) | ||
| (b). | Express P => Q in terms of {7, v) only. | |
| (c). | Let A be a subset of a set B. Express this fact in Predicate calculus. | |
| (d). | Let x, y e N, the set of natural numbers. A relation R is defined in N as follows : | |
| x R y if and only if x + 3y = 12. | ||
| Determine whether R is | ||
| (i) reflexive | ||
| (ii) symmetric | ||
| (iii) anti-symmetric. | ||
| (e). | Define complement union and intersection of fuzzy subsets of a given set X . Support each of your definitions with one example. | |
| (f). | A graph G has the following adjacency matrix. Check whether it is connected. | |
A(G) =
![]() |
||
| (g). | Find a minimal spanning tree for the connected weighted graph given below : | |
![]() |
||
| (h). | Fill in the blanks : | |
| (i) Let G be a graph in
which the degree of every vertex is al least two. Then G contains a ................... . |
||
| (ii) A connected graph G is
Euler if and only if the n >= 3, and the degree d(y) >= n/2 for every vertex v of G, then G is .................. . |
||
| (iii) If G is a simple graph
with n vertices where n >= 3, and the degree d(y) >= n/2 for every vertex v of G, then G is ................. . |
||
| (iv) Use Karnaugh map
representation to find sum-of-products expression for the boolean functions : |
||
| f{x, y, z, w} = S {4, 5, 6, 7, 13, 15} | ||
| (g). | Design a circuit that accepts a three-bit number and gives an output 0 if the input represents an even decimal number and gives an output 1 if the input represents an odd number. | |
| 2. | (a). | Translate the following english sentences into corresponding Propositional/Predicate formulae : |
| (i) If eitheer housing is
scarce or people or people like to live with their in-laws, and if people do not like to live with their in-laws, then housing is scarce. |
||
| (ii) Some mathematicians are not good at computer science. | ||
| (b). | Obtain the Principal Distributive Normal Form of 7 P v Q. | |
| (c). | For the given set of premises | |
| P <-> Q, R v 7S, Q -> s and 7P -> R, | ||
| determine the validity of the following conclusion | ||
| C : R | ||
| 3. | (a). | Describe a going network corresponding to the statement formula : |
|
|
||
| (b). | Show that the set {7, => } of logical operators is functionally complete. | |
| (c). | In a group of 50 foreign tourists. 30 tourists can understand Hindi and 25 understand Tamil. Ten tourists understand neither Hindi nor Tamil. How many tourists understand both Hindi and Tamil ? | |
| 4. | (a). | Write down the permutation |
![]() |
||
| as a product of disjoint cycles and then express it as a product of transpositions. | ||
| (b). | Use the fusion algorithm to determine whether the graph specified by the following adjacency matrix is connected or not. | |
![]() |
||
| Find the product G1 x G2 of the two graphs G1 and G2 given below : | ||
![]() |
||
| 5. | (a). | Apply Dijkstra's Algorithm to find the shortest path from s to t in the graph given below : |
![]() |
||
| (b). | Carry out the two optimal algorithm on the following complete weighted graph for the travelling salesman problem. | |
| 6. | (a). | Show that the poset with the Hessa diagram given below is not a lattice. |
![]() |
||
| (b). | Prove that in every lattice with a lower bound an atom is join irreducible. | |
| (c). | Draw circuit diagram for Half-Adder module.s |