Discrete Structure TU Board 2026 question paper

Explain direct proof and proof by contraposition with suitable examples.

Using the laws of sets, prove that A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).

Using the principle of mathematical induction, prove that 1 + 3 + 5 + ... + (2n − 1) = n² for all positive integers n.

Define partial order relation. Let A = {1, 2, 3, 6} and define a relation R on A by aRb if a divides b. Determine whether R is a partial order relation.

Define composite function. Let f:R→R and g:R→R be defined by f(x)=3x−1 and g(x)=x²+2. Find (f∘g)(x) and (g∘f)(x).

Define graph isomorphism. Consider two graphs G and H with vertex sets V(G)={a,b,c,d} and V(H)={1,2,3,4}, where E(G)={{a,b},{b,c},{c,d},{d,a}} and E(H)={{1,2},{2,3},{3,4},{4,1}}. Determine whether G and H are isomorphic and give a suitable vertex correspondence.

Define bipartite graph with an example. Prove that a graph containing an odd cycle cannot be bipartite.

State the pigeonhole principle. Show that among any 25 students, at least three students were born in the same month.

Define equivalence relation. Let A={1,2,3,4,5,6} and define a relation R by aRb if a and b have the same remainder when divided by 3. Show that R is an equivalence relation and find its equivalence classes.

Define a valid argument.

Define contradiction with an example.

What is a symmetric relation?

Define an injective function with an example.

Find the first four terms of the sequence defined by aₙ = 3aₙ₋₁ + 1, where a₀ = 1.

Define circular permutation with an example.

What is a simple graph?

Define a connected graph.

What is an expression tree?

Define source and sink vertices in a directed graph.

Explain direct proof and proof by contraposition with suitable examples.

Using the laws of sets, prove that A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).

Using the principle of mathematical induction, prove that 1 + 3 + 5 + ... + (2n − 1) = n² for all positive integers n.

Define partial order relation. Let A = {1, 2, 3, 6} and define a relation R on A by aRb if a divides b. Determine whether R is a partial order relation.

Define composite function. Let f:R→R and g:R→R be defined by f(x)=3x−1 and g(x)=x²+2. Find (f∘g)(x) and (g∘f)(x).

Define graph isomorphism. Consider two graphs G and H with vertex sets V(G)={a,b,c,d} and V(H)={1,2,3,4}, where E(G)={{a,b},{b,c},{c,d},{d,a}} and E(H)={{1,2},{2,3},{3,4},{4,1}}. Determine whether G and H are isomorphic and give a suitable vertex correspondence.

Define bipartite graph with an example. Prove that a graph containing an odd cycle cannot be bipartite.

State the pigeonhole principle. Show that among any 25 students, at least three students were born in the same month.

Define equivalence relation. Let A={1,2,3,4,5,6} and define a relation R by aRb if a and b have the same remainder when divided by 3. Show that R is an equivalence relation and find its equivalence classes.

Define the adjacency matrix of a graph. A graph G with vertices {v₁,v₂,v₃,v₄} has the following adjacency matrix: 0110101111010110 Find the degree of each vertex and the total number of edges in the graph.

Determine whether the proposition (p → q) ↔ (¬q → ¬p) is a tautology, contradiction, or contingency. Justify your answer using a truth table.

Show that the function f:R→R defined by f(x)=5x−7 is bijective. Also find f⁻¹(x).

For the expression (a − b) × (c + d), write its prefix and postfix expressions and determine the inorder, preorder, and postorder traversals of its expression tree.

Find the expansion of (2x − 3y)⁴ using the binomial theorem.

Find the number of distinct arrangements that can be formed using all the letters of the word "MATHEMATICS".