(SEM III) THEORY EXAMINATION 2017-18 Discrete Structures & Theory of Logic

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.