Q.1 Which of the following is a tautology?
p ∧ ¬p
p ∨ ¬p
p → q
p ∧ q
Explanation - A tautology is a statement that is always true. 'p ∨ ¬p' is always true regardless of the truth value of p.
Correct answer is: p ∨ ¬p
Q.2 What is the power set of {a, b}?
{a, b}
{∅, {a}, {b}, {a, b}}
{{a}, {b}}
{∅, {a}, {b}}
Explanation - The power set of a set is the set of all its subsets, including the empty set and the set itself.
Correct answer is: {∅, {a}, {b}, {a, b}}
Q.3 Which of the following is an example of a bijective function?
f(x) = x^2 from R to R
f(x) = x + 1 from R to R
f(x) = sin(x) from R to R
f(x) = x^3 from R to R
Explanation - A bijective function is both injective (one-to-one) and surjective (onto). f(x) = x^3 satisfies both properties over the real numbers.
Correct answer is: f(x) = x^3 from R to R
Q.4 Which logic gate is equivalent to the expression ¬(A ∧ B)?
AND
OR
NAND
NOR
Explanation - The NAND gate gives the negation of the AND operation. So ¬(A ∧ B) is exactly NAND.
Correct answer is: NAND
Q.5 What is the value of 1011 (binary) + 1101 (binary)?
10100
11000
11110
10000
Explanation - Binary addition: 1011 + 1101 = 1 0110 + 1000 = 11000 (carry handled correctly).
Correct answer is: 11000
Q.6 Which of the following sets is countably infinite?
The set of real numbers between 0 and 1
The set of integers
The set of points on a line segment
The set of all functions from R to R
Explanation - The integers can be put in one-to-one correspondence with the natural numbers, so they are countably infinite.
Correct answer is: The set of integers
Q.7 Which of the following is a valid representation of a relation R on set A = {1, 2}?
{(1, 1), (2, 2)}
{(1, 2), (2, 3)}
{1, 2}
{(1), (2)}
Explanation - A relation on a set is a subset of the Cartesian product A × A. {(1,1), (2,2)} is a subset of A × A.
Correct answer is: {(1, 1), (2, 2)}
Q.8 What is the complement of set A = {1, 2, 3} in universal set U = {1, 2, 3, 4, 5}?
{1, 2, 3}
{4, 5}
{1, 2, 3, 4, 5}
{∅}
Explanation - The complement of a set A in a universal set U is the set of all elements in U not in A.
Correct answer is: {4, 5}
Q.9 Which of the following is a necessary condition for a graph to have an Eulerian circuit?
All vertices have even degree
All vertices have odd degree
Graph is complete
Graph is connected
Explanation - For a graph to have an Eulerian circuit, all vertices must have even degree and the graph must be connected.
Correct answer is: All vertices have even degree
Q.10 If P → Q is false, what can we conclude?
P is true, Q is false
P is false, Q is true
Both P and Q are false
P is true, Q is true
Explanation - An implication P → Q is false only when P is true and Q is false.
Correct answer is: P is true, Q is false
Q.11 What is the cardinality of the set of all subsets of a set with 4 elements?
4
8
16
12
Explanation - The power set of a set with n elements has 2^n elements. 2^4 = 16.
Correct answer is: 16
Q.12 Which of the following is not a property of equivalence relations?
Reflexive
Symmetric
Transitive
Antisymmetric
Explanation - Equivalence relations are reflexive, symmetric, and transitive. They are generally not antisymmetric.
Correct answer is: Antisymmetric
Q.13 The number of edges in a complete graph with n vertices is:
n(n-1)/2
n^2
n(n+1)/2
2n
Explanation - In a complete graph, each vertex is connected to every other vertex. Number of edges = n(n-1)/2.
Correct answer is: n(n-1)/2
Q.14 Which of the following is a prime example of a simple graph?
Graph with loops
Graph with multiple edges between same vertices
Graph without loops or multiple edges
Directed graph with cycles
Explanation - A simple graph has no loops and no multiple edges between the same pair of vertices.
Correct answer is: Graph without loops or multiple edges
Q.15 Which counting principle is used when arranging n distinct objects in a sequence?
Permutation
Combination
Multiplication principle
Inclusion-exclusion
Explanation - Permutation counts arrangements where the order matters, which applies to sequences of distinct objects.
Correct answer is: Permutation
Q.16 Which of the following is a valid logical equivalence?
¬(P ∧ Q) ≡ ¬P ∨ ¬Q
¬(P ∨ Q) ≡ ¬P ∧ Q
P → Q ≡ ¬P ∧ Q
P ∧ Q ≡ P ∨ Q
Explanation - This is De Morgan's law: the negation of a conjunction is equivalent to the disjunction of the negations.
Correct answer is: ¬(P ∧ Q) ≡ ¬P ∨ ¬Q
Q.17 In a directed graph, if the in-degree and out-degree of each vertex is 2, which of the following must be true?
The graph is strongly connected
The graph has an Eulerian circuit
The graph is bipartite
The graph is complete
Explanation - A directed graph has an Eulerian circuit if it is connected and every vertex has equal in-degree and out-degree.
Correct answer is: The graph has an Eulerian circuit
Q.18 Which of the following best describes a partial order relation?
Reflexive, antisymmetric, transitive
Reflexive, symmetric, transitive
Irreflexive, symmetric, transitive
Irreflexive, antisymmetric, transitive
Explanation - A partial order relation satisfies reflexivity, antisymmetry, and transitivity.
Correct answer is: Reflexive, antisymmetric, transitive
Q.19 The number of ways to choose 3 objects from 6 distinct objects is:
20
15
18
10
Explanation - Number of combinations = C(6,3) = 6! / (3! * 3!) = 20.
Correct answer is: 20
Q.20 Which of the following statements is true about trees?
A tree with n vertices has n edges
A tree with n vertices has n-1 edges
A tree can have cycles
A tree is always disconnected
Explanation - A tree is a connected acyclic graph. It always has exactly n-1 edges for n vertices.
Correct answer is: A tree with n vertices has n-1 edges
Q.21 Which of the following is NOT a principle of mathematical induction?
Base case
Inductive hypothesis
Inductive step
Contradiction assumption
Explanation - Mathematical induction uses a base case, inductive hypothesis, and inductive step. Contradiction is a different proof method.
Correct answer is: Contradiction assumption
Q.22 Which of the following is a reflexive relation on set {1,2,3}?
{(1,1), (2,2), (3,3)}
{(1,2), (2,3)}
{(1,1), (2,2)}
{(1,2), (2,1)}
Explanation - A reflexive relation contains all pairs of the form (x,x) for all x in the set.
Correct answer is: {(1,1), (2,2), (3,3)}
Q.23 Which of the following best describes an adjacency matrix of a graph?
A matrix showing vertex degrees
A matrix representing connections between vertices
A matrix of shortest paths
A matrix of edge weights only
Explanation - An adjacency matrix represents edges of a graph: A[i][j]=1 if there is an edge between vertex i and vertex j.
Correct answer is: A matrix representing connections between vertices
Q.24 What is the truth table size for a compound proposition with 4 variables?
8
16
4
32
Explanation - For n variables, the truth table has 2^n rows. 2^4 = 16.
Correct answer is: 16