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