# DISCREATE MATH

MC0063

Discrete Mathematics

[Part A – 1 mark each]

1)      Let (R, +, .), (R-1, +, .) be two ring A mapping & - R→ R-1 is said to be a llll 1 (or a sing morphonism) if-

a)      ф (a+b) = ф (a) + ф (b) function a, b Є R

b)      ф (ab) = ф (a) ф (b) function a, b Є R

c)      All of the above

d)     None of the above

2)      The proposition ~p ν (p ν q) is a

a)      Tautology

c)      Logical equivalence

d)     None of the above

3)      If n(A) = P then n [P (A)] is equal to

a)      pn

b)      np

c)      n2

d)     None of the above

4)      If A = {1, 2, 3, 4, 5, 6} B = {2, 4} then (A ÎB) is

a)      6

b)      4

c)      3

d)     none of the above

5)      The value of x for which ((3x + 1), 2) =(7,2)

a)      5

b)      3

c)      2

d)     None of the above

6)      The congruence modulo m, a = b(mod m) in the set Z is

a)      An equivalence relation

b)      A partial ordering relation

c)      Binary relation

d)     None of the above

7)      If f and g are functions from R to R defined by f(x) = x2 + 3 and g(x) = 4× 5 then fog (x) is ((4x-5)2 +3)

a)      2(4x + 5)3

b)      (4x – 5)2

c)      (4x +5)2-3

d)     None of the above

8)      The number of ways in which the child can choose two flavors for a double scoop ice-cream cone from Mr. sticky’s Delicious flavours is

a)      25p2

b)     25c2

c)      25pt

d)     None of the above

9)      Let A ={1, 2, 3, 4, 6, 8, 12, 24} be set under the relation a/b (a divides b). Then greatest and the least element of the set A is

a)      12, 2

b)      24, 2

c)      24, 1

d)     none of the above

10) The weight of x = 11100 in b5 is

a)      |x| = 1

b)      |x| = 5

c)      |x| = 3

d)     none of the above

11) The proposition ~p ν (p ν q) is a

a)      Tautology

c)      Logical equivalence

d)     None of the above

12) A well formed formula for “Every one is loyal to someone”

a)      ×( "y loyal(x, y))

b)      ×(\$y loyal(x, y))

c)      ×("y loyal(x,y))

d)     None of these

13) If n(A) = P then n [P (A)] is equal to

a)      pn

b)      np

c)      n2

d)     None of the above

14) If A = {1, 2, 3, 4, 5, 6} B = {2, 4} then (AЄB) is

a)      6

b)      4

c)      3

d)     none of the above

15) The value of x for which ((3x + 1), 2) =(7,2)

a)      5

b)      3

c)      2

d)     None of the above

16) A relation R on Set A is called partially ordered set, if it is

a)      Reflexive

b)      Transitive

c)      Antisymmetric

d)     All of these

17) A poset has at least one _______ element and atmost ________ element.

a)      Least, 2, greatest

b)     Greatest, one least

c)      Greatest, one, equal

d)     None

18) The set Zn = {………..-3, -2, -1, 0, 1, 2, 3, ………….} under the binary operation ‘+’ is

a)      Monoid

b)      Algebraic system

c)      Abelian group

d)     None of these

19) When R is a congruence relation of the monoid (S, *) and the operation in S/R is defined by [a] * [b] then [S/R, *] is a

a)      Semigroup

b)     Monoid

c)      Group

d)     None

20) When a function maps all elements of set A to every element of Set B, the function is:

a)      Into

b)     One one

c)      Surjective

d)     None

21) The generating function for the numeric function a = (30, 31, 32, 33-------3r-------)

a)      1/(1-t)

b)     1/(1-3t)

c)      t

d)     none

22) p←→q can also be written is the form:

a)      (p→q) ν (q→p)

b)      (p→p) c (q ^ p)

c)      ~(q ^ p) → (q ^ p)

d)     (p →q) ^ (q→p)

23) If a lattice L contains a smallest element with respect to ≤, then this uniquely determined element is called the

a)      Unit Element

b)      None Element

c)      Zero Element

d)     None of these

24) If a lattice L contains a smallest element with respect to ≤, then this uniquely determined element is called the

a)      Unit Element

b)      None Element

c)       Zero Element

d)     None of these

25)  Let R be a congruence relation on the semigroup (S,*) The relation  from S/R X S/R in which the ordered pair ([a],[b]) is for a and b in S related to [a*b], then (S/R,      ) is a called

a)      Semigroup

b)      Monoid

c)      Quotient Semigroup

d)     None of These

26)  Let R be a congruence relation on the semigroup (S,*) and let then (S/R,      ) ba corresponding Quotient semigroup Then function fR: S-> S/R defined by fR(a)=[a] is an

a)      Factor Semigroup

b)     Onto Homomorphism

c)      Isomprphism

d)     None of These

27) If H is a subgroup of G then there is a _______________ correspondence between any two righ cosets of H in G

a)      One to One

b)      Onto

c)      One One

d)     None of these

28) Cosh x =

a)      (ex- ex)/2

b)     (ex+ ex)/2

c)      (ex- ex)/ (ex+ ex)

d)     2/((ex- ex)

29) Sinh2x=

a)      2 Sinhx coshx

b)      Cosh2x+ Sinh2x

c)      Cosh2x- Sinh2x

d)     1- Sinh2x

30) The greatest of [3.75]

a)      3

b)      4

c)      -3

d)     -4

31) The greatest integer of [-3.5]

a)      -4

b)      4

c)      3

d)     -3

32) If G is finite group and H is a subgroup of G, then O(H) is a divisor of O(G) this is a

a)      Rolles theorem

b)     Lagranges Theorem

c)      Homomorphism

d)     Isomorphism

33) A non empty set R is said to be a ring if there exists two operations “+” and “.” On R such that

a)      (R,+) is a n abelian group

b)      (R, . ) is a semigroup

c)      For any a,b,c ÎR we have a(b+c) =ab+ac, (a+b)c=ac+bc

d)     All of these

34)  (Z(Set of integers ),+, . ) is a commutative ring

a)      With Identity

b)      Without Identity

c)      Ring without identity

d)     None of these

35) (Z(Set of even integers ),+, . ) is a commutative ring

a)      With Identity

b)     Without Identity

c)      Ring without identity

d)     None of these

36) (Q(Set of rationals ),+, . ) is a commutative ring

a)      With Identity

b)      Without Identity

c)      Ring without identity

d)     None of these

37) (Z(integer modulo n ),+, . ) is a commutative ring

a)      With Identity

b)      Without Identity

c)      Ring without identity

d)     None of these

38) Any expression involving the operators Ú and Ù which is valid in any lattice (L, Ú , Ù) remains vlid if we replace Ú and Ù everywhere in the expression this is called

a)      Pigeon Hole Principle

b)      Closure Law

c)      Duality Law

d)     Distributive Law

39) (L, Ú , Ù) is algebraic system satisfying

a)      Commutative Law

b)      Absorption Law

c)      Idempotent Law with a≤b, if and only if aÙb=a

d)     All of these

40) if a lattice L is bounded (by 0 or 1), then every xÎL satisfies:

a)      0≤x≤1

b)      0^x =0and 0Úx=x

c)      1^x=x and 1Úx=1

d)     All of the above

[Part B – 2 marks each]

41) Semi groups (Z,+)and (T, +) where T is the set of all even integers , are isomorphic, if it has following properties

a)      If is one-one

b)      If onto

c)      If homomorphism

d)     All of the above

42)  If G is group then Match the following

1. Finite Group                              1. If G contains only a finite number of elements

1. Infinite Group                         2. If G contains infinite number of elements

a)      1,1 & 2,2

b)      1,2 & 2,1

c)      None of these

43) (z,+, .) is ____________ domain with characteristic________

a)      Integral, 0

b)      Not an integral , p

c)      Integral, p

d)     Non integral, 0

44) (Zn, +, .) is ____________ domain with characteristic________

a)      Integral, 0

b)      Not an integral , p

c)      Integral, p

d)     Non integral, 0

45) (Z6, +, .) is ____________ domain with characteristic________

a)      Integral, 0

b)     Commutative Ring

c)      Integral, p

d)     Non integral, 0

46) (Z6, +, .) is____________________

a)      Integral, 0

b)     Commutative Ring

c)      Integral, p

d)     Non integral, 0

47) (Z12, +, .) is ____________ domain with characteristic________

a)      Integral, 0

b)     Commutative Ring

c)      Integral, p

d)     Non integral, 0

48) The next permutation to the permutation 2431    in lexicographic order

a)      1234

b)      1324

c)      3124

d)     2143

49) The next permutation to the permutation 4123 in reverse lexicographic order

a)      2413

b)      2143

c)      2134

d)     3124

50) According to principle of inclusion and exclusion

a)      │A1UA2│=│A1│+│A2│-│A1∩ A2

b)      │A1UA2│=│A1│+│A2│+│A1∩ A2

c)      │A1UA2│=│A1│-│A2│-│A1∩ A2

d)     None of These

51) The no of integers between 1 to 250

a)      100

b)      120

c)      190

d)     193

52) How many arrangements of the digits 0,1,2,3,4,5,6,7,8,9 contain atleast one patterns 289, 234, 487

a)      2X3!-5!

b)      8!

c)      8X4!

d)     3X8! – 6!

For Que 34- 36

In How many ways can 4 prizes be distributed among 5 persons when

53) No person gets more than 1 prize

a)      625

b)     10

c)      620

d)     120

54) A person may get any number of prize

a)      625

b)      10

c)      620

d)     120

55) A person get all the prizes

a)      625

b)      10

c)      620

d)     120

56) How many positive integers less than or equal to 70 are relatively prime to 70

a)      22

b)     24

c)      32

d)     36

For 38-39

No. of derangements of the integers from 1 to 10 inclusive satisfying the condition that the set of elements in the first 5 places is

57) 1,2,3,4,5 in some order

a)      D4.D5

b)      D6.D5

c)      D5.D5

d)     None of these

58) 6,7,8,9,10 in some order

a)      5!

b)     (5!)2

c)      4!

d)     None of these

59) How many cards can be pick from a standard 2 card deck to be sure of getting atleast one red card

a)      24

b)      25

c)      26

d)     27

60) The no of integers between 1 to 250

a)      100

b)      120

c)      190

d)     193

[Part C – 4 marks each]

61) The recurrence relation of the Fibonacci Sequence
an=an-1+an-2, n³2 a0=0,a1=1

a)      1/Ö5[(1+Ö5)/2]n-[(1-Ö5)/2]n

b)      1/Ö5[(1+Ö5)/2]n/2-[(1+Ö5)/2]n

c)      1/Ö5[(1-Ö5)/2]n-[(1-Ö5)/2]n

d)     1/Ö5[(1-Ö5)/2]n+[(1-Ö5)/2]n

62) ëx+nû=

a)      ënû

b)     ëxû

c)      ëx+nû

d)     None of these

Match the following

19)

 1.Partial ordered set are used for 1. Searching 2.Diagramatic forms of lattices are used 2. Sorting 3. Lattices are used for 3. Boolean Algebra and Logic Circuits The concepts of POSets and lattices are used in 4. Construction of Logical representation

a)      (1,1),(2,3),(3,2),(4,4)

b)     (1,3),(2,3),(3,4),(4,1)

c)      (1,2),(2,3),(3,1),(4,4)

d)     None of these

63) Which of these is equivalence relation

a)      S={Lines in the plane };xRyÛx is parallel to y

b)      N ={set of Natural nos}, xRyÛ │x-y│≤5

c)      None of these

d)     Both of these

64) Match the following

1. Chain

1. is a set S with relation R on S which is reflexive,

 PC Training Institute Ltd., An ISO-9001 Certified Organisation
antisymmetric, antisymmetric and transitive

2.Atoms

2. The elements in level -1

3.Posets

3. A POset if for any pair of elements x,y Î L , glb(x,y) and lub(x,y) exist

4. Lattice

4. In a POset is sequence a0, a1, a2 ……….an

a)      (1,1)(2,2),(3,3),(4,4)

b)      (1,2),(2,3),(3,1)(4,4)

c)      (1,4),(2,2),(3,1),(4,3)

d)     None of these

65) A well formed formula for “Every one is loyal to someone”

a)      ×( "y loyal(x, y))

b)      (\$y loyal(x, y))

c)      ×("y loyal(x,y))

d)     None of these

66) A lattice (L) is called _____________ if its elements a, b, c in
L satisfies following ____________ properties.

a ^ ( b ν c) = (a ^ b) ν (a ^ c)

a ν ( b ^ c) = (a ν b) ^ (a ν c)

a)      bounded, associative

b)     Distributive, distributive

c)      Both a & b

d)     None of the above

67) A lattice (L ν ^ )is modular Û

a)      xÙ{yÙ(xÚz)}=(xÚy)Ú (xÚz) for all xÎL

b)      xÚ{yÙ(xÙz)}=(xÙy)Ù(xÙz) for all xÎL

c)      xÚ{yÙ(xÚz)}=(xÚy)Ù(xÚz) for all xÎL

d)     None of these

68) Match the following

 1.Commutative Property 1. a*(b*c)=(a*b)*c 2. Distributive Property 2. a*e=e*a=a 3. Associative Law 3. a*(b+c)= a*b+a*c 4. Identitiy Property 4. a*b=b*a

a)      (1,1)(2,3)(3,4)(4,3)

b)      (1,4),(2,3)(3,1),(4,2)

c)      (1,2)(2,3),(3,4)(4,1)

d)     None of These

69) If A={1,2,3}, B={2,4,5} then ADB= ?

a)      {1,2,3}

b)     {1,3,4,5}

c)      {4,5}

d)     {1,3}

70) The statement is true or false 34n+2+ 52n+1 is divisible by 14 for all positive integers.

a)      True

b)      False

71) Sum to n terms the series
1                      +                      1                      +……………+                        1
(a+1)(a+2)                              (a+2)(a+3)                                                          (a+n) (a+n+1)

a)                  1
(a+n+1)

b)                 n
(a+n+1)

c)                  N+1
(a+n+1)

d)     None of these

72) The shortest sequence of moves that transfers a tower of n disks from the left peg A to the right peg B, if direct moves between A and B are disallowed.(Each move must be from middle peg)

a)      3n-1

b)      3n+1

c)      3n/n

d)     None of these

73) G[e,a,b,c} is an abelian group with ‘e’ as identity element. The order of the other elements are

a)      2,2,3

b)      3,3,3

c)      2,2,4

d)     2,3,4

74) Match the following

A. Groups                               I. Associativity

B. Semi groups                        II. Identity

C. Monoids                             III. Commutative

D. Abelian Groups                  IV. Left Inverse

Codes:

A         B         C         D

a)         IV        I           II         III

b)         III        I           IV        I

c)         II         III        I           IV

d)         I           II         III        IV

75) If the binary operation * is defined on a set of ordered pairs of real numbers as (a,b) * (c,d) = (ad+bc, bd) and is associative, then (1,2) * 3,5) * (3,4) =

a)      (74, 40)

b)      (32, 40)

c)      (23,11)

d)     (7,11)