DISCRETE STRUCTURE

DISCRETE STRUCTURE
SEM-III, 2011-12
B.TECH EXAMINATION
UTTARAKHAND TECHNICAL UNIVERSITY
utu previous year question paper

Time: 3 Hours

Total Marks:100

Note: Attempt all questions. Be precise in your answer.

Attempt any four of the following:

1. For any two sets A and B, prove that following:
   (i) (A ᴗ B)^C = A^C ᴖ B^C
   (ii) (A ᴖ B)^C = A^C ᴗ B^C
2. Let A be the set {1, 2, 3}, define the following types of binary relation on A.
   (i) A relation that is both symmetric and antisymmetric
   (ii) A relation that is neither symmetric nor antisymmetric.
3. Let f : A→ B and g : B→ C be two invertible mapping then prove
   (i) gof is invertible
   (ii) (gof)^-1 = f ^-1og ^-1
4. Prove by induction method that if n ≥ 10, then 2ⁿ > n3.
5. Prove that contradiction that √5 is irrational.
6. Prove that the intersection of two equivalence relation is also an equivalence relation, but the union of two equivalence relation may not be an equivalence relation.

Attempt any four of the following:

1. Show that the set N of natural number is semigroup under the operation x * y = max {x, y}. Is it a monoid?
2. Show that in a group ‹G, *›, if for any a,b Є G, (a * b)² = a² * b², then ‹G, *› must be abelian.
3. If an abelian group has subgroups of orders m and n, then show that it has a subgroup whose order is the least common multiple of m and n.
4. Show that every subgroup of a cyclic group is normal.
5. What are permutation groups? Explain by taking a suitable example.
6. Prove that if a, b Є R where ‹R,+,.› is a ring, then (a + b)² = a² + a .b + b. a + b² where a²=a. a.

Attempt any two of the following:

1. Draw the Hasse diagrams of the following sets under the partial ordering relation "divides", and indicates those which are totally ordered.
   (i) {2 , 6 , 24}
   (ii) {3, 5 ,15}
   (iii) {1, 2, 3 ,6,12}
   (iv) {2, 4, 8, 16}
   (v) {3, 9, 27, 54}
2. (i) What is distributive lattice? Show that in a bounded distributive lattice, the elements which have components from a sublattice.
   (ii) Show that in a lattice with two or more elements, no element is its own complement.
3. (i) Show that there are only five distinct Hasse diagrams for partially ordered sets that contain three elements.
   (ii) What is a complemented lattice? Explain by taking a suitable example.

Attempt any two of the following:

1. (i) Make a truth table for
   (p˄~p)˅ (~(q ˄ r))
   (ii) p →(q→ r)↔ p→(~q˅ r) ↔(p ˄ q) →r
2. (i) Demonstrate that R is a valid inference from the premises p→ q, q→ r and p.
   (ii) Explain the concept of tautology, contradiction and contingency by taking a suitable example.
3. (i) Find the truth value of V x(P(x) ˅v(x)), where p(x): x =1, v(x) : x =2 and the universe of discourse is {1,2}.
   (ii) Show that ~ P(a, b) factors logically from Vx  Vy (P(x, y)→ W(x, y)) and ˥W(a, b).

Attempt any two of the following:

1. Solve a = na_n-1 + 3ⁿ with a₀=0 using exponential generating functions.
2. (i) n like balls are to be placed in 3 unlike boxes so that there is at-least one ball in each box. Find the number of different ways this can be done.
   (ii) Find the number of positive unequal integral solutions of the equation x + y + z + w = 20.
3. A box contains N coins, m of which are fair and the rest are biased. The probability of getting a head when a fair coin is tossed is 1/2, while it is 2/3 when a biased coin is tossed. A coin is drawn from the box at random and is tossed twice. The first time it shows head and the second time it shows tail. What is probability that coin drawn is fair?

______________________________