Category: Discrete Mathematics Objective Questions

Discrete Mathematics Multiple Choice Questions on “Properties of Tree”.

1. An undirected graph G which is connected and acyclic is called ____________
a) bipartite graph
b) cyclic graph
c) tree
d) forest

Answer: c
Clarification: An undirected graph G which is connected and acyclic is termed as a tree. G contains no cycles and if any edge is added to G a simple cycle is formed.

2. An n-vertex graph has ______ edges.
a) n²
b) n-1
c) n*n
d) n*(n+1)/2

Answer: b
Clarification: Suppose G is a connected graph which has no cycles. Every subgraph of G includes at least one vertex with zero or one incident edges. It has n vertices and n-1 edges. Generally, the order-zero graph is not considered to be a tree.

3. What is a star tree?
a) A tree having a single internal vertex and n-1 leaves
b) A tree having n vertices arranged in a line
c) A tree which has 0 or more connected subtrees
d) A tree which contains n vertices and n-1 cycles

Answer: a
Clarification: A star tree of order n is a tree with as many leaves as possible or in other words a star tree is a tree that consists of a single internal vertex and n-1 leaves. However, an internal vertex is a vertex of degree at least 2.

4. A polytree is called _______________
a) directed acyclic graph
b) directed cyclic graph
c) bipartite graph
d) connected graph

Answer: a
Clarification: A directed acyclic graph is known as a polytree whose underlying undirected graph is a tree. In other words, a directed tree is a directed graph which would be tree if the directions on the edges were ignored.

5. The tree elements are called __________
a) vertices
b) nodes
c) points
d) edges

Answer: b
Clarification: Every tree element is called a node and the lines connecting the elements are called branches. A finite tree structure has a member that has no superior and is called the “root” Or root node. Nodes that have no child are called leaf nodes.

6. In an n-ary tree, each vertex has at most ______ children.
a) n
b) n⁴
c) n*n
d) n-1

Answer: a
Clarification: An n-ary tree is a rooted tree in which each vertex has at most n children. 2-ary trees are termed as binary trees, 3-ary trees are sometimes called ternary trees.

7. A linear graph consists of vertices arranged in a line.
a) false
b) true
c) either true or false
d) cannot determined

Answer: b
Clarification: A linear graph also known as a path graph is a graph which consists of k vertices arranged in a line, so that vertices from i and i+1 are connected by an edge for i=0,…, k-1.

8. Two labeled trees are isomorphic if ____________
a) graphs of the two trees are isomorphic
b) the two trees have same label
c) graphs of the two trees are isomorphic and the two trees have the same label
d) graphs of the two trees are cyclic

Answer: c
Clarification: The number of labeled trees of k number of vertices is k^n-2. Two labeled trees are isomorphic if their graphs are isomorphic and the corresponding points of the two trees have the same labels.

9. A graph which consists of disjoint union of trees is called ______
a) bipartite graph
b) forest
c) caterpillar tree
d) labeled tree

Answer: b
Clarification: A forest is an undirected acyclic graph in which all the connected components are individual trees. This graph contains a disjoint union of trees.

10. What is a bipartite graph?
a) a graph which contains only one cycle
b) a graph which consists of more than 3 number of vertices
c) a graph which has odd number of vertices and even number of edges
d) a graph which contains no cycles of odd length

Answer: d
Clarification: A graph is called a bipartite graph if and only if it contains no cycle of odd length. Every tree is a bipartite graph and a median graph.

Discrete Mathematics Multiple Choice Questions on “Groups – Subgroups”.

1. A trivial subgroup consists of ___________
a) Identity element
b) Coset
c) Inverse element
d) Ring

Answer: a
Clarification: 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.

2. Minimum subgroup of a group is called _____________
a) a commutative subgroup
b) a lattice
c) a trivial group
d) a monoid

Answer: c
Clarification: 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.

3. Let K be a group with 8 elements. Let H be a subgroup of K and Ha) 8
b) 2
c) 3
d) 4

Answer: d
Clarification: 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.

4. __________ 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
Clarification: 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.

5. 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
Clarification: 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.

6. Intersection of subgroups is a ___________
a) group
b) subgroup
c) semigroup
d) cyclic group

Answer: b
Clarification: The subgroup property is intersection closed. An arbitrary (nonempty) intersection of subgroups with this property, also attains the similar property.

7. 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
Clarification: 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).

8. 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
Clarification: 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.

9. 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
Clarification: 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.

10. Two groups are isomorphic if and only if __________ is existed between them.
a) homomorphism
b) endomorphism
c) isomorphism
d) association

Answer: c
Clarification: 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).

Discrete Mathematics Multiple Choice Questions on “Logics – Propositions”.

1. Which of the following statement is a proposition?
a) Get me a glass of milkshake
b) God bless you!
c) What is the time now?
d) The only odd prime number is 2

Answer: d
Clarification: Only this statement has got the truth value which is false.

2. The truth value of ‘4+3=7 or 5 is not prime’.
a) False
b) True

Answer: b
Clarification: Compound statement with ‘or’ is true when either of the statement is true. Here the first part of the statement is true, hence the whole is true.

3. Which of the following option is true?
a) If the Sun is a planet, elephants will fly
b) 3 +2 = 8 if 5-2 = 7
c) 1 > 3 and 3 is a positive integer
d) -2 > 3 or 3 is a negative integer

Answer: a
Clarification: Hypothesis is false, thus the whole statement is true.

4. What is the value of x after this statement, assuming the initial value of x is 5?
‘If x equals to one then x=x+2 else x=0’.
a) 1
b) 3
c) 0
d) 2

Answer: c
Clarification: If condition is false so value decided according to else condition.

5. Let P: I am in Bangalore.; Q: I love cricket.; then q -> p(q implies p) is?
a) If I love cricket then I am in Bangalore
b) If I am in Bangalore then I love cricket
c) I am not in Bangalore
d) I love cricket

Answer: a
Clarification: Q is hypothesis and P is conclusion. So the compound statement will be if hypothesis then conclusion.

6. Let P: If Sahil bowls, Saurabh hits a century.; Q: If Raju bowls, Sahil gets out on first ball. Now if P is true and Q is false then which of the following can be true?
a) Raju bowled and Sahil got out on first ball
b) Raju did not bowled
c) Sahil bowled and Saurabh hits a century
d) Sahil bowled and Saurabh got out

Answer: c
Clarification: Either hypothesis should be false or both (hypothesis and conclusion) should be true.

7. The truth value ‘9 is prime then 3 is even’.
a) False
b) True

Answer: b
Clarification: The first part of the statement is false, hence whole is true.

8. Let P: I am in Delhi.; Q: Delhi is clean.; then q ^ p(q and p) is?
a) Delhi is clean and I am in Delhi
b) Delhi is not clean or I am in Delhi
c) I am in Delhi and Delhi is not clean
d) Delhi is clean but I am in Mumbai

Answer: a
Clarification: Connector should be ‘and’, that is q and p.

9. Let P: This is a great website, Q: You should not come back here. Then ‘This is a great website and you should come back here.’ is best represented by?
a) ~P V ~Q
b) P ∧ ~Q
c) P V Q
d) P ∧ Q

Answer: b
Clarification: The second part of the statement is negated, hence negation operator is used.

10. Let P: We should be honest., Q: We should be dedicated., R: We should be overconfident. Then ‘We should be honest or dedicated but not overconfident.’ is best represented by?
a) ~P V ~Q V R
b) P ∧ ~Q ∧ R
c) P V Q ∧ R
d) P V Q ∧ ~R

Answer: d
Clarification: The third part of the statement is negated, hence negation operator is used, for (‘or’ –V) is used and for(’but’- ∧).

Discrete Mathematics Quiz on “Cartesian Product of Sets”.

1. Let set A = {1, 2} and C be {3, 4} then A X B (Cartesian product of set A and B) is?
a) {1, 2, 3, 4}
b) {(1, 3),(2, 4)}
c) {(1, 3), (2, 4), (1, 4), (2, 3)}
d) {(3, 1), (4, 1)}

Answer: c
Clarification: In set A X B : {(c , d) |c ∈ A and d ∈ B}.

2. If set A has 4 elements and B has 3 elements then set n(A X B) is?
a) 12
b) 14
c) 24
d) 7

Answer: a
Clarification: The total elements in n(A X B) = n(A) * n(B).

3. If set A has 3 elements then number of elements in A X A X A are __________
a) 9
b) 27
c) 6
d) 19

Answer: b
Clarification: n(A X A X A) = n(A)* n(A)* n(A).

4. Which of the following statements regarding sets is false?
a) A X B = B X A
b) A X B ≠ B X A
c) n(A X B) = n(A) * n(B)
d) All of the mentioned

Answer: a
Clarification: The Cartesian product of sets is not commutative.

5. If n(A X B) = n(B X A) = 36 then which of the following may hold true?
a) n(A)=2, n(B)=18
b) n(A)=9, n(B)=4
c) n(A)=6, n(b)=6
d) None of the mentioned

Answer: c
Clarification: n(A) should be equal to n(B) for n(A X B) = n(B x A).

6. If C = {1} then C X (C X C) = (C X C) X C the given statement is true or false.
a) True
b) False

Answer: b
Clarification: The Cartesian product is not associative, (C × C) × C = { ((1, 1), 1) } ≠ { (1,(1, 1)) } = C × (C × C).

7. Let the sets be A, B, C, D then (A ∩ B) X (C ∩ D) is equivalent to __________
a) (A X C) ∩ (B X D)
b) (A X D) U (B X C)
c) (A X C) U ( B X D)
d) None of the mentioned

Answer: a
Clarification: (A ∩ B) X (C ∩ D) = (A X C) ∩ (B X D) but in case of unions this is not true.

8. If A ⊆ B then A X C ⊆ B X C the given statement is true or false.
a) True
b) False

Answer: a
Clarification: Let an arbitrary element x ∈ A and y ∈ C, then x ∈ B (subset property), (x,y) ∈ AX C also (x,y) ∈ B X C. This implies A X C ⊆ B X C.

9. If set A and B have 3 and 4 elements respectively then the number of subsets of set (A X B) is?
a) 1024
b) 2048
c) 512
d) 4096

Answer: d
Clarification: The A X B has 12 elements, then the number of the subset are 2 12 = 4096.

10. If set A X B=B X A then which of the following sets may satisfy?
a) A={1, 2, 3}, B={1, 2, 3, 4}
b) A={1, 2}, B={2, 1}
c) A={1, 2, 3}, B={2, 3, 4}
d) None of the mentioned

Answer: b
Clarification: For set A X B = B X A, this is possible only when set A = B.

Discrete Mathematics Multiple Choice Questions on “Properties of Matrices”.

1. The determinant of identity matrix is?
a) 1
b) 0
c) Depends on the matrix
d) None of the mentioned

Answer: a
Clarification: In identity matrix a_ii = 1, and all other elements = 0, hence the determinant is 1.

2. If determinant of a matrix A is Zero than __________
a) A is a Singular matrix
b) A is a non-Singular matrix
c) Can’t say
d) None of the mentioned

Answer: a
Clarification: Determinant of singular matrices are zero.

3. For a skew symmetric even ordered matrix A of integers, which of the following will not hold true?
a) det(A) = 9
b) det(A) = 81
c) det(A) = 7
d) det(A) = 4

Answer: c
Clarification: Determinant of a skew symmetric even ordered matrix A is a perfect square.

4. For a skew symmetric odd ordered matrix A of integers, which of the following will hold true?
a) det(A) = 9
b) det(A) = 81
c) det(A) = 0
d) det(A) = 4

Answer: c
Clarification: Determinant of a skew symmetric odd ordered matrix A is always 0.

5. Let A = [ka_ij]_nxn, B = [a_ij]_nxn, be an nxn matrices and k be a scalar then det(A) is equal to _________
a) Kdet(B)
b) Kⁿdet(B)
c) K³det(b)
d) None of the mentioned

Answer: b
Clarification: The scalar is multiplied with each of the element of matrix A then determinant is multiplied, the number of row times to the scalar i.e. Kⁿdet(B).

6. The Inverse exist only for non-singular matrices.
a) True
b) False

Answer: a
Clarification: Since for singular matrix det(A)=0.Hence Inverse does not exist.

7. If for a square matrix A and B, null matrix O, AB = O implies BA=O.
a) True
b) False

Answer: b
Clarification: Let A = [0 1 0 0], B = [1 0 0 0]AB=O and BA is not equal to O.

8. If for a square matrix A and B,null matrix O, AB = O implies A=O and B=O.
a) True
b) False

Answer: b
Clarification: Let A = [0 1 0 0], B = [1 0 0 0]AB=O and B, A is not equal to O.

9. Let A be a nilpotent matrix of order n then?
a) Aⁿ = O
b) nA = O
c) A = nI, I is Identity matrix
d) None of the mentioned

Answer: a
Clarification: n is the smallest possible number such that An = O.

10. Which of the following property of matrix multiplication is correct?
a) Multiplication is not commutative in general
b) Multiplication is associative
c) Multiplication is distributive over addition
d) All of the mentioned

Answer: d
Clarification: Matrix multiplication is associative, distributive, but not commutative.

Basic Discrete Mathematics Questions and Answers on “Number Theory and Cryptography – Rules of Exponents”.

1. For some number b, (¹⁄_b)^-n is equal to _________
a) -bⁿ
b) n^b
c) bⁿ
d) none of the mentioned

Answer: c
Clarification: b^-1 reciprocal of b.

2. If ab = 1, where a and b are real numbers then?
a) a = b^-1
b) b = a
c) a = b = 2
d) none of the mentioned

Answer: a
Clarification: This means that a is inverse of b or b is inverse of a.

3. If a is a real number than a⁰ is defined as _________
a) 0
b) a
c) 1
d) -1

Answer: a
Clarification: Any number to the power zero is one.

4. For some number a, b and c, c^a x c^b is equal to _________
a) c^a-b
b) c^a+b
c) c
d) none of the mentioned

Answer: b
Clarification: If base are same then exponenents powers are added.

5. For some number a, b and c, c^a/c^b is equal to _________
a) c^a-b
b) c^a+b
c) c
d) None of the mentioned

Answer: a
Clarification: If base are same then exponenents powers are added, 1/c^b = c^-b.

6. State whether the given statement is true or false.
Exponentiation is commutative.
a) True
b) False

Answer: b
Clarification: A^b is not equal to b^A, exponentiation is not commutative.

7. State whether the given statement is true or false.
Exponentiation is associative.
a) True
b) False

Answer: b
Clarification: Exponentiation is not associative.

8. If 2^a-b = 1 then the value of a-b is equal to _________
a) 1
b) 0
c) 2
d) none of the mentioned

Answer: b
Clarification: 1 = 2⁰, so a-b = 0.

9. For some number a, b and c, a^c x b^c is equal to _________
a) (ab)^c
b) (ac)^b
c) (cb)^a
d) None of the mentioned

Answer: a
Clarification: If power are same then bases are multiplied.

10. If 0^a is not equal to zero then which of the values a cannot take _________
a) 1
b) 2
c) -1
d) 0

Answer: d
Clarification: a⁰ = 1, for any real number.