Discrete Structures MCQs
Practice 100 important Discrete Structures MCQs covering Mathematical Logic, Sets, Relations, Functions, Counting, Induction, Number Theory, Boolean Algebra, Graph Theory, Trees, Algebraic Structures, Automata, and Formal Languages. These questions are useful for Computer Science students and competitive exams such as AJKPSC, FPSC, PPSC, and other IT-related examinations.
Chapter 1: Mathematical Logic
1. Which logical connective is represented by the symbol ∧?
A) Conjunction
B) Disjunction
C) Implication
D) Negation
Answer: A) Conjunction
Explanation: The symbol ∧ represents logical AND. The result is true only when both propositions are true.
2. Which statement is true when p is false?
A) p ∧ q
B) p ∨ q
C) p → q
D) ¬p
Answer: D) ¬p
Explanation: Negation reverses the truth value. Therefore, when p is false, ¬p becomes true.
3. The statement p ∨ ¬p is a:
A) Contradiction
B) Tautology
C) Contingency
D) Predicate
Answer: B) Tautology
Explanation: Either p is true or p is false. In both cases, p ∨ ¬p is always true.
4. A proposition that is always false is called:
A) Tautology
B) Predicate
C) Contradiction
D) Implication
Answer: C) Contradiction
Explanation: A contradiction has a false result for every possible combination of its variables.
5. What is the negation of p ∧ q?
A) ¬p ∨ ¬q
B) ¬p ∧ ¬q
C) p ∨ q
D) p → q
Answer: A) ¬p ∨ ¬q
Explanation: By De Morgan’s law, negating AND changes it to OR and negates both propositions.
6. The implication p → q is false when:
A) p false, q true
B) p true, q false
C) Both true
D) Both false
Answer: B) p true, q false
Explanation: An implication promises q whenever p is true. It fails only when p occurs but q does not.
7. Which symbol represents logical negation?
A) ∨
B) ∧
C) ¬
D) →
Answer: C) ¬
Explanation: The ¬ symbol means NOT. It changes a true proposition to false and a false proposition to true.
8. The converse of p → q is:
A) ¬p → ¬q
B) q → p
C) ¬q → ¬p
D) p ∧ q
Answer: B) q → p
Explanation: The converse is obtained by interchanging the hypothesis and conclusion of the original implication.
9. The contrapositive of p → q is:
A) q → p
B) p → ¬q
C) ¬p → q
D) ¬q → ¬p
Answer: D) ¬q → ¬p
Explanation: The contrapositive reverses the implication and negates both propositions. It is logically equivalent to p → q.
10. Which expression is logically equivalent to p → q?
A) p ∧ q
B) ¬p ∨ q
C) p ∨ ¬q
D) ¬p ∧ q
Answer: B) ¬p ∨ q
Explanation: An implication can be rewritten as NOT p OR q. Both expressions have the same truth values.
Chapter 2: Sets
11. A set containing no elements is called:
A) Empty set
B) Universal set
C) Finite set
D) Singleton set
Answer: A) Empty set
Explanation: An empty set contains zero elements. It is commonly represented by ∅ or {}.
12. If A = {1,2,3} and B = {3,4,5}, then A ∩ B is:
A) {1,2,3,4,5}
B) {1,2}
C) {3}
D) {4,5}
Answer: C) {3}
Explanation: Intersection contains only elements present in both sets. Here, 3 is the only common element.
13. If A = {1,2} and B = {2,3}, then A ∪ B is:
A) {2}
B) {1,2,3}
C) {1,3}
D) {1,2}
Answer: B) {1,2,3}
Explanation: Union combines all distinct elements from both sets. The repeated element 2 appears only once.
14. The number of elements in a set is called its:
A) Degree
B) Order
C) Rank
D) Cardinality
Answer: D) Cardinality
Explanation: Cardinality tells us how many elements a set contains. For example, {a,b,c} has cardinality 3.
15. A set containing exactly one element is called:
A) Singleton set
B) Null set
C) Universal set
D) Power set
Answer: A) Singleton set
Explanation: A singleton set contains exactly one element, such as {5}.
16. If A ⊆ B, then every element of A is:
A) Outside B
B) In B
C) Equal to B
D) Greater than B
Answer: B) In B
Explanation: A is a subset of B when every element belonging to A also belongs to B.
17. The power set of A contains:
A) Only proper subsets
B) Only elements
C) All subsets
D) Only disjoint sets
Answer: C) All subsets
Explanation: The power set includes the empty set, individual elements, larger subsets, and the original set itself.
18. If |A| = 3, then |P(A)| equals:
A) 3
B) 6
C) 9
D) 8
Answer: D) 8
Explanation: A set with n elements has 2ⁿ subsets. Therefore, 2³ = 8.
19. Which operation gives elements in A but not B?
A) A − B
B) A ∩ B
C) A ∪ B
D) A × B
Answer: A) A − B
Explanation: Set difference A − B contains elements that belong to A but are excluded from B.
20. De Morgan’s law states (A ∪ B)’ equals:
A) A’ ∪ B’
B) A’ ∩ B’
C) A ∩ B
D) A − B
Answer: B) A’ ∩ B’
Explanation: The complement of a union equals the intersection of the individual complements.
Chapter 3: Relations
21. A relation R on A is reflexive if:
A) aRb for all a,b
B) aRa for every a
C) aRb implies bRa
D) No element relates
Answer: B) aRa for every a
Explanation: Reflexivity requires every element to be related to itself. Thus, (a,a) must belong to R for every a.
22. A relation R is symmetric if:
A) aRb implies bRa
B) aRa always
C) aRb implies aRc
D) No pair repeats
Answer: A) aRb implies bRa
Explanation: If a is related to b, symmetry requires b to be related back to a.
23. A relation is transitive if:
A) aRb implies bRa
B) aRa always
C) aRb and bRc imply aRc
D) aRb implies aRa
Answer: C) aRb and bRc imply aRc
Explanation: Transitivity connects a chain of relations. If a relates to b and b relates to c, then a must relate to c.
24. A relation that is reflexive, symmetric and transitive is called:
A) Partial order
B) Universal relation
C) Equivalence relation
D) Identity relation
Answer: C) Equivalence relation
Explanation: These three properties together define an equivalence relation, which groups related elements into equivalence classes.
25. Which relation represents ≤ on integers?
A) Symmetric only
B) Equivalence
C) Partial order
D) Universal
Answer: C) Partial order
Explanation: ≤ is reflexive, antisymmetric, and transitive. These are exactly the properties of a partial order.
26. A relation that is reflexive, antisymmetric and transitive is a:
A) Partial order
B) Equivalence relation
C) Symmetric relation
D) Universal relation
Answer: A) Partial order
Explanation: A partial order must satisfy reflexivity, antisymmetry, and transitivity.
27. If aRb and bRa imply a = b, R is:
A) Reflexive
B) Symmetric
C) Antisymmetric
D) Transitive
Answer: C) Antisymmetric
Explanation: Antisymmetry allows both directions only when the two elements are actually equal.
28. The relation {(1,1),(2,2),(3,3)} on {1,2,3} is:
A) Empty
B) Identity relation
C) Universal
D) Asymmetric
Answer: B) Identity relation
Explanation: An identity relation contains only pairs where each element is related to itself.
29. The number of ordered pairs in A × B is:
A) |A| + |B|
B) |A| − |B|
C) |A||B|
D) |A|/|B|
Answer: C) |A||B|
Explanation: Every element of A can be paired with every element of B, so the total is the product of their sizes.
30. If |A|=2 and |B|=3, |A×B| is:
A) 5
B) 6
C) 8
D) 9
Answer: B) 6
Explanation: The Cartesian product contains 2 × 3 = 6 ordered pairs.
Chapter 4: Functions
31. A function assigns each input exactly:
A) One output
B) Two outputs
C) No output
D) Many outputs
Answer: A) One output
Explanation: Every element in the domain must have exactly one corresponding output in the codomain.
32. A function that maps distinct inputs to distinct outputs is:
A) Surjective
B) Constant
C) Injective
D) Identity
Answer: C) Injective
Explanation: In an injective function, different domain elements cannot produce the same output.
33. A function whose range equals its codomain is:
A) Injective
B) Surjective
C) Constant
D) Partial
Answer: B) Surjective
Explanation: A surjective function reaches every element of its codomain at least once.
34. A function that is both injective and surjective is:
A) Constant
B) Partial
C) Identity
D) Bijective
Answer: D) Bijective
Explanation: Bijective functions are both one-to-one and onto, so every output has exactly one input.
35. Which function has f(x)=x for every x?
A) Identity function
B) Constant function
C) Zero function
D) Inverse function
Answer: A) Identity function
Explanation: An identity function leaves every input unchanged. For example, f(5) = 5.
36. A function having the same output for every input is:
A) Bijective
B) Constant
C) Injective
D) Identity
Answer: B) Constant
Explanation: A constant function produces one fixed output regardless of which input is supplied.
37. A function having an inverse function if it is:
A) Constant
B) Bijective
C) Partial
D) Many-to-one
Answer: B) Bijective
Explanation: A bijection provides a unique input for every output, allowing the mapping to be reversed.
38. The composition f ∘ g means:
A) f + g
B) g − f
C) f(g(x))
D) g(f(x))
Answer: C) f(g(x))
Explanation: In f ∘ g, function g is applied first and its result becomes the input of f.
39. If f(x)=2x+1, then f(3) equals:
A) 5
B) 6
C) 7
D) 8
Answer: C) 7
Explanation: Substitute x = 3: f(3) = 2(3)+1 = 7.
40. A many-to-one function can be:
A) Injective
B) Surjective
C) Bijective
D) Identity
Answer: B) Surjective
Explanation: A many-to-one function can still cover every element of its codomain, making it surjective.
Chapter 5: Counting and Combinatorics
41. The number of ways to arrange n distinct objects is:
A) n!
B) 2n
C) n²
D) n+1
Answer: A) n!
Explanation: For the first position there are n choices, then n−1, and so on, giving n!.
42. What is 5!?
A) 25
B) 60
C) 100
D) 120
Answer: D) 120
Explanation: 5! = 5 × 4 × 3 × 2 × 1 = 120.
43. The formula for combinations is:
A) n!/(n−r)!
B) n!/(r!(n−r)!)
C) r!/(n−r)!
D) n!/r!
Answer: B) n!/(r!(n−r)!)
Explanation: This formula counts selections where the order of chosen objects does not matter.
44. How many ways can 3 objects be selected from 5?
A) 5
B) 10
C) 15
D) 20
Answer: B) 10
Explanation: C(5,3) = 5!/(3!2!) = 10 possible selections.
45. In permutations, order is:
A) Ignored
B) Always equal
C) Important
D) Optional
Answer: C) Important
Explanation: Permutations represent arrangements, so changing the order creates a different arrangement.
46. In combinations, order is:
A) Important
B) Ignored
C) Reversed
D) Fixed
Answer: B) Ignored
Explanation: Combinations represent selections. Choosing A,B is the same as choosing B,A.
47. The Pigeonhole Principle guarantees that if 6 objects occupy 5 boxes, at least one box contains:
A) No object
B) One object
C) Two objects
D) Five objects
Answer: C) Two objects
Explanation: Six objects cannot be placed into five boxes without at least one box receiving two or more objects.
48. How many subsets does a set with n elements have?
A) n²
B) n!
C) 2n
D) 2ⁿ
Answer: D) 2ⁿ
Explanation: Each element has two choices: included or excluded. Therefore, n elements give 2ⁿ subsets.
49. The number of ways to arrange 4 distinct objects is:
A) 16
B) 24
C) 12
D) 8
Answer: B) 24
Explanation: The number of arrangements is 4! = 4 × 3 × 2 × 1 = 24.
50. Which principle is useful for counting overlapping sets?
A) Pigeonhole Principle
B) Inclusion-Exclusion Principle
C) Identity Principle
D) Closure Principle
Answer: B) Inclusion-Exclusion Principle
Explanation: It prevents elements belonging to multiple sets from being counted more than once.
Chapter 6: Mathematical Induction and Recurrence
51. Mathematical induction is mainly used to prove statements about:
A) Natural numbers
B) Real functions only
C) Matrices only
D) Graphs only
Answer: A) Natural numbers
Explanation: Mathematical induction is especially useful for proving statements involving positive integers or natural numbers.
52. The first step of mathematical induction is:
A) Inductive step
B) Base case
C) Contradiction
D) Conclusion
Answer: B) Base case
Explanation: The base case verifies that the statement is true for the initial value before applying the induction process.
53. In induction, the assumption that P(k) is true is called:
A) Base assumption
B) Inductive hypothesis
C) Direct proof
D) Recursive rule
Answer: B) Inductive hypothesis
Explanation: During the inductive step, P(k) is temporarily assumed true to prove P(k+1).
54. The step proving P(k+1) from P(k) is called:
A) Base case
B) Recursive case
C) Inductive step
D) Initial condition
Answer: C) Inductive step
Explanation: This step shows that truth at one integer leads to truth at the next integer.
55. A recurrence relation defines a sequence using:
A) Previous terms
B) Random values
C) Only constants
D) Sets
Answer: A) Previous terms
Explanation: A recurrence defines a term using one or more earlier terms of the sequence.
56. Which sequence is defined by Fibonacci recurrence?
A) aₙ=aₙ₋₁+1
B) aₙ=aₙ₋₁+aₙ₋₂
C) aₙ=2n
D) aₙ=n²
Answer: B) aₙ=aₙ₋₁+aₙ₋₂
Explanation: Each Fibonacci term is obtained by adding the two preceding terms.
57. The Fibonacci sequence begins with:
A) 1, 1
B) 0, 1
C) 2, 3
D) 1, 2
Answer: B) 0, 1
Explanation: In the standard definition, the first two Fibonacci numbers are 0 and 1.
58. Which method proves a statement by assuming its negation?
A) Direct proof
B) Induction
C) Contradiction
D) Construction
Answer: C) Contradiction
Explanation: A proof by contradiction assumes the opposite of the desired result and derives an impossible conclusion.
59. A proof that directly uses definitions and known facts is:
A) Direct proof
B) Contradiction
C) Induction
D) Exhaustion
Answer: A) Direct proof
Explanation: A direct proof starts with known conditions and logically derives the required conclusion.
60. Strong induction assumes the statement is true for:
A) Only k
B) Only k+1
C) All previous cases
D) No cases
Answer: C) All previous cases
Explanation: Strong induction assumes the result for every required value before k+1, rather than only for k.
Chapter 7: Number Theory and Boolean Algebra
61. A number divisible only by 1 and itself is:
A) Composite
B) Prime
C) Even
D) Perfect
Answer: B) Prime
Explanation: A prime number has exactly two positive divisors: 1 and itself.
62. Which number is prime?
A) 21
B) 27
C) 29
D) 33
Answer: C) 29
Explanation: 29 has no positive divisors other than 1 and 29, so it is prime.
63. The greatest common divisor of 12 and 18 is:
A) 2
B) 3
C) 6
D) 9
Answer: C) 6
Explanation: Common divisors are 1, 2, 3 and 6. The largest is 6.
64. The least common multiple of 4 and 6 is:
A) 8
B) 10
C) 12
D) 24
Answer: C) 12
Explanation: 12 is the smallest positive number divisible by both 4 and 6.
65. In Boolean algebra, A + 0 equals:
A) 0
B) A
C) 1
D) A’
Answer: B) A
Explanation: OR with 0 does not change the value of A. This is the identity law.
66. In Boolean algebra, A · 1 equals:
A) 0
B) 1
C) A
D) A’
Answer: C) A
Explanation: AND with 1 leaves the original Boolean value unchanged.
67. In Boolean algebra, A + A equals:
A) 0
B) 1
C) A
D) A’
Answer: C) A
Explanation: Repeating the same Boolean variable with OR does not change its value.
68. In Boolean algebra, A · A equals:
A) A
B) 0
C) 1
D) A’
Answer: A) A
Explanation: Repeating the same variable with AND also gives the original variable.
69. The complement of A + B is:
A) A’ + B’
B) A’B’
C) AB
D) A + B
Answer: B) A’B’
Explanation: De Morgan’s law changes OR to AND while complementing each variable.
70. Which gate produces 1 only when both inputs are 1?
A) OR
B) XOR
C) AND
D) NOR
Answer: C) AND
Explanation: An AND gate produces 1 only if every input is 1.
Chapter 8: Graph Theory
71. A graph consists primarily of vertices and:
A) Edges
B) Functions
C) Sets
D) Matrices
Answer: A) Edges
Explanation: Vertices represent points, while edges represent connections between those points.
72. A graph in which every pair of vertices is connected is called:
A) Bipartite graph
B) Complete graph
C) Null graph
D) Simple path
Answer: B) Complete graph
Explanation: In a complete graph, every vertex has a direct edge to every other vertex.
73. How many edges does K₄ have?
A) 4
B) 5
C) 6
D) 8
Answer: C) 6
Explanation: A complete graph has n(n−1)/2 edges. For K₄: 4×3/2 = 6.
74. A graph with no edges is called:
A) Complete graph
B) Null graph
C) Directed graph
D) Weighted graph
Answer: B) Null graph
Explanation: A null graph contains vertices but has no edges connecting them.
75. A graph whose edges have directions is:
A) Simple graph
B) Undirected graph
C) Directed graph
D) Complete graph
Answer: C) Directed graph
Explanation: Each directed edge has a specified starting and ending vertex.
76. The degree of a vertex is the number of:
A) Vertices
B) Incident edges
C) Paths
D) Cycles
Answer: B) Incident edges
Explanation: The degree counts how many edges are connected to a vertex.
77. A path that begins and ends at the same vertex is a:
A) Cycle
B) Tree
C) Trail
D) Bridge
Answer: A) Cycle
Explanation: A cycle is a closed path that returns to its starting vertex.
78. A graph containing no cycles is called:
A) Complete graph
B) Cyclic graph
C) Acyclic graph
D) Regular graph
Answer: C) Acyclic graph
Explanation: The prefix “a-” means without, so an acyclic graph contains no cycles.
79. A graph that can be divided into two independent sets is:
A) Complete graph
B) Bipartite graph
C) Cyclic graph
D) Regular graph
Answer: B) Bipartite graph
Explanation: In a bipartite graph, edges connect vertices from different sets, not within the same set.
80. Which graph representation uses an n × n matrix?
A) Adjacency matrix
B) Incidence list
C) Edge list
D) Path matrix
Answer: A) Adjacency matrix
Explanation: An adjacency matrix uses rows and columns for vertices and records whether edges exist between them.
Chapter 9: Trees
81. A connected graph with no cycles is called a:
A) Tree
B) Complete graph
C) Network
D) Circuit
Answer: A) Tree
Explanation: A tree is connected and contains no cycles. This makes there exactly one simple path between any two vertices.
82. A tree with n vertices has how many edges?
A) n
B) n+1
C) n−1
D) 2n
Answer: C) n−1
Explanation: Every tree with n vertices always contains exactly n−1 edges.
83. The topmost node of a rooted tree is called:
A) Leaf
B) Root
C) Branch
D) Parent
Answer: B) Root
Explanation: The root is the starting or highest node from which the tree structure branches.
84. A node with no children is called a:
A) Root
B) Parent
C) Leaf
D) Branch
Answer: C) Leaf
Explanation: A leaf is an end node because it has no child nodes below it.
85. In a binary tree, each node has at most:
A) One child
B) Two children
C) Three children
D) Four children
Answer: B) Two children
Explanation: A binary tree restricts every node to a maximum of two children, usually called left and right.
86. Which traversal visits Root, Left, Right?
A) Inorder
B) Postorder
C) Preorder
D) Level-order
Answer: C) Preorder
Explanation: Preorder processes the root first, followed by the left subtree and then the right subtree.
87. Which traversal visits Left, Root, Right?
A) Inorder
B) Preorder
C) Postorder
D) Level-order
Answer: A) Inorder
Explanation: Inorder visits the left subtree first, then the root, and finally the right subtree.
88. Which traversal visits Left, Right, Root?
A) Preorder
B) Inorder
C) Level-order
D) Postorder
Answer: D) Postorder
Explanation: Postorder processes both child subtrees before processing their parent node.
89. In a binary search tree, smaller values are generally placed:
A) Right
B) Left
C) Above
D) At root
Answer: B) Left
Explanation: In a binary search tree, values smaller than a node are stored in its left subtree, while larger values go right.
90. Which data structure is commonly used for hierarchical data?
A) Stack
B) Queue
C) Tree
D) Array
Answer: C) Tree
Explanation: Trees naturally represent parent-child relationships such as file directories and organizational structures.
Chapter 10: Algebraic Structures, Automata and Formal Languages
91. A set with a binary operation satisfying closure, associativity, identity and inverses forms a:
A) Group
B) Ring
C) Field
D) Lattice
Answer: A) Group
Explanation: A group must satisfy closure, associativity, identity, and inverse properties under its operation.
92. A group whose operation is commutative is called:
A) Cyclic group
B) Abelian group
C) Simple group
D) Finite group
Answer: B) Abelian group
Explanation: In an Abelian group, changing the order of the operation does not change the result.
93. Which structure has closure and associativity with an identity element?
A) Group
B) Monoid
C) Field
D) Ring
Answer: B) Monoid
Explanation: A monoid is a set with an associative binary operation and an identity element. Inverses are not required.
94. A finite-state machine consists of states and:
A) Transitions
B) Tables only
C) Variables only
D) Functions only
Answer: A) Transitions
Explanation: Transitions define how an automaton moves from one state to another when it receives input.
95. Which automaton accepts regular languages?
A) Pushdown automaton
B) Turing machine
C) Finite automaton
D) Linear bounded automaton
Answer: C) Finite automaton
Explanation: Finite automata have limited states and recognize exactly the class of regular languages.
96. Which automaton uses a stack as additional memory?
A) DFA
B) NFA
C) Pushdown automaton
D) Finite automaton
Answer: C) Pushdown automaton
Explanation: A pushdown automaton uses a stack, allowing it to recognize context-free languages.
97. A deterministic finite automaton has how many transitions for each state-symbol pair?
A) Exactly one
B) At least two
C) Zero or two
D) Unlimited
Answer: A) Exactly one
Explanation: For every state and input symbol, a DFA has exactly one defined next state.
98. Which language is recognized by a finite automaton?
A) Context-free language
B) Regular language
C) Recursive language
D) Natural language
Answer: B) Regular language
Explanation: Regular languages can be represented by regular expressions and recognized by finite automata.
99. A grammar that generates regular languages is called:
A) Context-free grammar
B) Regular grammar
C) Context-sensitive grammar
D) Unrestricted grammar
Answer: B) Regular grammar
Explanation: Regular grammars generate exactly the regular languages recognized by finite automata.
100. Which formal model is considered the most powerful among these?
A) Finite automaton
B) Pushdown automaton
C) Turing machine
D) Regular grammar
Answer: C) Turing machine
Explanation: A Turing machine has an unrestricted tape and can model general-purpose computation.