DISCRETE STRUCTURE

DISCRETE STRUCTURE
SEM-III, 2012-13
B.TECH EXAMINATION
UTTARAKHAND TECHNICAL UNIVERSITY
(UTU)

Time: 3 Hours

Total Marks: 100

Do any four Questions:

1. Draw Venn Diagram for (A ∩ B) ⋃ C.
2. If f: R→R is a function such that f(x) = 3x + 5 prove that f is one - one onto. Also find the inverse of f.
3. Determine the number of integer solutions to the equation:
   x1 + x2 + x3 + x4 = 7
   where xi > =0 for all i = 1,2,3,4
4. Confirm or disprove the following identities:
   (A ⋃ B) X (C ⋃ D) = (A X C) ⋃ (B X D)
5. Let {A₁, A₂ ...A_k} be a partition of set A. We define a binary relation R on A such that an ordered pair (a, b) is in R if and only if a and b are in the same block of the partition. Show that R is an equivalence relation.
6. Show that among n+1 positive integers less than or equal to 2n there are two of them that are relative prime.

Do any two Questions:

1. Let (A, *) be an algebraic system such that for all a, b, c, d in A
   a * a = a
   (a * b)* (c * d) = (a * c) * (b * d)
   Show that
   A * (b * c) = (a * b) * (a * c)
2. Let G = (V,E) be a directed graph in which there is exactly one path of length 2 between any two vertices. For any two vertices a and b in V, let (a,c) and (c,b) be the two edges in the path from a to b. We define an algebraic system (v,*) such that a * b =c. Show that (V, *) is a central groupoid.
3. The order of an element a in a group is defined to be the least positive integer m such that a^m = e. (If no positive power of a equals e, the order of a is defined to be infinite). Show that, in a finite group, the order of an element divides the order of an element divides the order of the group.

Do any two Questions:

1. What is Hasse diagram? Let A = {1, 3, 9, 27, 81}. Draw Hasse diagram of the post (A, /).
2. Show that a lattice (A, <=) is distributive if and only if for any elements a, b, c in A, (a ˄ b) ˅ (b ˄ c) ˅ (c ˄ a) = (a ˅ b) ˄ (b ˅ c) ˄ (c ˅ a).
3. We study in this problem the possibility of defining a lattice by an algebraic system two binary operations. Let (A, ˅, ˄) be an algebraic system, where ˅ and ˄ are binary operations satisfying the commutative, associative and absorption laws. Define a binary relation <= on A such that for any a and b in A, a<=b if and only if a ˄ b =a. Show that <= is a partial ordering relation.

Do any two Questions:

1. Write down the following statements in symbolic form:
   (a) The sun is bright and the humidity is not high
   (b) If I finish my homework before dinner and it does not rain, then I will go to the ball game.
   (c) If you do not see me tomorrow, it means I have gone to Delhi.
   (d) Either the material is interesting or the exercises are not challenging, but not both.
2. Tony, Mike, and John belong to the Alpine club. Every club member is either a skier or a mountain climber or both. No mountain climber likes rain, and all skiers like snow. Mike dislike whatever Tony likes and likes whatever Tony dislikes. Tony likes rain and snow. Is there a member of the Alpine club who is mountain climber but not a skier?
3. It is known that at the university 60% of the professors play tennis, 50% of them play bridge, 70% jog, 20% play tennis and bridge, 30% play tennis and jog, and 40% bridge and jog. If someone claims that 20% of the processors jog and Play Bridge and tennis would you believe this claim? Why?

Do any two Questions:

1. There are 10 pairs of shoes in closet. If eight shoes are chosen at random, what is the probability that no complete pair of shoes is chosen? That exactly on complete pair of shoes is chosen?
2. There are 30% chance that it rain on any particular day. What is the probability that there is at least one rainy day within a 7 day period? Given that there is at least one rainy day, what is probability that there are at least two rainy days?
3. One of 10 keys opens the door. If we try the key one after another, what is the probability that the door is opened on the first attempt? On the second attempt? On the third attempt?

_____________________________