(SEM III) THEORY EXAMINATION 2021-22 DISCRETE STRUCTURES & THEORY OF LOGIC

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.