This question paper is from the B.Tech Semester III subject Discrete Structures & Theory of Logic (KCS303).
It carries 100 marks and covers all important mathematical foundations required for computer science, including sets, relations, functions, groups, lattices, logic, recurrence relations, and graph theory.
The paper is divided into three main sections (A, B, C), each designed to test conceptual clarity, analytical skills, and deep mathematical reasoning.
SECTION A – Short Conceptual Questions (20 Marks)
This section contains 10 questions (2 marks each), checking fundamental understanding of:
Equivalence classes of a relation
Ackermann function computation
Cyclic group and why every cyclic group is abelian
Difference between Ring and Field
Complemented vs distributive lattices
De Morgan’s & Absorption laws
Logical statements: converse, inverse, contrapositive
Universal modus ponens & modus tollens
Euler’s formula & planar graph regions
Pigeonhole principle
This section ensures the student knows basics of discrete mathematics, algebraic structures, and logic.
SECTION B – Analytical & Problem-Solving Questions (30 Marks)
Students must attempt any three out of five 10-mark questions.
Topics include:
Set theory identities and proofs
Cyclic groups, subgroup concepts, and Lagrange’s theorem (“order of subgroup divides order of group”)
K-Map simplification of Boolean expression
Constructing truth tables for compound logical statements
Solving recurrence relations using generating functions
This section evaluates the ability to perform proofs, apply group theory concepts, solve Boolean algebra, and work with recurrence relations.
SECTION C – Long, Detailed Mathematical Reasoning (50 Marks)
This section contains five major questions, each with two choices. Students must answer one part from each question (5 × 10 marks).
Q3 – Equivalence Relations / Transitive Closure
Principle of duality & proving a geometric relation is an equivalence relation
OR transitive closure using Warshall’s algorithm + composition of inverse functions
Q4 – Group Theory
Verifying an operation forms an abelian group and discussing properties
OR proving subgroup intersection property & abelian group condition
Q5 – Lattice Theory
Proving modular lattice identities
OR proving a lattice structure on D36 and showing two lattices are isomorphic
Q6 – Rules of Inference / Inconsistency
Using rules of inference to show given hypotheses imply “It rained”
OR proving inconsistency among four premises involving Nirmala
Q7 – Graph Theory
Definitions and examples of graph coloring, chromatic number, edges in complete graphs, isomorphic & Hamiltonian graphs, bipartite graphs, and handshaking theorem
OR proving properties such as:
total odd-degree vertices in undirected graph is even
maximum edges in simple graph is n(n−1)/2
This section checks deep reasoning, proof writing, algebraic structure understanding, logic-based inference, and graph theory fundamentals.
OVERALL SUMMARY
This Discrete Structures & Theory of Logic question paper is a complete mathematical foundation exam covering:
Set theory
Relations and functions
Logic and proof techniques
Boolean algebra & K-maps
Group theory & rings
Lattices
Recurrence relations
Graph theory
It tests the student's ability to prove statements, simplify expressions, derive logical conclusions, work with algebraic structures, and analyze graphs — essential skills for algorithms, data structures, and theoretical computer science.
