This document is the B.Tech Semester III Theory Examination Question Paper for the subject KCS303 – Discrete Structure & Theory of Logic, conducted by Dr. A.P.J. Abdul Kalam Technical University (AKTU) for the academic year 2020–2021. The exam duration is 3 hours, and the total marks allotted are 100. The paper follows the official AKTU pattern and is divided into multiple structured sections designed to test conceptual understanding, logical reasoning, mathematical proof skills, graph theory concepts, Boolean algebra, and functional analysis.
Section A – Short Answer Questions (10 Questions × 2 Marks = 20 Marks)
This section includes ten short questions, each worth 2 marks, covering core definitions and fundamental concepts from functions, relations, algebraic structures, logic, lattices, binary trees, and graph theory.
Examples include:
Checking injectivity of a function
Counting reflexive and symmetric relations on a set
Defining a group and a ring
Drawing a Hasse diagram for a divisibility relation
Writing negation of statements
Expressing English statements symbolically
Explaining complete graph and regular graph
Proving maximum vertices in a binary tree of height h
These questions test basic understanding and theoretical clarity.
Section B – Attempt Any Three (Each 10 Marks)
This section evaluates analytical and problem-solving skills.
Questions touch upon:
Composition of functions (fogoh, gog, goh, hogof)
Lagrange’s theorem (statement and proof)
Proving distributive inequalities in lattices
Logical argument validation
Euler’s formula for planar graphs (n – e + r = 2)
This section requires step-by-step reasoning, proofs, and detailed explanations.
Section C – Mathematical Induction & Number Problems (Attempt One, 10 Marks)
This section focuses on mathematical induction and number theory.
Students must either:
Prove expressions divisible by 17 using induction
or
Find the numbers between 100 and 1000 divisible by 3, 5, or 7
These questions test logical reasoning and number system understanding.
Section D – Group Theory (One Question, 10 Marks)
This section covers group theory concepts including normal subgroups and inverse properties.
Students must prove group identities such as:
(a⁻¹)⁻¹ = a
(ab)⁻¹ = b⁻¹ a⁻¹
or prove the definition of a normal subgroup.
This tests abstract algebra understanding.
Section E – Boolean Algebra Simplification (One Question, 10 Marks)
Students must simplify Boolean expressions using Boolean algebra or express Boolean functions using minterms.
One question also requires drawing the corresponding logic circuit.
This section measures digital logic competency.
Section F – Propositional Logic & Predicate Logic (One Question, 10 Marks)
This includes:
Identifying whether a compound statement is a tautology, contradiction, or contingency
Translating English statements into symbolic logic
Examples include statements about positivity of sums, universal love, admiration, and parental roles.
This tests symbolic logic and reasoning.
Section G – Trees & Recurrence Relations (One Question, 10 Marks)
Students may either:
Construct a binary tree from given inorder & preorder traversal and find postorder traversal
or
Solve a recurrence relation
This section tests knowledge of data structures and discrete mathematics.
Overall Description
This AKTU question paper offers a well-structured and comprehensive evaluation of Discrete Structure & Theory of Logic, covering:
Functions & relations
Group theory & lattices
Logical equivalences & proofs
Boolean algebra & circuits
Graph theory & planar graphs
Recurrence relations
Tree construction
Mathematical induction
The paper reflects the breadth of discrete mathematics crucial for computer science students, testing both theoretical knowledge and analytical depth.
