Discrete Structure Module 2: Relations and Functions

1.A __________ is an ordered collection of objects.
a) Relation
b) Function
c) Set
d) Proposition
Answer: c
Explanation: By the definition of set.

2.The set O of odd positive integers less than 10 can be expressed by _____________
a) {1, 2, 3}
b) {1, 3, 5, 7, 9}
c) {1, 2, 5, 9}
d) {1, 5, 7, 9, 11}
Answer: b
Explanation: Odd numbers less than 10 is {1, 3, 5, 7, 9}.

3.Power set of empty set has exactly _________ subset.
a) One
b) Two
c) Zero
d) Three
Answer: a
Explanation: Power set of null set has exactly one subset which is empty set.

4.What is the Cartesian product of A = {1, 2} and B = {a, b}?
a) {(1, a), (1, b), (2, a), (b, b)}
b) {(1, 1), (2, 2), (a, a), (b, b)}
c) {(1, a), (2, a), (1, b), (2, b)}
d) {(1, 1), (a, a), (2, a), (1, b)}
Answer: c
Explanation: A subset R of the Cartesian product A x B is a relation from the set A to the set B.

5.The Cartesian Product B x A is equal to the Cartesian product A x B.
a) True
b) False
Answer: b
Explanation: Let A = {1, 2} and B = {a, b}. The Cartesian product A x B = {(1, a), (1, b), (2, a), (2, b)} and the Cartesian product B x A = {(a, 1), (a, 2), (b, 1), (b, 2)}. This is not equal to A x B.

6.What is the cardinality of the set of odd positive integers less than 10?
a) 10
b) 5
c) 3
d) 20
Answer: b
Explanation: Set S of odd positive an odd integer less than 10 is {1, 3, 5, 7, 9}. Then, Cardinality of set S = |S| which is 5.

7.Which of the following two sets are equal?
a) A = {1, 2} and B = {1}
b) A = {1, 2} and B = {1, 2, 3}
c) A = {1, 2, 3} and B = {2, 1, 3}
d) A = {1, 2, 4} and B = {1, 2, 3}
Answer: c
Explanation: Two set are equal if and only if they have the same elements.

8.The set of positive integers is _____________
a) Infinite
b) Finite
c) Subset
d) Empty
Answer: a
Explanation: The set of positive integers is not finite.

10.What is the Cardinality of the Power set of the set {0, 1, 2}?
a) 8
b) 6
c) 7
d) 9
Answer: a
Explanation: Power set P ({0, 1, 2}) is the set of all subsets of {0, 1, 2}. Hence, P({0, 1, 2}) = {null, {0}, {1}, {2}, {0, 1}, {0,2}, {1, 2}, {0, 1, 2}}.

11.The members of the set S = {x | x is the square of an integer and x < 100} is ________________
a) {0, 2, 4, 5, 9, 58, 49, 56, 99, 12}
b) {0, 1, 4, 9, 16, 25, 36, 49, 64, 81}
c) {1, 4, 9, 16, 25, 36, 64, 81, 85, 99}
d) {0, 1, 4, 9, 16, 25, 36, 49, 64, 121}
Answer: b
Explanation: The set S consists of the square of an integer less than 10.

12.The union of the sets {1, 2, 5} and {1, 2, 6} is the set _______________
a) {1, 2, 6, 1}
b) {1, 2, 5, 6}
c) {1, 2, 1, 2}
d) {1, 5, 6, 3}
Answer: b
Explanation: The union of the sets A and B, is the set that contains those elements that are either in A or in B.

13.The intersection of the sets {1, 2, 5} and {1, 2, 6} is the set _____________
a) {1, 2}
b) {5, 6}
c) {2, 5}
d) {1, 6}
Answer: a
Explanation: The intersection of the sets A and B, is the set containing those elements that are in both A and B.

14.Two sets are called disjoint if there _____________ is the empty set.
a) Union
b) Difference
c) Intersection
d) Complement
Answer: c
Explanation: By the definition of the disjoint set.

15.Which of the following two sets are disjoint?
a) {1, 3, 5} and {1, 3, 6}
b) {1, 2, 3} and {1, 2, 3}
c) {1, 3, 5} and {2, 3, 4}
d) {1, 3, 5} and {2, 4, 6}
Answer: d
Explanation: Two sets are disjoint if the intersection of two sets is the empty set.

16.The difference of {1, 2, 3} and {1, 2, 5} is the set ____________
a) {1}
b) {5}
c) {3}
d) {2}
Answer: c
Explanation: The difference of the sets A and B denoted by A-B, is the set containing those elements that are in A not in B.

17.The complement of the set A is _____________
a) A – B
b) U – A
c) A – U
d) B – A
Answer: b
Explanation: The complement of the set A is the complement of A with respect to U.

18.The bit string for the set {2, 4, 6, 8, 10} (with universal set of natural numbers less than or equal to 10) is ____________________
a) 0101010101
b) 1010101010
c) 1010010101
d) 0010010101
Answer: a
Explanation: The bit string for the set has a one bit in second, fourth, sixth, eighth, tenth positions, and a zero elsewhere.

19.Let Ai = {i, i+1, i+2, …..}. Then set {n, n+1, n+2, n+3, …..} is the _________ of the set Ai.
a) Union
b) Intersection
c) Set Difference
d) Disjoint
Answer: b
Explanation: By the definition of the generalized intersection of the set.

20.The bit strings for the sets are 1111100000 and 1010101010. The union of these sets is ___________
a) 1010100000
b) 1010101101
c) 1111111100
d) 1111101010
Answer: d
Explanation: The bit string for the union is the bitwise OR of the bit strings.

21.The set difference of the set A with null set is __________
a) A
b) null
c) U
d) B
Answer: a
Explanation: The set difference of the set A by the null set denoted by A – {null} is A.

22.Let the set A is {1, 2, 3} and B is {2, 3, 4}. Then the number of elements in A U B is?
a) 4
b) 5
c) 6
d) 7
Answer: a
Explanation: AUB is {1, 2, 3, 4}.

23.Let the set A is {1, 2, 3} and B is { 2, 3, 4}. Then number of elements in A ∩ B is?
a) 1
b) 2
c) 3
d) 4
Answer: b
Explanation: A ∩ B is {2, 3}.

25.Let the set A is {1, 2, 3} and B is {2, 3, 4}. Then the set A – B is?
a) {1, -4}
b) {1, 2, 3}
c) {1}
d) {2, 3}
Answer: c
Explanation: In A – B the common elements get cancelled.

26.In which of the following sets A – B is equal to B – A?
a) A = {1, 2, 3}, B = {2, 3, 4}
b) A = {1, 2, 3}, B = {1, 2, 3, 4}
c) A = {1, 2, 3}, B = {2, 3, 1}
d) A = {1, 2, 3, 4, 5, 6}, B = {2, 3, 4, 5, 1}
Answer: c
Explanation: A- B= B-A = Empty set.

27.Let A be set of all prime numbers, B be the set of all even prime numbers, C be the set of all odd prime numbers, then which of the following is true?
a) A ≡ B U C
b) B is a singleton set.
c) A ≡ C U {2}
d) All of the mentioned
Answer: d
Explanation: 2 is the only even prime number.

28.If A has 4 elements B has 8 elements then the minimum and maximum number of elements in A U B are ____________
a) 4, 8
b) 8, 12
c) 4, 12
d) None of the mentioned
Answer: b
Explanation: Minimum would be when 4 elements are same as in 8, maximum would be when all are distinct.

29.If A is {{Φ}, {Φ, {Φ}}}, then the power set of A has how many element?
a) 2
b) 4
c) 6
d) 8
Answer: b
Explanation: The set A has got 2 elements so n(P(A))=4.

30.Two sets A and B contains a and b elements respectively. If power set of A contains 16 more elements than that of B, value of ‘b’ and ‘a’ are _______
a) 4, 5
b) 6, 7
c) 2, 3
d) None of the mentioned
Answer: a
Explanation: 32-16=16, hence a=5, b=4.

31.Let A be {1, 2, 3, 4}, U be set of all natural numbers, then U-A’(complement of A) is given by set.
a) {1, 2, 3, 4, 5, 6, ….}
b) {5, 6, 7, 8, 9, ……}
c) {1, 2, 3, 4}
d) All of the mentioned
Answer: c
Explanation: U – A’ ≡ A.

32.Which sets are not empty?
a) {x: x is a even prime greater than 3}
b) {x : x is a multiple of 2 and is odd}
c) {x: x is an even number and x+3 is even}
d) { x: x is a prime number less than 5 and is odd}
Answer: d
Explanation: Because the set is {3}.

33.A function is said to be ______________ if and only if f(a) = f(b) implies that a = b for all a and b in the domain of f.
a) One-to-many
b) One-to-one
c) Many-to-many
d) Many-to-one
Answer: b
Explanation: A function is one-to-one if and only if f(a)≠f(b) whenever a≠b.

35.The function f(x)=x+1 from the set of integers to itself is onto. Is it True or False?
a) True
b) False
Answer: a
Explanation: For every integer “y” there is an integer “x ” such that f(x) = y.

36.The value of ⌊1/2.⌊5/2⌋ ⌋ is ______________
a) 1
b) 2
c) 3
d) 0.5
Answer: a
Explanation: The value of ⌊5/2⌋ is 2 so, the value of ⌊1/2.2⌋ is 1.

36.Which of the following function f: Z X Z → Z is not onto?
a) f(a, b) = a + b
b) f(a, b) = a
c) f(a, b) = |b|
d) f(a, b) = a – b
Answer: c
Explanation: The function is not onto as f(a)≠b.

37.The domain of the function that assign to each pair of integers the maximum of these two integers is ___________
a) N
b) Z
c) Z +
d) Z+ X Z+
Answer: d
Explanation: The domain of the integers is Z+ X Z+.

38.Let f and g be the function from the set of integers to itself, defined by f(x) = 2x + 1 and g(x) = 3x + 4. Then the composition of f and g is ____________
a) 6x + 9
b) 6x + 7
c) 6x + 6
d) 6x + 8
Answer: a
Explanation: The composition of f and g is given by f(g(x)) which is equal to 2(3x + 4) + 1.

39.__________ bytes are required to encode 2000 bits of data.
a) 1
b) 2
c) 3
d) 8
Answer: b
Explanation: Two bytes are required to encode 2000 (actually with 2 bytes you can encode up to and including 65,535.

40.The inverse of function f(x) = x3 + 2 is ____________
a) f -1 (y) = (y – 2) 1/2
b) f -1 (y) = (y – 2) 1/3
c) f -1 (y) = (y) 1/3
d) f -1 (y) = (y – 2)
Answer: b
Explanation: To find the inverse of the function equate f(x) then find the value of x in terms of y such that f -1 (y) = x.

40The function f(x) = x3 is bijection from R to R. Is it True or False?
a) True
b) False
Answer: a
Explanation: The function f(x) = x3 is one to one as no two values in domain are assigned the same value of the function and it is onto as all R of the co domain is images of elements in the domain.

41.The g -1({0}) for the function g(x)= ⌊x⌋ is ___________
a) {x | 0 ≤ x < 1}
b) {x | 0 < x ≤ 1}
c) {x | 0 < x < 1}
d) {x | 0 ≤ x ≤ 1}
Answer: d
Explanation: g({0}) for the function g(x) is {x | 0 ≤ x ≤ 1}. Put g(x) = y and find the value of x in terms of y such that ⌊x⌋ = y.

Prepare For Your Placements : https://lastmomenttuitions.com/courses/placement-preparation/
/ Youtube Channel: https://www.youtube.com/channel/UCGFNZxMqKLsqWERX_N2f08Q

Follow For Latest Updates, Study Tips & More Content!

/ lastmomenttuition

/ Last Moment Tuitions

/ lastmomentdost

Discrete Structure Module 3: Posets & Lattice

1.A Poset in which every pair of elements has both a least upper bound and a greatest lower bound is termed as _______
a) sublattice
b) lattice
c) trail
d) walk
Answer: b
Explanation: A poset in which every pair of elements has both a least upper bound and a greatest lower bound is called a lattice. A lattice can contain sublattices which are subsets of that lattice.

2.In the poset (Z+, |) (where Z+ is the set of all positive integers and | is the divides relation) are the integers 9 and 351 comparable?
a) comparable
b) not comparable
c) comparable but not determined
d) determined but not comparable
Answer: a
Explanation: The two integers 9 and 351 are comparable since 9|351 i.e, 9 divides 351. But 5 and 127 are not comparable since 5 | 127 i.e 5 does not divide 127.

3.If every two elements of a poset are comparable then the poset is called ________
a) sub ordered poset
b) totally ordered poset
c) sub lattice
d) semigroup
Answer: b
Explanation: A poset (P, <=) is known as totally ordered if every two elements of the poset are comparable. “<=” is called a total order and a totally ordered set is also termed as a chain.

4.______ and _______ are the two binary operations defined for lattices.
a) Join, meet
b) Addition, subtraction
c) Union, intersection
d) Multiplication, modulo division
Answer: a
Explanation: Join and meet are the binary operations reserved for lattices. The join of two elements is their least upper bound. It is denoted by V, not to be confused with disjunction. The meet of two elements is their greatest lower bound. It is denoted by ∧ and not to be confused with a conjunction.

5. A ________ has a greatest element and a least element which satisfy 0<=a<=1 for every a in the lattice(say, L).
a) semilattice
b) join semilattice
c) meet semilattice
d) bounded lattice
Answer: d
Explanation: A lattice that has additionally a supremum element and an infimum element which satisfy 0<=a<=1, for every an in the lattice is called a bounded lattice. A partially ordered set is a bounded lattice if and only if every finite set (including the empty set) of elements has a join and a meet.

6.The graph given below is an example of _________
discrete-mathematics-questions-answers-lattices-q6
a) non-lattice poset
b) semilattice
c) partial lattice
d) bounded lattice
Answer: a
Explanation: The graph is an example of non-lattice poset where b and c have common upper bounds d, e and f but none of them is the least upper bound.

7.A sublattice(say, S) of a lattice(say, L) is a convex sublattice of L if _________
a) x>=z, where x in S implies z in S, for every element x, y in L
b) x=y and y<=z, where x, y in S implies z in S, for every element x, y, z in L
c) x<=y<=z, where x, y in S implies z in S, for every element x, y, z in L
d) x=y and y>=z, where x, y in S implies z in S, for every element x, y, z in L
Answer: c
Explanation: A sublattice S of a lattice L is a convex sublattice of L, if x ≤ z ≤ y and x, y in S implies that z belongs to S, for all elements x, y, z in L.

8.The graph is the smallest non-modular lattice N5. A lattice is _______ if and only if it does not have a _______ isomorphic to N5.
discrete-mathematics-questions-answers-lattices-q8
a) non-modular, complete lattice
b) moduler, semilattice
c) non-modular, sublattice
d) modular, sublattice
Answer: d
Explanation: A lattice (L, ∨, ∧) is modular if for all elements a, b, c of L, the following identity holds->modular identity: (a ∧ c) ∨ (b ∧ c) = [(a ∧ c) ∨ b] ∧ c. This condition is equivalent to the following axiom -> modular law: a ≤ c implies a ∨ (b ∧ c) = (a ∨ b) ∧ c. A lattice is modular if and only if it does not have a sublattice isomorphic to N5.

9.Every poset that is a complete semilattice must always be a _______
a) sublattice
b) complete lattice
c) free lattice
d) partial lattice
Answer: b
Explanation: A poset is called a complete lattice if all its subsets have both a join and a meet. Every complete lattice is a bounded lattice. Every poset that is a complete semilattice must always be a complete lattice.

10.A free semilattice has the _______ property.
a) intersection
b) commutative and associative
c) identity
d) universal
Answer: d
Explanation: Any set X may be used to generate the free semilattice FX. The free semilattice is defined to consist of all of the finite subsets of X with the semilattice operation given by ordinary set union; the free semilattice has the universal property.

11.Hasse diagrams are first made by ______
a) A.R. Hasse
b) Helmut Hasse
c) Dennis Hasse
d) T.P. Hasse
Answer: b
Explanation: Hasse diagrams can be described as the transitive reduction as an abstract directed acyclic graph. This graph drawing techniques are constructed by Helmut Hasse(1948).

12.If a partial order is drawn as a Hasse diagram in which no two edges cross, its covering graph is called ______
a) upward planar
b) downward planar
c) lattice
d) biconnected components
Answer: a
Explanation: In a Hasse diagram if no two edges cross each other in the drawing of partial order Hasse diagram, then its covering graph called the upward planar.

13.If the partial order of a set has at most one minimal element, then to test whether it has a non-crossing Hasse diagram its time complexity __________
a) NP-complete
b) O(n2)
c) O(n+2)
d) O(n3)Answer: a
Explanation: If the partial order has at most one minimal element, or it has at most one maximal element, then to test whether a partial order with multiple sources and sinks can be drawn as a crossing-free Hasse diagram or not it’s time complexity is NP-complete.

14. Which of the following relation is a partial order as well as an equivalence relation?
a) equal to(=)
b) less than(<)
c) greater than(>)
d) not equal to(!=)
Answer: a
Explanation: The identity relation = on any set is a partial order in which every two distinct elements are incomparable and that depicts the relation of both a partial order and an equivalence relation. For non-linear orders, there are many advanced properties of posets.

16.The relation ≤ is a partial order if it is ___________
a) reflexive, antisymmetric and transitive
b) reflexive, symmetric
c) asymmetric, transitive
d) irreflexive and transitive
Answer: a
Explanation: Let A is a set and ≤ is a relation on A, then ≤ is a partial order if it satisfies reflexive, antisymmetric, and transitive, i.e., for all x, y and z in P. That means, x ≤ x (reflexivity);

17.if x ≤ y and y ≤ x then x = y (antisymmetry) and if x ≤ y and y ≤ z then x ≤ z (transitivity).
In which of the following relations every pair of elements is comparable?
a) ≤
b) !=
c) >=
d) ==
Answer: a
Explanation: In the ≤(or less than and equal to) relation, every pair of elements is comparable.

18.In a poset (S, ⪯), if there is no element n∈S with m<n, then which of the following is true?
a) an element n exists for which m=n
b) An element m is maximal in the poset
c) A set with the same subset of the poset
d) An element m is minimal in the poset
Answer: b
Explanation: By the definition, an element m exists in a poset (S, ⪯) is maximal if and only if there is no n∈S with m≺n.

19. In a poset P({v, x, y, z}, ⊆) which of the following is the greatest element?
a) {v, x, y, z}
b) 1
c) ∅
d) {vx, xy, yz}
Answer: a
Explanation: We know that, in a Hasse diagram, the maximal element(s) are the top and the minimal elements are at the bottom of the diagram. In the given poset, {v, x, y, z} is the maximal or greatest element and ∅ is the minimal or least element.

20.Suppose P1 is a partially ordered class and a cut of P1 is pair (D, T) of nonempty subclasses of P1 satisfies which of the following properties?
a) D∩T=Ø
b) D∪T=P1
c) xyz∈T
d) z∈T and zx∈DAnswer: a
Explanation: Suppose P1 is a partially ordered class and a cut of P1 is pair (D, T) of nonempty subclasses of P1 satisfies the following properties: i) D∩T=Ø and D∪T=P1 ii) If z∈D and y≤z, then y∈D and iii) If z∈T and y≥z, then y∈T.

21.Let G be the graph defined as the Hasse diagram for the ⊆ relation on the set S{1, 2,…, 18}. How many edges are there in G?
a) 43722
b) 2359296
c) 6487535
d) 131963
Answer: b
Explanation: Here the total number of elements in S is 18 and so number of vertices in Hasse diagram are 218. Hence, the number of edges in Hasse diagram are 18 * 218-1=2359296.

22.Let a set S = {2, 4, 8, 16, 32} and <= be the partial order defined by S <= R if a divides b. Number of edges in the Hasse diagram of is ______
a) 6
b) 5
c) 9
d) 4
Answer: b
Explanation: Hasse Diagram is:
          32  

          / 

       16 

       /

     8  

   /   \  

  2     4

So, the number of edges should be: 4.

23. The less-than relation, <, on a set of real numbers is ______
a) not a partial ordering because it is not asymmetric and irreflexive equals antisymmetric
b) a partial ordering since it is asymmetric and reflexive
c) a partial ordering since it is antisymmetric and reflexive
d) not a partial ordering because it is not antisymmetric and reflexive
Answer: a
Explanation: Relation less than a set of real numbers is not antisymmetric and reflexive. Relation is not POSET because it is irreflexive. Again, aRb != bRa unless a=b and so it is antisymmetric. A relation may be ‘not asymmetric and not reflexive but still antisymmetric, as {(1,1) (1,2)}. So, the relation is not a partial ordering because it is not asymmetric and irreflexive equals antisymmetric.

24.If the longest chain in a partial order is of length l, then the partial order can be written as _____ disjoint antichains.
a) l2
b) l+1
c) l
d) ll
Answer: c
Explanation: If the length of the longest chain in a partial order is l, then the elements in the POSET can be partitioned into l disjoint antichains.

25.Suppose X = {a, b, c, d} and π1 is the partition of X, π1 = {{a, b, c}, d}. The number of ordered pairs of the equivalence relations induced by __________
a) 15
b) 10
c) 34
d) 5
Answer: b
Explanation: The ordered pairs of the equivalence relations induced = {(a,a), (a,b), (a,c), (b,a), (b,b), (b,c), (c,a), (c,b), (c,c), (d,d)}. Poset -> equivalence relations = each partition power set – Φ.

26. A partial order P is defined on the set of natural numbers as follows. Here a/b denotes integer division. i)(0, 0) ∊ P. ii)(a, b) ∊ P if and only if a % 10 ≤ b % 10 and (a/10, b/10) ∊ P. Consider the following ordered pairs:
(101, 22) ii. (22, 101) iii. (145, 265) iv. (0, 153)
The ordered pairs of natural numbers are contained in P are ______ and ______
a) (145, 265) and (0, 153)
b) (22, 101) and (0, 153)
c) (101, 22) and (145, 265)
d) (101, 22) and (0, 153)
Answer: d
Explanation: For ordered pair (a, b), to be in P, each digit in a starting from unit place must not be larger than the corresponding digit in b. This condition is satisfied by options (iii) (145, 265) => 5 ≤ 5, 4 < 6 and 1 < 2; (iv) (0, 153) => 0 < 3 and no need to examine further.

27. The inclusion of ______ sets into R = {{1, 2}, {1, 2, 3}, {1, 3, 5}, {1, 2, 4}, {1, 2, 3, 4, 5}} is necessary and sufficient to make R a complete lattice under the partial order defined by set containment.
a) {1}, {2, 4}
b) {1}, {1, 2, 3}
c) {1}
d) {1}, {1, 3}, {1, 2, 3, 4}, {1, 2, 3, 5}
Answer: c
Explanation: A lattice is complete if every subset of partial order set has a supremum and infimum element. For example, here we are given a partial order set R. Now it will be a complete lattice if whatever be the subset we choose, it has a supremum and infimum element. Here relation given is set containment, so supremum element will be just union of all sets in the subset we choose. Similarly, the infimum element will be just an intersection of all the sets in the subset we choose. As R now is not complete lattice, because although it has a supremum for every subset we choose, but some subsets have no infimum. For example, if we take subset {{1, 3, 5}, {1, 2, 4}}, then intersection of sets in this is {1}, which is not present in R. So clearly, if we add set {1} in R, we will solve the problem. So adding {1} is necessary and sufficient condition for R to be a complete lattice.

28. Consider the ordering relation a | b ⊆ N x N over natural numbers N such that a | b if there exists c belong to N such that a*c=b. Then ___________
a) | is an equivalence relation
b) It is a total order
c) Every subset of N has an upper bound under |
d) (N,|) is a lattice but not a complete lattice
Answer: d
Explanation: A set is called lattice if every finite subset has a least upper bound and greatest lower bound. It is termed as a complete lattice if every subset has a least upper bound and greatest lower bound. As every subset of this will not have LUB and GLB so (N,|) is a lattice but not a complete lattice.

29. Consider the set N* of finite sequences of natural numbers with a denoting that sequence a is a prefix of sequence b. Then, which of the following is true?
a) Every non-empty subset of has a greatest lower bound
b) It is uncountable
c) Every non-empty finite subset of has a least upper bound
d) Every non-empty subset of has a least upper bound
Answer: a
Explanation: Consider any sequence like “45, 8, 7, 2” – it can have many (infinite) least upper bounds like “45, 8, 7, 2, 5”, “45, 8, 7, 2, 1” and so on but it can have only 1 greatest lower bound – “45, 8, 7” because we are using the prefix relation. So, every non-empty subset has a greatest lower bound.

30.A partial order ≤ is defined on the set S = {x, b1, b2, … bn, y} as x ≤ bifor all i and bi ≤ y for all i, where n ≥ 1. The number of total orders on the set S which contain the partial order ≤ is ______
a) n+4
b) n2
c) n!
d) 3
Answer: c
Explanation: To make this partial order a total order, we need the relation to hold for every two element of the partial order. Currently, there is no relation between any bi and bj. So, for every bi and bj, we have to add either (bi, bj) or (bj, bi) in total order. So, this translates to giving an ordering for n elements between x and y, which can be done in n! ways.

31.Let (A, ≤) be a partial order with two minimal elements a, b and a maximum element c. Let P:A –> {True, False} be a predicate defined on A. Suppose that P(a) = True, P(b) = False and P(a) ⇒ P(b) for all satisfying a ≤ b, where ⇒ stands for logical implication. Which of the following statements cannot be true?
a) P(x) = True for all x S such that x ≠ b
b) P(x) = False for all x ∈ S such that b ≤ x and x ≠ c
c) P(x) = False for all x ∈ S such that x ≠ a and x ≠ c
d) P(x) = False for all x ∈ S such that a ≤ x and b ≤ x
Answer: d
Explanation: Here, maximum element is c and so c is of a higher order than any other element in A. Minimal elements are a and b: No other element in A is of lower order than either a or b.
We are given P(a) = True. So, for all x such that a≤x, P(x) must be True. We do have at least one such x, which is c as it is the maximum element. So, P(x) = False for all x ∈ S such that a ≤ x and b ≤ x -> cannot be true. P(x) = True for all x S such that x ≠ b -> can be True as all elements mapped to TRUE doesn’t violate the given implication. P(x) = False for all x ∈ S such that x ≠ a and x ≠ c -> can be True if a is related only to c. P(x) = False for all x ∈ S such that b ≤ x and x ≠ c -> can be True as b≤x ensures x≠a and for all other elements P(x) can be False without violating the given implication.

Prepare For Your Placements : https://lastmomenttuitions.com/courses/placement-preparation/
/ Youtube Channel: https://www.youtube.com/channel/UCGFNZxMqKLsqWERX_N2f08Q

Follow For Latest Updates, Study Tips & More Content!

/ lastmomenttuition

/ Last Moment Tuitions

/ lastmomentdost

Discrete Structure Module 4: Counting

1. How many even 4 digit whole numbers are there?
a) 1358
b) 7250
c) 4500
d) 3600
Answer: c
Explanation: The thousands digit cannot be zero, so there are 9 choices. There are 10 possibilities for the hundreds digit and 10 possibilities for the tens digit. The units digit can be 0, 2, 4, 6 or 8, so there are 5 choices. By the basic counting principle, the number of even five-digit whole numbers is 9 × 10 × 10 × 5 = 45,00.

 2.In a multiple-choice question paper of 15 questions, the answers can be A, B, C or D. The number of different ways of answering the question paper are ________
a) 65536 x 47
b) 194536 x 45
c) 23650 x 49
d) 11287435
Answer: a
Explanation: There are 415 = 65536 x 47 different ways of answering the exam paper of 15 MCQs.

3. How many words with seven letters are there that start with a vowel and end with an A? Note that they don’t have to be real words and letters can be repeated.
a) 45087902
b) 64387659
c) 12765800
d) 59406880
Answer: d
Explanation: The first letter must be a vowel, so there are 5 choices. The second letter can be any one of 26, the third letter can be any one of 26, the fourth letter can be any one of 26 and fifth and sixth letters can be any of 26 choices. The last letter must be an A, so there is only 1 choice. By the basic counting principle, the number of ‘words’ is 5 × 26 × 26 × 26 × 26 × 26 × 1 = 59406880.

4. Neela has twelve different skirts, ten different tops, eight different pairs of shoes, three different necklaces and five different bracelets. In how many ways can Neela dress up?
a) 50057
b) 14400
c) 34870
d) 56732
Answer: b
Explanation: By the basic counting principle, the number of different ways = 12 × 10 × 8 × 3 × 5 = 14400. Note that shoes come in pairs. So she must choose one pair of shoes from ten pairs, not one shoe from twenty.

 5.How many five-digit numbers can be made from the digits 1 to 7 if repetition is allowed?
a) 16807
b) 54629
c) 23467
d) 32354
Answer: a
Explanation: 75 = 16807 ways of making the numbers consisting of five digits if repetition is allowed.

 6.For her English literature course, Ruchika has to choose one novel to study from a list of ten, one poem from a list of fifteen and one short story from a list of seven. How many different choices does Rachel have?
a) 34900
b) 26500
c) 12000
d) 10500
Answer: d
Explanation: By the Basic Counting Principle, the number of different choices is 10 × 15 × 7 = 10500.

7. There are two different Geography books, five different Natural Sciences books, three different History books and four different Mathematics books on a shelf. In how many different ways can they be arranged if all the books of the same subjects stand together?
a) 353450
b) 638364
c) 829440
d) 768700
Answer: c
Explanation: There are four groups of books which can be arranged in 4! different ways. Among those books, two are Geography books, five are Natural Sciences books, three are History books and four are Mathematics books. Therefore, there are 4! × 2! × 5! × 3! × 4! = 829440 ways to arrange the books.

8. The code for a safe is of the form PPPQQQQ where P is any number from 0 to 9 and Q represents the letters of the alphabet. How many codes are possible for each of the following cases? Note that the digits and letters of the alphabet can be repeated.
a) 874261140
b) 537856330
c) 549872700
d) 456976000
Answer: d
Explanation: 103 × 264 = 456976000 possible codes are formed for the safe with the alphanumeric digits.

 9.Amit must choose a seven-digit PIN number and each digit can be chosen from 0 to 9. How many different possible PIN numbers can Amit choose?
a) 10000000
b) 9900000
c) 67285000
d) 39654900
Answer: a
Explanation: By the basic counting principle, the total number of PIN numbers Amit can choose is 10 × 10 × 10 × 10 × 10 × 10 × 10 = 10,000000.

10. A head boy, two deputy head boys, a head girl and 3 deputy head girls must be chosen out of a student council consisting of 14 girls and 16 boys. In how many ways can they are chosen?
a) 98072
b) 27384
c) 36428
d) 44389
Answer: b
Explanation: There are 16 × 15 × 14 + 14 × 13 × 12 × 11 = 27384 ways to choose from a student council.

11. A drawer contains 12 red and 12 blue socks, all unmatched. A person takes socks out at random in the dark. How many socks must he take out to be sure that he has at least two blue socks?
a) 18
b) 35
c) 28
d) 14
Answer: d
Explanation: Given 12 red and 12 blue socks so, in order to take out at least 2 blue socks, first we need to take out 12 shocks (which might end up red in worst case) and then take out 2 socks (which would be definitely blue). Thus we need to take out total 14 socks.

12. The least number of computers required to connect 10 computers to 5 routers to guarantee 5 computers can directly access 5 routers is ______
a) 74
b) 104
c) 30
d) 67
Answer: c
Explanation: Since each 5 computer need directly connected with each router. So 25 connections + now remaining 5 computer, each connected to 5 different routers, so 5 connections = 30 connections. Hence,

c1->r1, r2, r3, r4, r5

c2->r1, r2, r3, r4, r5

c3->r1, r2, r3, r4, r5

c4->r1, r2, r3, r4, r5

c5->r1, r2, r3, r4, r5

c6->r1

c7->r2

c8->r3

c9->r4

c10->r5

Now, any pick of 5 computers will have a direct connection to all the 5 routers.




 13.In a group of 267 people how many friends are there who have an identical number of friends in that group?
a) 266
b) 2
c) 138
d) 202
Answer: b
Explanation: Suppose each of the 267 members of the group has at least 1 friend. In this case, each of the 267 members of the group will have 1 to 267-1=266 friends. Now, consider the numbers from 1 to n-1 as holes and the n members as pigeons. Since there is n-1 holes and n pigeons there must exist a hole which must contain more than one pigeon. That means there must exist a number from 1 to n-1 which would contain more than 1 member. So, in a group of n members there must exist at least two persons having equal number of friends. A similar case occurs when there exist a person having no friends.

14. When four coins are tossed simultaneously, in _______ number of the outcomes at most two of the coins will turn up as heads.
a) 17
b) 28
c) 11
d) 43
Answer: c
Explanation: The question requires you to find number of the outcomes in which at most 2 coins turn up as heads i.e., 0 coins turn heads or 1 coin turns head or 2 coins turn heads. The number of outcomes in which 0 coins turn heads is 4C0 = 1 outcome. The number of outcomes in which 1 coin turns head is 4C1 = 6 outcomes. The number of outcomes in which 2 coins turn heads is,
4C2 = 15 outcomes. Therefore, total number of outcomes = 1 + 4 + 6 = 11 outcomes.

15. How many numbers must be selected from the set {1, 2, 3, 4} to guarantee that at least one pair of these numbers add up to 7?
a) 14
b) 5
c) 9
d) 24
Answer: b
Explanation: With 2 elements pairs which give sum as 7 = {(1,6), (2,5), (3,4), (4,3)}. So choosing 1 element from each group = 4 elements (in worst case 4 elements will be either {1,2,3,4} or {6,5,4,3}). Now using pigeonhole principle = we need to choose 1 more element so that sum will definitely be 7. So Number of elements must be 4 + 1 = 5.

 16.During a month with 30 days, a cricket team plays at least one game a day, but no more than 45 games. There must be a period of some number of consecutive days during which the team must play exactly ______ number of games.
a) 17
b) 46
c) 124
d) 24
Answer: d
Explanation: Let a1 be the number of games played until day 1, and so on, ai be the no games played until i. Consider a sequence like a1,a2,…a30 where 1≤ai≤45, ∀ai. Add 14 to each element of the sequence we get a new sequence a1+14, a2+14, … a30+14 where, 15 ≤ ai+14 ≤ 59, ∀ai. Now we have two sequences 1. a1, a2, …, a30 and 2. a1+14, a2+14, …, a30+14. having 60 elements in total with each elements taking a value ≤ 59. So according to pigeon hole principle, there must be at least two elements taking the same value ≤59 i.e., ai = aj + 14 for some i and j. Therefore, there exists at least a period such as aj to ai, in which 14 matches are played.

17. In how many ways can 8 different dolls be packed in 5 identical gift boxes such that no box is empty if any of the boxes hold all of the toys?
a) 2351
b) 365
c) 2740
d) 1260
Answer: d
Explanation: Dolls are different but the boxes are identical. If none of the boxes is to remain empty, then we can pack the dolls in one of the following ways:
Case i. 2, 2, 2, 1, 1
Case ii. 3, 3, 1, 1
Case i: Number of ways of achieving the first option 2, 2, 2, 1, 1. Two dolls out of the 8 can be selected in 8C2 ways, another 2 out of the remaining 6 can be selected in 6C2 ways, another 2 out of the remaining 4 can be selected in 4C2 ways and the last two dolls can be selected in 1C1 ways each. However, as the boxes are identical, the two different ways of selecting which box holds the first two dolls and which one holds the second set of two dolls will look the same. Hence, we need to divide the result by 2. Therefore, total number of ways of achieving the 2, 2, 2, 1, 1 is = (8C2 * 6C2 * 4C2 * 1C1 * 1C1) / 2 = 1260.

 18.A group of 20 girls plucked a total of 200 oranges. How many oranges can be plucked one of them?
a) 24
b) 10
c) 32
d) 7
Answer: a
Explanation: Suppose all of them plucked the different number of oranges. A girl can pluck at least 0 oranges and the number of oranges plucks by each student is distinct. So, total number of plucked oranges should be less than 100. But 0+1+2…..+19+20 = 210>200 a contradiction.
Thus there exist two girls who plucked the same number of oranges. If thus there exist two girls who plucked the same number of oranges. It means each girl of remaining 18 students plucked different number of oranges. Number of oranges Plucked by 18 students = 0+1+2+3…+17 = 153 oranges. Number of oranges plucked by remaining 2 student = 200 – 153 = 47. Both students plucked same number of oranges. So, Number of oranges plucked by one of them = 47/2=24.

 19.In a get-together party, every person present shakes the hand of every other person. If there were 90 handshakes in all, how many persons were present at the party?
a) 15
b) 14
c) 16
d) 17
Answer: b
Explanation: Let the total number of persons present at the party be m, Then, [{x *(x−1)}/2] = 90.

x = 14.

 20.A bag contains 25 balls such as 10 balls are red, 7 are white and 8 are blue. What is the minimum number of balls that must be picked up from the bag blindfolded (without replacing any of it) to be assured of picking at least one ball of each colour?
a) 10
b) 18
c) 63
d) 35
Answer: b
Explanation: Consider three buckets red, white and blue and we want the total number of balls such that each bucket contain at least one ball. Now consider the state of picking up a ball without replacement : (normally you consider the worst case scenario in these cases) Starting 10 balls all are red and thus goes to bucket name Red. Now again picking up the ball gives 7 balls which are of same colour and put all of them in a bucket named White. The next pick will definitely be of different colour thus: we picked 10 + 7 + 1 = 18.

21.Consider the recurrence relation a1=4, an=5n+an-1. The value of a64is _________
a) 10399
b) 23760
c) 75100
d) 53700
Answer: a
Explanation: an=5n+an-1
= 5n + 5(n-1) + … + an-2
= 5n + 5(n-1) + 5(n − 2) +…+ a1
= 5n + 5(n-1) + 5(n − 2) +…+ 4 [since, a1=4]
= 5n + 5(n-1) + 5(n − 2) +…+ 5.1 – 1
= 5(n + (n − 1)+…+2 + 1) – 1
= 5 * n(n+1)/ 2 – 1
an = 5 * n(n+1)/ 2 – 1
Now, n=64 so the answer is a64 = 10399.

 22.Determine the solution of the recurrence relation Fn=20Fn-1 − 25Fn-2 where F0=4 and F1=14.
a) an= 14*5n-1
b) an= 7/2*2n−1/2*6n
c) an = 7/2*2n−3/4*6n+1
d) an = 3*2n−1/2*3n
Answer: b
Explanation: The characteristic equation of the recurrence relation is → x2−20x+36=0
So, (x-2)(x-18)=0. Hence, there are two real roots x1=2 and x2=18. Therefore the solution to the recurrence relation will have the form: an=a2n+b18n. To find a and b, set n=0 and n=1 to get a system of two equations with two unknowns: 4=a20+b180=a+b and 3=a21+b61=2a+6b. Solving this system gives b=-1/2 and a=7/2. So the solution to the recurrence relation is,
an = 7/2*2n−1/2*6n.

 23.What is the recurrence relation for 1, 7, 31, 127, 499?
a) bn+1=5bn-1+3
b) bn=4bn+7!
c) bn=4bn-1+3
d) bn=bn-1+1
Answer: c
Explanation: Look at the differences between terms: 1, 7, 31, 124,…. and these are growing by a factor of 4. So, 1⋅4=4, 7⋅4=28, 31⋅4=124, and so on. Note that we always end up with 3 less than the next term. So, bn=4bn-1+3 is the recurrence relation and the initial condition is b0=1.

24. If Sn=4Sn-1+12n, where S0=6 and S1=7, find the solution for the recurrence relation.
a) an=7(2n)−29/6n6n
b) an=6(6n)+6/7n6n
c) an=6(3n+1)−5n
d) an=nn−2/6n6n
Answer: b

 25.Find the value of a4for the recurrence relation an=2an-1+3, with a0=6.
a) 320
b) 221
c) 141
d) 65
Answer: c
Explanation: When n=1, a1=2a0+3, Now a2=2a1+3. By substitution, we get a2=2(2a0+3)+3.
Regrouping the terms, we get a4=141, where a0=6.

 26.The solution to the recurrence relation an=an-1+2n, with initial term a0=2 are _________
a) 4n+7
b) 2(1+n)
c) 3n2
d) 5*(n+1)/2
Answer: b
Explanation: When n=1, a1=a0+2. By substitution we get, a2=a1+2 ⇒ a2=(a0+2)+2 and so on. So the solution to the recurrence relation, subject to the initial condition should be an=2+2n=2(1+n).

27. Determine the solution for the recurrence relation bn=8bn-1−12bn-2with b0=3 and b1=4.
a) 7/2*2n−1/2*6n
b) 2/3*7n-5*4n
c) 4!*6n
d) 2/8n
Answer: a
Explanation: Rewrite the recurrence relation bn-8bn-1+12bn-2=0. Now from the characteristic equation: x2−8x+12=0 we have x: (x−2)(x−6)=0, so x=2 and x=6 are the characteristic roots. Therefore the solution to the recurrence relation will have the form: bn=b2n+c6n. To find b and c, set n=0 and n=1 to get a system of two equations with two unknowns: 3=b20+c60=b+c, and 4=b21+c61=2b+6c. Solving this system gives c=-1/2 and b=7/2. So the solution to the recurrence relation is, bn=7/2*2n−1/2*6n.

28.What is the solution to the recurrence relation an=5an-1+6an-2?
a) 2n2
b) 6n
c) (3/2)n
d) n!*3
Answer: b
Explanation: Check for the left side of the equation with all the options into the recurrence relation. Then, we get that 6n is the required solution to the recurrence relation an=5an-1 + 6an-2.

 29.Determine the value of a2 for the recurrence relation an = 17an-1 + 30n with a0=3.
a) 4387
b) 5484
c) 238
d) 1437
Answer: d
Explanation: When n=1, a1=17a0+30, Now a2=17a1+30*2. By substitution, we get a2=17(17a0+30)+60. Then regrouping the terms, we get a2=1437, where a0=3.

 30.Determine the solution for the recurrence relation an = 6an-1−8an-2 provided initial conditions a0=3 and a1=5.
a) an = 4 * 2n – 3n
b) an = 3 * 7n – 5*3n
c) an = 5 * 7n
d) an = 3! * 5n
Answer: b
Explanation: The characteristic polynomial is x2−6x+8. By solving the characteristic equation, x2−6x+8=0 we get x=2 and x=4, these are the characteristic roots. Therefore we know that the solution to the recurrence relation has the form an=a*2n+b*4n, for some constants a and b. Now, by using the initial conditions a0 and a1 we have: a=7/2 and b=-1/2. Therefore the solution to the recurrence relation is: an = 4 * 2n – 1*3n = 7/2 * 2n – 1/2*3n.

Prepare For Your Placements : https://lastmomenttuitions.com/courses/placement-preparation/
/ Youtube Channel: https://www.youtube.com/channel/UCGFNZxMqKLsqWERX_N2f08Q

Follow For Latest Updates, Study Tips & More Content!

/ lastmomenttuition

/ Last Moment Tuitions

/ lastmomentdost

Discrete Structure Module 5: Algebraic Structures

1.An infinite cyclic group does not have a ______ series.
a) AP
b) GP
c) Composite
d) Finite
Answer: c
Explanation: Suppose that any finite group of order less than n has a composition series. Let G be a finite group of order n. If G is simple, then G⊳{e}, where e is the identity element of G and hence, it is a composition series. However, any infinite cyclic group does not have a composite series.

2.Every cyclic group is a/an ______
a) infinite subgroup
b) abelian group
c) monoid
d) commutative semigroup
Answer: b
Explanation: Let C be a cyclic group with a generator g∈C. Namely, we have G={g.Let x and y be arbitrary elements in C. Then, there exists n, m∈Z such that x=gn and y=gm. It follows that x*y = gn*gm = gn+m = gm*gn = yx. Hence, we find that xy=yx for any x,y belongs to G.Thus, G is an abelian group.

3. What is an irreducible module?
a) A cyclic module in a ring with any non-zero element as its generator
b) A cyclic module in a ring with any positive integer as its generator
c) An acyclic module in a ring with rational elements as its generator
d) A linearly independent module in a semigroup with a set of real numbers
Answer: a
Explanation: A nonzero R-module M is irreducible if and only if M is a cyclic module with any nonzero element as its generator. Suppose that M is an irreducible module. Let a∈M be any nonzero element and consider the submodule (a) generated by the element a. Since a is a nonzero element, the submodule (a) is non-zero. Since M is irreducible, this implies that M=(a). Hence M is a cyclic module generated by a. Since a is any nonzero element, the module M is a cyclic module with any nonzero element as its generator.

4. A finite group G of order 219 is __________
a) a semigroup
b) a subgroup
c) a commutative inverse
d) a cyclic group
Answer: d
Explanation: The prime factorization 219=3⋅73. By the definition of Sylow’s theorem, determine the number np of Sylow p-group for p=3,73. np≡1(mod p) and np divides n/p. Thus, n3 could be 1, 4, 7, 10, 13,… and n3 needs to divide 219/3=73. Hence the only possible value for n3 is n3=1. So there is a unique Sylow 3-subgroup P3 of G. By Sylow’s theorem, the unique Sylow 3-subgroup must be a normal subgroup of G. Similarly, n73=1, 74,… and n73 must divide 219/73=3 and hence we must have n73=1. Thus, G has a unique normal Sylow 73-subgroup P73.

5.The number of generators of cyclic group of order 219 is __________
a) 144
b) 124
c) 56
d) 218
Answer: a
Explanation: The number of generators of a cyclic group of order n is equal to the number of integers between 1 and n that are relatively prime to n.Namely, the number of generators is equal to ϕ(n), where ϕ is the Euler totient function. We know that G is a cyclic group of order 219. Hence, the number of generators of G is ϕ(219) = ϕ(3)ϕ(73) = 3⋅73 = 144.

6.The order of a simple abelian group is __________
a) infinite
b) real number
c) finite
d) prime
Answer: a
Explanation: Let p be the order of g (hence the order of G). As a contradiction, assume that p=ab is a composite number with integers a > 1, b > 1. Then (ga) is a proper normal subgroup of G. This is a contradiction since G is simple. Thus, p must be a prime number.
Therefore, the order of G is a prime number.

7.The Number of Elements Satisfying g7=e in a finite Group F is ______
a) even
b) not a number
c) odd
d) rational
Answer: c
Explanation: Let g≠e be an element in group F such that g7=e. As 7 is a prime number, this yields that the order of g is 7. Consider, the subgroup (g) is generated by g. As the order of g is 7, the order of the subgroup (g) is 7. Hence, the order must be odd.

8.All the rings of order p2 is ____________
a) associative
b) cyclic
c) inverse
d) commutative
Answer: d
Explanation: Let R be a ring with unit 1. Suppose that the order of R is |R|=p2 for some prime number p. Then it has been proven that R is a commutative ring.

9.An element of a commutative ring R(1≠0) is nilpotent if __________
a) a+1=0
b) an= 0, for some positive integer n
c) an= 1, for some integer n
d) a2 = 0
Answer: b
Explanation: Since a is nilpotent in a commutative ring R, we have an=0 for some positive integer n. since R is commutative, for any m∈R, we have (am)n=anmn=0. Then we have the following equality: (1−am) (1+(am) +(am)2+⋯+(am) n−1) =1. Hence, 1−am is a unit in R.

10.A group G of order 20 is __________
a) solvable
b) unsolvable
c) 1
d) not determined
Answer: a
Explanation: The prime factorization of 20 is 20=2⋅5. Let n5 be the number of 5-Sylow subgroups of G. By Sylow’s theorem, we have, n5≡1(mod 5) and n5|4. Thus, we have n5=1. Let P be the unique 5-Sylow subgroup of G. The subgroup P is normal in G as it is the unique 5-Sylow subgroup. Then consider the subnormal series G▹P▹{e}, where e is the identity element of G. Then the factor groups G/P, P/{e} have order 4 and 5 respectively. Hence these are cyclic groups (in particular abelian). Hence, the group G of order 20 has a subnormal series whose factor groups are abelian groups, and thus G is a solvable group.

Prepare For Your Placements : https://lastmomenttuitions.com/courses/placement-preparation/
/ Youtube Channel: https://www.youtube.com/channel/UCGFNZxMqKLsqWERX_N2f08Q

Follow For Latest Updates, Study Tips & More Content!

/ lastmomenttuition

/ Last Moment Tuitions

/ lastmomentdost

Discrete Structure Module 06: Graph Theory

1.A non empty set A is termed as an algebraic structure ________
a) with respect to binary operation *
b) with respect to ternary operation ?
c) with respect to binary operation +
d) with respect to unary operation –
Answer: a
Explanation: A non empty set A is called an algebraic structure w.r.t binary operation “*” if (a*b) belongs to S for all (a*b) belongs to S. Therefore “*” is closure operation on ‘A’.

2.An algebraic structure _________ is called a semigroup.
a) (P, *)
b) (Q, +, *)
c) (P, +)
d) (+, *)
Answer: a
Explanation: An algebraic structure (P,*) is called a semigroup if a*(b*c) = (a*b)*c for all a,b,c belongs to S or the elements follow associative property under “*”. (Matrix,*) and (Set of integers,+) are examples of semigroup.

3.Condition for monoid is __________
a) (a+e)=a
b) (a*e)=(a+e)
c) a=(a*(a+e)
d) (a*e)=(e*a)=a
Answer: d
Explanation: A Semigroup (S,*) is defined as a monoid if there exists an element e in S such that (a*e) = (e*a) = a for all a in S. This element is called identity element of S w.r.t *.

4.A monoid is called a group if _______
a) (a*a)=a=(a+c)
b) (a*c)=(a+c)
c) (a+c)=a
d) (a*c)=(c*a)=e
Answer: d
Explanation: A monoid(B,*) is called Group if to each element there exists an element c such that (a*c)=(c*a)=e. Here e is called an identity element and c is defined as the inverse of the corresponding element.

5.A group (M,*) is said to be abelian if ___________

a) (x+y)=(y+x)
b) (x*y)=(y*x)
c) (x+y)=x
d) (y*x)=(x+y)
Answer: b
Explanation: A group (M,*) is said to be abelian if (x*y) = (x*y) for all x, y belongs to M. Thus Commutative property should hold in a group.

6.Matrix multiplication is a/an _________ property.
a) Commutative
b) Associative
c) Additive
d) Disjunctive
Answer: b
Explanation: The set of two M*M non-singular matrices form a group under matrix multiplication operation. Since matrix multiplication is itself associative, it holds associative property.

7.A cyclic group can be generated by a/an ________ element.
a) singular
b) non-singular
c) inverse
d) multiplicative
Answer: a
Explanation: A singular element can generate a cyclic group. Every element of a cyclic group is a power of some specific element which is known as a generator ‘g’.

8.How many properties can be held by a group?

a) 2
b) 3
c) 5
d) 4
Answer: c
Explanation: A group holds five properties simultaneously –
i) Closure
ii) associative
iii) Commutative
iv) Identity element
v) Inverse element.

9.A cyclic group is always _________
a) abelian group
b) monoid
c) semigroup
d) subgroup
Answer: a
Explanation: A cyclic group is always an abelian group but every abelian group is not a cyclic group. For instance, the rational numbers under addition is an abelian group but is not a cyclic one.

10.{1, i, -i, -1} is __________
a) semigroup
b) subgroup
c) cyclic group
d) abelian group
Answer: c
Explanation: The set of complex numbers {1, i, -i, -1} under multiplication operation is a cyclic group. Two generators i and -i will covers all the elements of this group. Hence, it is a cyclic group.

11.A trivial subgroup consists of ___________
a) Identity element
b) Coset
c) Inverse element
d) Ring
Answer: a
Explanation: Let G be a group under a binary operation * and a subset H of G is called a subgroup of G if H forms a group under the operation *. The trivial subgroup of any group is the subgroup consisting of only the Identity element.

12.Minimum subgroup of a group is called _____________
a) a commutative subgroup
b) a lattice
c) a trivial group
d) a monoid
Answer: c
Explanation: The subgroups of any given group form a complete lattice under inclusion termed as a lattice of subgroups. If o is the Identity element of a group(G), then the trivial group(o) is the minimum subgroup of that group and G is the maximum subgroup.

13.Let K be a group with 8 elements. Let H be a subgroup of K and H<K. It is known that the size of H is at least 3. The size of H is __________
a) 8
b) 2
c) 3
d) 4
Answer: d
Explanation: For any finite group G, the order (number of elements) of every subgroup L of G divides the order of G. G has 8 elements. Factors of 8 are 1, 2, 4 and 8. Since given the size of L is at least 3(1 and 2 eliminated) and not equal to G(8 eliminated), the only size left is 4. Size of L is 4.

14.__________ is not necessarily a property of a Group.
a) Commutativity
b) Existence of inverse for every element
c) Existence of Identity
d) Associativity
Answer: a
Explanation: Grupoid has closure property; semigroup has closure and associative; monoid has closure, associative and identity property; group has closure, associative, identity and inverse; the abelian group has group property and commutative.

15.A group of rational numbers is an example of __________
a) a subgroup of a group of integers
b) a subgroup of a group of real numbers
c) a subgroup of a group of irrational numbers
d) a subgroup of a group of complex numbers
Answer: b
Explanation: If we consider the abelian group as a group rational numbers under binary operation + then it is an example of a subgroup of a group of real numbers.

16.Intersection of subgroups is a ___________
a) group
b) subgroup
c) semigroup
d) cyclic group
Answer: b
Explanation: The subgroup property is intersection closed. An arbitrary (nonempty) intersection of subgroups with this property, also attains the similar property.

17.The group of matrices with determinant _________ is a subgroup of the group of invertible matrices under multiplication.
a) 2
b) 3
c) 1
d) 4
Answer: c
Explanation: The group of real matrices with determinant 1 is a subgroup of the group of invertible real matrices, both equipped with matrix multiplication. It has to be shown that the product of two matrices with determinant 1 is another matrix with determinant 1, but this is immediate from the multiplicative property of the determinant. This group is usually denoted by(n, R).

18.What is a circle group?
a) a subgroup complex numbers having magnitude 1 of the group of nonzero complex elements
b) a subgroup rational numbers having magnitude 2 of the group of real elements
c) a subgroup irrational numbers having magnitude 2 of the group of nonzero complex elements
d) a subgroup complex numbers having magnitude 1 of the group of whole numbers
Answer: a
Explanation: The set of complex numbers with magnitude 1 is a subgroup of the nonzero complex numbers associated with multiplication. It is called the circle group as its elements form the unit circle.

19.A normal subgroup is ____________
a) a subgroup under multiplication by the elements of the group
b) an invariant under closure by the elements of that group
c) a monoid with same number of elements of the original group
d) an invariant equipped with conjugation by the elements of original group
Answer: d
Explanation: A normal subgroup is a subgroup that is invariant under conjugation by any element of the original group that is, K is normal if and only if gKg-1=K for any g belongs to G Equivalently, a subgroup K of G is normal if and only if gK=Kg for any g belongs to G.Normal subgroups are useful in constructing quotient groups and in analyzing homomorphisms.

20.Two groups are isomorphic if and only if __________ is existed between them.
a) homomorphism
b) endomorphism
c) isomorphism
d) association
Answer: c
Explanation: Two groups M and K are isomorphic (M ~= K) if and only if there exists an isomorphism between them. An isomorphism f:M -> K between two groups M and K is a mapping which satisfies two conditions: 1) f is a bijection and 2) for every x,y belongs to M, we have f(x*My) = f(x) * Kf(y).

21.An infinite cyclic group does not have a ______ series.
a) AP
b) GP
c) Composite
d) Finite
Answer: c
Explanation: Suppose that any finite group of order less than n has a composition series. Let G be a finite group of order n. If G is simple, then G⊳{e}, where e is the identity element of G and hence, it is a composition series. However, any infinite cyclic group does not have a composite series.

22.Every cyclic group is a/an ______
a) infinite subgroup
b) abelian group
c) monoid
d) commutative semigroup
Answer: b
Explanation: Let C be a cyclic group with a generator g∈C. Namely, we have G={g.Let x and y be arbitrary elements in C. Then, there exists n, m∈Z such that x=gn and y=gm. It follows that x*y = gn*gm = gn+m = gm*gn = yx. Hence, we find that xy=yx for any x,y belongs to G.Thus, G is an abelian group.

23.What is an irreducible module?
a) A cyclic module in a ring with any non-zero element as its generator
b) A cyclic module in a ring with any positive integer as its generator
c) An acyclic module in a ring with rational elements as its generator
d) A linearly independent module in a semigroup with a set of real numbers
Answer: a
Explanation: A nonzero R-module M is irreducible if and only if M is a cyclic module with any nonzero element as its generator. Suppose that M is an irreducible module. Let a∈M be any nonzero element and consider the submodule (a) generated by the element a. Since a is a nonzero element, the submodule (a) is non-zero. Since M is irreducible, this implies that M=(a). Hence M is a cyclic module generated by a. Since a is any nonzero element, the module M is a cyclic module with any nonzero element as its generator.

24.A finite group G of order 219 is __________
a) a semigroup
b) a subgroup
c) a commutative inverse
d) a cyclic group
Answer: d
Explanation: The prime factorization 219=3⋅73. By the definition of Sylow’s theorem, determine the number np of Sylow p-group for p=3,73. np≡1(mod p) and np divides n/p. Thus, n3 could be 1, 4, 7, 10, 13,… and n3 needs to divide 219/3=73. Hence the only possible value for n3 is n3=1. So there is a unique Sylow 3-subgroup P3 of G. By Sylow’s theorem, the unique Sylow 3-subgroup must be a normal subgroup of G. Similarly, n73=1, 74,… and n73 must divide 219/73=3 and hence we must have n73=1. Thus, G has a unique normal Sylow 73-subgroup P73.

25.The number of generators of cyclic group of order 219 is __________
a) 144
b) 124
c) 56
d) 218
Answer: a
Explanation: The number of generators of a cyclic group of order n is equal to the number of integers between 1 and n that are relatively prime to n.Namely, the number of generators is equal to ϕ(n), where ϕ is the Euler totient function. We know that G is a cyclic group of order 219. Hence, the number of generators of G is ϕ(219) = ϕ(3)ϕ(73) = 3⋅73 = 144.

26.The order of a simple abelian group is __________
a) infinite
b) real number
c) finite
d) prime
Answer: a
Explanation: Let p be the order of g (hence the order of G). As a contradiction, assume that p=ab is a composite number with integers a > 1, b > 1. Then (ga) is a proper normal subgroup of G. This is a contradiction since G is simple. Thus, p must be a prime number.
Therefore, the order of G is a prime number.

27.The Number of Elements Satisfying g7=e in a finite Group F is ______
a) even
b) not a number
c) odd
d) rational
Answer: c
Explanation: Let g≠e be an element in group F such that g7=e. As 7 is a prime number, this yields that the order of g is 7. Consider, the subgroup (g) is generated by g. As the order of g is 7, the order of the subgroup (g) is 7. Hence, the order must be odd.

28.All the rings of order p2 is ____________
a) associative
b) cyclic
c) inverse
d) commutative
Answer: d
Explanation: Let R be a ring with unit 1. Suppose that the order of R is |R|=p2 for some prime number p. Then it has been proven that R is a commutative ring.

29.An element of a commutative ring R(1≠0) is nilpotent if __________
a) a+1=0
b) an= 0, for some positive integer n
c) an= 1, for some integer n
d) a2 = 0
Answer: b
Explanation: Since a is nilpotent in a commutative ring R, we have an=0 for some positive integer n. since R is commutative, for any m∈R, we have (am)n=anmn=0. Then we have the following equality: (1−am)(1+(am)+(am)2+⋯+(am)n−1)=1. Hence, 1−am is a unit in R.

30.A group G of order 20 is __________
a) solvable
b) unsolvable
c) 1
d) not determined
Answer: a
Explanation: The prime factorization of 20 is 20=2⋅5. Let n5 be the number of 5-Sylow subgroups of G. By Sylow’s theorem, we have, n5≡1(mod 5)and n5|4. Thus, we have n5=1. Let P be the unique 5-Sylow subgroup of G. The subgroup P is normal in G as it is the unique 5-Sylow subgroup. Then consider the subnormal series G▹P▹{e}, where e is the identity element of G. Then the factor groups G/P, P/{e} have order 4 and 5 respectively. Hence these are cyclic groups(in particular abelian). Hence, the group G of order 20 has a subnormal series whose factor groups are abelian groups, and thus G is a solvable group.

Prepare For Your Placements : https://lastmomenttuitions.com/courses/placement-preparation/
/ Youtube Channel: https://www.youtube.com/channel/UCGFNZxMqKLsqWERX_N2f08Q

Follow For Latest Updates, Study Tips & More Content!

/ lastmomenttuition

/ Last Moment Tuitions

/ lastmomentdost