This document contains the complete B.Tech Semester III – Theory Examination 2017–18 question paper for Discrete Structures & Theory of Logic (RCS-301). The paper consists of 2 printed pages, carries 70 marks, and comprehensively tests concepts from graph theory, logic, sets, relations, lattices, and recurrence relations.
Section A — Short Conceptual Questions (14 Marks)
Section A includes seven brief questions, each testing fundamental definitions and logical understanding. Topics include:
Eulerian path, circuit and graph
Constructing a relation matrix for a relation defined on set A
Meaning of edge coloring and k-edge coloring
Definitions of chromatic number and isomorphic graphs
Union and intersection of multisets with examples
Finding the contrapositive of a given statement
Definition and basic properties of rings
These questions evaluate clarity on foundational concepts of discrete mathematics, graph theory, logic, and algebraic structures.
Section B — Descriptive / Problem-Solving Questions (21 Marks)
Students must attempt any three out of the five questions. These include:
Mathematical induction proof for a repeated-decimal series
Definitions with examples of bipartite graph, complete graph, number of edges in Kn and Km,n, and planar graph
Lattice assessment of the structure (D36, |)
Checking if a relation on X = {1,2…7} is an equivalence relation, and drawing its digraph
Boolean function simplification using K-map
These questions test deeper mathematical reasoning, graph construction, induction skills, Boolean simplification, and relational analysis.
Section C — Advanced Logic, Algebra & Recurrence Problems (35 Marks)
Students must attempt one part from each question group. Topics include:
1. Recurrence & Logical Consistency
Solving a linear recurrence relation with given initial conditions
Showing a set of propositions is logically inconsistent
2. Group Theory & Induction
Properties of groups, and proving that a given set is not a group under modulo operations
Another induction proof showing divisibility for an expression involving n
3. Lattices & Hasse Diagrams
Explanation of modular, distributive, and bounded lattices with diagrams
Drawing the Hasse diagram of a poset defined by divisibility on the set A = {3,4,12,24,48,72}
4. Tree Construction & Predicate Logic
Reconstructing a binary tree from inorder and postorder traversals, and determining preorder
Translating real-world sentences into predicate logic with quantifiers
5. Graph Algorithms & Recurrence Solving
Explanation of BFS, DFS, Euler graphs, and adjacency matrices
Solving a recurrence relation of order 2
(Page 2)
Discrete-Structures-Theory-of-L…
Summary
This exam paper provides a complete evaluation of essential areas of Discrete Mathematics, including:
Graph theory
Propositional & predicate logic
Mathematical induction
Set theory & relations
Algebraic structures (groups, rings, lattices)
Boolean algebra & K-maps
Recurrence relations
Tree traversal & construction
It is a valuable academic resource for students studying theoretical computer science, algorithms, mathematical logic, and foundational computational structures.
