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
b) Contradiction
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
b) Contradiction
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
- 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,
|
|
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)