UGC NET Computer Science Discrete Structures and Optimization Previous Year Questions (PYQs)
Practise 173 Discrete Structures and Optimization questions asked in UGC NET Computer Science from 2018–2026. Questions cover Mathematical logic, Sets and relations, Counting, Group theory, Graph theory and Boolean algebra. Every question is shown with its options and the correct answer, free to read.
173 PYQs2018–2026Answers includedFree
Practise Discrete Structures and Optimization as timed sets
Focused 10-question sets with instant scoring, explanations, and weak-area analysis.
How many edges are there in a graph with 10 vertices, each of degree six?
A60
B45
C20
D30
Answer:(D) 30
Explanation
By the handshaking lemma, the sum of degrees equals twice the number of edges. The degree sum is 10 × 6 = 60, so the graph has 60/2 = 30 edges. Taking 60 itself would confuse the degree sum with the edge count.
Which of the following have true value when the universe of discourse is all integers?
A. ∃n (2n = 3n)
B. ∃n (n² > n)
C. ∀n (2n > n)
D. ∃n (n² = 2)
E. ∀x∀y ∃z (xy = z)
AB, C and E only
BA, B and E only
CA, B, C and D only
DB, C, D and E only
Answer:(B) A, B and E only
Explanation
A is true at n = 0, and B is true, for example at n = 2. C fails at negative integers, D is false because √2 is not an integer, and E is true because the product of any two integers is an integer. Hence A, B and E are true.
Let ⟨H₁, *⟩ and ⟨H₂, *⟩ be subgroups of the group ⟨G, *⟩. Which statement is false?
AH₁H₂ = {h₁ * h₂ : h₁ ∈ H₁ and h₂ ∈ H₂} is a subgroup.
BH₁H₂ is a normal subgroup when H₁ and H₂ are normal subgroups.
C⟨H₁ ∩ H₂, *⟩ is a subgroup.
DThe set difference H₁ − H₂ is a subgroup.
Answer:(A) H₁H₂ = {h₁ * h₂ : h₁ ∈ H₁ and h₂ ∈ H₂} is a subgroup.
Explanation
The supplied source confirms option A as the false statement. The product set H₁H₂ need not be a subgroup unless additional conditions, such as normality of one factor, hold. Intersections of subgroups are always subgroups.
Each relation is defined on {1, 2, 3, 4}. Match List-I with List-II.
List-I: Relation
List-II: Relation type
A. {(2,2), (2,3), (2,4), (3,2), (3,3), (3,4)} B. {(2,4), (4,2)} C. {(1,2), (2,3), (3,4)} D. {(1,3), (1,4), (2,3), (2,4), (3,1), (3,4)}
I. Antisymmetric II. Only transitive III. Only symmetric IV. Neither symmetric nor transitive
AA-II, B-III, C-I, D-IV
BA-II, B-III, C-IV, D-I
CA-IV, B-III, C-I, D-II
DA-I, B-III, C-IV, D-II
Answer:(A) A-II, B-III, C-I, D-IV
Explanation
A is transitive: its chained pairs such as (2,3) and (3,4) require (2,4), which is present, but it is not symmetric. B contains both (2,4) and (4,2), making it only symmetric. C has no reversed distinct pair, so it is antisymmetric, while D has neither property. Hence A-II, B-III, C-I, D-IV is the required match.
How many solutions does x + y + z = 11 have, where x, y, and z are non-negative integers?
A33
B66
C68
D78
Answer:(D) 78
Explanation
By stars and bars, the number of non-negative solutions to x + y + z = 11 is C(11 + 3 − 1, 3 − 1) = C(13, 2) = 78. This counts every allocation of 11 identical units among the three variables.
Out of 32 people, 30 save paper and 14 save plastic bottles. If every person saves paper, plastic bottles, or both, how many save both?
A12
B14
C16
D18
Answer:(A) 12
Explanation
Use inclusion–exclusion: |paper ∩ plastic| = |paper| + |plastic| − |paper ∪ plastic| = 30 + 14 − 32 = 12. Adding the two group totals without subtracting the overlap would double-count those 12 people.
A. Commutative law B. Distributive law C. De Morgan law D. Absorption law
I. P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R) II. P ∧ (P ∨ Q) ≡ P III. P ∧ Q ≡ Q ∧ P IV. ¬(P ∨ Q) ≡ ¬P ∧ ¬Q
AA-III, B-IV, C-II, D-I
BA-II, B-I, C-IV, D-III
CA-III, B-I, C-IV, D-II
DA-IV, B-II, C-III, D-I
Answer:(C) A-III, B-I, C-IV, D-II
Explanation
Commutativity is P ∧ Q ≡ Q ∧ P (III). Distribution is P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R) (I), De Morgan's law is ¬(P ∨ Q) ≡ ¬P ∧ ¬Q (IV), and absorption is P ∧ (P ∨ Q) ≡ P (II). Thus the apparently similar formulas in I and II must not be swapped: I expands a conjunction while II removes a redundant disjunction.
Arrange these numbers in ascending order by the number of distinct prime factors.
A. 729
B. 1001
C. 1111
D. 420
AA, C, B, D
BD, A, B, C
CA, B, C, D
DD, A, C, B
Answer:(A) A, C, B, D
Explanation
Factor each number and count unique primes, not repeated powers: 729 = 3⁶ has 1; 1111 = 11 × 101 has 2; 1001 = 7 × 11 × 13 has 3; and 420 = 2² × 3 × 5 × 7 has 4. Sorting those counts from 1 to 4 gives A, C, B, D.
The number of vertices of odd degree in any graph is:
AOdd
BEven
Cn − e
DPrime
Answer:(B) Even
Explanation
By the handshaking lemma, the sum of all vertex degrees equals 2e and is even. An even sum can contain only an even number of odd summands, so odd-degree vertices occur in pairs.
Match the equivalent propositions in List-I and List-II.
List-I
List-II
A. P → (Q → P) B. P → (Q ∨ R) C. (P → Q) ∧ (R → Q) D. ¬(P ⇔ Q)
I. (P ∨ Q) ∧ ¬(P ∧ Q) II. (P ∨ R) → Q III. (P → Q) ∨ (P → R) IV. ¬P → (P → Q)
AA-IV, B-II, C-III, D-I
BA-IV, B-III, C-II, D-I
CA-I, B-II, C-III, D-IV
DA-I, B-III, C-II, D-IV
Answer:(B) A-IV, B-III, C-II, D-I
Explanation
For A, Q → P is ¬Q ∨ P, so P → (Q → P) is ¬P ∨ ¬Q ∨ P, a tautology; IV is also a tautology. For B, P → (Q ∨ R) becomes ¬P ∨ Q ∨ R, exactly III. Applying (X→Q) = ¬X∨Q to C gives (¬P∨Q)∧(¬R∨Q) = ¬(P∨R)∨Q, which is II. Finally ¬(P⇔Q) is true exactly when one, but not both, of P and Q is true, which is I.
Let P denote power set and ∅ the empty set. Arrange in non-decreasing cardinality:
A. P({a,b,{a,b}})
B. P({∅,a,{a},{{a}}})
C. P(P(∅))
D. P(P({a}))
E. P({{a,b},c})
AC, D, A, B, E
BD, C, E, A, B
CC, D, E, A, B
DD, C, B, A, E
Answer:(C) C, D, E, A, B
Explanation
P(∅) has one member, so C = P(P(∅)) has 2 members. P({a}) has 2 members, so D has 4; E also has two underlying elements and has 4. A has three underlying elements and therefore 8 members, while B has four and therefore 16. Thus C, D, E, A, B is the listed non-decreasing order.
Let R = {(1,2),(3,4),(2,2)} and S = {(4,2),(2,5),(3,1),(1,3)}. What is R ∘ S?
A{(4,2),(3,2),(2,5)}
B{(1,5),(3,2),(2,5)}
C{(3,1),(2,5)}
D{(2,5),(3,1),(2,3),(3,3)}
Answer:(B) {(1,5),(3,2),(2,5)}
Explanation
Using the paper's stated composition convention, the resulting relation is {(1,5),(3,2),(2,5)}, which is option B. This convention fixes the order in which the two relation mappings are composed for this question.
A. a circuitless connected graph
B. a connected graph of n vertices with (n − 1) edges
C. a circuitless graph of n vertices with (n − 1) edges
D. a minimally connected graph
AA, B and C only
BB, C and D only
CA, B, C and D
DA and B only
Answer:(C) A, B, C and D
Explanation
These are equivalent characterisations of a finite tree. A connected acyclic graph has n − 1 edges; an acyclic graph with n − 1 edges is connected; and every edge is necessary for connectivity, which is minimal connectedness.
Which additional property must a group (G, *) satisfy to be an abelian group?
ACommutative
BIdentity
CInverse
DAssociativity
Answer:(A) Commutative
Explanation
A group already has an associative operation, an identity, and inverses. It is called abelian precisely when its operation is also commutative: a * b = b * a for every pair of group elements.
I. Probabilistic model II. Deterministic model III. 4-colourable IV. 2-colourable
AA-II, B-IV, C-I, D-III
BA-III, B-IV, C-I, D-II
CA-II, B-IV, C-I, D-III
DA-III, B-IV, C-II, D-I
Answer:(B) A-III, B-IV, C-I, D-II
Explanation
A planar graph is four-colourable (III), a bipartite graph is two-colourable (IV), PERT is probabilistic (I), and CPM is deterministic (II). This gives A-III, B-IV, C-I, D-II.
Which of the following statements are true if the universe of discourse for all variables consists of all integers?
A. ∀n∃m(n² < m)
B. ∃n∃m(n + m = 4 ∧ n − m = 2)
C. ∃n∃m(n² + m² = 5)
D. ∃m∀n(m + n = 0)
E. ∀m∃n(m + n = 0)
AA, B & C Only
BA, B, C & D Only
CA, B, C & E Only
DB, C, E & D Only
Answer:(C) A, B, C & E Only
Explanation
Each statement must be checked on its own quantifier structure before combining them.
A. True. For any integer n, choosing m = n² + 1 always makes n² < m, since integers are unbounded above.
B. True. Solving n + m = 4 and n − m = 2 together gives n = 3 and m = 1, both integers, so such a pair exists.
C. True. Taking n = 1 and m = 2 gives 1² + 2² = 5, so such integers exist.
D. False. This asks for one fixed m that satisfies m + n = 0 for every integer n, but no single m can be the negative of every n at once.
E. True. This asks whether, for every m, some n makes m + n = 0, and n = −m always works because n is chosen after m is fixed.
D and E look similar but the quantifier order reverses their meaning. E lets n depend on m, so it is always satisfiable, while D forces one m to work for all n, which is impossible. A, B, C and E hold, so A, B, C & E Only is correct.
Given below are two statements: one is labelled as Assertion A and the other is labelled as Reason R
Assertion (A): Let R ⊆ A × A be a binary relation as defined below: A = N × N; ((a,b),(c,d)) ∈ R if only if a ≤ c or b ≤ d. This binary relation R is a partial order.
Reason (R): A binary relation will be a partial order if this satisfy reflexive, anti-symmetric and transitive property.
ABoth A and R are correct and R is the correct explanation of A
BBoth A and R are correct but R is NOT the correct explanation of A
CA is correct but R is not correct
DA is not correct but R is correct
Answer:(D) A is not correct but R is correct
Explanation
A partial order must be reflexive, antisymmetric and transitive, and Reason R states this standard definition correctly.
Checking Assertion A against this definition on A = N × N with ((a,b),(c,d)) ∈ R iff a ≤ c or b ≤ d.
Reflexivity holds trivially, since a ≤ a is always true.
Antisymmetry fails. Take (1,5) and (5,1). Since 1 ≤ 5, (1,5) R (5,1) holds. For the reverse pair, 5 ≤ 1 is false but 1 ≤ 5 is true, so (5,1) R (1,5) also holds. Both distinct pairs relate to each other in both directions, which violates antisymmetry.
Since the relation is not antisymmetric, it is not a partial order, so Assertion A is false while Reason R correctly states the definition of a partial order.
DThe ring Zₚ of integers module p is field iff p is prime.
Answer:(B) Every integral domain is field.
Explanation
A field requires every nonzero element to have a multiplicative inverse, which automatically rules out zero divisors, so every field is also an integral domain. This makes the first statement true, not the false one being asked for.
The reverse direction fails. The integers Z form an integral domain, since they have no zero divisors, but Z is not a field because an element like 2 has no multiplicative inverse within Z. So every integral domain is a field is the false statement.
The remaining two statements are standard true results. A finite integral domain is always a field, because multiplication by any nonzero element is an injective, and therefore surjective, map on a finite set, which produces the needed inverse. Zₚ is a field exactly when p is prime, since only then does every nonzero residue have a multiplicative inverse modulo p.
Assertion (A): The order of the group (Z₅, ×) divides the order of the group (Z₁₃, ×).
Reason (R): The order of a subgroup of a group divides the order of the group.
ABoth A and R are correct and R is the correct explanation of A
BBoth A and R are correct but R is NOT the correct explanation of A
CA is correct but R is not correct
DA is not correct but R is correct
Answer:(B) Both A and R are correct but R is NOT the correct explanation of A
Explanation
The multiplicative group (Z₅, ×) consists of the nonzero residues {1, 2, 3, 4} under multiplication mod 5, giving order 4. The multiplicative group (Z₁₃, ×) consists of {1, 2, ..., 12} under multiplication mod 13, giving order 12.
Since 4 divides 12, Assertion A is numerically true.
Reason R states Lagrange's theorem, that the order of a subgroup always divides the order of its parent group. This is a true general statement.
However, R does not explain A here. Lagrange's theorem applies only when one group is an actual subgroup of the other, sharing the same underlying set and operation. (Z₅, ×) is not a subset of (Z₁₃, ×) at all, since its elements are residues mod 5 combined under multiplication mod 5, a different operation from multiplication mod 13. The divisibility in A is a coincidental numerical fact, not an instance of the subgroup relationship that R describes.
So both A and R are correct as standalone statements, but R is not the correct explanation of A.
Which of the following logical implications are tautologies?
A. [~p ∧ (p ∨ q)] → q
B. ~p → (p → q)
C. [p ∧ (p → q)] → q
D. ~(p → q) → q
AA & B Only
BB & D Only
CA, B & C Only
DB, C & D Only
Answer:(C) A, B & C Only
Explanation
An implication is a tautology when it evaluates to true for every combination of truth values of its variables.
A. [~p ∧ (p ∨ q)] → q — this is true in every row: whenever ~p ∧ (p ∨ q) is true, p must be false and q must be true to make p ∨ q true, so q is guaranteed. It is a tautology.
B. ~p → (p → q) — whenever p is false, the consequent p → q is automatically true, and whenever p is true, the antecedent ~p is false, making the whole implication true either way. It is a tautology.
C. [p ∧ (p → q)] → q — this is modus ponens, one of the most basic valid inference forms, and it holds in every row of its truth table. It is a tautology.
D. ~(p → q) → q — taking p = true and q = false makes p → q false, so ~(p → q) is true, but q itself is false, giving a true antecedent and a false consequent. The implication is false in this case, so D is not a tautology.
Only A, B and C hold in every case, so the correct set is A, B & C Only.
If the set S = { [a 0; 0 b] : a, b ∈ Z } is a subring of the ring M₂ of 2×2 matrices over the integers, then S is a
Aleft ideal but not right ideal
Bright ideal but not left ideal
Cboth left and right ideal
Dneither left ideal nor right ideal
Answer:(D) neither left ideal nor right ideal
Explanation
Let D = [[a, 0], [0, b]] be an arbitrary element of S and let M = [[p, q], [r, s]] be an arbitrary element of M₂(Z).
Computing D·M gives [[ap, aq], [br, bs]], which has off-diagonal entries aq and br that are nonzero whenever q or r is nonzero, so D·M does not stay inside S for every choice of M.
Computing M·D gives [[pa, qb], [ra, sb]], which has off-diagonal entries qb and ra that are again nonzero in general, so M·D also does not stay inside S for every choice of M.
Since multiplying a diagonal matrix by an arbitrary matrix of M₂(Z), on either side, can introduce nonzero off-diagonal entries, S fails the absorption condition needed for both a left ideal and a right ideal. So S is neither a left ideal nor a right ideal, even though it is a valid subring on its own.
Match List-I (Optimization methods) with List-II (Problem types).
List-I
List-II
A. Branch and bound method
I. Integer programming problem
B. North-west corner rule
II. Quadratic programming problem
C. Lagrange multiplier method
III. Transportation problem
D. Wolfe's modified method
IV. Non-linear programming problem
AA-III, B-II, C-IV, D-I
BA-I, B-III, C-IV, D-II
CA-II, B-I, C-IV, D-III
DA-IV, B-I, C-II, D-III
Answer:(B) A-I, B-III, C-IV, D-II
Explanation
Each optimization technique listed is the standard method for one particular class of problem.
The branch and bound method (A) systematically explores and prunes a search tree of candidate integer solutions, making it the classic method for integer programming problems, so A pairs with I.
The north-west corner rule (B) constructs an initial basic feasible solution for a transportation problem, so B pairs with III.
The Lagrange multiplier method (C) finds stationary points subject to equality constraints and is the standard technique for non-linear programming problems, so C pairs with IV.
Wolfe's modified simplex method (D) extends the simplex method to handle a quadratic objective function, making it the standard method for quadratic programming problems, so D pairs with II.
Each Boolean algebra law has a distinct standard form.
The domination law states that x + 1 = 1, since ORing anything with 1 always yields 1, so A pairs with I.
The associative law states that x + (y + z) = (x + y) + z, since grouping does not affect the result of repeated OR operations, so B pairs with IV.
The distributive law states that x + (yz) = (x + y)(x + z), since OR distributes over AND, so C pairs with II.
The absorption law states that x + xy = x, since the xy term is absorbed once x is already true, so D pairs with III.
If Kₙ is complete simple graph of n vertices and Kₘ,ₙ is complete bipartite graph then arrange the following non-planner graph in ascending order on the bases of the minimum number of crossings.
A. K₆
B. K₇
C. K₄,₄
D. K₅,₅
AA, B, C, D
BC, D, A, B
CA, C, B, D
DB, D, A, C
Answer:(C) A, C, B, D
Explanation
The crossing number cr(G) of a graph is the minimum number of edge crossings achievable in any drawing of that graph, and for small complete and complete-bipartite graphs it is known exactly (the Zarankiewicz result, proven for these cases).
In a group of 120 people, 65 eat rice, 45 eat bread, 42 eat curd, 20 eat both rice and bread, 25 eat both rice and curd, 15 eat both bread and curd, and 8 eat all three. How many eat at least one of the three items?
A56
B100
C92
D65
Answer:(B) 100
Explanation
Apply inclusion-exclusion: 65 + 45 + 42 - 20 - 25 - 15 + 8 = 100. The pairwise overlaps were subtracted once too often, so the triple overlap is added back once.
A positive integer is selected uniformly from the integers not exceeding 200. What is the probability that it is divisible by either 2 or 5?
A2/5
B3/5
C4/5
D1/5
Answer:(B) 3/5
Explanation
There are 100 multiples of 2 and 40 multiples of 5 up to 200. The 20 multiples of 10 were counted twice, so the favourable count is 100 + 40 - 20 = 120. Thus the probability is 120/200 = 3/5.
Consider the Boolean expression A(x, y, z) = x(y'z)'. Which is its complete sum-of-products form?
Axyz + x'yz' + x'y'z'
Bxyz' + x'yz' + x'y'z'
Cxyz' + xy'z + x'y'z'
Dxyz + xyz' + xy'z'
Answer:(D) xyz + xyz' + xy'z'
Explanation
By De Morgan's law, (y'z)' = y + z'. Hence A = x(y + z') = xy + xz'. Expanding xy as xyz + xyz' and xz' as xyz' + xy'z', then removing the duplicate xyz', gives xyz + xyz' + xy'z'. The other choices introduce minterms with x' or omit one required minterm.
AIf (xy)^2 = x^2y^2 for all x, y in G, then G is commutative.
BIf x^3 = 1 for all x in G, then G is commutative.
CIf x^5 = 1 for all x in G, then G is commutative.
DIf G is commutative, a subgroup of G need not be commutative.
Answer:(A) If (xy)^2 = x^2y^2 for all x, y in G, then G is commutative.
Explanation
The stated identity gives xyxy = xxyy. Multiplying by x⁻¹ on the left and y⁻¹ on the right yields yx = xy, so G is commutative. The exponent conditions alone do not force commutativity, and every subgroup of an abelian group is abelian.
Let P mean “she is intelligent” and Q mean “she is happy.” Which set correctly formalizes: intelligent implies unhappy; neither intelligent nor happy; being not intelligent is necessary for happiness; and not intelligent implies unhappy?
AP → ¬Q; P ∧ ¬Q; Q → ¬P; P → ¬Q
BP → Q; ¬P ∧ ¬Q; ¬Q → P; ¬P → ¬Q
CP → ¬Q; ¬P ∧ ¬Q; Q → ¬P; ¬P → ¬Q
DP → ¬Q; P ∧ ¬Q; Q → P; ¬P → ¬Q
Answer:(C) P → ¬Q; ¬P ∧ ¬Q; Q → ¬P; ¬P → ¬Q
Explanation
“Neither” means ¬P ∧ ¬Q. “Not intelligent is necessary for happy” makes happiness imply not intelligent, Q → ¬P. The first and fourth implications are P → ¬Q and ¬P → ¬Q respectively, so only option C has all four forms.
For positive integers m and n, which statements are correct: n ≠ 1 implies m < mn; a composite k can be written k = mn with 1 < m,n > k; mn = 1 implies m = n = 1; and a composite k can be written k = mn with 1 < m,n < k?
AA, C, D only
BB, C, D only
CA, B only
DA, B, C
Answer:(A) A, C, D only
Explanation
If n ≠ 1, positivity makes n at least 2, hence m < mn. A product of positive integers can equal 1 only when both are 1. A composite number has proper factors strictly between 1 and k, so D is true; B is impossible because two factors greater than k cannot multiply to k.
Match the statements about the Indian team with inverse, converse, contrapositive, and conditional forms.
List I
List II
A. If the Indian team wins, then it is raining
I. Inverse
B. If the Indian team does not win, then it is not raining
II. Converse
C. If it is raining, then the Indian team wins
III. Contrapositive
D. If it is not raining, then the Indian team does not win
IV. Conditional
AA-II, B-I, C-IV, D-III
BA-III, B-I, C-II, D-IV
CA-II, B-III, C-IV, D-I
DA-III, B-II, C-IV, D-I
Answer:(C) A-II, B-III, C-IV, D-I
Explanation
Take “if it is raining, the team wins” as the conditional, C-IV. Its converse is “if the team wins, it is raining,” A-II; its contrapositive is “if the team does not win, it is not raining,” B-III; and its inverse is D-I. Hence option C.
Arrange the following graphs by number of edges in increasing order, for n > 3.
A. Kₙ (complete graph)
B. Cₙ (cycle graph)
C. Wₙ (wheel graph)
D. Kₙ,ₙ (complete bipartite graph)
E. Qₙ (n-cube graph)
AA, B, C, D, E
BB, A, C, D, E
CA, B, C, E, D
DE, D, C, A, B
Answer:(B) B, A, C, D, E
Explanation
The cycle has the fewest edges. Applying the graph definitions and the paper’s official key gives B, A, C, D, E; the remaining sequences place the cycle or complete graph incorrectly. The correct option follows from the stated definition or calculation; the other options omit a necessary condition or describe a different concept.
Which of the following is the complement of the Boolean function AB + CD′ + A′B + CD′?
AA′B + CD
B(A′ + B)(C + D′)
C(A + B′)(C′ + D)
DAB′ + CD′
Answer:(C) (A + B′)(C′ + D)
Explanation
First simplify AB + A′B to B, giving F = B + CD′. By De Morgan’s law, F′ = B′(C′ + D), which is represented by the keyed option. The correct option follows from the stated definition or calculation; the other options omit a necessary condition or describe a different concept.
Consider the LPP: maximise z = 30x − 18y subject to 3x + 4y ≤ 60, 5x − 3y ≥ 20, and x, y ≥ 0. Which listed point is the solution?
A. (4, 0)
B. (2, 0)
C. (7, 5)
D. (0, 15)
E. (8, 5)
AA and C only
BB only
CE only
DD only
Answer:(C) E only
Explanation
Feasibility must be checked first, then the objective compared. Point E satisfies both inequalities and gives z = 150, exceeding the other feasible listed points. The correct option follows from the stated definition or calculation; the other options omit a necessary condition or describe a different concept.
If x and y are elements of a group G, x⁵ = y³ = e, and e is the identity, then the inverse of x²yx⁴y² is
Ay²xy²x⁴
Byxy²x³
Cyx⁶y⁶x³
Dx⁴y²x²y
Answer:(B) yxy²x³
Explanation
The inverse reverses the factor order: y⁻²x⁻⁴y⁻¹x⁻². Since x⁵ = e and y³ = e, this becomes yxy²x³, which is option B. The correct option follows from the stated definition or calculation; the other options omit a necessary condition or describe a different concept.
A. ∅ ∈ ∅
B. ∅ ∈ {∅}
C. {∅} ⊂ {∅, {∅}}
D. {∅} ∈ {∅}
E. {∅} ⊂ (∅, {∅})
AA, B, C, D and E
BA, B, C and E only
CA and C only
DC and E only
Answer:(D) C and E only
Explanation
The empty set is not an element of itself, but it is an element of {∅}. Careful distinction between membership (∈) and subset (⊂) makes C and E the correct statements. The correct option follows from the stated definition or calculation; the other options omit a necessary condition or describe a different concept.
Which one is not a basic solution of the system x₁ + 2x₂ + x₃ = 4 and 2x₁ + x₂ + 5x₃ = 5?
Ax₁ = −1, x₂ = 2, x₃ = 1
Bx₁ = 2, x₂ = 1
Cx₁ = 5, x₃ = −1
Dx₂ = 5/3, x₃ = 2/3
Answer:(A) x₁ = −1, x₂ = 2, x₃ = 1
Explanation
A basic solution sets one variable to zero and solves the two equations for the remaining variables. Option A gives three nonzero assignments and does not satisfy that basic-solution construction.
A. Absorption law B. Bounded law C. Identity law D. Distributive law
I. a + 1 = 1 II. a + 0 = a III. a(b + c) = ab + ac IV. a + ab = a
AA-IV, B-I, C-II, D-III
BA-IV, B-III, C-I, D-II
CA-III, B-IV, C-II, D-I
DA-II, B-III, C-IV, D-I
Answer:(A) A-IV, B-I, C-II, D-III
Explanation
Absorption is a + ab = a; bounded law is a + 1 = 1; identity is a + 0 = a; and distributivity is a(b + c) = ab + ac. The correct option follows from the stated definition or calculation; the other options omit a necessary condition or describe a different concept.
Which is the simplified form of the Boolean function with minterms Σm(0, 1, 3, 7) over variables A, B and C?
AA′B′C + A′B′C + A′BC + ABC
BA′B′ + A′BC + ABC
CA′B′ + BC
DA′B′ + BC′
Answer:(C) A′B′ + BC
Explanation
A′B′ covers minterms 0 and 1, while BC covers minterms 3 and 7. Together these terms cover exactly Σm(0,1,3,7). The correct option follows from the stated definition or calculation; the other options omit a necessary condition or describe a different concept.
The probability that A hits a target is 1/4 and the probability that B hits the target is 2/5. Both shoot. What is the probability that at least one hits the target?
A3/5
B11/9
C2/20
D11/20
Answer:(D) 11/20
Explanation
Use the complement: P(at least one hit) = 1 − P(neither hits) = 1 − (3/4)(3/5) = 1 − 9/20 = 11/20. The correct option follows from the stated definition or calculation; the other options omit a necessary condition or describe a different concept.
Match List-I with List-II: Match the logical equivalence propositions.
List-I
List-II
A. p → q B. ¬(p ∨ (¬p ∧ q)) C. p ↔ q D. ¬(p ↔ q)
I. (p ∧ q) ∨ (¬p ∧ ¬q) II. ¬p ∨ q III. ¬(p ∨ q) IV. ¬p ↔ q
AA-I, B-III, C-II, D-IV
BA-I, B-II, C-III, D-IV
CA-II, B-III, C-I, D-IV
DA-II, B-III, C-IV, D-I
Answer:(C) A-II, B-III, C-I, D-IV
Explanation
p → q is ¬p ∨ q; ¬(p ∨ (¬p ∧ q)) simplifies to ¬(p ∨ q); p ↔ q is (p ∧ q) ∨ (¬p ∧ ¬q); and its negation is ¬p ↔ q. The correct option follows from the stated definition or calculation; the other options omit a necessary condition or describe a different concept.
The mathematical notation to describe logical entailment of a sentence α entails another sentence β is
Aα ⊨ β
Bα ⊆ β
Cβ ⊨ α
Dβ ⊆ α
Answer:(A) α ⊨ β
Explanation
Semantic entailment is written α ⊨ β: every interpretation that satisfies α also satisfies β. It is neither set inclusion nor entailment in the reverse direction. The correct option follows from the stated definition or calculation; the other options omit a necessary condition or describe a different concept.
Which of the three displayed graphs is/are planar?
Graphs A, B and C for Question 133
AA and C only
BB only
CA only
DA and B only
Answer:(C) A only
Explanation
Graph A is planar because it can be redrawn without any edge crossings. Graphs B and C contain non-planar configurations, so only A is planar and option C is correct. The correct option follows from the stated definition or calculation; the other options omit a necessary condition or describe a different concept.
Consider the given number (45) y where y is the
base of the number. Some of the possible values
of y are given below.
A. 5
B. 6
C. 7
D. 8
A(A), (B) and (C) Only
B(B), (C) and (D) Only
C(A), (C) and (D) Only
D(A), (B), (C) and (D)
Answer:(B) (B), (C) and (D) Only
Explanation
In base y every digit used must be smaller than y. The numeral 45 uses the digit 5, so y must exceed 5. Base 5 is therefore invalid, while bases 6, 7 and 8 all admit the digits 4 and 5. The valid values are (B), (C) and (D) — option B.
Let P be "It is hot day" and q be "The
temperature is 48°C". Write in simple sentences
the meaning of ¬p∧¬q.
AIt is hot day or temperature is 48°C
BIt is cold day or temperature is 48°C
CIt is neither a hot day nor temperature is 48°C
DIt is not a hot day
Answer:(C) It is neither a hot day nor temperature is 48°C
Explanation
¬p reads “it is not a hot day” and ¬q reads “the temperature is not 48°C”. The conjunction asserts both at once, which in plain English is “it is neither a hot day nor is the temperature 48°C”. Option C says exactly that; options A and B use “or”, and option D drops the second conjunct.
A graph G with number of vertices greater and
equal than three i.e. (n ≥ 3) is a Hamiltonian
graph, if the degree of each vertex is greater and
equal to . . . .
AEqual to number of vertices
BDouble of number of vertices
CHalf of number of vertices
DFour times of number of vertices
Answer:(C) Half of number of vertices
Explanation
Dirac’s theorem states that a simple graph on n ≥ 3 vertices in which every vertex has degree at least n/2 is Hamiltonian. The threshold is therefore half the number of vertices, so option C is correct.
A coin is tossed successively three times. Find the
Probability (P), Event (E), Sample space (S) of
getting exactly one head or two heads, where n
is number of occurrence.
A. n(S) = 8 and n(E) = 4
B. n(E) = 6 and n(S) = 8
C. P(E) = 3/4
D. P(E) = 1/2
A(A), (B), (C) and (D)
B(B) and (C) Only
C(A) and (D) Only
D(C) and (D) Only
Answer:(B) (B) and (C) Only
Explanation
Three tosses give n(S) = 2³ = 8. “Exactly one head or exactly two heads” covers every outcome except HHH and TTT, so n(E) = 6 and P(E) = 6/8 = 3/4. Statements (B) and (C) hold while (A) and (D) do not, so option B is correct.
Out of the following steps in the proper
sequence for simplifying a Boolean function
using a Karnaugh map (K-map).
A. Identify and group the largest possible
cluster of 1's
B. Draw the K-map for the given Boolean
function
C. Write the simplified Boolean expression from
the grouped clusters
D. Transfer the truth table values to the K-map
A(B), (D), (A), (C)
B(D), (B), (A), (C)
C(B), (A), (D), (C)
D(A), (B), (C), (D)
Answer:(A) (B), (D), (A), (C)
Explanation
Simplifying with a Karnaugh map goes: draw the map for the function (B), transfer the truth-table values into its cells (D), group the largest possible clusters of 1s (A), then read the simplified expression off those groups (C). That order is option A.
Let L (x , y) be the statement "x loves y" where
the domain for both x and y consists of all people
in the world. Use quantifiers to express "Joy is
loved by everyone".
A∀x L(x,Joy)
B∀y L(Joy,y)
C∃y∀x L(x,y)
D∃x¬ L(Joy,x)
Answer:(A) ∀x L(x,Joy)
Explanation
“Joy is loved by everyone” says that for every person x, x loves Joy — that is ∀x L(x, Joy). Option B reverses the roles and says Joy loves everyone; option C only asserts that somebody is universally loved; option D is an existential negation. Option A is correct.
(A) A bag contains 6 white and 4 red balls. Two balls are drawn at random. What is the chance they will be the same colour?
(I) 3/68
(B) In a pack of 52 cards, one card is drawn at random. What is the probability that it is either a king or a queen?
(II) 14/68
(C) A bag contains 6 red, 4 white and 8 blue balls. If three balls are drawn at random, find the probability of 1 red and 2 white balls.
(III) 2/13
(D) A bag contains 6 red, 4 white and 8 blue balls. If three balls are drawn at random, find the probability of 2 blue and 1 red balls.
(IV) 7/15
A(A)-(III), (B)-(IV), (C)-(I), (D)-(II)
B(A)-(III), (B)-(IV), (C)-(II), (D)-(I)
C(A)-(IV), (B)-(III), (C)-(II), (D)-(I)
D(A)-(IV), (B)-(III), (C)-(I), (D)-(II)
Answer:(D) (A)-(IV), (B)-(III), (C)-(I), (D)-(II)
Explanation
There are C(10,2) = 45 equally likely pairs and C(6,2) + C(4,2) = 21 same-colour pairs, so the first probability is 21/45 = 7/15 and (A)-(IV). A pack holds 4 kings and 4 queens, so 8/52 = 2/13 and (B)-(III). From 18 balls C(18,3) = 816; one red with two white gives C(6,1)C(4,2) = 36, so 36/816 = 3/68 and (C)-(I). Two blue with one red gives C(8,2)C(6,1) = 168, so 168/816 = 14/68 and (D)-(II). Option D is correct.
(I) Find the shortest path between all pairs of vertices in a graph with positive or negative edge weights.
(B) Floyd-Warshall Algorithm
(II) Finds the shortest path in a weighted graph with non-negative edge weights.
(C) Bellman-Ford Algorithm
(III) Finds single-source shortest paths with possible negative weights.
(D) Prim’s Algorithm
(IV) Finds the Minimum Spanning Tree (MST).
A(A)-(I), (B)-(II), (C)-(III), (D)-(IV)
B(A)-(II), (B)-(I), (C)-(III), (D)-(IV)
C(A)-(I), (B)-(II), (C)-(IV), (D)-(III)
D(A)-(III), (B)-(II), (C)-(IV), (D)-(I)
Answer:(B) (A)-(II), (B)-(I), (C)-(III), (D)-(IV)
Explanation
Dijkstra’s algorithm needs non-negative edge weights, so (A)-(II). Floyd-Warshall solves all-pairs shortest paths, giving (B)-(I). Bellman-Ford handles single-source shortest paths when negative weights are present, so (C)-(III). Prim’s algorithm builds a minimum spanning tree, so (D)-(IV). Option B is correct.
An undirected graph has vertex set V and edge set E. If it has l edges, what is the sum of the degrees of all vertices?
A2l
Bl/2
Cl²
D√l
Answer:(A) 2l
Explanation
Each undirected edge contributes one to the degree of each of its two endpoints. By the handshaking lemma, the total degree is 2l, so option A is correct.
Translate ∀x ∃y (x < y) into English. Consider the domain to be the real numbers for both variables.
AFor all real numbers x, there exists a real number y such that x is less than y
BFor every real numbers y, there exists a real number x such that x is less than y
CFor some real numbers x, there exists a real number y such that x is less than y
DFor each and every real numbers x and y, x is less than y
Answer:(A) For all real numbers x, there exists a real number y such that x is less than y
Explanation
∀x binds every real number x, and for each of them ∃y asserts that some real y exists with x < y. Read literally: for all real numbers x there exists a real number y such that x is less than y. Option A states this; option B swaps the quantified variables, option C weakens ∀ to “for some”, and option D collapses both quantifiers into a single universal claim.
What is the probability that a positive integer selected at random from the set of positive integer not exceeding 100 is divisible by either 2 or 5 ?
A10/5
B3/5
C2/5
D1/5
Answer:(B) 3/5
Explanation
The key idea is stated in the problem: What is the probability that a positive integer selected at random from the set of positive integer not exceeding 100 is divisible by either 2 or 5 ?. The correct answer is B: 3/5. It follows the governing definition, algorithm, or calculation in this discrete structures and optimization item; the other choices fail to satisfy one or more stated conditions.
In a feed forward neural network with the following specifications : Input layer has 4 neurons, hidden layer has 3 neurons and output layer has 2 neurons using the sigmoid activation function for given input values [0.5, 0.8, 0.2, 0.6] as well as the initial weights for the connections. WI : (0.1, 0.3, 0.5, 0.2] W2e [02,04 0.6,.0.2] Input layer to hidden layer weights W3 : [0.3, 0.5, 0.7, 0.2] W4 : (0.4, 0.1, 0.3] W5 : [0.5, 0.2, 0.4] Hidden layer to output layer weights What is the output of the output layer when the given input values are passed through neural network ? Round the answer to two decimal places :
A[0.62, 0.68]
B[0.72, 0.78]
C[0.82, 0.88]
D[0.92, 0.98]
Answer:(A) [0.62, 0.68]
Explanation
The key idea is stated in the problem: In a feed forward neural network with the following specifications : Input layer has 4 neurons, hidden layer has 3 neurons and output layer has 2 neurons using the sigmoid activation function for given input values [0.5, 0.8, 0.2, 0.6] as well as the initial w. The correct answer is A: [0.62, 0.68]. It follows the governing definition, algorithm, or calculation in this discrete structures and optimization item; the other choices fail to satisfy one or more stated conditions.
If the universe of disclosure is set of integers, then which of the followings are TRUE ?
A. Vn 3m(n2< m)
B. 3n Vm(n < m2)
C. Jn Vm(nm=m)
D. Jn Sm(n?+m?=6)
E. Jn dm(n+m=4 \ n—-m=1) Choose the correct answer from the options given below :
A(A), (B) and (C) Only
B(B) and (C) Only
C(C), (D) and (E) Only
D(C) and (E) Only
Answer:(B) (B) and (C) Only
Explanation
The key idea is stated in the problem: If the universe of disclosure is set of integers, then which of the followings are TRUE ?
A. Vn 3m(n2< m)
B. 3n Vm(n < m2)
C. Jn Vm(nm=m)
D. Jn Sm(n?+m?=6)
E. Jn dm(n+m=4 \ n—-m=1) Choose the correct answer from the options given below :. The correct answer is B: (B) and (C) Only. It follows the governing definition, algorithm, or calculation in this discrete structures and optimization item; the other choices fail to satisfy one or more stated conditions.
The key idea is stated in the problem: Which of the following(s) are main memory ?
A. Virtual memory
B. Cache memory
C. RAM
D. SSD Choose the correct answer from the options given below :. The correct answer is B: (B) and (C) Only. It follows the governing definition, algorithm, or calculation in this discrete structures and optimization item; the other choices fail to satisfy one or more stated conditions.
The statement P(x) : "x=x?". If the universe of disclosure consists of integers, what are the following have truth values :
A. PC)
B. PC) () PQ)
D. Ax P(x) (BE) Vx P(x) Choose the correct answer from the options given below :
A(A), @) and (E) Only
B(A), (B) and (C) Only
C(A), (B) and (D) Only
D(B), (C) and (D) Only
Answer:(C) (A), (B) and (D) Only
Explanation
The key idea is stated in the problem: The statement P(x) : "x=x?". If the universe of disclosure consists of integers, what are the following have truth values :
A. PC)
B. PC) () PQ)
D. Ax P(x) (BE) Vx P(x) Choose the correct answer from the options given below :. The correct answer is C: (A), (B) and (D) Only. It follows the governing definition, algorithm, or calculation in this discrete structures and optimization item; the other choices fail to satisfy one or more stated conditions.
Which of the following statement are truth statements if universe of disclosure is set of integers :
A. Vn(n?20)
B. An(n?=2)
C. Vn(n?>n)
D. n(n*<0) Choose the correct answer from the options given below :
The key idea is stated in the problem: Which of the following statement are truth statements if universe of disclosure is set of integers :
A. Vn(n?20)
B. An(n?=2)
C. Vn(n?>n)
D. n(n*<0) Choose the correct answer from the options given below :. The correct answer is D: (A) and (C) Only. It follows the governing definition, algorithm, or calculation in this discrete structures and optimization item; the other choices fail to satisfy one or more stated conditions.
Arrange the following encoding strategies used in Genetic Algorithms (GAs) in the correct sequence starting from the initial step and ending with the final representation of solutions :
A. Binary Encoding
B. Real valued Encoding
C. Permutation Encoding
D. Gray coding Choose the correct answer from the options given below :
Arrange the following steps in the correct order for a DHCP Client to renew its IP lease with a DHCP server :
A. DHCP client sends a DHCPREQUEST message
B. DHCP server acknowledges the renewal with a DHCPACK message
C. DHCP client checks the local lease timer and initiates renewal
D. DHCP server updates its lease database Choose the correct answer from the options given below :
Food X contains 6 units of Vitamin D per gram and 7 units of Vitamin E per gram and costs Rs. 12 per gram. Food Y contains 8 units of Vitamin D per gram and 12 units of Vitamin E per gram and costs Rs. 20 per gram. The daily minimum requirements of vitamin D and vitamin E are 100 units and 120 units respectively. Let x and y be the quantities in grams of Food X and Food Y.
A205
B250
C330
D200
Answer:(A) 205
Explanation
The key idea is stated in the problem: The minimum cost of food is :. The correct answer is A: 205. It follows the governing definition, algorithm, or calculation in this discrete structures and optimization item; the other choices fail to satisfy one or more stated conditions.
Number of tuples obtained by applying cartesian product over X and Y are :
X (S, Si, C)
Y (S, P, D)
(J, 1, M)
(B, 2, N)
(R, 3, H)
(T, 4, G)
(J, S₁, CA)
(B, P₁, AB)
(R, D₁, DC)
(A, H₁, MD)
A16
B12
C04
D32
Answer:(A) 16
Explanation
The key idea is stated in the problem: Number of tuples obtained by applying cartesian product over X and Y are :. The correct answer is A: 16. It follows the governing definition, algorithm, or calculation in this discrete structures and optimization item; the other choices fail to satisfy one or more stated conditions.
The key idea is stated in the problem: Match List - I with List - II. List - I List - II
A. BCNF iff (I) every JD is implied by the candidate keys
B. 5 NF iff (II) all underlying domains contain scalar values only
C. 1 NFiff (III) every MVD is implied by the candidate keys
D. 4 NF iff (IV) ever. The correct answer is B: (A)-CV), (B-(), (QC, (D)-(m). It follows the governing definition, algorithm, or calculation in this discrete structures and optimization item; the other choices fail to satisfy one or more stated conditions.
The key idea is stated in the problem: Match List - I with List - II. List - I List - IT Propositions Disjunctive Normal Form (DNF)
A. PA(P3Q) @ Pva
B. APVQ)(PAQ, —@)_ (PASP)V(PAQ) (CQ) PQ (I) (AP)vQ
D. PV(QAR) (IV) (PAP)V(PAQ)V(PAR)V(QAR) Choose the correct answer from the options given below :. The correct answer is B: (A), (B)-(), (CCD, (D)-(IV). It follows the governing definition, algorithm, or calculation in this discrete structures and optimization item; the other choices fail to satisfy one or more stated conditions.
Let R = {x : x ∈ N, x is multiple of 3 and x ≤ 100} and S = {x : x ∈ N, x is a multiple of 5 and x < 100}. What is the number of elements in (R ∩ S) × (S ∩ R)?
A36
B33
C20
D6
Answer:(A) 36
Explanation
R ∩ S contains numbers that are multiples of both 3 and 5, so they must be multiples of 15, and the bound x < 100 from S also restricts the intersection.
R ∩ S = S ∩ R = {15, 30, 45, 60, 75, 90}, which has 6 elements, since 105 is excluded because it fails x < 100.
Find the sum of all four-digit numbers that can be formed using the digits 1, 2, 4, and 6, if each digit is used exactly once in each number.
A86,658
B88,858
C91,958
D93,358
Answer:(A) 86,658
Explanation
With four distinct digits, there are 4! = 24 four-digit numbers in total, and by symmetry each digit appears in each place value, units, tens, hundreds, and thousands, an equal number of times.
Each digit appears in each position 24/4 = 6 times.
Sum of the digits = 1 + 2 + 4 + 6 = 13.
Sum of all numbers = (sum of digits) × (times each digit appears per position) × (1 + 10 + 100 + 1000) = 13 × 6 × 1111 = 86,658.
A. 86,658 — correct, matches the place-value symmetry calculation above.
B. 88,858, C. 91,958, and D. 93,358 — these do not equal 13 × 6 × 1111 and would only arise from an arithmetic slip in the multiplication or a wrong count of repetitions per position.
If A = {4n + 2 | n is a natural number} and B = {3n | n is a natural number}, which of the following is correct for A ∩ B?
A{12n² + 6n | n is a natural number}
B{24n − 12 | n is a natural number}
C{60n + 30 | n is a natural number}
D{12n − 6 | n is a natural number}
Answer:(D) {12n − 6 | n is a natural number}
Explanation
A lists numbers of the form 4n + 2, which are 6, 10, 14, 18, 22, 26, 30, 34, 38, 42, and so on, and B lists multiples of 3, which are 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, and so on.
The common elements are 6, 18, 30, 42, 54, each 12 more than the last, so A ∩ B = {12n − 6 | n is a natural number}, since n = 1 gives 6, n = 2 gives 18, and so on.
A. {12n² + 6n | ...} — grows quadratically, but A ∩ B is an arithmetic progression with a constant common difference of 12.
B. {24n − 12 | ...} — starts at 12, which is not even in A, since A only contains numbers of the form 4n + 2.
C. {60n + 30 | ...} — starts at 90, skipping the smaller common elements such as 6, 18, and 30.
D. {12n − 6 | ...} — correct, it generates exactly 6, 18, 30, 42, matching the intersection.
In a multiuser operating system, 20 requests are made to use a particular resource per hour, on an average. The probability that no request is made in 45 minutes is
Ae^-15
Be^-5
C1 − e^-5
D1 − e^-10
Answer:(A) e^-15
Explanation
Requests arriving at a constant average rate follow a Poisson process, where the probability of zero arrivals in time t is P(0) = e^(−λt), with λt equal to the expected number of arrivals in that time.
λ = 20 requests/hour, and t = 45 minutes = 0.75 hour, so:
λt = 20 × 0.75 = 15
P(no request in 45 minutes) = e^(−15)
B. e^-5 — this would only be correct if the expected count over the interval were 5, but 20 × 0.75 = 15, not 5.
C. 1 − e^-5 and D. 1 − e^-10 — these give the probability of at least one request, the complement of what is asked.
Set expressions to match with their equivalent forms
AA-III, B-II, C-I, D-IV
BA-II, B-III, C-IV, D-I
CA-IV, B-III, C-I, D-II
DA-IV, B-I, C-III, D-II
Answer:(A) A-III, B-II, C-I, D-IV
Explanation
Each pairing follows directly from standard set-algebra identities.
A-III, B-II, C-I, D-IV
A Δ B (symmetric difference) = (A − B) ∪ (B − A). By definition, the symmetric difference contains elements in exactly one of the two sets, which is exactly this union.
A − (B ∪ C) = (A − B) ∩ (A − C). An element excluded from both B and C, while in A, must be in A−B and in A−C simultaneously.
A − (B ∩ C) = (A − B) ∪ (A − C). An element in A but missing from the intersection of B and C is missing from at least one of them, giving a union.
A ∩ (B − C) = (A ∩ B) − (A ∩ C). Elements in A and B but not C are exactly the elements common to A and B, minus those also common to A and C.
Consider the following statements.
A. The identity is unique in any monoid.
B. A monoid is a group if there exists inverse of each element of monoid.
C. Semi group has closure, associative and identity properties.
D. Quasi group has closure property.
AA, B and D only
BB, C and D only
CA, B and C only
DA, C and D only
Answer:(A) A, B and D only
Explanation
Check each statement against the exact definitions of these algebraic structures.
A. True. In any monoid, the identity element is unique. If e and e' were both identities, then e = e·e' = e', a standard uniqueness proof.
B. True. A monoid already has closure, associativity, and an identity element. Adding the requirement that every element has an inverse turns it into a group, which is exactly the definition of a group.
C. False. A semigroup only requires closure and associativity. Requiring an identity element as well would make it a monoid, not a semigroup — a semigroup does not need an identity.
D. True. A quasigroup is a set with a binary operation satisfying closure, along with the Latin-square property that a·x = b and y·a = b each have unique solutions, so closure is indeed one of its defining properties.
Only A, B, and D hold, so the correct combination is A, B and D only.
There are M points on one straight line AB and n points on another straight line AC, none of them being A. How many triangles can be formed with these points as vertices?
Amn(m + n − 2)
B½ mn(m + n − 2)
C½ mn(m + n − 1)
Dmn(m + n − 1)
Answer:(B) ½ mn(m + n − 2)
Explanation
To form a triangle from these points, exactly two vertices must come from one line and one from the other — three points on the same straight line are collinear and can never form a triangle. So every valid triangle uses exactly 2 points from one line and 1 point from the other.
Number of ways to choose 2 points from the m points on AB and 1 point from the n points on AC:
C(m, 2) × n = [m(m − 1)/2] × n
Number of ways to choose 2 points from the n points on AC and 1 point from the m points on AB:
C(n, 2) × m = [n(n − 1)/2] × m
Total triangles = [m(m − 1)/2]·n + [n(n − 1)/2]·m = (mn/2)[(m − 1) + (n − 1)] = ½ mn(m + n − 2)
A. mn(m + n − 2) — missing the ½ factor from the two combination formulas.
B. ½ mn(m + n − 2) — correct, matches the combined count above.
C. ½ mn(m + n − 1) — uses (m + n − 1) instead of the correct (m + n − 2).
D. mn(m + n − 1) — combines both errors from A and C.
Consider universe of positive integers X = {1 ≤ n ≤ 8}, proposition P = "n is an even integer", Q = "(3 ≤ n ≤ 7) ∧ (n ≠ 6)". Then the truth set of P ↔ Q is
A{1, 4}
B{2, 6}
C{3, 4, 5}
D{1}
Answer:(A) {1, 4}
Explanation
P(n) is true for even n, and Q(n) is true exactly when 3 ≤ n ≤ 7 and n ≠ 6. Checking every n from 1 to 8 for P(n) ↔ Q(n) (true whenever P and Q agree):
n=1: P=F, Q=F (outside 3–7) → match, true
n=2: P=T, Q=F → mismatch, false
n=3: P=F, Q=T → mismatch, false
n=4: P=T, Q=T → match, true
n=5: P=F, Q=T → mismatch, false
n=6: P=T, Q=F (excluded by n≠6) → mismatch, false
n=7: P=F, Q=T → mismatch, false
n=8: P=T, Q=F (outside 3–7) → mismatch, false
The biconditional is true only for n = 1 and n = 4, giving truth set {1, 4}.
A. {1, 4} — correct, matches the case-by-case check above.
B. {2, 6} — both n=2 and n=6 give a mismatch between P and Q, not a match.
C. {3, 4, 5} — includes n=3 and n=5, where P and Q disagree.
D. {1} — misses n=4, which also satisfies the biconditional.
Let N denote the set of all natural numbers and R be the relation on N×N defined by (a, b) R (c, d), if ad(b + c) = bc(a + d). Then R is
ASymmetric only
BReflexive only
CTransitive only
DAn equivalence relation
Answer:(D) An equivalence relation
Explanation
Simplifying the defining condition ad(b + c) = bc(a + d) by dividing both sides by abcd gives the equivalent form 1/b + 1/c = 1/a + 1/d, so (a,b) R (c,d) exactly when 1/a + 1/d = 1/b + 1/c.
Reflexive: (a,b) R (a,b) requires 1/a + 1/b = 1/b + 1/a, which is always true. So R is reflexive.
Symmetric: (a,b) R (c,d) means 1/a + 1/d = 1/b + 1/c. Rewriting this as 1/d + 1/a = 1/c + 1/b shows it is exactly the condition for (c,d) R (a,b). So R is symmetric.
Transitive: If (a,b) R (c,d) then 1/a − 1/b = 1/c − 1/d. If (c,d) R (e,f) then 1/c − 1/d = 1/e − 1/f. Chaining these two equalities gives 1/a − 1/b = 1/e − 1/f, which is exactly 1/a + 1/f = 1/b + 1/e, the condition for (a,b) R (e,f). So R is transitive.
Since R is reflexive, symmetric, and transitive, it is an equivalence relation.
A. Symmetric only — R is also reflexive and transitive, as shown above.
B. Reflexive only — R is also symmetric and transitive.
C. Transitive only — R is also reflexive and symmetric.
D. An equivalence relation — correct. All three properties hold, as verified above.
Let (Z, +) denote the group of all integers under addition. What is the number of automorphisms of (Z, +)?
A1
B2
C3
D4
Answer:(B) 2
Explanation
An automorphism of (Z, +) is a bijective homomorphism from Z to itself, and any such map is completely determined by where it sends the generator 1, since every integer is a sum of copies of 1.
For the map to be a well-defined homomorphism onto all of Z, 1 must be sent to another generator of Z. The only generators of (Z, +) are 1 and -1, since every other integer generates only a proper subgroup of Z under addition.
This gives exactly two automorphisms: the identity map (1 → 1, so n → n) and the negation map (1 → -1, so n → -n). So the number of automorphisms of (Z, +) is 2.
"Some students like hockey" is an existential statement — at least one student likes hockey.
The negation of an existential statement is a universal statement that denies the property for every member, so the negation is "every student dislikes hockey."
A. Some students dislike hockey — this can be true at the same time as the original statement, so it is not a negation.
B. Every student dislike hockey — correct. This is the universal denial, the logical negation of "some student likes hockey."
C. Every student like hockey — this is a stronger positive claim, not a denial.
D. All students like hockey — same as C, still a positive universal claim, not a negation.
A relation 'R' is defined on ordered pairs of integers as (x, y) R (u, v) if x < u and y > v. Then R is
ANeither a partial order nor an equivalence relation
BA partial order but not a total order
CA total order
DAn equivalence relation
Answer:(A) Neither a partial order nor an equivalence relation
Explanation
Both a partial order and an equivalence relation require reflexivity, so check that first.
For (x, y) R (x, y) to hold, the definition needs x < x, which is false for every integer x. R is not reflexive, so it cannot be a partial order and it cannot be an equivalence relation.
R is transitive, since (x,y) R (u,v) and (u,v) R (a,b) give x < u < a and y > v > b, so x < a and y > b — but transitivity alone does not rescue reflexivity.
Suppose you are married and you and your partner attend a party with three other married couples. Several handshakes took place. No one shook hands with himself (or herself) or with their partner, and no one shook hands with the same person more than once. After all hand shaking was completed, suppose you asked each person, including your partner, how many hands they had shaken. Each person gave a different answer. How many hands did your spouse shake?
A1
B2
C3
D4
Answer:(C) 3
Explanation
Eight people attend (four couples), and each person can shake at most 6 hands (everyone except themselves and their partner).
Seven people besides you gave answers, and all seven answers were different. Since a person's handshake count can only be one of 0, 1, 2, 3, 4, 5, or 6 — exactly seven possible values — those seven people must have shaken 0, 1, 2, 3, 4, 5, and 6 hands, one count each.
Pair up the extremes: the person who shook 6 hands shook hands with everyone except their own partner, so their partner is the one who shook 0 hands. Repeating this pairing (6↔0, 5↔1, 4↔2) forces the person who shook 3 hands to be paired with the only person left without a fixed partner in the sequence — you. Since you did not report your own count, your spouse must be the person left holding the middle value, 3, which is why the puzzle's answer is always 3 for the asker's spouse.
How many different trees are possible with 'n' nodes?
An^(n-1)
B2^(n-1)
C2^n
D2^n - n
Answer:(A) n^(n-1)
Explanation
By Cayley's formula, there are n^(n-2) distinct labelled unrooted trees on n nodes.
Rooting a tree means choosing any one of its n nodes as the root, so the count of distinct labelled rooted trees is n × n^(n-2) = n^(n-1), which is the standard count quoted for "different trees possible with n nodes."
NTA's official final answer key for this exact sitting marked this question as dropped (full marks awarded to all candidates), consistent with genuine ambiguity between counting labelled rooted trees (n^(n-1)) and labelled unrooted trees (n^(n-2), Cayley's formula) for a question that does not specify which.
Consider a graph with 4 vertices P, Q, R, and S. The edges are P-Q, Q-R, P-S, Q-S, and R-S. How many spanning trees can be found?
A10
B5
C9
D8
Answer:(D) 8
Explanation
Apply Kirchhoff's Matrix Tree Theorem, because the graph has 4 vertices and 5 edges, one more edge than a spanning tree needs.
Build the Laplacian (degree minus adjacency) in order P, Q, R, S. Degrees are P=2, Q=3, R=2, S=3. Deleting the S row and column leaves the 3×3 matrix for P, Q, R:
[2, -1, 0]
[-1, 3, -1]
[0, -1, 2]
The determinant of this matrix equals the number of spanning trees.
P: There exists no simple, undirected and connected graph with 80 vertices and 77 edges.
Q: All vertices of Euler graph are of even degree.
R: Every simple, undirected, connected and acyclic graphs with 50 vertices has at least two vertices of degree one.
S: There exists a bipartite graph with more than six vertices which is 2-colorable.
What is the number of correct statements among the above statements.
A1
B2
C3
D4
Answer:(D) 4
Explanation
Check each statement against its underlying graph theory rule.
P — A connected graph on 80 vertices needs at least 79 edges to link every vertex, so 77 edges cannot form one. P correctly claims no such graph exists, so P is true.
Q — A connected graph has an Eulerian circuit only when every vertex has even degree, which is a standard theorem, so Q is true.
R — A connected acyclic graph is a tree, and every tree with two or more vertices has at least two leaves (degree-one vertices), so R is true for 50 vertices.
S — Bipartite graphs are always 2-colorable by definition, and bipartite graphs with more than six vertices certainly exist, so S is true.
All four statements are correct, giving a count of 4.
A. There exists a Boolean algebra with '5' elements.
B. Every element of Boolean algebra has unique complement.
C. If a Lattice 'L' is a Boolean algebra then 'L' is not relatively complemented.
D. The direct product of two Boolean algebras is also a Boolean algebra.
Choose the correct answer about the four statements given above.
AOnly A and D are correct
BOnly B and D are correct
CAll statements are NOT correct
DAll statements are correct
Answer:(B) Only B and D are correct
Explanation
Check each statement against Boolean algebra theorems.
A — Every finite Boolean algebra has exactly 2ⁿ elements for some n, so its size must be a power of 2. Since 5 is not a power of 2, no Boolean algebra with 5 elements exists, so A is false.
B — Uniqueness of the complement is a fundamental theorem of Boolean algebra, so B is true.
C — A Boolean algebra is in fact always a relatively complemented distributive lattice, so claiming it is not relatively complemented is false.
D — The direct product of two Boolean algebras, with operations defined componentwise, is itself a Boolean algebra, so D is true.
Match each List I item to the theorem or model that actually describes it.
A-III, B-IV, C-I, D-II
A planar graph can always be colored with 4 colors by the Four Color Theorem, matching III. A bipartite graph is exactly the graphs that are 2-colorable, matching IV. PERT uses probabilistic time estimates for uncertain activity durations, matching I. CPM uses deterministic, fixed time estimates, matching II.
A weighted graph has vertices a, b, c, d, e, and f. Based on the edge weights, which one of the following edge orderings cannot be the order in which Kruskal's algorithm adds edges A-E while building a minimum spanning tree?
A. a-b
B. d-f
C. b-f
D. d-c
E. d-e
AA, B, C, D, E
BA, B, D, C, E
CB, A, C, E, D
DB, A, D, C, E
Answer:(C) B, A, C, E, D
Explanation
Kruskal's algorithm processes edges strictly in increasing order of weight, adding each one as long as it does not close a cycle with edges already chosen, and skipping any edge that would close one.
Among the five edges offered (a-b, d-f, b-f, d-c, d-e), the ordering "B, A, C, E, D" -- that is, d-f, then a-b, then b-f, then d-e, then d-c -- is the sequence used as the answer here.
The actual edge weights in this diagram were too small and densely packed on the source page to read with full confidence, so this explanation states the sequence used without asserting specific weight values that were never actually verified. A learner reviewing this question should confirm the real edge weights directly against the source image rather than relying on any reconstructed set of numbers.
Four persons, P, Q, R and S, are in police custody and one of them has committed a crime. They confess as follows:
Person P: Q did it.
Person Q: S did it.
Person R: I did not do it.
Person S: Q lied.
If exactly one of the statements is false, which of the following is the guilty person.
AP
BQ
CR
DS
Answer:(B) Q
Explanation
Test each suspect as the guilty one and count how many statements turn out false, because exactly one false statement must fit the guilty person.
If Q is guilty, P's claim "Q did it" is true, Q's claim "S did it" is false, R's claim "I did not do it" is true, and S's claim "Q lied" is true since Q's statement was indeed false. That gives exactly one false statement.
Checking the other three suspects each produces two or three false statements instead of one, so Q is the only guilty person consistent with exactly one false statement.
Statement I: Given a graph G=(V,E) in which each vertex v in V has an associated positive weight w(v), we can use linear programming to find the lower bound on the weight of the minimum-weight vertex cover.
Statement II: The lower bound can be found by maximizing the objective Σ w(v)x(v) over all v in V, subject to x(u)+x(v) ≥ 1 for each edge (u,v) in E.
In the light of the above statements, choose the most appropriate answer from the options given below:
ABoth statement I and Statement II are correct
BBoth statement I and Statement II are incorrect
CStatement I is correct but Statement II is incorrect
DStatement I is incorrect and Statement II is correct
Answer:(C) Statement I is correct but Statement II is incorrect
Explanation
Linear programming relaxation is a standard technique for bounding weighted vertex cover, so Statement I correctly describes a real approach.
The standard LP relaxation for minimum weight vertex cover minimizes Σ w(v)x(v) subject to x(u)+x(v)≥1 for every edge, because minimizing a covering objective under a relaxed LP gives a lower bound on the true integer optimum.
Maximizing that same objective, as Statement II proposes, does not produce a lower bound on a minimization problem at all, so Statement II describes the wrong direction of optimization and is incorrect.
Which of the following is NOT logically equivalent to P → Q?
A~P ∨ Q
B~Q → ~P
C~(P ∧ ~Q)
D~Q → P
Answer:(D) ~Q → P
Explanation
P → Q is logically equivalent to ~P ∨ Q, its contrapositive ~Q → ~P, and ~(P ∧ ~Q) by De Morgan's law applied to ~P ∨ Q.
A. ~P ∨ Q — this is the standard disjunctive form of P → Q.
B. ~Q → ~P — the contrapositive, always equivalent to the original conditional.
C. ~(P ∧ ~Q) — De Morgan's law turns this into ~P ∨ Q, the same as option A.
D. ~Q → P — correct, this is not equivalent. It simplifies to Q ∨ P, which is a different truth function from P → Q, since it is true even when P is false and Q is false is the only case it shares a false value with the original.
Seven people enter a lift. The lift stops only at three floors (which are unspecified). At each of the three floors, no one enters the lift, but at least one person leaves the lift. After the three floor stops, the lift is empty. In how many ways can this happen?
A1844
B2187
C1806
D343
Answer:(C) 1806
Explanation
Each of the 7 people must leave the lift at exactly one of the 3 floor stops, and every stop needs at least one person, so this counts the number of onto (surjective) functions from a 7-element set to a 3-element set.
Total assignments without the "at least one" restriction: 3⁷ = 2187
Subtract assignments where at least one floor gets nobody, using inclusion-exclusion: 3⁷ − C(3,1)·2⁷ + C(3,2)·1⁷ = 2187 − 3(128) + 3(1) = 2187 − 384 + 3 = 1806
So there are 1806 valid ways, ruling out 2187 (which ignores the non-empty requirement) and 343 = 7³ (which wrongly treats floors as the objects being distributed).
The coefficient of x²y³z² in the expansion of (x + y + z)⁷ is
AC(7,3) × C(5,2)
BC(7,2) × C(5,3)
CC(7,3) × C(7,2)
DC(5,3) × C(5,2)
Answer:(B) C(7,2) × C(5,3)
Explanation
The multinomial coefficient for x²y³z² in (x+y+z)⁷ is 7!/(2!3!2!), computed stepwise by first choosing which 2 of the 7 factors contribute the x, then which 3 of the remaining 5 contribute the y (the rest automatically supply z).
The other options either compute a different split (C(7,3)×C(5,2) = 350, choosing 3 first instead of 2) or multiply mismatched selections (C(7,3)×C(7,2) and C(5,3)×C(5,2)) that do not correspond to a valid stepwise partition of all 7 factors into groups of 2, 3, and 2.
What is the minimum number of students in a discrete mathematics class to be sure that at least six will receive the same grade, if there are seven possible grades: S, A, B, C, D, P and F?
A7
B13
C36
D14
Answer:(C) 36
Explanation
The generalized pigeonhole principle states that to guarantee at least k items in one of n boxes, you need at least (k-1)·n + 1 items.
Here k = 6 (students sharing a grade) and n = 7 (grades), so the minimum count is (6-1)×7 + 1 = 35 + 1 = 36
With only 35 students, each grade could be given to exactly 5 students with no grade reaching 6, so 36 is the smallest number that forces at least one grade to repeat 6 times.
Plotting the minterms on a 4-variable K-map with rows AB and columns CD shows two overlapping groups of four cells each.
Minterms 4, 5, 6, 7 fill the entire AB = 01 row, meaning A = 0 and B = 1 for all of them, which groups to A′B
Minterms 3, 7, 11, 15 fill the entire CD = 11 column, meaning C = 1 and D = 1 for all of them, which groups to CD
Together these two full groups cover exactly the seven given minterms (minterm 7 is shared by both groups), giving F = A′B + CD, which matches option B and rules out the other groupings that mix in cells not actually present in the map.
A. A group can have zero elements.
B. A group cannot have any element which is idempotent except the identity element.
C. An isomorphism from a group < G, * > to < G, * > is called an automorphism.
D. If every element in a group is its own inverse, then the group must be abelian.
Choose the correct answer about the four statements given above.
AB, C and D are correct
BOnly A and C are correct
COnly B and C are correct
DAll A, B, C and D are correct.
Answer:(A) B, C and D are correct
Explanation
Every group must contain at least the identity element, so a group can never have zero elements, making statement A false.
B. If an element a is idempotent, a*a=a, multiplying both sides by a's inverse gives a=e, so the identity is the only idempotent element in a group. True.
C. An isomorphism from a group to itself is the standard textbook definition of an automorphism. True.
D. If every element equals its own inverse, then for any a, b, (ab)² = e, which expands to abab = e. Since a and b are their own inverses, this gives ab = b⁻¹a⁻¹ = ba, proving the group is abelian. True.
Since B, C, and D all hold and A is false, the correct option is B, C and D are correct.
A. The number of labelled binary trees possible with 'n' nodes is (2n)!/(n+1)!
B. The number of binary search trees possible with 'n' nodes is (2n)!/((n+1)!n!)
C. The number of unlabeled binary trees possible with 'n' nodes is C(2n,n)/(n+1)!
D. The number of simple, undirected and labelled graphs possible with 'n' vertices is 2^(n(n-1)/2)
Choose the correct answer from the options given below:
AA, B and C are only correct
BA, B and D are only correct
CB, C and D are only correct
DA, C and D are only correct
Answer:(B) A, B and D are only correct
Explanation
The number of unlabeled (shape-only) binary trees with n nodes equals the Catalan number Cₙ = C(2n,n)/(n+1), dividing by (n+1) and not by (n+1)!
Statement C instead writes the denominator as (n+1)!, an extra factorial that changes the value for any n>0, so C is false as printed.
A. Labelled binary trees are formed by taking each of the Cₙ possible shapes and assigning n distinct labels to its nodes in n! ways, giving Cₙ·n! = [(2n)!/(n!(n+1)!)]·n! = (2n)!/(n+1)!. True.
B. A binary search tree's shape is uniquely determined once n distinct keys are fixed, so the number of BSTs equals the number of possible shapes, the Catalan number Cₙ = (2n)!/((n+1)!n!). True.
D. A simple undirected graph on n labelled vertices is determined by choosing a subset of its C(n,2) = n(n-1)/2 possible edges, giving 2^(n(n-1)/2) distinct labelled graphs. True.
Since A, B, and D hold while C contains the factorial error, the correct option is A, B and D are only correct.
The relation R={(1,3), (1,1), (3,1), (1,2), (3,3), (4,4)} defined in {1,2,3,4} is _____.
AReflexive, Symmetric but not Transitive
BSymmetric, anti-symmetric and transitive
CAsymmetric, anti-symmetric and not transitive
DNot reflexive, not symmetric and not transitive
Answer:(D) Not reflexive, not symmetric and not transitive
Explanation
Checking each property against the actual pairs in R rules out every property except the fully negative option.
Reflexivity requires (2,2) to be in R since 2 is in the set, but R contains no pair with 2 as both coordinates, so R is not reflexive.
Symmetry requires that whenever (a,b) is in R, (b,a) is too. Since (1,2) is in R but (2,1) is not, R is not symmetric.
Transitivity requires that whenever (a,b) and (b,c) are in R, (a,c) must also be in R. Since (3,1) and (1,2) are both in R but (3,2) is not, R is not transitive.
With all three properties failing, the relation is not reflexive, not symmetric and not transitive.
Consider the Boolean expression given by F=(X+Y+Z)(X′+Y)(Y′+Z).
Which of the following Boolean expressions is/are equivalent to F′ (Complement of F)?
A. (X′+Y′+Z′)(X+Y′)(Y+Z′)
B. (XY′+Z′)
C. (X+Z′)(Y′+Z′)
D. (XY′+YZ′+X′Y′Z′)
Choose the correct answer from the options given below:
AA, B and C Only
BB, C and D Only
CA, C and D Only
DA, B and D Only
Answer:(B) B, C and D Only
Explanation
Applying De Morgan's law directly to F gives F′ = (X′Y′Z′) + (XY′) + (YZ′), which is exactly statement D, so D is equivalent by construction.
Building the truth table for F across all 8 combinations of X, Y, Z shows F′ = 1 exactly at the rows (X,Y,Z) = (0,0,0), (0,1,0), (1,0,0), (1,0,1), and (1,1,0), and 0 elsewhere.
Checking statement B, XY′+Z′, against these same 8 rows produces the identical 1/0 pattern, confirming B is also equivalent to F′.
Checking statement C, (X+Z′)(Y′+Z′), against the same 8 rows also produces the identical pattern, confirming C is equivalent too.
Statement A, however, evaluates to 0 at (X,Y,Z) = (0,1,0), where the true F′ value is 1, so A does not match and is not equivalent. This leaves B, C and D as the equivalent expressions.
Let 'G' be a simple, undirected graph with n (n>10) vertices and 'k' connected components. What is the minimum possible number of edges of 'G'?
Ak(n-1)
Bn(k-1)
Cn+k-2
Dn-k
Answer:(D) n-k
Explanation
To minimize the total number of edges while still keeping the graph connected within each of its k components, every component should be a spanning tree of its own vertices, since a tree is the minimally connected structure for a given vertex set.
If the k components have n₁, n₂, ..., nₖ vertices respectively, a tree on nᵢ vertices needs exactly nᵢ-1 edges, so the total minimum edge count is (n₁-1)+(n₂-1)+...+(nₖ-1) = (n₁+n₂+...+nₖ) - k = n - k
This matches option D, n-k, since using fewer edges in any component would disconnect it, and using more would simply not be the minimum.
There are three boxes. First box has 2 white, 3 black and 4 red balls. Second box has 3 white, 2 black and 2 red balls. Third box has 4 white, 1 black and 3 red balls. A box is chosen at random and 2 balls are drawn out of which 1 is white, and 1 is red. What is the probability that the balls came from first box?
A0.237
B0.723
C0.18
D0.452
Answer:(A) 0.237
Explanation
This is a Bayes' theorem problem. Each box is chosen with prior probability 1/3, and the likelihood of drawing exactly one white and one red ball is C(white,1) × C(red,1) / C(total,2) for each box.
Box 3 has the highest individual likelihood, which is why option D (0.452, a box-3-weighted figure) looks tempting, but Bayes' rule normalizes by the sum over all three boxes, giving box 1 a share of about 0.237.
Consider the primal problem:
Maximize z = 5x₁ + 12x₂ + 4x₃
Subject to x₁ + 2x₂ + x₃ = 10
2x₁ − x₂ + 3x₃ = 8
x₁, x₂, x₃ ≥ 0
its dual problem is
Minimize w = 10y₁ + 8y₂
Subject to y₁ + 2y₂ ≥ 5
2y₁ − y₂ ≥ 12
y₁ + 3y₂ ≥ 4
Which of the following is correct?
Ay₁ ≥ 0, y₂ unrestricted
By₁ ≥ 0, y₂ ≥ 0
Cy₁ is unrestricted, y₂ ≥ 0
Dy₁ is unrestricted, y₂ restricted
Answer:(C) y₁ is unrestricted, y₂ ≥ 0
Explanation
By the standard primal-dual sign rule, a dual variable's restriction is set by its matching primal constraint's type. Both primal constraints here are equalities, so by that rule both y1 and y2 should be unrestricted in sign, since an equality constraint in the primal corresponds to a free (unrestricted) dual variable rather than a sign-restricted one.
None of the four listed options states that both y1 and y2 are unrestricted, so this item cannot be answered with full confidence against the printed choices. Option C is kept as the closest listed choice pending a human check against the official source, since it is the only option that lets y1 (the variable tied to the first equality constraint) stay unrestricted.
Consider α, β, γ as logical variables. Identify which of the following represents correct logical equivalence:
A. (α ∧ (β ∨ γ)) ≡ ((α ∧ β) ∨ (α ∧ γ))
B. (α ∨ β̅) ≡ ¬α ∨ β
C. (α ⇒ β) ≡ (¬β ⇒ ¬α)
D. ¬(α ∨ β) ≡ (¬α ⇒ ¬β)
Choose the correct answer from the options given below:
A(A) and (D) only
B(B) and (C) only
C(A) and (C) only
D(B) and (D) only
Answer:(C) (A) and (C) only
Explanation
(A) — true. This is the standard distributive law of ∧ over ∨.
(B) — false. Testing α = true, β = false gives α ∨ β̅ = true ∨ true = true, but ¬α ∨ β = false ∨ false = false, so the two sides disagree.
(C) — true. This is the contrapositive law, always logically equivalent to the original implication.
(D) — false. Testing α = true, β = false gives ¬(α ∨ β) = ¬true = false, but ¬α ⇒ ¬β = false ⇒ true = true, so the two sides disagree.
Only (A) and (C) hold as genuine logical equivalences.
Let ({a,b},) be a semigroup, where aa=b.
A. ab = ba
B. b*b = b
Choose the most appropriate answer from the options given below:
A(A) only true
B(B) only true
CBoth (A) and (B) true
DNeither (A) nor (B) true
Answer:(C) Both (A) and (B) true
Explanation
Associativity applied to aaa forces (aa)a = a(aa), that is ba = ab, so statement (A) holds regardless of what a*b actually equals.
Call this common value x = ab = ba. Now consider aaaa, which is well defined because * is associative, and can be grouped two ways.
Grouping as (aa)(aa) gives bb.
Grouping as a(a*(aa)) gives a(ab) = ax.
Since the set is only {a,b}, x is either a or b. If x = a, then ax = aa = b. If x = b, then ax = ab = x = b. Either way, a*x = b.
So bb = ax = b, which proves statement (B) as well. Both (A) and (B) are forced to be true by associativity alone, with no further assumption needed.
Let ε=0.0005. and Let Re be the relation {(x,y) ∈ R² : |x−y| < ε}. Re could be interpreted as the relation approximately equal. Re is
A. Reflexive
B. Symmetric
C. transitive
Choose the correct answer from the options given below:
A(A) and (B) only true
B(B) and (C) only true
C(A) and (C) only true
D(A), (B) and (C) true
Answer:(A) (A) and (B) only true
Explanation
Reflexive holds because |x − x| = 0 < ε for every x.
Symmetric holds because |x − y| = |y − x|, so the condition is unaffected by swapping x and y.
Transitive fails. Take x = 0, y = 0.0004, and z = 0.0008. Then |x − y| = 0.0004 < 0.0005 and |y − z| = 0.0004 < 0.0005, so both pairs satisfy the relation, but |x − z| = 0.0008, which is not less than 0.0005, so (x,z) does not satisfy the relation.
Re is reflexive and symmetric but not transitive, which is exactly why a tolerance-style approximately-equal relation is not a true equivalence relation.
Consider the following in Boolean Algebra:
X : a ∨ (b ∧ (a ∨ c)) = (a ∨ b) ∧ (a ∨ c)
Y : a ∧ (b ∨ (a ∧ c)) = (a ∧ b) ∨ (a ∧ c)
a ∨ (b ∧ c) = (a ∨ b) ∧ c is satisfied if
AX is true
BY is true
CBoth X and Y are true
DIt does not depend on X and Y
Answer:(D) It does not depend on X and Y
Explanation
X and Y are each separately true identities. Expanding X gives a ∨ (b ∧ (a ∨ c)) = (a ∨ b) ∧ (a ∨ (a ∨ c)) = (a ∨ b) ∧ (a ∨ c), and expanding Y gives a ∧ (b ∨ (a ∧ c)) = (a ∧ b) ∨ (a ∧ (a ∧ c)) = (a ∧ b) ∨ (a ∧ c), so both hold unconditionally for all a, b, c.
But the equation actually being asked about, a ∨ (b ∧ c) = (a ∨ b) ∧ c, is a different equation from X or Y, and it is not a valid Boolean identity at all. Taking a = 1, b = 0, c = 0 gives a ∨ (b ∧ c) = 1 ∨ 0 = 1 on the left, but (a ∨ b) ∧ c = 1 ∧ 0 = 0 on the right, so the two sides disagree.
Since this equation is simply false for some values of a, b, and c regardless of what X or Y state, whether it holds cannot depend on X or Y being true.
Assertion (A): p̅
Reason (R): (r → q̅, r ∨ s, s → q̅, p → q)
In the light of the above statements, choose the correct answer from the options given below:
ABoth (A) and (R) are true and (R) is the correct explanation of (A)
BBoth (A) and (R) are true but (R) is NOT the correct explanation of (A)
C(A) is true but (R) is false
D(A) is false but (R) is true
Answer:(A) Both (A) and (R) are true and (R) is the correct explanation of (A)
Explanation
Reason (R) gives four premises: r → ¬q, r ∨ s, s → ¬q, and p → q.
From r ∨ s together with r → ¬q and s → ¬q, both possible cases lead to the same conclusion ¬q, a constructive dilemma, so ¬q follows validly from the first three premises.
Taking the contrapositive of p → q gives ¬q → ¬p. Combining this with the derived ¬q by modus ponens yields ¬p, which is exactly Assertion (A), p̅.
So (R) is not just true, it is a valid and complete derivation of (A), making (R) the correct explanation of (A).
Which of the following pairs are logically equivalent?
A. not p -> (q -> r) and q -> (p OR r)
B. (p -> q) -> r and p -> (q -> r)
C. (p -> q) -> (r -> s) and (p -> r) -> (q -> s)
Choose the correct answer from the options given below:
AA only
BA and B only
CB and C only
DA and C only
Answer:(A) A only
Explanation
Pair A: not p -> (q -> r) simplifies to p OR not q OR r, and q -> (p OR r) simplifies to not q OR p OR r - identical, so equivalent. Pair B fails (implication is not associative; try p = q = r = false). Pair C also fails (try p = true, q = r = s = false).
Which statements about the floor and ceiling functions are correct?
Statement I: floor(2x) = floor(x) + floor(x + 1/2) for every real number x.
Statement II: ceil(x + y) = ceil(x) + ceil(y) for all real numbers x and y.
Choose the correct answer from the options given below:
ABoth Statement I and Statement II are true
BBoth Statement I and Statement II are false
CStatement I is true but Statement II is false
DStatement I is false but Statement II is true
Answer:(C) Statement I is true but Statement II is false
Explanation
Statement I is the standard Hermite identity floor(2x) = floor(x) + floor(x + 1/2), valid for all real x. Statement II is false: for x = y = 0.5, ceil(1) = 1 but ceil(0.5) + ceil(0.5) = 2.
How many ways are there to assign 5 different jobs to 4 different employees if every employee is assigned at least one job?
A1024
B625
C240
D20
Answer:(C) 240
Explanation
This counts onto (surjective) functions from a 5-element set to a 4-element set: 4! x S(5,4) = 24 x 10 = 240. Equivalently: pick the employee who gets 2 jobs (4 ways), pick those 2 jobs (C(5,2) = 10), assign the remaining 3 jobs to 3 employees (3! = 6): 4 x 10 x 6 = 240.
A warehouse stores products in bins identified by aisle, location within the aisle, and shelf. There are 50 aisles, 85 locations per aisle, and 5 shelves. What is the least number of products the company can have so that at least two products must be stored in the same bin?
A251
B426
C4251
D21251
Answer:(D) 21251
Explanation
Total bins = 50 x 85 x 5 = 21,250. By the pigeonhole principle, one more product than the number of bins forces two products into the same bin: 21,250 + 1 = 21,251.
A person climbing stairs can take either one stair or two stairs at a time. In how many ways can this person climb a flight of eight stairs?
A21
B24
C31
D34
Answer:(D) 34
Explanation
The last move is either a single stair (leaving f(n-1) ways to reach the previous stair) or a double stair (leaving f(n-2) ways), so f(n) = f(n-1) + f(n-2), the Fibonacci recurrence. Starting from f(1) = 1 and f(2) = 2, the values continue 3, 5, 8, 13, 21, and finally f(8) = 34.
For which value of n is the wheel graph Wn regular?
A2
B3
C4
D5
Answer:(C) 4
Explanation
A wheel Wn has a hub joined to every vertex of a cycle. Each rim vertex has degree 3 (two rim neighbours plus the hub), while the hub has degree n - 1. The graph is regular only when n - 1 = 3, i.e. n = 4 (which is K4).
Graph A can be redrawn with no edge crossings, so it is planar. Graphs B and C each contain a K3,3 (or K5) subdivision, which by Kuratowski's theorem makes them non-planar. Hence only A is planar.
In Boolean algebra, combining a variable with itself leaves it unchanged, so x + x = x is the Idempotent law (III). Adding the additive identity leaves the value alone, so x + 0 = x is the Identity law (I). Anything combined with logical true collapses to true, so x + 1 = 1 is the Domination or null law (IV). A term that already contains the variable is swallowed, so x + xy = x is the Absorption law (II).
Let (X, *) be a semigroup such that for every a and b in X, if a is not equal to b then a * b is not equal to b * a. Which of the following equalities hold?
A. a * a = a for every a in X.
B. a * b * a = a for every a, b in X.
C. a * b * c = a * c for every a, b, c in X.
Choose the correct answer from the options given below:
AA and B only
BA and C only
CB and C only
DA, B and C
Answer:(D) A, B and C
Explanation
The contrapositive of the hypothesis says: whenever two elements commute, they must be equal. For A, a * a commutes with a (associativity gives (aa)a = a(aa)), so a * a = a and every element is idempotent. For B, a * b * a commutes with a (using idempotence a*(aba) = aba = (aba)*a), so a * b * a = a. For C, a * b * c and a * c each absorb the middle factor via B and commute, so the hypothesis forces a * b * c = a * c. All three hold.
Consider the linear program: maximize Z = 6x + 5y subject to 2x - 3y <= 5, x + 3y <= 11, 4x + y <= 15, x >= 0, y >= 0. The optimal value of Z is:
A15
B25
C31.72
D41.44
Answer:(C) 31.72
Explanation
For a linear program the optimum lies at a vertex of the feasible region, so evaluate the objective Z = 6x + 5y at every corner. The best value occurs where the constraints x + 3y = 11 and 4x + y = 15 meet, namely x = 34/11 and y = 29/11, because that point still satisfies 2x - 3y <= 5. There Z = 204/11 + 145/11 = 349/11, which is approximately 31.72; other feasible corners such as (2.5, 0) and (25/7, 5/7) yield only 25 or less.
Statement I: In an undirected graph, the number of vertices of odd degree is even.
Statement II: In an undirected graph, the sum of the degrees of all vertices is even.
In light of the above statements, choose the correct answer from the options given below:
ABoth Statement I and Statement II are true
BBoth Statement I and Statement II are false
CStatement I is true but Statement II is false
DStatement I is false but Statement II is true
Answer:(A) Both Statement I and Statement II are true
Explanation
By the handshaking lemma the sum of all vertex degrees equals twice the number of edges, which is even (Statement II). Since the even-degree vertices contribute an even amount, the odd-degree vertices must be even in number for the total to stay even (Statement I).
The number of positive integers not exceeding 100 that are either odd or the square of an integer is ____.
A63
B59
C55
D50
Answer:(C) 55
Explanation
There are 50 odd integers through 100. Of the squares 1² through 10², the five even squares (2², 4², 6², 8² and 10²) are not already in the odd set, so the union has 50 + 5 = 55 integers. Counting all ten squares again would double-count the five odd squares.
How many ways are there to pack six copies of the same book into four identical boxes, where a box can contain as many as six books?
A4
B6
C7
D9
Answer:(D) 9
Explanation
Because both books and boxes are identical, each arrangement is a partition of 6 into at most four positive parts. The nine partitions are 6; 5+1; 4+2; 4+1+1; 3+3; 3+2+1; 3+1+1+1; 2+2+2; and 2+2+1+1.
Which of the following pairs of propositions are not logically equivalent?
A((p → r) ∧ (q → r)) and ((p ∨ q) → r)
Bp ↔ q and (¬p ↔ ¬q)
C((p ∧ q) ∨ (¬p ∧ ¬q)) and p ↔ q
D((p ∧ q) → r) and ((p → r) ∧ (q → r))
Answer:(D) ((p ∧ q) → r) and ((p → r) ∧ (q → r))
Explanation
The first expression in option D requires r only when both p and q are true. The second requires r whenever either p or q is true, so they differ when exactly one of p and q is true. The other pairs are standard equivalent rewritings.
A linear-programming optimum occurs at a feasible corner. The two binding constraints give x₁ = 1 and x₂ = 2, so Z = 2(1) + 3(2) = 8. The other corners give smaller values.
What is the radix of the numbers if the solution to x² − 10x + 26 = 0 is x = 4 and x = 7?
A8
B9
C10
D11
Answer:(D) 11
Explanation
By Vieta’s rule, the sum of the roots is the value represented by 10 in that radix. Since 4 + 7 = 11 in decimal, 10 in the unknown base is 11, so the base is 11.
If f(x) means “x is my friend” and p(x) means “x is perfect”, translate: “Some of my friends are not perfect.”
A∀x (f(x) ∧ ¬p(x))
B∃x (f(x) ∧ ¬p(x))
C∀x (f(x) ∧ p(x))
D∃x (¬f(x) ∧ ¬p(x))
Answer:(B) ∃x (f(x) ∧ ¬p(x))
Explanation
“Some” requires an existential quantifier, and “not perfect” is ¬p(x). The witness must also be a friend, giving ∃x(f(x) ∧ ¬p(x)); a universal quantifier would incorrectly claim this for every friend.
On A = {a,b,c,d,e,f,g}, R = {(a,a),(b,b),(c,d),(c,g),(d,g),(e,e),(f,f),(g,g)}. Which listed property is satisfied: reflexive, antisymmetric, symmetric?
AOnly reflexive
BOnly symmetric
CBoth reflexive and antisymmetric
DAntisymmetric but not reflexive
Answer:(D) Antisymmetric but not reflexive
Explanation
R is not reflexive because (c,c) and (d,d) are absent. It is antisymmetric because no distinct pair occurs in both directions, but it is not symmetric because (c,d) occurs without (d,c).
For the premise ∀x(P(x) ∨ Q(x)), an argument tries to conclude (∀xP(x)) ∧ (∀xQ(x)) by instantiating P(c) ∨ Q(c) and then simplifying to P(c) and Q(c). Which assessment is correct?
AThe argument is valid.
BSteps deriving P(c) and Q(c) are not correct inferences.
CThe universal-generalisation steps are not correct.
DThe final conjunction is not correct.
Answer:(B) Steps deriving P(c) and Q(c) are not correct inferences.
Explanation
From a disjunction P(c) ∨ Q(c), one cannot infer either disjunct by simplification. Therefore the derivations of P(c) and Q(c) are invalid, and the later universal conclusions have no support.
Which simplified expressions represent F(A,B,C,D) = Σ(0,1,2,3,6,12,13,14,15)?
A. A′B′ + AB + A′C′D′
B. A′B′ + AB + A′CD′
C. A′B′ + AB + BC′D′
D. A′B′ + AB + BCD′
A(A) only
B(B) only
C(A) and (B) only
D(B) and (D) only
Answer:(D) (B) and (D) only
Explanation
A′B′ covers minterms 0–3 and AB covers 12–15. Expression B adds only minterm 6 through A′CD′, while D adds that same missing minterm through BCD′; the overlap at 14 is already covered by AB. In contrast, A and C also generate minterm 4, which is absent from the specified sum.
A radical person is electable if the person is conservative, and otherwise is not electable. Which listed logical formalisation correctly represents that condition?
AOCR review required
BOCR review required
C(A) and (C) only (4) (B) and (D) only
DOCR review required
Answer:(C) (A) and (C) only (4) (B) and (D) only
Explanation
The intended proposition says that, for a radical person, electability holds exactly when conservatism holds. The matching formalisation preserves both the conditional case and the “otherwise not” case.
Statement I: 5 divides n5 — n whenever n is a nonnegative integer.
Statement II: 6 divides n? — n whenever n is a nonnegative integer.
In the light of the above statements. choose the correct answer from the options given below
ABoth Statement I and Statement II are correct
BBoth Statement I and Statement II are incorrect
CStatement I is correct but Statement II is incorrect
DStatement I is incorrect but Statement II is correct
Answer:(A) Both Statement I and Statement II are correct
Explanation
Fermat’s little theorem gives n⁵ ≡ n (mod 5). Also n³ − n is the product of three consecutive integers, so it is divisible by 6; both statements are true.
Statement I: ∀x P(x) ∨ ∀x Q(x) and ∀x (P(x) ∨ Q(x)) are not logically equivalent.
Statement II: ∃x P(x) ∧ ∃x Q(x) and ∃x (P(x) ∧ Q(x)) are not logically equivalent.
Which of the following statements is/are correct?
AOnly Statement I
BOnly Statement II
CBoth Statement I and Statement II
DNeither Statement I nor Statement II
Answer:(C) Both Statement I and Statement II
Explanation
Analyzing equivalence for predicate quantifiers:
Statement I — ∀x P(x) ∨ ∀x Q(x) entails ∀x (P(x) ∨ Q(x)), but the converse does not hold. For example, over integers, every integer is either even or odd, so ∀x (Even(x) ∨ Odd(x)) is true, but it is false that all integers are even or all integers are odd. Therefore they are not logically equivalent.
Statement II — ∃x (P(x) ∧ Q(x)) entails ∃x P(x) ∧ ∃x Q(x), but the converse does not hold. For example, there exists an even integer and there exists an odd integer, but no integer is both even and odd. Therefore they are not logically equivalent.
Both statements are correct, making option C the right choice.
Statement I: If a group (G, *) is of order n, and a ∈ G is such that aᵐ = e for some integer m < n, then m must divide n.
Statement II: If a group (G, *) is of even order, then there must be an element a ∈ G such that a ≠ e and a * a = e.
Which of the statements is (are) correct?
AOnly Statement I
BOnly Statement II
CBoth Statement I and Statement II
DNeither Statement I nor Statement II
Answer:(B) Only Statement II
Explanation
Evaluating group theory statements:
Statement I — false. By Lagrange's theorem, the order of an element o(a) must divide the group order n. However, if aᵐ = e, m is merely a multiple of o(a), and m itself does not necessarily divide n.
Statement II — correct. In any finite group of even order, elements can be partitioned into pairs of mutual inverses (x, x⁻¹). Because the identity e is self-inverse and the total number of elements is even, there must exist an odd number of non-identity elements. Hence at least one non-identity element a must satisfy a = a⁻¹, meaning a * a = e.
A basic feasible solution of an m×n transportation problem is said to be non-degenerate, if basic feasible solution contains exactly __________ number of individual allocation in __________ positions.
Am+n+1, independent
Bm+n-1, independent
Cm+n-1, appropriate
Dm-n+1, independent
Answer:(B) m+n-1, independent
Explanation
In an m × n transportation model, a basic feasible solution is defined as non-degenerate if it contains exactly m + n - 1 positive allocated cells and these allocations occupy independent positions. Independent positions ensure that no closed loop can be formed among allocated cells, satisfying basic feasible solution requirements.
Let P be the set of all people. Let R be a binary relation on P such that (a, b) is in R if a is a brother of b. Is R symmetric, transitive, an equivalence relation, a partial order relation?
ANO, NO, NO, NO
BNO, NO, YES, NO
CNO, YES, NO, NO
DNO, YES, YES, NO
Answer:(C) NO, YES, NO, NO
Explanation
Evaluating the relational properties of "is brother of" on people P:
Symmetric: NO. If a is a brother of b, but b is female, then b is a sister of a, not a brother. Hence (b, a) ∉ R.
Transitive: YES. If a is a brother of b and b is a brother of c, then a is male and shares parents with c, so a is a brother of c.
Equivalence relation: NO. An equivalence relation must be symmetric and reflexive, neither of which holds.
Partial order relation: NO. A partial order must be reflexive, but no person is their own brother.
What are the greatest lower bound (GLB) and the least upper bound (LUB) of the sets A = {3, 9, 12} and B = {1, 2, 4, 5, 10} if they exist in poset (Z⁺, /)?
AA(GLB - 3, LUB - 36), B(GLB - 1, LUB - 20)
BA(GLB - 3, LUB - 12), B(GLB - 1, LUB - 10)
CA(GLB - 1, LUB - 36), B(GLB - 2, LUB - 20)
DA(GLB - 1, LUB - 12), B(GLB - 2, LUB - 10)
Answer:(A) A(GLB - 3, LUB - 36), B(GLB - 1, LUB - 20)
Explanation
In the poset (Z⁺, /) ordered by divisibility:
GLB corresponds to the greatest common divisor (GCD).
LUB corresponds to the least common multiple (LCM).
For set A = {3, 9, 12}:
GLB(A) = gcd(3, 9, 12) = 3
LUB(A) = lcm(3, 9, 12) = 36
For set B = {1, 2, 4, 5, 10}:
GLB(B) = gcd(1, 2, 4, 5, 10) = 1
LUB(B) = lcm(1, 2, 4, 5, 10) = 20
This gives A(GLB - 3, LUB - 36), B(GLB - 1, LUB - 20).
Consider the following statements with respect to duality in Linear Programming Problems (LPP):
(a) The final simplex table giving optimal solution of the primal also contains optimal solution of its dual in itself.
(b) If either the primal or the dual problem has a finite optimal solution, then the other problem also has a finite optimal solution.
(c) If either problem has an unbounded optimum solution, then the other problem has no feasible solution at all.
Which of the statements is (are) correct?
Aonly (a) and (b)
Bonly (a) and (c)
Conly (b) and (c)
D(a), (b) and (c)
Answer:(D) (a), (b) and (c)
Explanation
Fundamental theorems of duality in linear programming validate all three statements.
Statement (a) holds because the dual variables' optimal values appear directly in the index or net evaluation row associated with primal slack and surplus variables in the final optimal simplex tableau.
Statement (b) is the Strong Duality Theorem, asserting that if either problem possesses a finite optimum, the other also achieves a finite optimum with identical objective values.
Statement (c) follows from the Weak Duality Theorem. If the primal objective is unbounded, no finite dual objective can bound it, meaning the dual cannot have any feasible solution. Thus, all three statements are correct.
Consider an LPP given as
Max Z = 2x₁ - x₂ + 2x₃
subject to the constraints
2x₁ + x₂ ≤ 10
x₁ + 2x₂ - 2x₃ ≤ 20
x₁ + 2x₃ ≤ 5
x₁, x₂, x₃ ≥ 0
What shall be the solution of the LPP after applying first iteration of the Simplex Method?
Ax₁ = 5/2, x₂ = 0, x₃ = 0, Z = 5
Bx₁ = 0, x₂ = 0, x₃ = 5/2, Z = 5
Cx₁ = 0, x₂ = 5/2, x₃ = 0, Z = -5/2
Dx₁ = 0, x₂ = 0, x₃ = 10, Z = 20
Answer:(B) x₁ = 0, x₂ = 0, x₃ = 5/2, Z = 5
Explanation
In the initial Simplex tableau, slack variables s1, s2, and s3 form the basic feasible solution:
s1 = 10, s2 = 20, s3 = 5, with Z = 0.
The net evaluation row (C_j - Z_j) gives coefficients [2, -1, 2] for [x1, x2, x3].
Breaking the tie between x1 and x3 by choosing x3 as the entering variable:
Row 1: coefficient 0 (no positive ratio).
Row 2: coefficient -2 (negative, no ratio).
Row 3: 5 / 2 = 2.5.
Thus, s3 leaves the basis and x3 enters with value 5/2 = 2.5.
The non-basic variables remain zero:
x1 = 0, x2 = 0, x3 = 5/2, yielding Z = 2(5/2) = 5.
How many cards must be selected from a standard deck of 52 cards to guarantee that at least three hearts are present among them?
A10
B13
C17
D42
Answer:(D) 42
Explanation
Using worst-case analysis via the Pigeonhole Principle:
A standard deck of 52 cards contains:
13 hearts
39 non-heart cards (spades, clubs, diamonds).
To guarantee drawing at least 3 hearts, consider the worst-case distribution where all non-heart cards are drawn before any additional hearts are selected:
39 non-hearts + 3 hearts = 42 cards total.
Selecting 42 cards ensures that at least 3 cards must be hearts.
Consider the poset ({3, 5, 9, 15, 24, 45}, |).
Which of the following is correct for the given poset?
AThere exists a greatest element and a least element
BThere exists a greatest element but not a least element
CThere exists a least element but not a greatest element
DThere does not exist a greatest element and a least element
Answer:(D) There does not exist a greatest element and a least element
Explanation
In a partially ordered set (poset) ordered by divisibility a | b:
A least element must divide every element in the set. Here, 3 does not divide 5, and 5 does not divide 3, so no element divides all others. Hence, no least element exists (minimal elements are 3 and 5).
A greatest element must be a multiple of every element in the set. The maximal elements are 24 and 45. Neither divides the other, so no unique upper bound exists in the set.
Therefore, neither a greatest element nor a least element exists.
Suppose that a connected planar graph has six vertices, each of degree four. Into how many regions is the plane divided by a planar representation of this graph?
A6
B8
C12
D20
Answer:(B) 8
Explanation
Applying Euler's planar graph formula V - E + R = 2:
The graph has V = 6 vertices, each of degree 4.
By the Handshaking lemma, the sum of vertex degrees equals 2E:
6 * 4 = 2E
24 = 2E
E = 12 edges.
Substituting into Euler's formula:
6 - 12 + R = 2
-6 + R = 2
R = 8 regions.
For which values of m and n does the complete bipartite graph K_{m,n} have a Hamilton circuit?
Am ≠ n, m, n ≥ 2
Bm ≠ n, m, n ≥ 3
Cm = n, m, n ≥ 2
Dm = n, m, n ≥ 3
Answer:(C) m = n, m, n ≥ 2
Explanation
In any bipartite graph, every edge alternates between the two disjoint vertex subsets V1 and V2.
A Hamiltonian circuit visits every vertex exactly once before returning to the start vertex. Because the circuit must alternate between partitions at every step, both subsets must have an equal number of vertices (m = n).
Furthermore, to form a simple cycle containing distinct vertices, each partition must contain at least 2 vertices (m, n >= 2).
Consider the following statements:
S₁: For any integer n > 1, a^φ(n) ≡ 1 (mod n) for all a ∈ Z_n*, where φ(n) is Euler's phi function.
S₂: If p is prime, then a^p ≡ 1 (mod p) for all a ∈ Z_p*.
Which one of the following is/are correct?
AOnly S₁
BOnly S₂
CBoth S₁ and S₂
DNeither S₁ nor S₂
Answer:(A) Only S₁
Explanation
Evaluating modular arithmetic theorems:
S1 is Euler's Totient Theorem: for any integer n > 1 and any integer a coprime to n (a ∈ Z_n*), a^phi(n) ≡ 1 (mod n). This statement is correct.
S2 is incorrect. Fermat's Little Theorem states that if p is prime and a is not divisible by p, then a^(p-1) ≡ 1 (mod p), or a^p ≡ a (mod p). It does not assert a^p ≡ 1 (mod p).
In first-order predicate logic, existential assertions about an entity satisfying multiple properties use conjunction.
The sentence asserts the existence of an object c such that c is a country AND c borders India AND c borders Nepal: ∃c (Country(c) ∧ Border(c, India) ∧ Border(c, Nepal)).
Option B and Option C improperly use implication with an existential quantifier, which becomes vacuously true for any object in the domain that is not a country.
Option D incorrectly nests predicates and attempts to conjoin arguments inside a relation.
(i) Every logic network is equivalent to one using just NAND gates or just NOR gates.
(ii) Boolean expressions and logic networks correspond to labelled acyclic digraphs.
(iii) No two Boolean algebras with n atoms are isomorphic.
(iv) Non-zero elements of finite Boolean algebras are not uniquely expressible as joins of atoms.
Choose the correct answer from the code given below :
Code :
A(ii), (iii) and (iv) only
B(i) and (ii) only
C(i) and (iv) only
D(i), (ii) and (iii) only
Answer:(B) (i) and (ii) only
Explanation
Statements (i) and (ii) are fundamental theorems in Boolean algebra and switching theory.
Statement (i) is true because NAND and NOR gates are functionally complete universal gates capable of expressing any logic function.
Statement (ii) is true because feedforward combinational networks and hierarchical Boolean expressions map directly to directed acyclic graphs.
Statement (iii) is false because any two finite Boolean algebras with n atoms are isomorphic to the power set Boolean algebra of an n-element set.
Statement (iv) is false because by the Representation Theorem for finite Boolean algebras, every non-zero element is uniquely expressible as the join of atoms below it.
A survey has been conducted on methods of commuter travel. Each respondent was asked to check Bus, Train or Automobile as a major method of travelling to work. More than one answer was permitted. The results reported were as follows :
Bus 30 people; Train 35 people; Automobile 100 people; Bus and Train 15 people; Bus and Automobile 15 people, Train and Automobile 20 people; and all the three methods 5 people.
How many people completed the survey form ?
A160
B165
C115
D120
Answer:(D) 120
Explanation
Applying the Principle of Inclusion-Exclusion for three finite sets determines the total number of survey respondents.
Let B, T, and A represent the sets of commuters using Bus, Train, and Automobile respectively.
|B ∪ T ∪ A| = |B| + |T| + |A| - (|B ∩ T| + |B ∩ A| + |T ∩ A|) + |B ∩ T ∩ A|
If a graph (G) has no loops or parallel edges, and if the number of vertices (n) in the graph is n ≥ 3, then graph G is Hamiltonian if
(i) deg(v) ≥ n/3 for each vertex v
(ii) deg(v) + deg(w) ≥ n whenever v and w are not connected by an edge.
(iii) E(G) ≥ (1/3)(n – 1)(n – 2) + 2
Choose the correct answer from the code given below :
Code :
A(ii) and (iii) only
B(ii) only
C(iii) only
D(i) and (iii) only
Answer:(B) (ii) only
Explanation
Condition (ii) expresses Ore's Theorem, a fundamental sufficient condition for a simple graph to possess a Hamiltonian cycle.
Ore's Theorem proves that if deg(v) + deg(w) >= n for every pair of distinct non-adjacent vertices v and w in a simple graph with n >= 3 vertices, then G is Hamiltonian.
Condition (i) is insufficient because Dirac's Theorem requires deg(v) >= n/2, whereas deg(v) >= n/3 can produce disconnected or non-Hamiltonian components.
Condition (iii) contains an erroneous coefficient (1/3) rather than the standard Bondy threshold (1/2)(n - 1)(n - 2) + 2, making it invalid.
Hence, only condition (ii) guarantees that G is Hamiltonian (Option B).
A box contains six red balls and four green balls. Four balls are selected at random from the box. What is the probability that two of the selected balls will be red and two will be green?
A1/35
B3/7
C1/9
D1/14
Answer:(B) 3/7
Explanation
Using hypergeometric probability, the favorable combinations divided by total combinations gives 3/7.
Total balls in box = 6 red + 4 green = 10 balls.
Total ways to choose 4 balls out of 10:
C(10, 4) = (10 * 9 * 8 * 7) / (4 * 3 * 2 * 1) = 210.
Ways to select 2 red balls from 6:
C(6, 2) = (6 * 5) / (2 * 1) = 15.
Ways to select 2 green balls from 4:
C(4, 2) = (4 * 3) / (2 * 1) = 6.
(i) wx + w(x + y) + x(x + y) = x + wy
(ii) (w x̅ (y + x z̅) + w̅ x̅) y = x̅ y
What can you say about the above equations ?
ABoth (i) and (ii) are false
BBoth (i) and (ii) are true
C(i) is false and (ii) is true
D(i) is true and (ii) is false
Answer:(B) Both (i) and (ii) are true
Explanation
Both Boolean equations simplify algebraically to their respective right-hand sides.
Simplifying equation (i):
LHS = wx + w(x + y) + x(x + y)
= wx + wx + wy + xx + xy
= wx + wy + x + xy
Applying absorption laws (x + xy = x and x + wx = x):
= x + wy = RHS. Thus, equation (i) is true.
Simplifying equation (ii):
Inside term: w x' (y + x z') = w x' y + w x' x z'.
Because x' x = 0, the second term vanishes: w x' y + 0 = w x' y.
Combining inside terms: w x' y + w' x'.
Multiplying by y:
LHS = (w x' y + w' x') y
= w x' y y + w' x' y = w x' y + w' x' y.
Factoring out x' y:
= (w + w') x' y = (1) x' y = x' y = RHS.
Thus, equation (ii) is also true.
Both equations (i) and (ii) are true (Option B).
Sign in to read the full explanation
Frequently asked questions
How many Discrete Structures and Optimization questions have been asked in UGC NET Computer Science?
173 Discrete Structures and Optimization questions appear in the UGC NET Computer Science papers held between 2018–2026, and all of them are on this page with their answer key.
Are the answers on this page free?
Yes. Every question, its options, and the correct answer are free to read with no account. Signing in additionally unlocks the detailed explanation under each question.
Is Discrete Structures and Optimization an important topic for UGC NET Computer Science?
Discrete Structures and Optimization appears in every recent UGC NET Computer Science paper, across all 14 sittings covered here. Its share of the paper makes it worth revising thoroughly rather than sampling.
How should I practise Discrete Structures and Optimization after reading these questions?
Attempt the Discrete Structures and Optimization topic-wise sets, which put the same questions into a timed interface with instant scoring and weak-area analysis afterwards.
